Vehicle Routing with Stochastic Supply of Crowd Vehicles and Time Windows

Fabian Torres (), Michel Gendreau () and Walter Rei ()
Additional contact information
Fabian Torres: Centre interuniversitaire de recherche sur les reseaux d’entreprise, la logistique et le transport (CIRRELT), Montréal, Quebec H3T 1J4, Canada; Département de mathématiques et de génie industriel, Polytechnique Montréal, Montréal, Quebec H3C 3A7, Canada
Michel Gendreau: Centre interuniversitaire de recherche sur les reseaux d’entreprise, la logistique et le transport (CIRRELT), Montréal, Quebec H3T 1J4, Canada; Département de mathématiques et de génie industriel, Polytechnique Montréal, Montréal, Quebec H3C 3A7, Canada
Walter Rei: Centre interuniversitaire de recherche sur les reseaux d’entreprise, la logistique et le transport (CIRRELT), Montréal, Quebec H3T 1J4, Canada; Département de management et technologie, Université de Québec à Montréal, Montréal, Quebec H2L 2C4, Canada

Transportation Science, 2022, vol. 56, issue 3, 631-653

Abstract: The growth of e-commerce has increased demand for last-mile deliveries, increasing the level of congestion in the existing transportation infrastructure in urban areas. Crowdsourcing deliveries can provide the additional capacity needed to meet the growing demand in a cost-effective way. We introduce a setting where a crowd-shipping platform sells heterogeneous products of different sizes from a central depot. Items sold vary from groceries to electronics. Some items must be delivered within a time window, whereas others need a customer signature. Furthermore, customer presence is not guaranteed, and some deliveries may need to be returned to the depot. Delivery requests are fulfilled by a fleet of professional drivers and a pool of crowd drivers. We present a crowd-shipping platform that standardizes crowd drivers’ capacities and compensates them to return undelivered packages back to the depot. We formulate a two-stage stochastic model, and we propose a branch and price algorithm to solve the problem exactly and a column generation heuristic to solve larger problems quickly. We further develop an analytical method to calculate upper bounds on the supply of vehicles and an innovative cohesive pricing problem to generate columns for the pool of crowd drivers. Computational experiments are carried out on modified Solomon instances with a pool of 100 crowd vehicles. The branch and price algorithm is able to solve instances of up to 100 customers. We show that the value of the stochastic solution can be as high as 18% when compared with the solution obtained from a deterministic simplification of the model. Significant cost reductions of up to 28% are achieved by implementing crowd drivers with low compensations or higher capacities. Finally, we evaluate what happens when crowd drivers are given the autonomy to select routes based on rational and irrational behavior. There is no cost increase when crowd drivers are rational and select routes that have a higher compensation first. However, when crowd drivers are irrational and select routes randomly, the cost can increase up to 4.2% for some instances.

Keywords: crowd shipping; crowd logistics; crowd drivers; occasional drivers; city logistics; stochastic programming; dynamic programming; column generation (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1101 (application/pdf)

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:inm:ortrsc:v:56:y:2022:i:3:p:631-653

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().