1

我真的需要帮助解决这个问题。

我试图解决的问题的设置如下：

有一个车站，所有车辆都从这里派出。车辆在站点装载了许多已满的垃圾箱。车辆从仓库行驶到站点，在那里他们放下装满的垃圾箱并捡起空垃圾箱。车辆继续访问站点，直到它们的容量用站点的空垃圾箱饱和。一旦装满空垃圾箱，车辆就会返回仓库，放下空垃圾箱，然后拿起装满的垃圾箱。重复此过程，直到所有站点都满足了他们对空箱的取货和满箱的下车的需求，并且车辆在必要时完成了多次旅行。目标应该是最大限度地减少满足所有站点需求所需的总时间。

我已经开始修改这个示例cvrp_reload，但我正在努力解决这两个维度的组合：空箱的取货和满箱的交付。

我的代码的主要思想：

  • 使用维度来跟踪空垃圾箱的拾取情况。
  • 使用另一个维度来跟踪满箱的交付情况。
  • 车辆上空箱和满箱的累计总和 <= 车辆容量
  • 复制仓库，以便车辆可以重新访问仓库以卸载空箱并在必要时重新装载满箱。

这里的问题是：

  1. 我举了一个简单的例子，取货和送货的需求是：[0,4,6,2,3]和[0,-5,-5,-2,-3]，车辆容量是6（我用这里只有一辆车）。我复制了 2 个仓库。
    _locations = [
        (4, 4),  # depot
        (2, 0), (8, 0),  # 1, 2
        (0, 1), (1, 1)]  # 3, 4
    _locations[1:1] = tuple(repeat(_locations[0], _duplicate_depot_num))

    data['locations'] = _locations
    data['num_locations'] = len(data['locations'])

    data['pickups'] = [0, 4, 6, 2, 3]  # pick up empty bins
    data['pickups'][1:1] = tuple(repeat(-_capacity, _duplicate_depot_num))

    data['deliveries'] = [0, -5, -5, -2, -3]  # delivery full bins
    data['deliveries'][1:1] = tuple(repeat(_capacity, _duplicate_depot_num))

当我将容量设置为 6 时，求解器丢弃了节点 4（拾取 6，交付 -5）。因为当它重新访问仓库时，它总是加载最大容量为 6。结果：

[(4, 4), (4, 4), (4, 4), (2, 0), (8, 0), (0, 1), (1, 1)]
Objective: 100026
dropped orders: [4]
dropped reload stations: [4, 2]
Route for vehicle 0:
 0 Pickups(0) Deliveries(0)-> 3 Pickups(0) Deliveries(5)-> 1 Pickups(4) Deliveries(0)-> 6 Pickups(0) Deliveries(6)-> 5 Pickups(3) Deliveries(3)-> 0 Pickups(5) Deliveries(1)
Distance of the route: 26m
Pickups of the route: 5
Deliveries of the route: 1

这显然不是最优解，因为很明显，车辆可以先满载 5 个箱子离开，然后立即访问节点 4，然后访问节点 3、5、6。为什么节点 4 被丢弃？

  1. 当我将容量设置为 10 时，结果是：
[(4, 4), (4, 4), (4, 4), (2, 0), (8, 0), (0, 1), (1, 1)]
Objective: 32
dropped orders: []
dropped reload stations: [2]
Route for vehicle 0:
 0 Pickups(0) Deliveries(0)-> 3 Pickups(0) Deliveries(10)-> 6 Pickups(4) Deliveries(5)-> 5 Pickups(7) Deliveries(2)-> 1 Pickups(9) Deliveries(0)-> 4 Pickups(0) Deliveries(10)-> 0 Pickups(6) Deliveries(5)
Distance of the route: 32m
Pickups of the route: 6
Deliveries of the route: 5

注意最后一步，车辆返回仓库时，Deliveries(5) 和 Pickups(6) 的总和为 11，大于 10！鉴于我添加了以下约束，为什么会出现这样的结果？

    # Add Constraint: Pick + Deliveries <= max_capacity
    for node in range(len(data['pickups'])):
        index = manager.NodeToIndex(node)
        routing.solver().Add(
            pickups_dimension.CumulVar(index) + deliveries_dimension.CumulVar(index) <= data["vehicle_capacity"])

我的完整代码在这里：cvrpspd.ipynb我已经为这个问题苦苦挣扎了好几天。任何见解将不胜感激！谢谢！！

4

0 回答 0