基于OR-Tools的多趟多取货带容量限制VRP问题求解咨询

问题定义 #

• 存在多个任务，每个任务包含多个需要工人收取的物品
• 同一物品可归属于多个任务（例：物品1可同时属于任务A和任务B）
• 已提前获取所有物品对应的距离矩阵
• 仓库点位固定
• 业务约束：单名工人每趟行程最多只能收取3个任务内的物品

核心诉求 #

需要基于OR-Tools实现满足以下要求的路径规划求解器：

• 支持工人返回仓库卸载已收取物品后，可继续执行下一趟行程
• 可配置约束限制工人每趟最多收取3个任务的物品

此前尝试方案 #

• 将出现在n个任务中的同一物品处理为n个不同节点，更新到距离矩阵中，且这n个节点之间的距离设为0
• 采用取件配送模型对每个任务建模，将同一任务内的其他物品均指向该任务内的某一个物品，设置容量约束上限为3，同时将该被指向的节点的需求设为1（例：任务A包含[1,2,3,4]，则添加取件配送对[1,4]、[2,4]、[3,4]，再为每个工人设置3的容量约束，节点4的需求设为1）。但添加该约束后Jupyter Notebook内核会崩溃，移除约束后代码可正常运行。

解法更新说明 #

使用AddDisjunction和AddPickupAndDelivery接口实现后得到的结果符合预期，方案如下：

• 将出现在不同任务中的同一物品处理为不同节点，将每个任务的所有物品设为一个析取集。
• 取件配送关系无需重复创建节点，仅将每个物品指向对应任务内的同一个物品。

实现代码 #

# "order" 等同于 "task"
data = {
    'distance_matrix': get_distance_matrix(locations),
    'demands': demands,
    'num_workers': number_of_order_groups,
    'max_num_orders': [num_orders_in_group] * number_of_order_groups,
    'disjunctions': disjunctions,
    'depot': 0,
}

manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_workers'], data['depot'])

routing = pywrapcp.RoutingModel(manager)

def distance_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

def demand_callback(from_index):
    """返回节点的需求"""
    # 将路径规划变量索引转换为需求节点索引
    from_node = manager.IndexToNode(from_index)
    return data['demands'][from_node]

demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
    demand_callback_index,
    0,  # 无容量松弛
    data['max_num_orders'],  # 车辆最大容量
    True,  # 初始累积值设为0
    'Capacity')

for d in data['disjunctions']:
    routing.AddDisjunction([manager.NodeToIndex(i) for i in d], 100000000, d.shape[0])

for d in data['disjunctions']:
    for i in d[:-1]:
        routing.AddPickupAndDelivery(manager.NodeToIndex(i), manager.NodeToIndex(d[-1]))

# 设置初始解启发式算法
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC
search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC

# 求解问题
solution = routing.SolveWithParameters(search_parameters)

# 控制台打印求解结果
if solution:
    print_solution(data, manager, routing, solution)

else:
    print('No solution found !')

运行输出结果 #

Objective: 4329
Route for worker 0:
 0 Load(0) ->  49 Load(0.0) ->  64 Load(0.0) ->  48 Load(0.0) ->  50 Load(0.0) ->  62 Load(0.0) ->  46 Load(0.0) ->  47 Load(0.0) ->  63 Load(0.0) ->  67 Load(0.0) ->  51 Load(0.0) ->  52 Load(1.0) ->  66 Load(1.0) ->  65 Load(2.0) ->  68 Load(2.0) ->  69 Load(3.0) ->  0 Load(3.0)
Distance of the route: 421m
Load of the route: 3.0

Route for worker 1:
 0 Load(0) ->  178 Load(0.0) ->  163 Load(0.0) ->  179 Load(0.0) ->  136 Load(0.0) ->  137 Load(0.0) ->  160 Load(0.0) ->  170 Load(0.0) ->  143 Load(0.0) ->  183 Load(0.0) ->  145 Load(0.0) ->  144 Load(0.0) ->  181 Load(0.0) ->  169 Load(0.0) ->  132 Load(0.0) ->  165 Load(0.0) ->  167 Load(0.0) ->  182 Load(0.0) ->  138 Load(0.0) ->  140 Load(0.0) ->  166 Load(0.0) ->  133 Load(0.0) ->  168 Load(0.0) ->  172 Load(0.0) ->  161 Load(0.0) ->  171 Load(0.0) ->  142 Load(0.0) ->  162 Load(0.0) ->  164 Load(0.0) ->  139 Load(0.0) ->  175 Load(0.0) ->  159 Load(0.0) ->  177 Load(0.0) ->  134 Load(0.0) ->  173 Load(1.0) ->  135 Load(1.0) ->  141 Load(1.0) ->  146 Load(2.0) ->  176 Load(2.0) ->  180 Load(2.0) ->  184 Load(3.0) ->  0 Load(3.0)
Distance of the route: 752m
Load of the route: 3.0

Route for worker 2:
 0 Load(0) ->  34 Load(0.0) ->  24 Load(0.0) ->  21 Load(0.0) ->  29 Load(0.0) ->  2 Load(0.0) ->  19 Load(0.0) ->  25 Load(0.0) ->  8 Load(0.0) ->  5 Load(0.0) ->  20 Load(0.0) ->  9 Load(0.0) ->  11 Load(0.0) ->  13 Load(0.0) ->  1 Load(0.0) ->  10 Load(0.0) ->  14 Load(0.0) ->  7 Load(0.0) ->  3 Load(0.0) ->  27 Load(0.0) ->  4 Load(0.0) ->  189 Load(0.0) ->  31 Load(0.0) ->  32 Load(0.0) ->  15 Load(0.0) ->  6 Load(0.0) ->  23 Load(0.0) ->  33 Load(0.0) ->  22 Load(0.0) ->  12 Load(0.0) ->  28 Load(0.0) ->  26 Load(0.0) ->  16 Load(1.0) ->  190 Load(1.0) ->  30 Load(1.0) ->  35 Load(2.0) ->  191 Load(3.0) ->  0 Load(3.0)
Distance of the route: 730m
Load of the route: 3.0

Route for worker 3:
 0 Load(0) ->  109 Load(0.0) ->  110 Load(0.0) ->  148 Load(0.0) ->  111 Load(0.0) ->  112 Load(0.0) ->  147 Load(0.0) ->  149 Load(0.0) ->  150 Load(1.0) ->  113 Load(2.0) ->  157 Load(2.0) ->  158 Load(3.0) ->  0 Load(3.0)
Distance of the route: 214m
Load of the route: 3.0

Route for worker 4:
 0 Load(0) ->  117 Load(0.0) ->  129 Load(0.0) ->  127 Load(0.0) ->  76 Load(0.0) ->  123 Load(0.0) ->  71 Load(0.0) ->  122 Load(0.0) ->  115 Load(0.0) ->  119 Load(0.0) ->  125 Load(0.0) ->  74 Load(0.0) ->  73 Load(0.0) ->  72 Load(0.0) ->  130 Load(0.0) ->  116 Load(0.0) ->  120 Load(0.0) ->  124 Load(0.0) ->  70 Load(0.0) ->  75 Load(0.0) ->  118 Load(0.0) ->  128 Load(0.0) ->  77 Load(1.0) ->  126 Load(1.0) ->  131 Load(2.0) ->  121 Load(3.0) ->  0 Load(3.0)
Distance of the route: 521m
Load of the route: 3.0

Route for worker 5:
 0 Load(0) ->  95 Load(0.0) ->  99 Load(0.0) ->  96 Load(0.0) ->  92 Load(0.0) ->  98 Load(0.0) ->  88 Load(0.0) ->  97 Load(0.0) ->  107 Load(0.0) ->  94 Load(0.0) ->  55 Load(0.0) ->  106 Load(0.0) ->  83 Load(0.0) ->  102 Load(0.0) ->  93 Load(0.0) ->  81 Load(0.0) ->  87 Load(0.0) ->  79 Load(0.0) ->  80 Load(0.0) ->  90 Load(0.0) ->  58 Load(0.0) ->  57 Load(0.0) ->  86 Load(0.0) ->  154 Load(0.0) ->  101 Load(0.0) ->  85 Load(0.0) ->  84 Load(0.0) ->  105 Load(0.0) ->  91 Load(0.0) ->  153 Load(0.0) ->  155 Load(0.0) ->  56 Load(0.0) ->  100 Load(0.0) ->  104 Load(0.0) ->  82 Load(0.0) ->  54 Load(0.0) ->  151 Load(0.0) ->  59 Load(1.0) ->  89 Load(1.0) ->  103 Load(1.0) ->  152 Load(1.0) ->  108 Load(2.0) ->  156 Load(3.0) ->  0 Load(3.0)
Distance of the route: 721m
Load of the route: 3.0

Route for worker 6:
 0 Load(0) ->  41 Load(0.0) ->  114 Load(1.0) ->  39 Load(1.0) ->  40 Load(1.0) ->  43 Load(1.0) ->  38 Load(1.0) ->  42 Load(1.0) ->  44 Load(2.0) ->  185 Load(2.0) ->  186 Load(3.0) ->  0 Load(3.0)
Distance of the route: 369m
Load of the route: 3.0

Route for worker 7:
 0 Load(0) ->  78 Load(1.0) ->  60 Load(1.0) ->  61 Load(2.0) ->  187 Load(2.0) ->  188 Load(3.0) ->  0 Load(3.0)
Distance of the route: 231m
Load of the route: 3.0

Route for worker 8:
 0 Load(0) ->  174 Load(1.0) ->  36 Load(1.0) ->  37 Load(2.0) ->  17 Load(2.0) ->  18 Load(3.0) ->  0 Load(3.0)
Distance of the route: 198m
Load of the route: 3.0

Route for worker 9:
 0 Load(0) ->  192 Load(1.0) ->  53 Load(2.0) ->  45 Load(3.0) ->  0 Load(3.0)
Distance of the route: 172m
Load of the route: 3.0

Total distance of all routes: 4329m
Total load of all routes: 30.0

内容的提问来源于stack exchange，提问作者Thomas