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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2020-11-08




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    The Vehicle Routing Problem with Release and Due Dates

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

    Free access



    A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing Problem

    Fukasawa, Ricardo / He, Qie / Song, Yongjia | British Library Online Contents | 2016


    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