期刊
TRANSPORTATION SCIENCE
卷 54, 期 2, 页码 417-433出版社
INFORMS
DOI: 10.1287/trsc.2019.0914
关键词
vehicle routing; large-scale instances; string removal; spatial slack; capacity slack; fleet minimization; ruin and recreate
资金
- Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen) [130855]
Dedicated algorithm and modeling improvements continue to advance the state of the art with respect to vehicle routing problems (VRPs). Despite these academic achievements, solving large VRP instances sufficiently fast for real-life applicability remains challenging. By exploiting VRP solution characteristics in an effective manner, this paper arrives at a powerful and fast optimization heuristic. Its primary contributions are threefold: a ruin method, a recreate method, and a fleet minimization procedure. The ruin method functions via adjacent string removal, introducing with it a novel property regarding vehicle routing problems that we term spatial slack, whereas the recreate method is categorized as greedy insertion with blinks. Combining these results in slack induction by string removals (SISRs), a powerful ruin and recreate approach. The fleet minimization procedure, meanwhile, introduces an absences-based acceptance criterion that serves as a complementary optimization component for when minimizing the number of vehicles constitutes the primary VRP objective. Together these three elements provide a suite of simple, powerful, and easily reproducible algorithmic methods that are successfully applied not only to the capacitated VRP but also to a wide range of related problems such as pickup and delivery problems and others that include time windows. SISRs serves to strip back the layers of complexity and specialization synonymous with the trend of algorithmic development throughout recent decades. Moreover, such simplicity and reproducibility are shown to not necessarily come at the expense of solution quality, with SISRs consistently outperforming alternative general approaches as well as dedicated single-purpose methods. Finally, aside from performance-related criteria, SISRs also serves to showcase a fresh perspective with respect to VRPs more generally, introducing a range of new terminology and procedures that, it is hoped, will invigorate further research and innovation.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据