10.18151/7217333
Grimme, Christian
University of Münster
Meisel, Stephan
University of Muenster
Trautmann, Heike
University of Münster
Rudolph, Guenter
Technische Universität Dortmund
Wölck, Martin
University of Muenster
Multi-objective Analysis of Approaches to Dynamic Routing of a Vehicle
University of Münster, Münster, Germany
2015
978-3-00-050284-2
multi-objective optimization
evolutionary algorithms
vehicle routing
We consider a routing problem for a single vehicle serving customer Locations in the course of time. A subset of these customers must necessarily be served, while the complement of this subset contains dynamic customers which request for service over time, and which do not necessarily need to be served. The decision maker’s conflicting goals are serving as many customers as possible as well as minimizing total travel distance. We solve this bi-objective Problem with an evolutionary multi-objective algorithm in order to provide an a-posteriori evaluation tool for enabling decision makers to assess the single objective solution strategies that they actually use in real-time. We present the modifications to be applied to the evolutionary multi-objective algorithm NSGA2 in order to solve the routing problem, we describe a number of real-time single-objective solution strategies, and we finally use the gained efficient trade-off solutions of NSGA2 to exemplarily evaluate the real-time strategies. Our results show that the evolutionary multi-objective approach is well-suited to generate benchmarks for assessing dynamic heuristic strategies. Our findings point into future directions for designing dynamic multi-objective approaches for the vehicle routing problem with time windows.