Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle

Meisel Stephan, Grimme Christian, Bossek Jakob, Wölck Martin, Rudolph Guenter, Trautmann Heike


Zusammenfassung
We evaluate the performance of a multi-objective evolutionary algorithm on a class of dynamic routing problems with a single vehicle. In particular we focus on relating algorithmic performance to the most prominent characteristics of problem instances. The routing problem considers two types of customers: mandatory customers must be visited whereas optional customers do not necessarily have to be visited. Moreover, mandatory customers are known prior to the start of the tour whereas optional customers request for service at later points in time with the vehicle already being on its way. The multi-objective optimization problem then results as maximizing the number of visited customers while simultaneously minimizing total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm aims at approximating the related Pareto set for specifically designed benchmarking instances differing in terms of number of customers, geographical layout, fraction of mandatory customers, and request times of optional customers. Conceptional and experimental comparisons to online heuristic procedures are provided.



Publikationstyp
Forschungsartikel in Sammelband (Konferenz)

Begutachtet
Ja

Publikationsstatus
Veröffentlicht

Jahr
2015

Konferenz
Genetic and Evolutionary Computation Conference

Konferenzort
Madrid, Spain

Buchtitel
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '15)

Erste Seite
425

Letzte Seite
432

Sprache
Englisch

ISBN
978-1-4503-3472-3

DOI