Robust optimization of dynamic route planning in same-day delivery networks with one-time observation of new demand

Local delivery networks expect drivers to make deliveries to and/or pickups from customers using the shortest routes in order to minimize costs, delivery time, and environmental impact. However, in real-world applications, it is often the case that not all customers are known when planning the initial delivery route. Instead, additional customers become known while the driver is making deliveries or pickups. Before serving the new demand requests, the vehicle will return to the depot for restocking. In other words, there exists a precedence relation in the delivery route to visit the depot before delivering new orders. The uncertainty in new customer locations can lead to expensive rerouting of the tour, as drivers revisit previous neighborhoods to serve the new customers. We address this issue by constructing the delivery route with the knowledge that additional customers will appear, using historical demand patterns to guide our predictions for the uncertainty. We model this network delivery problem as a precedence-constrained asymmetric traveling salesman problem using mixed-integer optimization. Experimental results show that the proposed robust optimization approach provides an effective delivery route under the uncertainty of customer demands.