自行车信使/ TSPPD与OptaPlanner [英] Bicycle messenger / TSPPD with OptaPlanner
问题描述
亲爱的OptaPlanner专家!
Dear OptaPlanner experts!
我想使用OptaPlanner(或类似的开源Java框架)来优化自行车信使服务的路线。让我们假设5名信使必须从某个来源获取30个信封并将它们送到某个目的地:
I would like to use OptaPlanner (or a similar Open Source Java Framework) to optimize routes for a bicycle messenger service. Let's assume 5 messengers have to pick up 30 envelopes FROM a certain origin and deliver them TO a certain destination:
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
我的五名信使分布在整个城市(所以我没有单一的仓库),他们不必回到他们开始的地方:
My five messengers are distributed through the city (so I don't have a single depot) and they don't have to go back to where they started:
X Y
messenger A 13750 57578
messenger B 15104 53410
messenger C 13728 55801
messenger D 12741 63478
messenger E 14676 18575
我会使用以下硬约束:
- 每个信使最多可携带15个信封
- 信封旅行的方式应少于直达路线的三倍(因此送货时间不会太长)
这些软限制:
- 优化信使的周期方式
我想我必须调整车辆路线示例,但由于我是新手,我不知道从哪里开始。如何确保在信使尝试发送信封之前拾取信封?如果你能在这里帮助我会很棒...
I guess I have to adjust the vehicle routing example, but since I am a newbie I don't know where to start. How can I make sure that an envelope is picked up before the messenger tries to deliver it? It would be great if you could help me out here...
谢谢!
推荐答案
我不是OptaPlanner专家。但是我想在你的括号(或类似的开源框架)中提取你提到的内容。但是,如果OptaPlanner已经为您提供了合理的解决方案,您可能会忽略这一点。如果没有,或者您只想比较结果,这可能对您有意义。
I am no OptaPlanner expert. But I'd like to pickup what you mentioned in your brackets (or similar Open Source Framework). However, if OptaPlanner already provided you with a reasonable solution, you can probably ignore this. If not or you just want to compare the results, this might be interesting for you.
首先,您描述的问题听起来很简单但是更具挑战性。它基本上是一个带有分拣和交付,多个仓库,开放路线和时间窗口/限制的Capapitated VRP。对于这类问题,您可能找不到很多开源解决方案。
First, the problem you describe sounds simple but is one of the more challenging. It is basically a Capacitated VRP with Pickup and Deliveries, Multiple Depots, Open Routes and Time Windows/Restrictions. You probably cannot find many Open Source solutions for this kind of problem.
我创建了一个名为 jsprit 的项目。 jsprit可以解决您的问题。它既不像OptaPlanner,也不是框架。它非常关注车辆路径问题,并且是一个Java工具包(即一组库)。
我实现了你的问题。 在这里,您可以找到评论的代码。
I created a project called jsprit. jsprit can solve your problem. It is neither similar to OptaPlanner nor it is framework. It has a strong focus on vehicle routing problems and is a Java toolkit (i.e. a set of libraries). I implemented your problem. Here you can find the commented code.
我略微改变了你的一个约束条件(信封行进的方式应该少于直接路线的三倍,因此交付时间不会太长)。如果你想确保交货速度相对较快,我相信你最好能够相对于最佳信使做出这种约束。因此,我将其替换为(信封行进的方式应该小于直接路线的三倍,使用最佳信使,即直接路线上最快的信使。
I slightly changed one of your constraints ("The way an envelope travels should be less than three times the direct route so the delivery doesn't take too long"). If you want to ensure that deliveries are comparably fast, I believe you are better off making this constraint relative to the "best" messenger. Thus, I replaced it with ("The way an envelope travels should be less than three times the direct route with the best messenger, i.e. the messenger that is the fastest on the direct route").
查看结果(您可以绘制并获得简短报告)并使用其他约束或算法配置来使其适应您的要求。如果您有任何疑问,请随时与我联系。
Look at the result (you can plot it and get a brief report) and play with other constraints or the algorithm configuration to adapt it to your requirements. If you have questions, do not hesitate to contact me.
jsprit 是绝对的,与OptaPlanner相比是一个非常年轻的项目,最终你发现bug或约束定义并不那么舒服应该。但好处是,你可以帮助改善它...通过报告错误,批评和建议替代解决方案等。:)。
jsprit is in absolute terms and in comparison to OptaPlanner a very young project, eventually you find bugs or constraint definition is not that comfortable as it should be. But the good thing is, you can help to improve it ... by reporting bugs, criticising and suggesting alternative solutions etc. :).
这篇关于自行车信使/ TSPPD与OptaPlanner的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!