Anticipatory Route Optimization in On-demand Same-day Grocery Delivery

Abstract

The recent decade has seen exponential growth in technology and information processing. This has enabled a paradigm shift in several logistical operations such as the introduction of on-demand same-day delivery of groceries.

One of the most relevant challenges in dynamic same-day pickup & delivery systems is related to uncertainty about future orders. Lack of knowledge about emerging orders results in the selection of routes that are optimal till such time additional information is not available and sub-optimal thereafter. This induces a mismatch between the routes of the vehicles in the future and the origins of the emerging orders. In our thesis, we introduce simple anticipatory techniques that solve this problem and can scale to large problem instances of thousands of orders. In particular, our techniques utilize endogenous properties of the problem to affect both how vehicles are assigned to orders, and how to route vehicles to serve those orders. One of our techniques introduces rewards that reduce the cost of assignment between a vehicle and a group of orders if the vehicle is routed towards a favorable zone. A favorable
zone can be a region with more number of orders that can be picked up at its nearest depots, or a region whose distance to the nearest depots is lower than others, etc. Another technique penalizes assignment between a vehicle and a group of orders if the vehicle is routed away from a high-demand zone and vice versa. We propose, formally discuss and experimentally evaluate several formulations of both rewards adjustment and adjustment with penalty + rewards.

We test our techniques in combination with the state-of-the-art Vehicle Group Analysis (VGA) framework in Amsterdam for a fleet of 10 vehicles and up to 3600 grocery orders. We further conduct extensive computation tests with varying hours of service under different conditions and compare the performance of our methods with the original VGA method. We identify that our most promising anticipatory technique can reduce the number of rejections in the busiest of demand scenarios by up to 1% of total demand. The increase in orders served comes at a cost of marginally increased distance traveled by
the fleet of vehicles. Additionally, we note that the value of rejections saved increases by up to 5% when the system is not working up to its maximum capacity and allowing for greater scope for anticipation. Furthermore, our results underpin the strength and weaknesses of each anticipatory technique
and highlight the importance of studying anticipation under a wide range of demand scenarios.