Slack Induction by String Removals for Vehicle Routing Problems

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.