论文标题
模因搜索与同时接送和时间窗口的车辆路由
Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows
论文作者
论文摘要
车辆路由问题的同时拾取交付和时间窗口（VRPSPDTW）在过去十年中引起了很多研究兴趣，这是由于其在现代物流中的广泛应用。由于VRPSPDTW是NP-HARD，并且精确的方法仅适用于小规模实例，因此通常采用启发式方法和元数据。在本文中，我们提出了一种新型的模因算法，并具有有效的本地搜索和被称为伴侣的延伸社区，以解决这个问题。与现有算法相比，伴侣的优势在两个方面。首先，由于其新颖的初始化过程，交叉和大型操作员，它能够更有效地探索搜索空间。其次，由于其复杂的恒定时间复杂性移动评估机制，它在本地剥削方面也更有效。公共基准测试的实验结果表明，伴侣的表现优于所有最新算法，尤其是在12个实例上找到了新的最著名的解决方案（总共65个实例）。此外，还进行了全面的消融研究，以显示伴侣中整合的新成分的有效性。最后，引入了源自JD物流的现实应用程序的大规模实例的新基准，该实例被引入了，它可以作为未来研究的新的，更具挑战性的测试集。
The Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows (VRPSPDTW) has attracted much research interest in the last decade, due to its wide application in modern logistics. Since VRPSPDTW is NP-hard and exact methods are only applicable to small-scale instances, heuristics and meta-heuristics are commonly adopted. In this paper we propose a novel Memetic Algorithm with efficient local search and extended neighborhood, dubbed MATE, to solve this problem. Compared to existing algorithms, the advantages of MATE lie in two aspects. First, it is capable of more effectively exploring the search space, due to its novel initialization procedure, crossover and large-step-size operators. Second, it is also more efficient in local exploitation, due to its sophisticated constant-time-complexity move evaluation mechanism. Experimental results on public benchmarks show that MATE outperforms all the state-of-the-art algorithms, and notably, finds new best-known solutions on 12 instances (65 instances in total). Moreover, a comprehensive ablation study is also conducted to show the effectiveness of the novel components integrated in MATE. Finally, a new benchmark of large-scale instances, derived from a real-world application of the JD logistics, is introduced, which can serve as a new and more challenging test set for future research.
