Dynamic Service Area Sizing for Same-Day Delivery Routing
Marlin Ulmer  1@  , Alan Erera  2@  , Martin Savelsbergh  2@  
1 : Technische Universität Braunschweig
2 : Georgia Institute of Technology

We consider a dynamic same-day delivery routing problem. Customers order goods over the course of the day and are served by a fleet of delivery vehicles. The vehicles perform several delivery tours from a depot to customers over the course of the day. The provider promises timely delivery, for example, within two hours. The delivery deadlines are occasionally violated, especially, when customer demand is high. Deadline violations result in customer dissatisfaction. To avoid customer dissatisfaction, the provider dynamically controls customer demand by changing the size of the service area. Same-day delivery service is only offered to customers within the service area. The provider's goal is to maximize the number of customers served while avoiding customer dissatisfaction.

Dynamically sizing the service area is challenging. First, the size of the service area should depend on the current workload and the expected future customer demand. Second, a current sizing decision impacts the fleet's potential to serve customers in the future. We present two steps to address these challenges. First, we derive a functional dependency between workload and suitable service area size. Second, to anticipate future demand, we parametrize the function differently for different times of the day. The parametrization is determined by value function approximation (VFA). The VFA uses simulation to estimate the value of having a certain parametrization at a certain time of day. We show that our method allows serving many customers without significant deadline violations.

Online user: 1 RSS Feed