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

Théo Le Colleter, Dorian Dumez, Fabien Lehuédé and Olivier Péton

European Journal of Operational Research, 2023, vol. 308, issue 3, 1233-1248

Abstract: 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.

Keywords: Routing; Park-and-loop; Large neighborhood search; Last-mile delivery (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723000085
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:308:y:2023:i:3:p:1233-1248

DOI: 10.1016/j.ejor.2023.01.007

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().