Talk Title:

Provably Good Region Partitioning for On-Time Last-Mile Delivery

Abstract:

People expect faster delivery of goods ranging from groceries to medicines. Managing on-time delivery systems is challenging because of the underlying uncertainties and combinatorial nature of the routing decision. In practice, the efficiency of such systems also hinges on the driver’s familiarity with the local neighborhood. In this talk, I will discuss a region partitioning policy to minimize the expected delivery time of customer orders in a stochastic and dynamic setting. This policy assigns every driver to a subregion, ensuring that drivers are only dispatched to their territories. In this work, we characterize the structure of the optimal partitioning policy and show its expected on-time performance converges to that of the flexible dispatching policy in heavy traffic. The optimal characterization features two insightful conditions that are critical to the on-time performance of last-mile delivery systems. We then develop partitioning algorithms with performance guarantees, leveraging ham sandwich cuts and 3-partitions from discrete geometry. This algorithmic development can be of independent interest to other logistics problems. We demonstrate the efficiency of the proposed region partitioning policy via numerical experiments using synthetic and real-world data sets.

Location:

1174 Etcheverry Hall or join via Zoom