OptaPlanner CVRPTW-容量问题解决方案 [英] OptaPlanner CVRPTW - solution with capacity issue
问题描述
我遇到以下CVRPTW问题，并且我正在尝试使用OptaPlanner找到一个好的解决方案.时间采用hh:mm:ss格式.
I have the following CVRPTW problem and I'm trying to find a good solution with OptaPlanner. Time is in hh:mm:ss format.
我的DRL文件类似于此，带有终止标签的区别:
My DRL file is like this. Moreover I defined also a hard contraint relative to the arrival before ready time. My solver configuration is like this, with the difference of the termination tag:
<termination>
<terminationCompositionStyle>OR</terminationCompositionStyle>
<maximumSecondsSpend>10</maximumSecondsSpend>
<scoreAttained>0hard/-750000soft</scoreAttained>
</termination>
这是问题陈述:
PROBLEM STATEMENT:
CustID ReadyTIME DueTIME ServiceDUR DEMAND
1 20:38:18 20:44:18 00:05:00 2
2 20:20:53 20:26:53 00:05:00 4
3 20:51:39 20:57:39 00:05:00 3
4 20:20:18 20:26:18 00:05:00 6
5 20:34:15 20:40:15 00:05:00 5
6 20:21:40 20:27:40 00:05:00 10
我有2辆可容纳10件物品和1个仓库的车辆.
I have 2 vehicles with both a capacity of 10 items and 1 depot.
这是解决方案(按车辆分组并按到达时间排序的客户):
This is the solution (customers grouped by vehicle and sorted by arrival time):
Vehicle 1 Capacity 10 - from Depot [1]
[6] D: 10 Ar.T: 20:21:40 Prev.D: 00:02:21 Next.D: --:--:--
Vehicle 2 Capacity 10 - from Depot [1]
[4] D: 6 Ar.T: 20:20:18 Prev.D: 00:01:08 Next.D: 00:02:21
[2] D: 4 Ar.T: 20:27:42 Prev.D: 00:02:24 Next.D: 00:03:38
[5] D: 5 Ar.T: 20:36:03 Prev.D: 00:03:21 Next.D: 00:02:09
[1] D: 2 Ar.T: 20:43:26 Prev.D: 00:02:23 Next.D: 00:07:23
[3] D: 3 Ar.T: 20:55:40 Prev.D: 00:07:14 Next.D: --:--:--
(D =需求，Ar.T =到达时间，Prev.D =到上一个位置的距离，Next.D到下一个位置的距离)
(D = demand, Ar.T = arrival time, Prev.D = distance from previous location, Next.D distance from next location)
如您所见，车辆2必须运输6 + 4 + 5 + 2 + 3 = 20个物品，这大于容量. 我不明白如果配置中的容量存在严格的矛盾，为什么求解器会建议我使用此解决方案.
As you can see vehicle 2 have to transport 6+4+5+2+3=20 items, which is greater than the capacity. I don't understand why the solver suggest me this solution if there's a hard contraint relative to the capacity in the configuration.
考虑到我的规则，这不是可接受的解决方案.我想念什么吗? 求解器没有提供解决方案的条件吗?是否计划解决程序失败"终止?
Considering my rules, this is not an acceptable solution. Am I missing something? Isn't there a condition where the solver provides no solution? Is it contemplated a "solver failed" termination?
推荐答案
如果我错了，请更正，但是您有:
Correct if I am wrong, but you have:
-
总需求为 30 (6 + 4 + 5 + 2 + 3 + 10)
a total demand of 30 (6+4+5+2+3+10)
总容量为 20 (2辆车，每辆10辆)
a total capacity of 20 (2 vehicles with 10 each)
当卡车只能运输20件物品时，不可能运输30件物品. 没有可行的解决方案(因此OptaPlanner会提供发现的最好的不可行解决方案).
It's impossible to transport 30 items when your trucks can only transport 20 items. There is no feasible solution (so OptaPlanner delivers the best infeasible solution it finds).
注意:如果同一辆车可以多次使用，请添加额外的Vehicle实例，并添加约束以惩罚使用同一牌照的多个Vehicle实例.
Note: If the same vehicle can be used multiple times, add extra Vehicle instances and add a constraint to penalize the usage of multiple Vehicle instances with the same license plate.
这篇关于OptaPlanner CVRPTW-容量问题解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
