traveling-salesman - 无仓库 VRP - 路边援助

Question

我正在研究一个非常独特的问题。
想象一家路边救援公司想要动态规划其车辆的路线。因此，对于每个新事件包，都希望根据某些约束（时间限制、道路可达性、车辆-事件匹配）创建满足它们的路线。

该公司拥有一支多样化的车队（摩托车用于简单的情况，拖车用于困难的情况）并且每个事件都表明它是独一无二的（我们知道它是否只需要燃料，或者需要牵引）。

没有车厂，只有街上来来往往的车辆。目标是在途中动态创建路线，同时牢记时间和总行驶距离的最小化。

你有没有遇到过这样的问题？你知道它属于哪个 VRP 变体吗？

我已经看到了之前的两个问题，但不幸的是它们不适合我的问题。受人尊敬的optaplanner - VRP but with no depot和是否 optaplanner out of box 支持 VRP with multiple trips and no depot，它们都是开放式 VRP。

不幸的是，我现在没有代码，因为我仍在模拟我将解决这个问题的方式。我真的很抱歉创建了一个建议问题而不是一个真正的问题。

非常感谢你。

标签： traveling-salesmanvehicle-routing

Answer 1

这是一个丰富的动态/实时车辆路线问题。您不会找到问题的确切名称，因为当 VRP 变得过于复杂时，它们不适合任何标准类别。

这显然是一个动态/实时问题（这些术语可以互换使用），因为您通常只会在短时间内发现路边故障。

有时您正在维修一辆抛锚的汽车，这将是一个单站（因此是车辆路线问题）。有时你在拖车，这将是一个提货问题。因此，您可以将两者混合在一起。

您会希望尽快找到发生故障的车辆，而有些车辆需要比其他车辆更快地修理（想想在高速公路上的危险位置抛锚的汽车）。因此，您将需要软时间窗口，这样您就可以惩罚迟到，而不是大多数 VRP 公式支持的标准硬时间窗口。

此外，为了让您能够扩展到更大的问题，您需要一个增量优化器，当添加新作业、更改车辆位置等时，它可以从以前的（可能现在不可行的）解决方案重新启动。这不支持开箱即用在我知道的开源求解器中。

我们开发了一个商业引擎来完成上述工作。我们开始使用 jsprit 库，它支持将单站和取件问题混合在一起。我们后来不得不替换 jsprit，因为我们必须重写大量代码才能让它在实时问题上愉快地运行，但是 jsprit 可能仍然是一个有用的起点。在本白皮书中，我们讨论了在让 jsprit 处理实时问题时必须克服的一些早期技术障碍。