Dynamic service area sizing in urban delivery

Abstract

We consider an urban instant delivery environment, e.g., meal delivery, in which customers place orders over the course of a day and are promised delivery within a short period of time after an order is placed. Deliveries are made using a fleet of vehicles, each completing one or more trips during the day. To avoid missing delivery time promises as much as possible, the provider manages demand by dynamically adjusting the size of the service area, i.e., the area in which orders can be delivered. The provider seeks to maximize the number of orders served while avoiding missed delivery time promises. We present three techniques to support the dynamic adjusting of the size of the service area which can be embedded in planning and execution tools that help the provider achieve its goal. First, we learn the functional dependency between expected demand and the service area that can be supported with the fleet of vehicles. Second, we use value function approximation to improve an initial service area sizing plan for the day based on expected demand. Finally, we introduce a correction mechanism to dynamically adjust the service area sizing plan in response to observed realized demand. Extensive computational experiments demonstrate the efficacy of the techniques and show that dynamic sizing of the service area can increase the number of orders served significantly without increasing the number of missed delivery time promises.

Keywords: Dynamic vehicle routing; Instant delivery; Meal delivery; Service area sizing; Uncertain demand.

Fig. 1

Example for a state, a decision, and a realization of stochastic information

Fig. 2

Comparison of empirical radius and power-function approximation for CA

Fig. 3

Example for customer locations for one day

Fig. 4

Daily customer arrivals pattern

Fig. 5

Average number of orders served and the average relative improvement over FIXED

Fig. 6

Average number of orders served for different COV values

Fig. 7

Average Radii over Time

Fig. 8

Performance of ${\mathit{ARS}}^{+}$ when enforcing a minimum service area size

Fig. 9

Comparison of radii over time with and without enforcing a minimum service area size

Fig. 10

Difference in number of orders served of ${\mathit{ARS}}^{+}$ and ${\mathit{ARS}}^{+}$(limited) compared to FIXED