The Vehicle Routing Problem with Availability Profiles

Stefan Voigt (), Markus Frank (), Pirmin Fontaine () and Heinrich Kuhn ()
Additional contact information
Stefan Voigt: Ingolstadt School of Management, Catholic University of Eichstätt-Ingolstadt, 85049 Ingolstadt, Germany
Markus Frank: Ingolstadt School of Management, Catholic University of Eichstätt-Ingolstadt, 85049 Ingolstadt, Germany
Pirmin Fontaine: Ingolstadt School of Management, Catholic University of Eichstätt-Ingolstadt, 85049 Ingolstadt, Germany
Heinrich Kuhn: Ingolstadt School of Management, Catholic University of Eichstätt-Ingolstadt, 85049 Ingolstadt, Germany

Transportation Science, 2023, vol. 57, issue 2, 531-551

Abstract: In business-to-consumer (B2C) parcel delivery, the presence of the customer at the time of delivery is implicitly required in many cases. If the customer is not at home, the delivery fails—causing additional costs and efforts for the parcel service provider as well as inconvenience for the customer. Parcel service providers typically report high failed-delivery rates, as they have limited possibilities to arrange a delivery time with the recipient. We address the failed-delivery problem in B2C parcel delivery by considering customer-individual availability profiles (APs) that consist of a set of time windows, each associated with a probability that the delivery is successful if conducted in the respective time window. To assess the benefit of APs for delivery tour planning, we formulate the vehicle routing problem with availability profiles (VRPAP) as a mixed integer program, including the trade-off between transportation and failed-delivery costs. We provide analytical insights concerning the model’s cost-savings potential by determining lower and upper bounds. In order to solve larger instances, we develop a novel hybrid adaptive large neighborhood search (HALNS). The HALNS is highly adaptable and also able to solve related time-constrained vehicle routing problems (i.e., vehicle routing problems with hard, multiple, and soft time windows). We show its performance on these related benchmark instances and find a total of 20 new best-known solutions. We additionally conduct various experiments on self-generated VRPAP instances to generate managerial insights. In a case study using real-world data, despite little information on the APs, we were able to reduce failed deliveries by approximately 12% and overall costs by 5%.

Keywords: vehicle routing problem; multiple time windows; soft time windows; last mile delivery; mixed integer programming; adaptive large neighborhood search (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1182 (application/pdf)

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:inm:ortrsc:v:57:y:2023:i:2:p:531-551

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().