Vehicle Routing for Trunk Delivery Applications

The growth of the e-commerce sector with the ever-increasing push towards online-shopping poses a major supply chain challenge for many companies. Year-over-year growing sales volumes, huge number of delivery locations, and aggressive service levels promised to customers drive companies to seek innovative modes of delivery. Among these is the trunk delivery service introduced recently by Amazon, Audi and DHL, in which a customer’s order has to be delivered to the trunk of the customer’s car during the time that the car is parked at one of the locations in the customer’s travel itinerary.

Motivated by the interest in trunk delivery services, we study the vehicle routing problem with roaming delivery locations (VRPRDL). In the first part of our study, we assume that we have complete knowledge of the itinerary of each customer. We devise an efficient branch-and-price algorithm to solve the VRPRDL optimally. This algorithm can also be used for solving a more general problem in which a hybrid delivery strategy is considered that allows a delivery to either a customer’s home or to the trunk of the customer’s car. We evaluate the effectiveness of our algorithmic choices and analyze the benefits of these innovative delivery strategies against a pure home delivery strategy. In the second part of our study, we investigate the VRPRDL in a dynamic setting where there may be deviations from the original customer itineraries which can render the planned delivery schedule infeasible or suboptimal. To this end, we propose a rolling-horizon based solution framework that uses the branch-and-price algorithm developed for the static version of the problem to re-optimize the vehicle routes each time the itinerary of a customer is updated and test its efficiency.