OR-tools路由优化节点兼容性

Question

我正在尝试解决一个有能力的路由问题，我有一组节点需要不同数量和不同类型的项目。
另外我想允许节点掉落，因为所有具有一种物品的节点可能仍然会超过车辆容量，从而导致无解。
然而，最终所有节点都应该被服务，所以我使用迭代方法，我将每个项目类型视为单独的路由问题。
但我想知道是否可以使用析取或类似的东西来解决 'global' 路由问题。感谢任何有关这是否可能的帮助。

Example:
Node 1 - item A - demand 10
Node 2 - item A - demand 10
Node 3 - item A - demand 12
Node 4 - item B - demand 10
Node 5 - item B - demand 10

vehicle I - capacity 20
vehicle II - capacity 10

我的做法：
首先解决项目 A：车辆 I 服务于节点 1 和 2，节点 3 被丢弃，保存丢弃的节点以供以后迭代
然后解决项目 B：车辆 I 服务于节点 4 和 5，车辆 II 处于空闲状态求解剩余节点 3：车辆 I 服务于节点 3

编辑我调整了我的方法以适应@mizux 的回答。代码下方：

EDIT2 修复了第一个循环中的需求回调函数仍会引用 product_index 变量并因此 return 错误需求的错误。使用 functools.partial.

修复

import functools
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

class CVRP():
    def __init__(self, data):
        # assert all(data['demands'] < max(data['vehicle_capacities'])) # if any demand exceeds cap no solution possible
        self.data = data

        self.vehicle_names_internal = [f'{i}:{j}' for j in data['products'] for i in data['vehicle_names']]
        self.manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), len(self.vehicle_names_internal), data['depot'])
        self.routing = pywrapcp.RoutingModel(self.manager)

        transit_callback_id = self.routing.RegisterTransitCallback(self._dist_callback)      
        self.routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_id)
        
        # set up dimension for each product type for vehicle capacity constraint
        for product_index, product in enumerate(data['products']):
            dem_product_callback = functools.partial(self._dem_callback_generic, product_index=product_index)
            dem_callback_id = self.routing.RegisterUnaryTransitCallback(dem_product_callback)
            vehicle_product_capacity = [0 for i in range(len(self.vehicle_names_internal))]
            vehicle_product_capacity[product_index*data['num_vehicles']:product_index*data['num_vehicles']+data['num_vehicles']] = data['vehicle_capacities']
            print(product_index, product)
            print(self.vehicle_names_internal)
            print(vehicle_product_capacity)
            self.routing.AddDimensionWithVehicleCapacity(
                dem_callback_id,
                0,
                vehicle_product_capacity,
                True,
                f'capacity_{product}',
                )

        # disjunction (allow node drops)
        penalty = int(self.data['distance_matrix'].sum()+1) # penalty needs to be higher than total travel distance in order to only drop locations if not other feasible solution
        for field_pos_idx_arr in self.data['disjunctions']: 
            self.routing.AddDisjunction([self.manager.NodeToIndex(i) for i in field_pos_idx_arr], penalty)

        
    def _dist_callback(self, i, j):
        return self.data['distance_matrix'][self.manager.IndexToNode(i)][self.manager.IndexToNode(j)]
    
    def _dem_callback_generic(self, i, product_index):
        node = self.manager.IndexToNode(i)
        if node == self.data['depot']:
            return 0
        else:
            return self.data['demands'][node, product_index]

    def solve(self, verbose=False):    
        search_parameters = pywrapcp.DefaultRoutingSearchParameters()
        search_parameters.first_solution_strategy = (
            routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)
        search_parameters.local_search_metaheuristic = (
            routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC)
        search_parameters.time_limit.FromSeconds(30)

        self.solution = self.routing.SolveWithParameters(search_parameters)

Answer 1

您应该创建两个容量维度，每种维度一个，在每个位置增加相关维度。
您可以为每种物品类型复制您的车辆，即：
- v0，车辆 1 类型 A：容量 A：20，容量 B：0
- v1，B 型车辆 1：容量 A：0，容量 B：20
- v2，A 型车辆 2：容量 A：10，容量 B：0
- v3，B 型车辆 2：容量 A：0，容量 B：10
注意：您可以复制它以允许多次旅行
您可以创建一个“门”节点以仅允许一种车辆配置。例如只允许 v0 或 v1 做一些访问
```
v0_start = routing.Start(0)
v0_end = routing.End(0)
v1_start = routing.Start(1)
v1_end = routing.End(1)
gate_index = manager.NodeToIndex(gate_index)
routing.NextVar(v0_start).setValues[gate_index, v0_end]
routing.NextVar(v1_start).setValues[gate_index, v1_end]
```
由于节点只能被访问一次，所以v0和v1中的一辆车可以通过门节点，而另一辆车只能去结束节点即空路径你可以在post处理时删除作业。
如果车辆 II 比车辆 I 便宜，您还可以将车辆固定成本添加到激励求解器以使用车辆 II 等...

将每个位置添加到析取，以便求解器可以根据需要删除它们

location_index = manager.NodeToIndex(location_id)
routing.AddDisjunction(
  [location_index], # locations
  penalty,
  max_cardinality=1 # you can omit it since it is already 1 by default
)

OR-tools路由优化节点兼容性

OR-tools routing optimization node compatibility

python

optimization

or-tools

vehicle-routing