本文介绍如何利用 python 的 itertools.permutations 高效求解“每条路径分配唯一车辆”的最小成本分配问题，通过数据结构预处理、笛卡尔式枚举与成本聚合，避免暴力遍历所有元组组合。
本文介绍如何利用 python 的 itertools.permutations 高效求解“每条路径分配唯一车辆”的最小成本分配问题，通过数据结构预处理、笛卡尔式枚举与成本聚合，避免暴力遍历所有元组组合。
在物流调度、任务分配等场景中，常需将有限资源（如车辆）一对一地分配给多个任务（如运输路线），且每个资源仅能使用一次。给定形如 (route, vehicle, cost) 的三元组列表，目标是为每条 route 分配一个互不重复的 vehicle，使总成本最小——这本质上是一个受限排列优化问题，而非简单组合。
直接对原始列表调用 permutations(route_cost, n_routes) 会产生大量无效项（例如同一车辆被多次分配、或不同 route 对应相同 vehicle 但未显式校验），效率低且逻辑冗余。更优策略是：先提取唯一 route 和 vehicle 集合，再生成 vehicle 的全排列（长度等于 route 数量），最后按 route 顺序与排列一一配对查表求和。
以下为完整实现：
from itertools import permutations
# 示例输入：(route, vehicle, cost)
route_cost = [(1, 1, 3), (1, 2, 5), (1, 3, 7),
(2, 1, 5), (2, 2, 8), (2, 3, 10)]
# 步骤1：结构化预处理 —— 构建 route/vehicle 集合 + 成本查找字典
routes, vehicles, costs = set(), set(), {}
for r, v, c in route_cost:
routes.add(r)
vehicles.add(v)
costs[(r, v)] = c # 支持 O(1) 查询：costs[(route, vehicle)]
routes, vehicles = sorted(routes), sorted(vehicles) # 排序确保确定性
# 步骤2：生成所有合法分配方案（vehicle 的 len(routes)-长排列）
# 每个 vp 是一个 vehicle 元组，如 (2, 1) 表示 route[0]→vehicle2, route[1]→vehicle1
allocations = (
(vp, sum(costs[(r, v)] for r, v in zip(routes, vp)))
for vp in permutations(vehicles, len(routes))
)
# 步骤3：选取总成本最小的方案
best = min(allocations, key=lambda x: x[1])
# 步骤4：格式化输出
print(f'The cheapest allocation, with a total cost of {best[1]}, is:')
for route, vehicle in zip(routes, best[0]):
print(f'\tRoute {route}: vehicle {vehicle} (cost = {costs[(route, vehicle)]})')✅ 关键设计说明：
- 使用 costs[(r, v)] 字典替代嵌套循环查找，将单次分配成本计算降至 O(1)；
- permutations(vehicles, len(routes)) 天然保证车辆不重复，无需额外去重或校验；
- zip(routes, vp) 实现 route 与 vehicle 的有序绑定，隐含“固定 route 顺序”的业务约束；
- 时间复杂度为 O(V^R)，其中 V 是车辆数、R 是路线数——适用于 R ≤ 10 的中小规模问题（如 5 路线 × 8 车辆 ≈ 6720 种排列）。
⚠️ 注意事项：
- 若 len(vehicles)
- 当 R 较大（如 > 12）时，应考虑匈牙利算法（scipy.optimize.linear_sum_assignment）等更高效方法；
- 若存在缺失 (route, vehicle) 组合（即某些分配不可行），需在 costs.get((r, v), float('inf')) 中设默认极大值，避免 KeyError。
该方案简洁、可读性强，精准契合“固定 route、枚举 vehicle 排列、求最小加权匹配”的核心需求，是 itertools.permutations 在运筹优化中的典型工程化应用。
