使用itertools.permutations()解决无重复车辆-路径低成本分配问题

核心思路 #

不用全排列遍历所有无效组合，而是通过分组+定向遍历减少计算量：

• 先把route_cost按路线分组，将每个路线对应的（车辆，成本）条目单独存放
• 固定第一条路线的某辆车辆，再遍历第二条路线中未被选中的车辆，计算总费用并记录最小值

代码实现 #

假设路线编号为0和1，以下是具体实现：

# 示例数据
route_cost = [
    (0, 0, 10),
    (0, 1, 15),
    (0, 2, 20),
    (1, 0, 25),
    (1, 1, 12),
    (1, 2, 18)
]

# 按路线分组，键为路线号，值为对应(车辆, 成本)的列表
route_groups = {}
for route, vehicle, cost in route_cost:
    route_groups.setdefault(route, []).append((vehicle, cost))

min_total = float('inf')
best_assignment = None

# 遍历第一条路线的所有车辆选项
for veh1, cost1 in route_groups[0]:
    # 遍历第二条路线中与veh1不重复的车辆选项
    for veh2, cost2 in route_groups[1]:
        if veh1 != veh2:
            total_cost = cost1 + cost2
            if total_cost < min_total:
                min_total = total_cost
                best_assignment = ((0, veh1, cost1), (1, veh2, cost2))

print(f"最低总成本: {min_total}")
print(f"最优分配方案: {best_assignment}")

效率优势对比 #

• 原方法itertools.permutations(route_cost, 2)会遍历所有2个条目的排列，其中包含大量同路线的无效组合，做了无用功
• 分组定向遍历直接过滤掉无效情况，只计算跨路线且车辆不重复的有效组合，计算量大幅减少

扩展场景说明 #

如果后续路线数量增加（比如n条路线），可以用itertools.permutations配合过滤条件（车辆不重复、覆盖所有路线），或采用回溯法实现，但当前2条路线的场景用双层循环最直接高效。

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