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


Abstract
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.



Publication type
Conference Paper

Peer reviewed
Yes

Publication status
Published

Year
2015

Conference
Genetic and Evolutionary Computation Conference

Venue
Madrid, Spain

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

Start page
425

End page
432

Language
English

ISBN
978-1-4503-3472-3

DOI