A novel extension of the classical vehicle routing and scheduling problems is introduced that integrates aspects of machine scheduling into vehicle routing. Associated with each customer order is a release date that defines the earliest time that the order is available to leave the depot for delivery and a due date that indicates the time by which the order should ideally be delivered to the customer. The objective is to minimize a convex combination of the operational costs and customer service level, represented by the total distance traveled and the total weighted tardiness of delivery, respectively. A path-relinking algorithm (PRA) is proposed to address the problem, and a variety of benchmark instances are generated to evaluate its performance. The PRA exploits the efficiency and aggressive improvement of neighborhood search but relies on a new path-relinking procedure and advanced population management strategies to navigate the search space effectively. To provide a comparator algorithm to the PRA, we embed the neighborhood search into a standard iterated local search algorithm (ILS). Extensive computational experiments on the benchmark instances show that the newly defined features have a significant and varied impact on the problem, and the performance of the PRA dominates that of the ILS algorithm.


    Access

    Download


    Export, share and cite



    Title :

    The Vehicle Routing Problem with Release and Due Dates


    Contributors:

    Publication date :

    2017-08-30


    Remarks:

    Shelbourne , B , Battarra , M & Potts , C N 2017 , ' The Vehicle Routing Problem with Release and Due Dates ' , INFORMS Journal on Computing , vol. 29 , no. 4 , pp. 705 - 723 . https://doi.org/10.1287/ijoc.2017.0756



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629



    The Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates

    Cattaruzza, Diego / Absi, Nabil / Feillet, Dominique | British Library Online Contents | 2016




    Multi-depot multi-trip vehicle routing problem with time windows and release dates

    Zhen, Lu / Ma, Chengle / Wang, Kai et al. | Elsevier | 2020


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

    Yang, Weibo / Ke, Liangjun / Wang, David Z.W. et al. | Elsevier | 2020