Crowd-shipping has gained significant attention as a last-mile delivery option over the recent years. In this study, we propose a variant of dynamic crowd-shipping model with in-store customers as crowd-shippers to deliver online orders within few hours. We formulate the problem as a Markov decision process and develop an approximate dynamic programming (ADP) policy using value function approximation for obtaining a highly scalable and real-time decision making strategy on matching orders to crowd-shippers while considering temporal and spatial uncertainty in arrival of online orders and crowd-shipper. We consider several algorithmic enhancements to the ADP algorithm such as employing hierarchical aggregation and imposing the monotonicity of the value functions, which significantly improve the convergence. We also propose an optimization-based myopic policy and compare it with the ADP policy using various performance measures including operational cost, percentage of served orders and average order postponement. Our numerical analysis with varying parameter settings show that ADP policies can lead to up 25.2 % cost savings and 9.8 % increase in the number of served orders. Accordingly, our findings demonstrate the viability of ADP for addressing the real-time decision making aspect of the dynamic crowd-shipping problem.
Citation
@Article{adpcrowd2021, author = {Kianoush Mousavi and Merve Bodur and Mucahit Cevik and Matthew J. Roorda}, title = {Approximate Dynamic Programming for Crowd-shipping with In-store Customers}, journal = {•}, year = {2021}, OPTkey = {•}, OPTvolume = {•}, OPTnumber = {•}, OPTpages = {•}, OPTmonth = {•}, OPTannote = {•}}