当前位置: 首页 > 知识库问答 >
问题:

具有多次跳闸的OR-Tools CVRP

濮阳鸿卓
2023-03-14

我正在尝试使用OR Tools的路由解算器来解决多行程容量VRP。我需要的是

  • 一个停车场,路线从这里开始和结束

因此,车辆应该从每个节点提取货物,直到装满货物。然后转到“卸载位置”,卸载所有节点的重量,并继续从节点收集需求,直到达到时间限制或收集所有货物。然后返回仓库。

CVRP重新装载的例子似乎非常接近,但在我的情况下,在路线的末尾,车辆应该在车辆段之前到达卸载位置。换言之,车辆不能满载前往车辆段(起点、终点位置)。

例子:

0: Depot
1: Unloading Location
2, 3, 4, 5, 6, 7: Nodes to pick up demand


0 > 2 > 3 > 4 > 1 (unload) > 5 > 6 > 7 > 1 (unload) > 0
0 > 2 > 3 > 4 > 1 (unload) > 5 > 6 > 7 > 0 This is the result cvrp_reload returns.

我对或工具相当陌生,正在尝试解决它。如果你有什么想法,你能帮我吗?

  • 我正在使用Python和/或工具v8.2

我认为,通过使用count\u维度,可以在最后一点(在仓库之前卸载)之前实现前面的约束,但我不知道如何实现。

共有1个答案

盖玉石
2023-03-14

简单地添加

    # Vehicles must be empty upon arrival
    capacity_dimension = routing.GetDimensionOrDie("Capacity")
    for v in range(manager.GetNumberOfVehicles()):
        print(f"vehicle {v}")
        end = routing.End(v)
        #routing.solver().Add(capacity_dimension.CumulVar(end) == 0) # see comment below
        capacity_dimension.SetCumulVarSoftUpperBound(end, 0, 100_000)

可能的输出:

./2442_unload.py
...
I0417 23:53:02.181640 17437 search.cc:260] Solution #317 (372696, objective maximum = 4838552, time = 2969 ms, branches = 3223, failures = 940, depth = 33, MakeInactiveOperator, neighbors = 265820, filtered neighbors = 317, accepted neighbors = 317, memory used = 14.93 MB, limit = 99%)
I0417 23:53:20.290527 17437 search.cc:260] Solution #318 (469816, objective minimum = 372696, objective maximum = 4838552, time = 2987 ms, branches = 3239, failures = 945, depth = 33, MakeInactiveOperator, neighbors = 267395, filtered neighbors = 318, accepted neighbors = 318, memory used = 14.93 MB, limit = 99%)
I0417 23:53:21.045410 17437 search.cc:260] Solution #319 (469816, objective minimum = 372696, objective maximum = 4838552, time = 2988 ms, branches = 3247, failures = 947, depth = 33, MakeActiveOperator, neighbors = 267415, filtered neighbors = 319, accepted neighbors = 319, memory used = 14.93 MB, limit = 99%)
I0417 23:53:22.304931 17437 search.cc:260] Solution #320 (372696, objective maximum = 4838552, time = 2989 ms, branches = 3253, failures = 949, depth = 33, MakeActiveOperator, neighbors = 267464, filtered neighbors = 320, accepted neighbors = 320, memory used = 14.93 MB, limit = 99%)
I0417 23:53:30.987548 17437 search.cc:260] Finished search tree (time = 2998 ms, branches = 3259, failures = 982, neighbors = 268318, filtered neighbors = 320, accepted neigbors = 320, memory used = 14.93 MB)
I0417 23:53:31.046630 17437 search.cc:260] End search (time = 2998 ms, branches = 3259, failures = 982, memory used = 14.93 MB, speed = 1087 branches/s)
Objective: 372696
dropped orders: [25]
dropped reload stations: [3, 5]
Route for vehicle 0:
 0 Load(0) Time(0,0) -> 20 Load(0) Time(75,506) -> 12 Load(3) Time(94,525) -> 14 Load(6) Time(119,550) -> 13 Load(10) Time(140,700) -> 8 Load(13) Time(159,1000) -> 0 Load(0) Time(237,1500)
Distance of the route: 2624m
Load of the route: 0
Time of the route: 237min

Route for vehicle 1:
 1 Load(0) Time(0,0) -> 19 Load(0) Time(2,182) -> 24 Load(3) Time(20,200) -> 26 Load(7) Time(42,400) -> 4 Load(15) Time(89,770) -> 7 Load(15) Time(92,773) -> 11 Load(0) Time(169,850) -> 17 Load(3) Time(188,959) -> 10 Load(11) Time(229,1000) -> 1 Load(0) Time(307,1500)
Distance of the route: 2648m
Load of the route: 0
Time of the route: 307min

Route for vehicle 2:
 2 Load(0) Time(0,0) -> 23 Load(0) Time(15,63) -> 22 Load(4) Time(37,85) -> 21 Load(7) Time(85,101) -> 9 Load(10) Time(104,120) -> 18 Load(0) Time(184,200) -> 16 Load(8) Time(226,600) -> 15 Load(12) Time(248,800) -> 6 Load(15) Time(268,1000) -> 2 Load(0) Time(346,1500)
Distance of the route: 2624m
Load of the route: 0
Time of the route: 346min

Total Distance of all routes: 7896m
Total Load of all routes: 0
Total Time of all routes: 890min

注意:我使用软约束,因为否则求解器更喜欢删除所有节点,并且永远不会设法从这个解决方案搜索空间点中逃脱。

 类似资料:
  • 我正在尝试解决一个路由问题,如下所示: 我们有许多“任务”,每个任务都包含许多需要工人收集的项目 我的问题是如何使用或工具实现以下解算器: 允许每个工人“卸载”在仓库收集的物品并继续下一次行程 到目前为止,我已经尝试: 将n个任务中出现的相同项目视为n个不同的节点(反映在距离矩阵中,这些n个节点之间的距离设置为0) 很抱歉问了这么长的问题,谢谢,请帮忙! 更新:我使用了AddDisconction

  • 请帮助我解决我的定期容量限制车辆路径问题。 在谷歌群组上找到同样的问题。 我试图建模的是: > 1个仓库 多个客户(假设4个) 多天(假设3天) 具有每公里价格和特定容量的多种车型 每个客户都有:交付频率和每次交付的需求 每个客户都必须被分配到一个交付模式。每个频率都可能有多种交付模式。模式指示当天是否可以交付。对于1和3个工作日的频率:,频率为2,频率为3:这些是可能的模式。 每个客户每次交付的

  • 我有数据。该表名为enc.per。每天的遭遇日。它有2403行,其中指定了服务日期和当天就诊的患者数量。我想看看在工作日中任何一种类型的患者的中位数。 这一行给出了一个错误 < code >[. data . table (enc . per . day,,list(patient . enches = median(n)),:j的列的计算结果与每个组的类型不一致:组4的结果具有类型为“integ

  • 问题内容: 在Python 的列表中,以下代码给出此输出: 是否存在使用JavaScript中的数组执行此操作的简便方法? 我编写了以下函数来做到这一点,但是有没有更短或更短的东西呢? 问题答案: 您可以这样做: 它在每次迭代中将数组加倍,因此可以创建很少迭代的真正大数组。 注意:您还可以通过使用代替来改善您的功能,因为每次迭代都会创建一个新的数组。像这样(作为一个如何使用数组的示例显示):

  • 我正在运行同一个Spring Boot 2.0.4应用程序的多个实例,出于扩展目的,它们使用以下命令消耗来自ActiveMQ队列的消息:@JmsListener(目的地="myQ") 只有第一个消费者接收消息,如果我停止第一个消费者,第二个实例开始接收消息。我希望每个消费者以循环方式使用一条消息,而不是同一条消息。但只有第一消费者消费消息。

  • 目前,我得到了以下函数,该函数遍历Pandas DataFrame()列并创建一个计数: 我有许多参数要分配给/调用函数——目前,我正在做以下工作: 这样做效果很好,但我想知道是否有更实用/有效的方法可以达到同样的效果。 我正在考虑将变量名添加到列表中,例如、、、等,并形成某种循环——如果这样做可行的话。。。 因此,也许有点像: 或者,有没有使用熊猫的方法?