Slack Induction by String Removals for Vehicle Routing Problems

Dedicated algorithm and modeling improvements continue to advance thestate of the art with respect to vehicle routing problems (VRPs). Despite these academicachievements, solving large VRP instances sufficiently fast for real-life applicability remainschallenging. By exploiting VRP solution characteristics in an effective manner, this paperarrives at a powerful and fast optimization heuristic. Its primary contributions are threefold:a ruin method, a recreate method, and afleet minimization procedure. The ruin methodfunctions via adjacent string removal, introducing with it a novel property regarding vehiclerouting problems that we termspatial slack, whereas the recreate method is categorized asgreedy insertion with blinks. Combining these results in slack induction by string removals(SISRs), a powerful ruin and recreate approach. Thefleet minimization procedure, mean-while, introduces an absences-based acceptance criterion that serves as a complementaryoptimization component for when minimizing the number of vehicles constitutes theprimary VRP objective. Together these three elements provide a suite of simple, powerful,and easily reproducible algorithmic methods that are successfully applied not only to thecapacitated VRP but also to a wide range of related problems such as pickup and deliveryproblems and others that include time windows. SISRs serves to strip back the layers ofcomplexity and specialization synonymous with the trend of algorithmic developmentthroughout recent decades. Moreover, such simplicity and reproducibility are shownto not necessarily come at the expense of solution quality, with SISRs consistently out-performing alternative general approachesas well as dedicated single-purpose methods.Finally, aside from performance-related criteria, SISRs also serves to showcase a fresh per-spective with respect to VRPs more generally, introducing a range of new terminology andprocedures that, it is hoped, will invigorate further research and innovation.

Publication year:2020

BOF-keylabel:yes

IOF-keylabel:yes

BOF-publication weight:6

CSS-citation score:3

Authors from:Higher Education

Accessibility:Open