The delivery problem: Optimizing hit rates in e-commerce deliveries

Unsuccessful delivery attempts, or failed hits, are still a recurring problem in the fulfillment of e-commerce orders to private customers. In this paper, we consider a parcel delivery company interested in optimizing the rate of successful deliveries. By doing so, the company is able to offer a differentiated service, increasing customer satisfaction, and reducing the costs related to failed delivery attempts. In order to achieve this, routes must be designed in a way that visiting times are convenient for the customers. Revisits to some customers may also be planned, so that the expected number of successful deliveries increases. We propose availability profiles to represent the availability of customers during the delivery period. Using these profiles, we are able to compute the expected number of successful hits in a given route. We model the delivery problem as a set-partitioning problem, and solve it with a branch-and-price algorithm. The corresponding pricing problem is solved with a labeling procedure, in which reduced cost bounds are employed to discard unpromising partial routes. We show that the reduced cost of route extensions is bounded by the optimal solution to an orienteering problem, and efficiently compute bounds for that problem within the labeling procedure. Computational experiments demonstrate the effectiveness of the approach for solving instances with up to 100 customers. A tradeoff analysis suggests that significant hit rate improvement can be achieved at the expense of small additional transportation cost. The results also indicate that flexibility regarding maximum route duration translates into an improved hit rate, and that planning revisits may reduce expected unsuccessful deliveries by more than 10%.