Small and large neighborhood search for the park-and-loop routing problem with parking selection

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. In particular, we remove the assumption that a vehicle can/must park in front of each customer. Second, we 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 focus on cases where parking locations should be selected among a large set of parking areas. To solve this problem, we develop a variant of the large neighborhood search metaheuristic called Small and Large Neighborhood Search (SLNS). We 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 on small instances of the PLRP-PS and in the park-and-loop routing problem, with eleven new best solutions found on an existing benchmark. Some realistic instances are 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.