Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Hybridizing Large Neighborhood Search and Exacts Methods for Generalized Vehicles Routing Problems with Time Windows

Abstract : Delivery options are at the heart of the generalized vehicle routing problem with time windows (GVRPTW) allowing that customer requests are shipped to alternative delivery locations which can also have different time windows. Recently, the vehicle routing problem with delivery options was introduced into the scientific literature. It extends the GVRPTW by capacities of shared locations and by specifying service-level constraints defined by the customers' preferences for delivery options. The vehicle routing problem with delivery options also generalizes the vehicle routing problem with home roaming delivery locations and the vehicle routing problem with multiple time windows. For all these GVRPTW variants, we present a widely applicable matheuristic that relies on a large neighborhood search (LNS) employing several problem-tailored destruction operators. Most of the time, the LNS performs relatively small and fast moves, but when the solution has not been improved for many iterations, a larger destruction move is applied to arrive in a different region of the search space. Moreover, an adaptive layer of the LNS embeds two exact components: First, a set-partitioning formulation is used to combine previously found routes to new solutions. Second, the Balas-Simonetti neighborhood is adapted to further improve already good solutions. These new components are in the focus of our work and we perform an exhaustive computational study to evaluate four configurations of the new matheuristic on several benchmark instances of the above-mentioned variants. On all the benchmark sets, our matheuristic is competitive with the previous state-of-the-art methods. Without manual problem-specific re-configurations of the matheuristic, we provide 81 new best-known solutions.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [45 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02935356
Contributor : Fabien Lehuédé <>
Submitted on : Thursday, September 10, 2020 - 11:51:16 AM
Last modification on : Monday, September 21, 2020 - 2:15:27 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02935356, version 1

Citation

Dorian Dumez, Christian Tilk, Stefan Irnich, Fabien Lehuédé, Olivier Péton. Hybridizing Large Neighborhood Search and Exacts Methods for Generalized Vehicles Routing Problems with Time Windows. 2020. ⟨hal-02935356⟩

Share

Metrics

Record views

56

Files downloads

121