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

Sébastien Mouthuy (), Florence Massen (), Yves Deville () and Pascal Van Hentenryck ()
Additional contact information
Sébastien Mouthuy: Institute of Information and Communication Technologies, Electronics and Applied Mathematics, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
Florence Massen: Institute of Information and Communication Technologies, Electronics and Applied Mathematics, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
Yves Deville: Institute of Information and Communication Technologies, Electronics and Applied Mathematics, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
Pascal Van Hentenryck: NICTA and the Australian National University, Canberra ACT 0200, Australia

Transportation Science, 2015, vol. 49, issue 2, 223-238

Abstract: This paper considers the vehicle routing problem with soft time windows, a challenging routing problem where customers' time windows may be violated at a certain cost. The vehicle routing problem with soft time windows has a lexicographic objective function, aimed at minimizing first the number of routes, then the number of violated time windows, and finally the total routing distance. We present a multistage very large-scale neighborhood search for this problem. Each stage corresponds to a variable neighborhood descent over a parameterizable very large-scale neighborhood. These neighborhoods contain an exponential number of neighbors, as opposed to classical local search neighborhoods. Often, searching very large-scale neighborhoods can produce local optima of a higher quality than polynomial-sized neighborhoods can. Furthermore, we use a sophisticated heuristic to determine service start times allowing us to minimize the number of violated time windows. We test our approach on a number of different problem types, and compare the results to the relevant state of the art. The experimental results show that our algorithm improves best known solutions on 53% of the most studied instances. Many of these improvements stem from a reduction of the number of vehicles, a critical objective in vehicle routing problems.

Keywords: vehicle routing problem; heuristic search; very large-scale neighborhood (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0558 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:49:y:2015:i:2:p:223-238

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().