In the last decades, the classical Vehicle Routing Problem (VRP), i.e., assigning a set of orders to vehicles and planning their routes has been intensively researched. As only the assignment of order to vehicles and their routes is already an NP-complete problem, the application of these algorithms in practice often fails to take into account the constraints and restrictions that apply in real-world applications, the so called rich VRP (rVRP) and are limited to single aspects. In this work, we incorporate the main relevant real-world constraints and requirements. We propose a two-stage strategy and a Timeline algorithm for time windows and pause times, and apply a Genetic Algorithm (GA) and Ant Colony Optimization (ACO) individually to the problem to find optimal solutions. Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.
翻译:在过去几十年中,对古典车辆运行问题(VRP)进行了深入的研究,即向车辆分配一系列订单和规划其路线,因为仅仅向车辆及其路线分配订单已经是一个NP问题,这些算法的实际应用往往没有考虑到现实应用中适用的制约和限制,即所谓的富富的VRP(rVRP),并局限于单一方面。在这项工作中,我们纳入了与现实世界相关的主要制约和要求。我们提出了一个两阶段战略和时间窗口和暂停时间的时线算法,并单独对问题采用遗传阿尔戈利特姆(GA)和Ant Colony Opptimical(ACO)来寻找最佳解决办法。我们对四种最先进的算法的八个不同问题案例的评估表明,我们的方法在合理的时间里处理所有设定的限制。