Small and Large Neighborhood Search for the Park-and-Loop Routing Problem with Parking Selection

Théo Le Colleter (1, 2) , Dorian Dumez (1, 2, 3) , Fabien Lehuédé (1, 2) , Olivier Péton (1, 2, 4)

1 LS2N - équipe MODELIS - Modélisation, Optimisation et DEcision pour la Logistique, l'Industrie et les Services
2 IMT Atlantique - DAPI - Département Automatique, Productique et Informatique
3 HEC Montréal - HEC Montréal
4 LS2N - équipe SLP - Systèmes Logistiques et de Production

This paper presents a variant of the vehicle routing problem regarding the delivery of products to customers in cities with a combination of walking and driving. The objective is first to offer a better modeling of delivery problems in congested cities and also to evaluate potential savings in traveled distances and parking times. We introduce the Park-and-Loop Routing Problem with Parking Selection (PLRP-PS) in which a parking space or loading zone has to be found for the driver and his vehicle before he walks to deliver to one or several customers. In this paper, we will focus on cases where parking locations should be selected among a large set of parking areas. To solve this problem, we developed a variant of the large neighborhood search metaheuristic called Small and Large Neighborhood Search (SLNS). We will focus on designing and comparing simple and efficient techniques to select parking spots for vehicles before goods are delivered by walking trips. The efficiency of the approach is demonstrated in the park-andloop routing problem, with eleven new best solutions found on an existing benchmark. Some realistic instances were generated based on open data from the city of Nantes, France. In these instances, we find that combining walking and driving to deliver to the center of a city can save 19% of working time on average compared to the classical vehicle routing approach.

Mots clés: vehicle routing; park-and-loop; large neighborhood search; last-mile delivery

Domaines: Recherche opérationnelle [math.OC]

Théo Le Colleter, Dorian Dumez, Fabien Lehuédé, Olivier Péton. Small and Large Neighborhood Search for the Park-and-Loop Routing Problem with Parking Selection. European Journal of Operational Research, 2023, ⟨10.1016/j.ejor.2023.01.007⟩. ⟨hal-03631730⟩