Abstract The park-and-loop routing problem is a variation of the vehicle routing problem in which routes include a main tour that is completed using a vehicle and subtours that are carried out on foot after parking the vehicle. Additionally, the route duration and total walking distance are bounded. To solve the problem, we propose an exact solution method based on the branch-price-and-cut framework. In particular, our method uses problem-specific components to solve the pricing problem. We report on computational experiments carried out on a standard set of 40 instances with up to 50 customers. The results show that our method delivers solutions that compare favorably to existing metaheuristic algorithms, matching all previously best-known solutions and improving 11 of them in reasonable computational times. Moreover, our method provides optimality certificates for 39 out of the 40 instances.

    Highlights We study the Park-and-loop Routing Problem. We propose an exact method based on the branch-price-and-cut framework. We extend the pulse algorithm to solve the pricing problem. We present extensive computational experiments against state-of-the-art algorithms. Our method provides optimality certificates for 42 out of the 80 instances.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Solving the park-and-loop routing problem by branch-price-and-cut


    Contributors:


    Publication date :

    2023-10-02




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English






    A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem

    Desaulniers, Guy / Rakke, Jørgen G. / Coelho, Leandro C. | British Library Online Contents | 2016


    Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem

    Tilk, Christian / Bianchessi, Nicola / Drexl, Michael et al. | BASE | 2018

    Free access

    Branch-and-price algorithm for the location-routing problem with time windows

    Ponboon, Sattrawut / Qureshi, Ali Gul / Taniguchi, Eiichi | Elsevier | 2015