Pre-Releasing Strategies for Same-Day Home Delivery

Abstract

This thesis investigates the optimization of Same-Day Delivery (SDD) in the context of a Dynamic and Stochastic Vehicle Routing Problem with Time-Windows (DSVRPTW). A central focus is the concept of pre-releasing; the process of assigning an order to a specific route and preparing it for delivery, effectively fixing theorder to the route. This happens before all orders are known, restricting the possibleroutes and thus increasing the costs.

By conducting computational experiments using real-life data from a European e-grocery, the study evaluates various pre-releasing heuristics. The most effective heuristic, which delays pre-releasing until the last possible moment before the route departs, results in a reduction of optimization costs of 20% compared to current operations. When allowing more than 2 time-windows per truck, the reduction increases to 32%.

The research also addresses the critical practical constraint of pre-releasing capacity, which represents the maximum number of orders that can be pre-released within an hour. Simulation analysis reveals that using the last-minute heuristic only slightly increases the pre-releasing rate compared to the current operations of companies. To address this constraint efficiently, the most cost-effective solution is to invest in additional warehouse workforce. Alternatively, pre-releasing orders one hour early incurs a 1% increase in costs, while pre-releasing two hours early results in a 4% cost increase. Furthermore, initiating pre-releasing activities in the morning rather than the previous night can lead to savings of up to 2%.

The e-grocery expresses a preference for a constant pre-releasing rate equal to the pre-releasing capacity. This thesis proposes eight additional heuristics that determine which orders should be pre-released in addition to those identified by the last-minute heuristic. While the results from limited data were inconclusive, on average, the best heuristics incur an 8% higher cost compared to only pre-releasing at the last moment by pre-releasing orders based on proximity to or distance from the warehouse. Notably, pre-releasing orders with closer time-windows appeared to be preferable. Implementing this strategy would allow the pre-release capacity to be reduced from 200 to 150, resulting in a savings of five full-time pickers in the warehouse.

Future research opportunities include testing the methods on different cases and datasets and estimating the probability of exceeding the pre-releasing capacity, which could be used for deciding whether or not it is necessary to pre-release extra orders.