本文介绍如何利用 itertools.permutations 为多条路线分配互斥车辆，确保每条路线分配唯一车辆，并以最小总成本为目标求解最优分配方案。
本文介绍如何利用 `itertools.permutations` 为多条路线分配互斥车辆，确保每条路线分配唯一车辆，并以最小总成本为目标求解最优分配方案。
在物流调度、任务分配等场景中，常需将有限资源（如车辆）一对一地分配给多个任务（如运输路线），且每个资源只能使用一次。给定形如 (route, vehicle, cost) 的三元组列表，目标是：为每条路线精确分配一辆不重复的车辆，使总成本最小。
核心挑战在于：不能简单对原始三元组列表做全排列（如 permutations(route_cost, 2)），因为那会混杂不同路线与车辆的无效组合；而应固定路线集合，对车辆集合做排列，再按路线顺序一一匹配，从而天然满足“一车一路、不复用”的约束。
以下是一个结构清晰、可直接运行的解决方案：
from itertools import permutations
# 示例数据：(路线ID, 车辆ID, 对应成本)
route_cost = [(1, 1, 3), (1, 2, 5), (1, 3, 7),
(2, 1, 5), (2, 2, 8), (2, 3, 10)]
# 步骤1：提取唯一路线和车辆，并构建快速查表（字典）
routes, vehicles, costs = set(), set(), {}
for r, v, c in route_cost:
routes.add(r)
vehicles.add(v)
costs[(r, v)] = c # 键为(route, vehicle)，值为cost
routes, vehicles = sorted(routes), sorted(vehicles) # 转为有序列表，保证确定性
# 步骤2：生成所有车辆到路线的满射排列（即len(routes)长度的车辆排列）
# 每个排列vp代表一种分配方案：vp[i]分配给routes[i]
allocations = (
(vp, sum(costs[(r, v)] for r, v in zip(routes, vp)))
for vp in permutations(vehicles, len(routes))
)
# 步骤3：选取总成本最小的方案
best_perm, min_total = min(allocations, key=lambda x: x[1])
# 步骤4：格式化输出结果
print(f'The cheapest allocation, with a total cost of {min_total}, is:')
for route, vehicle in zip(routes, best_perm):
print(f'\tRoute {route}: vehicle {vehicle} (cost = {costs[(route, vehicle)]})')运行结果：
The cheapest allocation, with a total cost of 10, is:
Route 1: vehicle 2 (cost = 5)
Route 2: vehicle 1 (cost = 5)✅ 关键设计说明：
- 使用 permutations(vehicles, len(routes)) 直接枚举车辆分配顺序，而非原始数据排列，从根本上避免了路线错配与车辆复用；
- zip(routes, vp) 自动完成“第 i 条路线 → 第 i 个排列元素（车辆）”的映射，逻辑简洁且无歧义；
- 成本查表 costs[(r, v)] 时间复杂度 O(1)，显著优于嵌套循环查找。
⚠️ 注意事项：
- 该方法时间复杂度为 O(V^R)（V 为车辆数，R 为路线数），当 R ≥ 10 且 V 较大时可能变慢；若规模扩大，建议切换至 scipy.optimize.linear_sum_assignment（匈牙利算法，O(V³)）或 ortools 等专用优化库；
- 输入数据必须覆盖所有 (route, vehicle) 组合的有效成本，缺失键将导致 KeyError —— 可预先用 defaultdict(lambda: float('inf')) 或校验逻辑增强鲁棒性；
- 若存在多条相同最小成本方案，min() 默认返回首个，如需全部解，可改用列表推导式 + 过滤。
该方案兼顾可读性、正确性与工程实用性，是小规模分配问题的优雅起点。
