OptaPlanner的车辆路线和客户访问之间的关系 [英] OptaPlanner vehicle routing and relations between customer visits
问题描述
我正在使用OptaPlanner优化车辆路径问题，与所提供的示例非常相似.
I am using OptaPlanner to optimize a vehicle routing problem very similar to the provided example.
我面临以下挑战，并且会感谢一些想法.
I am faced with the following challenge and will appreciate some ideas.
某些访问客户与其他访问有关系，例如:
Some of the visits to customers have relations to other visits, for example:
- 访问必须与另一个访问同时开始.
- 访问必须在另一次访问结束后2小时开始.
- 一次访问必须分配给分配给另一次访问的同一辆车.
挑战是:如何在移动其中之一的同时允许访问的移动而又不降低得分?
The challenge is: How to allow moves of the visits without resulting in lower score while moving one of them?
每次访问可能位于不同的脊椎上(分配给另一辆车)，因此所有提供的动作选择器很可能会提供仅更改一次访问的动作.由于依赖，这样的举动很可能导致得分较低，并且永远不会被选择.
Each visit might be on a different chine (allocated to a different vehicle), so that all provided moves selectors will most likely provide moves that change only one visit. Such moves most probably result in lower score due to the dependency and will never be selects.
相同的开始情况:更改一次访问的开始时间的任何举动都会导致得分降低. 同一车辆场景:任何将一次造访改变为另一车辆的举动都会导致得分降低.
Same start scenario: any move that change the start time of one visit will result in lower score. Same vehicle scenario: any move that change one visit to a different vehicle will result in lower score.
目前，我正在使用禁忌搜索获得令人满意的结果. 延迟接受可能是答案.
Currently I am using Tabu Search with satisfying results. Late Acceptance might be the answer.
谢谢.
推荐答案
What you're describing is a form of a score trap. Although Late Acceptance is likely to produce better results than Tabu Search when the score trap is present (and it's just changes 2 lines to switch to it), it's still going to affect the results badly.
那些 docs 描述2摆脱得分陷阱的答案:
Those docs describe 2 answers to get rid of the score trap:
1)在这种情况下，无法提高得分函数的粒度.
2)在这种情况下，课程移动将有效.例如，您可以添加一个自定义移动工厂(但也保留原始的moveSelectors-或更好地进行基准测试，无论是否包含原始moveSelectors).让自定义移动工厂生成不太可能打破这些约束的移动.例如:如果访问A和B需要同一辆车，则将A移到另一辆车的链条中，同时将B移到同一辆车的链条中的其他位置(重用CompositeMove).
2) Course grained moves will work in this case. For example you can add a custom move factory (but keep the original moveSelectors too - or better yet benchmark with and without the original moveSelectors). Let the custom move factory generate moves that are less likely to break those constraints. For example: if visit A and B need the same vehicle, move A inside another vehicle's chain and at the same time move B to somewhere else in the same vehicle's chain (reuse CompositeMove).
还有第三种方法，我会尽快记录下来(但我不认为这很容易应用于这种情况):
And there's a 3th way I 'll document soon (but I don't see it applying to this case easily):
3)在某些情况下，有可能将这样的硬约束烘焙到模型的类图中(这使它们内置了硬约束).例如，在考试安排中，如果需要在同一时间段内进行2场或更多场考试，则只有1场考试是领导者"，并且具有一个时隙变量.其他考试是成群的"，这意味着当领导者更换时，它们的时间间隔会由阴影变量进行调整.
3) In some cases, its possible to bake such hard constraints into the class diagram of the model (which makes them build-in hard constraints). For example in exam scheduling, if 2 ore more exams need to be at the same timeslot, only 1 exam is "the leader" and has a timeslot variable. The other exams are "herd", which means their timeslots get adjusted by a shadow variable when the leader changes.
这篇关于OptaPlanner的车辆路线和客户访问之间的关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
