The Last-mile Vehicle Routing Problem with Alternative Delivery Options
Christian Tilk  1, *@  , Stefan Irnich  1@  , Katharina Olkis  1@  
1 : Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz  (JGU Mainz)
Jakob-Welder-Weg 9, D-55128 Mainz -  Germany
* : Corresponding author

The ongoing rise in e-commerce comes along with an increasing number of first-time delivery failures due to the absence of the customer at the delivery location. Failed deliveries result in rework which in turn has a large impact on the carriers delivery cost. In this presentation, the vehicle routing problem with alternative delivery options is investigated. In contrast to the classical vehicle routing problem with time windows, in which each customer request has only one location and one time window describing where and when shipments need to be delivered, alternative delivery options imply that at least some requests allow the shipment to different locations and times. Furthermore, customers may favor some delivery options. The carrier must then decide for each request to which of the given alternative delivery options the shipment is sent such that the carriers overall costs are minimized and a certain service level regarding the customer preferences is achieved. Moreover, when delivery options share a common location (e.g., a locker), location capacities must be respected when assigning shipments.To solve the problem, we present a branch-price-and-cut algorithm. The resulting pricing problem is a shortest-path problem with resource constraints that is solved with a bidirectional labeling algorithm on an auxiliary network. We investigate two different modelling approaches for the auxiliary network and present optimal solutions for instances with up to 60 requests.

Online user: 1 RSS Feed