The Vehicle Routing Problem with Availability Profiles

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%. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1182 .