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. On-time last-mile delivery is expanding rapidly as people expect faster delivery of goods ranging from grocery 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. This paper studies the optimal region partitioning policy to minimize the expected delivery time of customer orders in a stochastic and dynamic setting. We allow both the order locations and on-site service times to be random and generally distributed. This policy assigns every driver to a subregion, hence making sure drivers will only be dispatched to their own territories. 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 three-partitions from discrete geometry. This algorithmic development can be of independent interest for other logistics problems. We demonstrate the efficiency of the proposed region partitioning policy via numerical experiments using synthetic and real-world data sets. Funding: The first author gratefully acknowledges the support of the Office of Naval Research [Grant N00014-21-1-2208] and METRANS [Grant PSR-21-22]. The second author gratefully acknowledges the support of the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2022-04950] and the National Natural Science Foundation of China [Grant 72242106]. The third author gratefully acknowledges the support of the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2023-04453]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2021.0588 .