The Probabilistic Travelling Salesman Problem with Crowdsourcing
The Probabilistic Travelling Salesman Problem with Crowdsourcing
复制标题
众包的概率旅行商问题
DOI：
10.1016/j.cor.2022.105722
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
João Pedro Pedroso
中科院分区：
文献类型：
--
作者：
Alberto Santini;Ana Viana;Xenia Klimentova;João Pedro Pedroso
我们研究了概率旅行推销员问题的一种变体，当零售商将最后一英里的送货众包给他们自己的客户时，客户可以拒绝或接受以换取奖励。计划者必须确定提供哪些送货服务，因为他们知道所有的送货服务都需要通过众包或使用零售商自己的车辆来完成。我们将这个问题形式化，并将其定位于众包的文献和并非所有客户都需要访问的路由问题中。我们证明，为了评估这个随机问题的目标函数，即使只有一个解，人们需要解决一个指数数量的旅行推销员问题。为了解决这种复杂性，我们提出了机器学习和蒙特卡罗模拟方法来近似目标函数，并提出了分支定界算法和启发式算法来减少评估次数。我们表明，这些方法在小规模实例中效果良好，并获得了对众包给客户带来的经济和环境效益的管理见解。
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.