4

亲爱的 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

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

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

我会使用以下硬约束：

  • 每个信使最多可携带十五个信封
  • 信封的运输方式应少于直达路线的三倍（因此投递时间不会太长）

还有这些软约束：

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

我想我必须调整车辆路线示例，但由于我是新手，我不知道从哪里开始。我如何确保在信使尝试投递之前取走信封？如果你能在这里帮助我，那就太好了……

谢谢！

4

2 回答 2

6

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

首先，您描述的问题听起来很简单，但却是一个更具挑战性的问题。它基本上是一个带有提货和交货、多个站点、开放路线和时间窗口/限制的容量 VRP。对于此类问题，您可能找不到很多开源解决方案。

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

我稍微改变了您的一个限制条件（“信封的行进方式应该少于直接路线的三倍，因此交付时间不会太长”）。如果您想确保交付速度相当快，我相信您最好相对于“最佳”信使进行此限制。因此，我将其替换为（“信封的行进方式应小于具有最佳信使的直接路线的三倍，即直接路线上最快的信使”）。

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

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

于 2013-12-05T23:01:39.193 回答
4

以 VRP（车辆路由）为例，调整如下：

  • 将类重命名Vehicle为Messenger
  • 将类Messenger的depot属性更改为startingLocation
  • 删除“车辆返回站点”约束（除非信使需要返回其起始位置）。
  • 将类重命名为CustomerPICKUPEnveloppeExchange或 DELIVERY
  • 注意：如果取件和交付EnveloppeExchange具有相同的位置，请使用 2 个单独的EnveloppeExchange实例。
  • EnveloppeExchange在调用中添加一个影子变量，该变量messengerContents枚举到达的信使所EnveloppeExchange具有的信封集。编写一个VariableListener（请参阅文档）使该影子变量保持最新。
  • 添加一个约束，即messengerContents在交货时EnveloppeExchange必须包含所需的信封
  • messengerContents添加at anyEnveloppeExchange不得大于 15的约束
  • 添加一个约束条件，即任何信封 X（即's包含该信封 X 的EnveloppeExchange距离之和）不得超过直接路线的 3 倍。EnveloppeExchangemessengerContents

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

于 2013-09-30T05:47:19.973 回答