Abstract

This paper presents a set-partitioning formulation and a novel decomposition heuristic (D-H) solution algorithm to solve large-scale instances of the urban crowdsourced shared-trip package delivery problem. The D-H begins by dividing the packages between shared personal vehicles (SPVs) and dedicated vehicles (DVs). For package-assignment to SPVs, this paper enumerates the set of routes each SPV can traverse and constructs a package-SPV route assignment problem. For package-assignment to DVs and routing, the paper first obtains DV routes by solving a conventional vehicle routing problem and then seeks potential solution improvements by switching packages from SPVs to DVs. The switching process is cost driven. The D-H significantly outperforms a commercial solver in terms of computational efficiency, while obtaining near-optimal solutions for small problem instances. This paper presents a city-scale case study to analyze the important service design factors that impact the efficiency of crowdsourced shared-trip delivery. The paper further analyzes the impact of three important service design factors on system performance, namely (i) the number of participating SPVs, (ii) the maximum detour willingness of SPVs, and (iii) the depot locations. The results and findings provide meaningful insights for industry practice, while the algorithms illustrate promise for large real-world systems.