The Vehicle Routing Problem with Availability Profiles

In business-to-consumer (B2C) parcel delivery the presence of the customer at the time of delivery isimplicitly required in many cases. If the customer is not at home, the delivery fails – causing additional costs and effort for the parcel service provider as well as inconvenience for the customer. Typically, parcel service providers 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 (MIP), including the tradeoff 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) with problem-specific operators. We find new best-known solutions for related benchmark instances from the literature and conduct various experiments on self-generated instances. 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%