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. In summary, the four configurations provide 81 new best-known solutions.


    Access

    Download


    Export, share and cite



    Title :

    Hybridizing large neighborhood search and exact methods for generalized vehicle routing problems with time windows


    Contributors:


    Publication date :

    2021




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    Unknown




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

    Mouthuy, Sébastien / Massen, Florence / Deville, Yves et al. | British Library Online Contents | 2015


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

    Mouthuy, Sébastien / Massen, Florence / Van Hentenryck, Pascal et al. | BASE | 2015

    Free access


    ALGORITMA GENERAL VARIABLE NEIGHBORHOOD SEARCH PADA CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME WINDOWS DAN IMPLEMENTASINYA

    Fadila, Ulil Ilmi / Wahyuningsih, Sapti / Satyananda, Darmawan | BASE | 2022

    Free access