A column and row generation approach to the crowd-shipping problem with transfers

Patrick Stokkink, Jean-François Cordeau and Nikolas Geroliminis

Omega, 2024, vol. 128, issue C

Abstract: Crowd-shipping is a last-mile delivery concept in which commuters pick up and deliver parcels on their pre-existing paths. In urban areas, crowd-shipping circumvents problems that traditional last-mile delivery systems suffer from, such as road congestion and lack of parking spaces, especially if more sustainable modes of transport are utilized, like bikes or e-bikes. Using transfers between crowd-shippers allows for expanding the service area and improving the overall performance. However, as this requires synchronization over space and time, it makes the problem more complex. In this work, we develop a model that can encompass fully heterogeneous crowd-shippers and parcels. Thereby, it allows for both direct time-synchronized transfers as well as intermediate storage at designated parcel lockers. We design a column generation algorithm to solve large-scale realistic instances to optimality. We extend the problem to allow crowd-shippers to carry multiple parcels at the same time and for this, we extend the algorithm to simultaneous column and row generation. We evaluate the performance of our algorithm as well as the potential of crowd-shipping with transfers on a realistic case study of a bike-based crowd-shipping system in Washington DC. Our methods solve realistic instances with 1000 crowd-shippers and 1000 parcels within minutes. The results show that a gain in revenue and service level of 30% can be obtained by allowing transfers. By letting part of the population of crowd-shippers carry two or three parcels at the same time, the revenue and service level can be further increased by 30 to 50%. Maximum locker capacities are shown to be reasonable and are the highest in areas where there is a large gap between the moment when parcels are dropped off and when they are picked up from parcel points, which are mainly in the city center.

Keywords: Crowd-shipping; Last-mile delivery; Transfers; Column generation; Row generation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048324001002
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:128:y:2024:i:c:s0305048324001002

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2024.103134

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().