Highlights A branch-price-and-cut algorithm is developed to exactly solve the VRPRD. An effective bidirectional labeling algorithm is proposed for the pricing problem. Extensive computational experiments are conducted to evaluate the performance of the proposed algorithm. The test instances and computational results are provided for future researchers of the problem.

    Abstract In this paper, we investigate the vehicle routing problem with release and due dates (VRPRD), which is a new variant of vehicle routing problem (VRP). In the problem, the order required by a customer is available for delivery later than its release date. A penalty cost, called tardiness cost, will be imposed if a customer is served after its due date. The objective of the VRPRD is to minimize the total routing and weighted tardiness costs. To address the problem, we develop an exact branch-price-and-cut algorithm based on the set-partitioning formulation. An effective bidirectional labeling algorithm is proposed to deal with the pricing problem. Numerical studies have verified that the proposed algorithm can obtain the exact optimal solutions for more than 75 % of benchmark instances within approximately six minutes on average.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates


    Beteiligte:
    Yang, Weibo (Autor:in) / Ke, Liangjun (Autor:in) / Wang, David Z.W. (Autor:in) / Lam, Jasmine Siu Lee (Autor:in)


    Erscheinungsdatum :

    2020-11-08




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    The Vehicle Routing Problem with Release and Due Dates

    Shelbourne, Benjamine / Battarra, Maria / Potts, Chris N. | BASE | 2017

    Freier Zugriff


    A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations

    Ozbaygin, Gizem / Ekin Karasan, Oya / Savelsbergh, Martin et al. | Elsevier | 2017