2012 | OriginalPaper | Buchkapitel
Efficient Solution of Capacitated Arc Routing Problems with a Limited Computational Budget
verfasst von : Min Liu, Tapabrata Ray
Erschienen in: AI 2012: Advances in Artificial Intelligence
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Capacitated Arc Routing Problem (CARP) is a well known combinatorial problem that requires the identification of the minimum total distance travelled by a set of vehicles to service a given set of roads subject to the vehicle’s capacity constraints. While a number of optimization algorithms have been proposed over the years to solve CARP problems, all of them require a large number of function evaluations prior to its convergence. Application of such algorithms are thus limited for practical applications as many of such applications require an acceptable solution within a limited time frame, e.g., dynamic versions of the problem. This paper is a pre-cursor to such applications, and the aim of this study is to develop an algorithm that can solve such problems with a limited computational budget of 50,000 function evaluations. The algorithm is embedded with a similarity based parent selection scheme inspired by the principles of multiple sequence alignment, hybrid crossovers, i.e., a combination of similarity preservation schemes, path scanning heuristics and random key crossovers. The performance of the algorithm is compared with a recent Memetic algorithm, i.e., Decomposition-Based Memetic Algorithm proposed in 2010 across three sets of commonly used benchmarks (
gdb
,
val
,
egl
). The results clearly indicate the superiority of performance across both small and large instances.