The probabilistic travelling salesman problem with crowdsourcing

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Santini, Alberto
• dc.contributor.author Viana, Ana
• dc.contributor.author Klimentova, Xenia
• dc.contributor.author Pedroso, João Pedro
• dc.date.accessioned 2023-07-17T07:05:03Z
• dc.date.available 2023-07-17T07:05:03Z
• dc.date.issued 2022
• dc.description.abstract We 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. We formalise the problem and position it in both the literature about crowdsourcing and among routing problems in which not all customers need a visit. We 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, we 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. We show that these approaches work well on small size instances and derive managerial insights on the economic and environmental benefits of crowdsourcing to customers.
• dc.description.sponsorship Alberto Santini was partially supported by grant “RTI2018-095197-B-I00” from the Spanish Ministry of Economy and Competitiveness and has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement 945380. The other authors are partially funded by the ERDF – European Regional Development Fund through the COMPETE Programme (operational programme for competitiveness) and by National Funds through the Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology ) within project “POCI-01-0145-FEDER-028611”.
• dc.format.mimetype application/pdf
• dc.identifier.citation Santini A, Viana A, Klimentova X, Pedroso JP. The probabilistic travelling salesman problem with crowdsourcing. Comput Oper Res. 2022;142:105722. DOI: 10.1016/j.cor.2022.105722
• dc.identifier.doi http://dx.doi.org/10.1016/j.cor.2022.105722
• dc.identifier.issn 0305-0548
• dc.identifier.uri http://hdl.handle.net/10230/57584
• dc.language.iso eng
• dc.publisher Elsevier
• dc.relation.ispartof Computers and Operations Research. 2022;142:105722.
• dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/945380
• dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/RTI2018-095197-B-I00
• dc.rights © 2022 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.rights.uri http://creativecommons.org/licenses/by/4.0/
• dc.subject.keyword Last-mile delivery
• dc.subject.keyword Crowdsourcing
• dc.subject.keyword Social engagement
• dc.subject.keyword Stochastic routing
• dc.title The probabilistic travelling salesman problem with crowdsourcing
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/publishedVersion