This paper proposes a two-tier last-mile delivery model that optimally selects mobile depot locations in advance of full information about the availability of crowd-shippers, and then transfers packages to crowd-shippers for the final shipment to the customers. Uncertainty in crowd-shipper availability is incorporated by modeling the problem as a two-stage stochastic integer program. Enhanced decomposition solution algorithms including branch-and-cut and cut-and-project frameworks are developed. A risk-averse approach is compared against a risk-neutral approach by assessing conditional-value-at-risk. A detailed computational study based on the City of Toronto is conducted. The deterministic version of the model outperforms a capacitated vehicle routing problem on average by 20%. For the stochastic model, decomposition algorithms usually discover near-optimal solutions within two hours for instances up to a size of 30 mobile depot locations, 40 customers and 120 crowd-shippers. The cut-and-project approach outperforms the branch-and-cut approach up to 85% in the risk-averse setting in certain instances. The stochastic model provides solutions that are 3.35% to 6.08% better than the deterministic model, and the improvements are magnified with the increased uncertainty in crowd-shipper availability. A risk-averse approach leads the operator to send more mobile depots or postpone customer deliveries, to reduce the risk of high penalties for non-delivery.
Citation
@Article{MousaviBodurRoorda2020, author = {Kianoush Mousavi and Merve Bodur and Matthew J. Roorda}, title = {Stochastic Last-mile Delivery with Crowd-shipping and Mobile Depots}, journal = {•}, year = {2020}, OPTkey = {•}, OPTvolume = {•}, OPTnumber = {•}, OPTpages = {•}, OPTmonth = {•}, OPTannote = {•}}