The Probabilistic Travelling Salesman Problem with Crowdsourcing
The authors study a variant of the Probabilistic Travelling Salesman Problem arising when retailers crowdsource last-mile deliveries to their own customers, who can refuse or accept in exchange for a reward. A planner must identify which deliveries to offer, knowing that all deliveries need fulfilment, either via crowdsourcing or using the retailer’s own vehicle. The authors formalise the problem and position it in both the literature about crowdsourcing and among routing problems in which not all customers need a visit. The authors show that to evaluate the objective function of this stochastic problem for even one solution, one needs to solve an exponential number of Travelling Salesman Problems. To address this complexity, the authors propose Machine Learning and Monte Carlo simulation methods to approximate the objective function, and both a branch-and-bound algorithm and heuristics to reduce the number of evaluations. The authors show that these approaches work well on small size instances and derive managerial insights on the economic and environmental benefits of crowdsourcing to customers.
- Record URL:
- Record URL:
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/oclc/1793974
-
Supplemental Notes:
- © 2022 Alberto Santini et al. Published by Elsevier Ltd. Abstract reprinted with permission of Elsevier.
-
Authors:
- Santini, Alberto
- Viana, Ana
-
0000-0001-5932-5203
- Klimentova, Xenia
- Pedroso, João Pedro
- Publication Date: 2022-6
Language
- English
Media Info
- Media Type: Web
- Features: Figures; References; Tables;
- Pagination: 105722
-
Serial:
- Computers & Operations Research
- Volume: 142
- Issue Number: 0
- Publisher: Elsevier
- ISSN: 0305-0548
- Serial URL: https://www.sciencedirect.com/journal/computers-and-operations-research
Subject/Index Terms
- TRT Terms: Crowdsourcing; Machine learning; Monte Carlo method; Routing; Stochastic processes; Traveling salesman problem
- Subject Areas: Data and Information Technology; Freight Transportation; Operations and Traffic Management; Planning and Forecasting;
Filing Info
- Accession Number: 01850103
- Record Type: Publication
- Files: TRIS
- Created Date: Jun 27 2022 5:16PM