Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
A Memetic Algorithm Solving the VRP, the CARP and General Routing Problems with Nodes, Edges and Arcs
verfasst von : Christian Prins, Samir Bouchenoua
Erschienen in: Recent Advances in Memetic Algorithms
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
The VRP (Vehicle Routing Problem) and the CARP (Capacitated Arc Routing Problem) involve the routing of vehicles in an undirected network to service respectively a set of nodes or a set of arcs. Motivated by applications in waste collection, we define a more general model called NEARP (Node, Edge and Arc Routing Problem) for tackling mixed graphs with required nodes, edges and arcs. A memetic algorithm (MA) is developed for the NEARP. An evaluation on standard VRP and CARP benchmarks shows that the MA is competitive with most metaheuristics for these particular cases of the NEARP. We finally propose a set of NEARP instances, together with the solutions costs achieved by the MA, as a challenge for other researchers in vehicle routing.