或工具路由优化节点兼容性

Question

我试图解决一个有能力的路由问题，其中我有一组节点，需要不同的数量和不同类型的项目。

此外，我希望允许节点下降，因为所有具有一种类型的项目的节点仍然可能超过车辆容量，因此不会导致任何解决方案。

但是，最终应该为所有节点服务，所以我使用了一种迭代方法，将每一项类型作为单独的路由问题来处理。

但我想知道是否可以使用中断或类似的方法来解决“全局”路由问题。对于是否有可能提供任何帮助，我们将不胜感激。

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项: vehicle I服务节点1和2，节点3被删除，保存掉的节点供以后的迭代

然后解决B项:车辆I服务节点4和5，车辆II空闲解决剩余节点3:车辆I服务节点3

编辑i调整了我的方法，以适应@mizux的回答。守则如下：

EDIT2修复了一个错误，第一个循环中的需求回调函数仍然会引用product_index变量，从而返回错误的需求。通过使用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

1. 您应该在每个位置为每个类型创建两个容量维度，增加相关维度。

1. 您可以复制每种物品类型的车辆，例如：

- v0, Vehicle 1 Type A with: capacity A: 20, capacity B: 0
- v1, Vehicle 1 Type B with: capacity A: 0, capacity B: 20
- v2, Vehicle 2 Type A with: capacity A: 10, capacity B: 0
- v3, Vehicle 2 Type B with: capacity A: 0, capacity B: 10

注意:您可以复制它以允许多次旅行。

1. ，您可以创建一个“门”节点，只允许一个车辆配置。只允许v0或v1进行某些访问

routing.NextVar(v0_start).setValuesgate_index，routing.NextVar(v1_start).setValuesgate_index，v1_end 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)

由于节点只能访问一次，所以v0和v1中的一辆车可以通过门节点，而另一辆车别无选择，只能到达终端节点，即在后处理分配时可以移除空路由。

1. 你也可以添加一个车辆FixedCost来激励解决者使用第二辆车，如果它比I型车便宜……

1. 将每个位置添加到析取中，以便解决程序可以在需要时删除它们。

location_index = manager.NodeToIndex(location_id) routing.AddDisjunction( location_index，# locations default，max_cardinality=1 #您可以省略它，因为默认情况下它已经是1 )