A Multi-Stage Very Large-Scale Neighborhood Search for the Vehicle Routing Problem with Soft Time Windows
Mouthuy, Sebastien; Massen, Florence; Deville, Yves; Van Hentenryck, Pascal
2015
Journal Article
Transportation science
49
2
163-432
This paper considers the VRP Problem with Soft Time-Windows (VRPSTW), a challenging routing problem due to its combination of hard time windows and a lexicographic objective function minimizing the number of vehicles, the violations of the soft time windows, and the total travel distance. The paper presents a multi-stage, variable neigh- borhood search algorithm for the VRPSTW, which uses the same very large-scale neighborhood (VLSN) for each of its three steps with different objective functions. Experimental results indicate that the multi-stage VLSN algorithm improves best-known solutions on 70% of the most studied instances with 100 customers. Equally interesting is the fact that the multi-stage algorithm decreases the number of routes in 38% of the instances and the soft time-window violations in 51% of the remaining instances.
nicta; data61
https://doi.org/10.1287/trsc.2014.0558
English
nicta:8049
Mouthuy, Sebastien; Massen, Florence; Deville, Yves; Van Hentenryck, Pascal. A Multi-Stage Very Large-Scale Neighborhood Search for the Vehicle Routing Problem with Soft Time Windows. Transportation science. 2015; 49(2):163-432. https://doi.org/10.1287/trsc.2014.0558
Loading citation data...
Citation counts
(Requires subscription to view)