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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:


    Erscheinungsdatum :

    2023-10-02




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    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

    Freier Zugriff

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

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