The Probabilistic Travelling Salesman Problem with Crowdsourcing

• Tipo: Artigo em Revista Científica Internacional
• Data: 2022

Autores

Santini, A (Autor) Outra; Viana, A (Autor) Outra; Klimentova, X (Autor) Outra; Joao Pedro Pedroso (Autor) FCUP

Revista

Título: Computers and Operations Research

Vol. 142

ISSN: 0305-0548

Editora: Elsevier

Indexação

ISI Web of Knowledge - 14 Citações

Scopus - 18 Citações

Outras Informações

ID Authenticus: P-00W-3TF

DOI: 10.1016/j.cor.2022.105722

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 17