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.
Solving the park-and-loop routing problem by branch-price-and-cut
2023-10-02
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem
Online Contents | 2016
|A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem
British Library Online Contents | 2016
|A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem
Online Contents | 2015
|Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem
BASE | 2018
|