Yang Zhiwei, van Osta Jan-Paul, van Veen Barry, van Krevelen Rick, van Klaveren Richard, Stam Andries, Kok Joost, Bäck Thomas, Emmerich Michael
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.
Nat Comput. 2017;16(1):119-134. doi: 10.1007/s11047-016-9550-9. Epub 2016 Apr 9.
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.
车辆路径问题是一个经典的组合优化问题。这项工作涉及具有动态变化订单和时间窗口的车辆路径问题的一个变体。在实际应用中，需求常常在运营期间发生变化。新订单出现，其他订单被取消。在这种情况下，需要即时生成新的调度计划。动态车辆路径的在线优化算法解决了这个问题，但到目前为止它们没有考虑时间窗口。此外，为了匹配实际问题中发现的场景，需要对基准进行调整。本文基于一家配送公司的日常路径规划流程对一个实际问题进行建模。工作日期间客户的新订单被动态引入，并且需要被纳入调度计划。提出了一种结合强大局部搜索程序的多重蚁群算法来解决带时间窗口的动态车辆路径问题。在基于工作日模拟的新基准上测试了其性能。这些问题取自所罗门的基准，但一定比例的订单仅在运营期间才向算法揭示。测试了不同版本的MACS算法，并确定了一个高性能变体。最后，在实地对该算法进行了测试：在一项实地研究中，该算法为一家监控公司调度一队汽车。我们将该算法的性能与公司使用的程序的性能进行比较，并总结从实际研究实施中获得的见解。结果表明，多重蚁群算法在学术基准问题上能够得到更好的解决方案，并且也能够集成到实际环境中。
