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

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.