自行车信使/ TSPPD与OptaPlanner

亲爱的OptaPlanner专家！

我想使用OptaPlanner（或类似的开源Java框架）来优化自行车信使服务的路线。 让我们假设5个信使必须从某个来源获取30个信封并将它们传送到某个目的地：

X(FROM) Y(FROM) X(TO) Y(TO) envelope 1 13745 55419 13883 55756 envelope 2 8406 53246 13937 55854 envelope 3 15738 57396 35996 79499 envelope 4 12045 60418 19349 57118 envelope 5 13750 56416 35733 78403 envelope 6 13190 57068 11860 59749 envelope 7 15021 55768 14098 57379 envelope 8 11513 58543 11501 59683 envelope 9 12013 64155 14120 59301 envelope 10 15006 57578 35511 78426 envelope 11 11450 58819 11916 58338 envelope 12 13728 56304 35524 79013 envelope 13 15104 60923 17937 57066 envelope 14 11373 58388 13983 53804 envelope 15 18575 55186 18718 54381 envelope 16 11639 50071 17363 58375 envelope 17 11273 53410 10860 60441 envelope 18 13766 59041 13963 57769 envelope 19 16138 55801 16183 56024 envelope 20 13728 56146 14301 61694 envelope 21 12848 57059 13586 59734 envelope 22 13645 56488 13955 55859 envelope 23 12896 56838 13937 55908 envelope 24 13341 58150 35709 78924 envelope 25 13483 57303 13614 57820 envelope 26 12741 63478 15230 59838 envelope 27 14676 51691 16501 48361 envelope 28 13748 54933 14120 56110 envelope 29 17875 59565 20453 61903 envelope 30 9772 56424 6404 55601 

我的五个信使分布在整个城市（所以我没有一个仓库），他们不必回到他们开始的地方：

  XY messenger A 13750 57578 messenger B 15104 53410 messenger C 13728 55801 messenger D 12741 63478 messenger E 14676 18575 

我会使用以下硬约束：

• 每个信使都可以携带十五个信封
• 信封的行进方式应少于直接路线的三倍（因此交货时间不会太长）

而这些软约束：

• 优化信使必须循环的方式

我想我必须调整车辆路由示例，但由于我是新手，我不知道从哪里开始。 如何确保在信使尝试发送信封之前拾取信封？ 如果你能帮助我在这里会很棒……

谢谢！

Answer 1

我不是OptaPlanner专家。 但是我想在你的括号（或类似的开源框架）中提取你提到的内容。 但是，如果OptaPlanner已经为您提供了合理的解决方案，您可能会忽略这一点。 如果没有，或者您只想比较结果，这可能对您有意义。

首先，您描述的问题听起来很简单但是更具挑战性。 它基本上是一个带有分拣和交付，多个仓库，开放路线和时间窗口/限制的Capapitated VRP。 对于这类问题，您可能找不到很多开源解决方案。

我创建了一个名为jsprit的项目。 jsprit可以解决您的问题。 它既不像OptaPlanner，也不是框架。 它非常关注车辆路径问题，是一个Java工具包（即一组库）。 我实现了你的问题。 在这里您可以找到评论的代码。

我略微改变了你的一个限制条件（“信封行进的方式应该少于直接路线的三倍，因此交付时间不会太长”）。 如果你想确保交货速度相对较快，我相信你最好能够相对于“最佳”信使做出这种约束。 因此，我将其替换为（“信封行进的方式应该是使用最佳信使的直接路线的三倍，即在直接路线上最快的信使”）。

查看结果（您可以绘制并获得简短报告）并使用其他约束或算法配置以使其适应您的要求。 如果您有任何疑问，请随时与我联系。

jsprit是绝对的，与OptaPlanner相比是一个非常年轻的项目，最终你发现错误或约束定义并不像它应该的那样舒适。 但好处是，你可以帮助改善它…通过报告错误，批评和建议替代解决方案等:)。

Answer 2

以VRP（车辆路线）为例进行调整，如下所示：

• 将类Vehicle重命名为Messenger
• 将类的Messenger的depot属性更改为startingLocation
• 删除“车辆返回仓库”约束（除非信使需要返回其起始位置）。
• 使用类型PICKUP或DELIVERY将Customer类重命名为EnveloppeExchange
• 注意：如果提取和交付EnveloppeExchange具有相同的位置，请使用2个单独的EnveloppeExchange实例。
• 在EnveloppeExchange添加一个名为messengerContents的影子变量，它枚举了EnvelopeExchange到达的信使的包络集。 编写一个VariableListener （参见文档），使该影子变量保持最新。
• 添加一个约束，即交付EnveloppeExchange中的messengerContents必须包含所需的enveloppe
• 添加一个约束，任何EnveloppeExchange上的messengerContents都不能大于15
• 添加一个约束条件，即EnveloppeExchange的messengerContents包含该信封X的任何包络X（ EnveloppeExchange距离的总和）不得超过直接路径的3倍。

最好使用6.0.0.CR4（今天发布）。