title: Dynamic vehicle routing with time windows in theory and practice.
abstract: The vehicle routing problem is a classical combinatorial optimization problem. This work is about a variant of the vehicle routing problem with dynamically changing orders and time windows. In real-world applications often the demands change during operation time. New orders occur and others are canceled. In this case new schedules need to be generated on-the-fly. Online optimization algorithms for dynamical vehicle routing address this problem but so far they do not consider time windows. Moreover, to match the scenarios found in real-world problems adaptations of benchmarks are required. In this paper, a practical problem is modeled based on the procedure of daily routing of a delivery company. New orders by customers are introduced dynamically during the working day and need to be integrated into the schedule. A multiple ant colony algorithm combined with powerful local search procedures is proposed to solve the dynamic vehicle routing problem with time windows. The performance is tested on a new benchmark based on simulations of a working day. The problems are taken from Solomon's benchmarks but a certain percentage of the orders are only revealed to the algorithm during operation time. Different versions of the MACS algorithm are tested and a high performing variant is identified. Finally, the algorithm is tested in situ: In a field study, the algorithm schedules a fleet of cars for a surveillance company. We compare the performance of the algorithm to that of the procedure used by the company and we summarize insights gained from the implementation of the real-world study. The results show that the multiple ant colony algorithm can get a much better solution on the academic benchmark problem and also can be integrated in a real-world environment.
authors.affiliation: Leiden Institute of Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands.|School of Information System and Management, National University of Defense Technology, Changsha, 410073 Hunan People's Republic of China.
authors.forename: Zhiwei
authors.initials: Z
authors.lastname: Yang
authors.affiliation: Leiden Institute of Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands.
authors.forename: Jan-Paul
authors.initials: JP
authors.lastname: van Osta
authors.affiliation: Leiden Institute of Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands.
authors.forename: Barry
authors.initials: B
authors.lastname: van Veen
authors.affiliation: Almende, Westerstraat 50, 3016 DJ Rotterdam, The Netherlands.
authors.forename: Rick
authors.initials: R
authors.lastname: van Krevelen
authors.affiliation: Almende, Westerstraat 50, 3016 DJ Rotterdam, The Netherlands.
authors.forename: Richard
authors.initials: R
authors.lastname: van Klaveren
authors.affiliation: Almende, Westerstraat 50, 3016 DJ Rotterdam, The Netherlands.
authors.forename: Andries
authors.initials: A
authors.lastname: Stam
authors.affiliation: Leiden Institute of Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands.
authors.forename: Joost
authors.initials: J
authors.lastname: Kok
authors.affiliation: Leiden Institute of Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands.
authors.forename: Thomas
authors.initials: T
authors.lastname: Bäck
authors.affiliation: Leiden Institute of Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands.
authors.forename: Michael
authors.initials: M
authors.lastname: Emmerich
keywords: Ant colony optimization; Dynamic vehicle routing problem with time windows; Pilot study; Vehicle routing problem