Dynamic on-demand delivery with spatial divisions of labor

The rapid evolution of on-demand delivery services has significantly influenced traditional logistics, particularly in urban areas where there is a surge in customer demand for timely and efficient delivery of small to medium-sized parcels. This paper investigates the concept of spatial divisions of labor in on-demand deliveries where the delivery network is partitioned into several operational regions, each managed by designated couriers. To facilitate parcel transshipment between regions, a set of accessible lockers is strategically placed at the shared borders of adjacent regions. We introduce and address a multi-hop delivery with spatial divisions of labor (MDSDL) problem, which involves dynamic parcel-courier dispatching and routing to minimize total operational costs. Within a rolling-horizon decision framework, the MDSDL problem is decomposed into two interdependent subproblems: (i) Region-Level Path Optimization (RLPO) that determines the coarse-grained, multi-hop path each parcel should take through the network, from its pickup region to its destination region, via the lockers, with the objective of minimizing delivery lateness. This path specifies the sequence of service regions a parcel must traverse to reach its final destination. (ii) Courier Route Optimization (CRO) that manages fine-grained, intra-region dispatching and routing by assigning incoming pickup and drop-off tasks to local couriers, who each has a continuously updated schedule. Subsequently, we develop a novel heuristic approach to dynamically solve RLPO and CRO in real time considering a rolling-horizon formulation. Extensive comparative experiments are conducted to demonstrate the advantages of the proposed approach. Implementing spatial divisions of labor not only enhances system efficiency and reduces operational costs but also improves the customer experience by reducing lateness and shortening ready-to-pickup times.