A Multi-Stage Very Large-Scale Neighborhood Search for the Vehicle Routing Problem with Soft Time Windows

Select |




Print


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)