Provably Good Region Partitioning for On-Time Last-Mile Delivery
研究了一种区域划分策略，将每位司机分配到固定子区域，以最小化随机动态环境下客户订单的预期配送时间，并证明了该策略在重交通下性能趋近于灵活调度策略。
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 “Provably Good Region Partitioning for On-Time Last-Mile Delivery,” Carlsson et al. study 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. The authors 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. Furthermore, the paper develops partitioning algorithms with performance guarantees, leveraging ham sandwich cuts and three-partitions from discrete geometry.