A continuum approximation approach to the depot location problem in a crowd-shipping system

Last-mile delivery in the logistics chain contributes to congestion in urban networks due to frequent stops. Crowd-shipping is a sustainable and low-cost alternative to traditional delivery but relies heavily on the availability of occasional couriers. In this work, we propose a crowd-shipping system that uses depots to improve accessibility for potential crowd-shippers to serve a large portion of the demand for small parcels. While small-scale versions of this problem have been recently addressed, scaling to larger instances significantly complexifies the problem. A heuristic approach based on continuum approximation is designed to evaluate the quality of a potential set of depots. By combining an efficient and accurate approximation method with a large neighborhood search heuristic, we can efficiently find a good set of depots, even for large-scale networks. The proposed methodology allows for heterogeneity among crowd-shippers and allows identifying the expected number of delivered parcels in every region, which can be used to enhance lower-level assignment decisions.A case study on the Washington DC network shows that depots are built at geographically central locations but most importantly at locations around popular origins for crowd-shippers. The optimal number of depots is mainly dependent on the marginal number of parcels that can be served by crowd-shippers from a specific depot, relative to the costs involved in opening that depot. The operational costs approximated by our continuum approximation approach deviate on average 2% from the actual operational costs using dynamic assignment strategies. For small instances, our algorithm finds better solutions than solving a discrete formulation using CPLEX, while being almost 200 times faster. For large instances, the discrete formulation cannot be constructed by CPLEX, whereas the CA-based approach finds good solutions within minutes. Finally, the results show that using CA-based strategies in all three layers of decision-making can improve overall performance by 15% compared to non-predictive strategies.