A multi-stage very large-scale neighborhood search for the vehicle routing problem with soft time-windows

Mouthuy, Sébastien;Deville, Yves;Van Hentenryck, Pascal
(2011) 9th Metaheuristics International Conference (MIC 2011) — Location: Udine, Italy, July 2011. (25.July.2011)

Files

multi.pdf
  • Open Access
  • Adobe PDF
  • 265.98 KB
Download

Details

Authors
  • Mouthuy, SébastienUCLouvain
    Author
  • Deville, Yvesorcid-logoUCLouvain
    Author
  • Van Hentenryck, PascalBrown University, USA
    Author
Abstract
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 neighborhood 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 90% and 100% of the Type 1 and Type 3 instances respectively. Equally interesting is the fact that the multi-stage algorithm decreases the number of routes in 33% of the instances and the soft time-window violations in 92% of the remaining instances
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Mouthuy, S., Deville, Y., & Van Hentenryck, P. (2011). A multi-stage very large-scale neighborhood search for the vehicle routing problem with soft time-windows. 9th Metaheuristics International Conference (MIC 2011), Udine, Italy, July 2011. https://hdl.handle.net/2078.5/253786