In the vehicle routing problem with multiple time windows (VRPMTW), a single time window must be selected for each customer from the multiple time windows provided. Compared with classical vehicle routing problems with only a single time window per customer, multiple time windows increase the complexity of the routing problem. To minimize the duration of any given route, we present an exact polynomial time algorithm to efficiently determine the optimal start time for servicing each customer. The proposed algorithm has a reduced worst-case and average complexity than existing exact algorithms. Furthermore, the proposed exact algorithm can be used to efficiently evaluate neighborhood operations during a local search resulting in significant acceleration. To examine the benefits of exact neighborhood evaluations and to solve the VRPMTW, the proposed algorithm is embedded in a simple metaheuristic framework generating numerous new best known solutions at competitive computation times.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows


    Beteiligte:
    Hoogeboom, Maaike (Autor:in) / Dullaert, Wout (Autor:in) / Lai, David (Autor:in) / Vigoa, Daniele (Autor:in)

    Erscheinungsdatum :

    2020-03-01


    Anmerkungen:

    Hoogeboom , M , Dullaert , W , Lai , D & Vigoa , D 2020 , ' Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows ' , Transportation Science , vol. 54 , no. 2 , pp. 400-416 . https://doi.org/10.1287/trsc.2019.0912



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



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

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

    Freier Zugriff

    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

    Freier Zugriff

    Agents Toward Vehicle Routing Problem With Time Windows

    Kalina, Petr / Vokřínek, Jiří / Mařík, Vladimír | Taylor & Francis Verlag | 2015


    A vehicle routing problem with flexible time windows

    Tas, D. / Jabali, O. / Woensel, van, T. | BASE | 2013

    Freier Zugriff