Joint optimization of parcel allocation and crowd routing for crowdsourced last-mile delivery

Abstract

Urban last-mile delivery providers are facing more and more challenges with the explosive development of e-commerce. The advancement of smart mobile and communication technology in recent years has stimulated the development of a new business model of city logistics, referred to as crowdsourced delivery or crowd-shipping. In this paper, we investigate a form of crowdsourced last-mile delivery that utilizes the journeys of commuters/travelers (crowd-couriers) to deliver parcels from intermediate stations to customers. We consider a logistics service provider that jointly optimizes parcel allocation to intermediate stations and the delivery routing of the crowd-couriers. The joint optimization model gives rise to a new variant of the last-mile delivery problem. We propose a data-driven column generation algorithm to solve the problem based on a set-partitioning formulation. Additionally, a rolling-horizon approach is proposed to address large-scale instances. Extensive numerical experiments are conducted to verify the efficiency of our model and solution approach, as well as the significance of the joint optimization of parcel allocation and the delivery route of the crowdsourced last-mile delivery. The results show that our data-driven column generation algorithm can obtain (near-)optimal solutions for up to 200 parcels in significantly less time than the exact algorithm. For larger instances, the combination of the data-driven column generation algorithm and the rolling-horizon approach can obtain good-quality solutions for up to 1000 parcels in 15 min. Moreover, compared with crowd-courier route optimization only, the joint optimization of parcel allocation and crowd-routing reduces the total cost by 32%.