CVRPSPD（同时取货和送货的车辆路径问题）
我真的需要帮助解决这个问题。
我试图解决的问题的设置如下：
有一个仓库，所有车辆都从该仓库调度。车辆在停车场装载有许多装满的垃圾箱。车辆从停车场行驶到现场，在那里他们放下装满的垃圾箱并捡起空的垃圾箱。车辆继续访问站点，直到站点的空垃圾箱填满其容量。一旦空垃圾箱饱和，车辆就会返回停车场，放下空垃圾箱，然后拿起满的垃圾箱。重复此过程，直到所有地点都满足了空垃圾箱的拾取和满垃圾箱的投放需求，如有必要，车辆可以完成多次旅行。目标应该是最大限度地减少满足所有现场需求所需的总时间。
我首先修改此示例 cvrp_reload 但我正在努力解决这两个维度的结合：空垃圾箱的拾取和满垃圾箱的交付。
我的代码的主要思想：
- 使用维度来跟踪空垃圾箱的拾取情况。
- 使用另一个维度来跟踪满箱的交付情况。
- 车辆上的空箱和满箱的累计总和<=
- 重复仓库的车辆容量，以便车辆可以重新访问仓库以卸载空箱并在必要时重新装载满箱。
这里的问题是：
- 我举了一个简单的例子，取货和送货的需求是：[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被丢弃？
- 当我将容量设置为 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，我一直在努力这个问题已经好几天了。任何见解将不胜感激！谢谢你！！
I really need help with this problem.
The setup of the problem I am attempting to solve is as follows:
There is a depot from which all vehicles are dispatched. Vehicles are loaded with a number of full bins at the depot. Vehicles travel from the depot to sites, where they drop off full bins and pick up empty bins. Vehicles continue to visit sites until they have saturated their capacity with empty bins from sites. Once saturated with empty bins, vehicles return to the depot, drop off their empty bins, and pick up full bins. This process repeats until all sites have had their demand for pickups of empty bins and dropoffs of full bins met, with vehicles completing multiple tours if necessary. Minimizing the total amount of time required to satisfy all site demands should be the objective.
I have begun by modifying this example cvrp_reload but am struggling with the combination of these two dimensions: pickups of empty bins and deliveries of full bins.
The main idea of my code:
- use a dimension to track the pickups of empty bins.
- use another dimension to track the deliveries of full bins.
- the cumulated sum of empty bins and full bins on the vehicle <= vehicle capacity
- duplicate depots so the vehicle could revisit the depot to unload the empty bins and reload full bins when necessary.
The problem here is that:
- I made up a simple example that the pickups and deliveries demand is: [0, 4, 6, 2, 3] and [0, -5, -5, -2, -3], the vehicle capacity is 6 (I use only one single vehicle here). I duplicate 2 depots.
_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))
When I set the capacity as 6, the solver dropped node 4(pick up 6, delivery -5). Because when it revisits depot, it is always loaded with a max capacity which is 6. The result:
[(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
This is obviously not the optimal solution, because obviously, the vehicle could first depart with a load of 5 full bins and immediately visit node 4, then visit nodes 3, 5, 6. Why node 4 is dropped?
- When I set the capacity as 10, the result is:
[(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
Notice the last step the vehicle return to the depot with Deliveries(5) and Pickups(6) which is 11 in sum, and it is larger than 10!!! Given I add the following constraint, why does it results like this?
# 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"])
My full code is here: cvrpspd.ipynb and I have been struggling with this problem for several days. Any insights would be greatly appreciated! Thank you!!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论