Dynamic vehicle routing with time windows in theory and practice

详细信息    查看全文

• 作者：Zhiwei Yang ; Jan-Paul van Osta ; Barry van Veen ; Rick van Krevelen…
• 关键词：Ant colony optimization ; Vehicle routing problem ; Dynamic vehicle routing problem with time windows ; Pilot study
• 刊名：Natural Computing
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：16
• 期：1
• 页码：119-134
• 全文大小：1293KB
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation; Evolutionary Biology; Processor Architectures; Artificial Intelligence (incl. Robotics); Complex Systems;
• 出版者：Springer Netherlands
• ISSN：1572-9796
• 卷排序：16

文摘

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.