满足取派件先后约束的路径生成算法及Python相关工具咨询

你遇到的是带前置依赖的排列生成问题，n组取派对的场景下，合规路径的总数为$\frac{(2n)!}{2^{n}$：2人场景下计算得$\frac{4!}{2}2}=6$，和你手动枚举的结果一致；3人场景下总数为$\frac{6!}{2^3}=90$，手动枚举效率极低，下面是可直接落地的算法方案和Python实现。

核心实现思路 #

1. 回溯法（推荐，性能最优） #

每次选择下一个点位时，仅允许选两类符合要求的点位：

• 还未被选中的取货点p
• 对应取货点已被选中、且自身未被选中的派送点d
  递归遍历所有合法选择，直到所有点位都被选中，即可得到全量合规路径。

2. 全排列过滤法（适合n≤5的小体量场景） #

先生成所有点位的全排列，再过滤掉不符合「d_i必须在对应p_i之后」约束的排列即可，逻辑简单易写，缺点是n变大后无效计算量会急剧上升。

Python代码示例 #

回溯法实现 #

def generate_valid_routes(passenger_count: int) -> list:
    current_route = []
    picked = [False] * passenger_count
    delivered = [False] * passenger_count
    valid_routes = []

    def backtrack():
        # 所有点位都已选完，保存当前路径
        if len(current_route) == 2 * passenger_count:
            valid_routes.append(current_route.copy())
            return
        # 优先尝试选择未取的取货点
        for i in range(passenger_count):
            if not picked[i]:
                picked[i] = True
                current_route.append(f'p{i+1}')
                backtrack()
                current_route.pop()
                picked[i] = False
        # 再尝试选择对应取货已完成、未派送的送货点
        for i in range(passenger_count):
            if picked[i] and not delivered[i]:
                delivered[i] = True
                current_route.append(f'd{i+1}')
                backtrack()
                current_route.pop()
                delivered[i] = False
    
    backtrack()
    return valid_routes

# 3名乘客场景调用
routes_3p = generate_valid_routes(3)
print(f"3人场景合规路径总数：{len(routes_3p)}")
# 输出前5条路径示例
print(routes_3p[:5])

全排列过滤法实现 #

from itertools import permutations

def generate_valid_routes_by_perm(passenger_count: int) -> list:
    all_points = [f'p{i+1}' for i in range(passenger_count)] + [f'd{i+1}' for i in range(passenger_count)]
    valid_routes = []
    for route in permutations(all_points):
        # 校验所有派送点是否在对应取货点之后
        legal = True
        for i in range(passenger_count):
            p_idx = route.index(f'p{i+1}')
            d_idx = route.index(f'd{i+1}')
            if d_idx < p_idx:
                legal = False
                break
        if legal:
            valid_routes.append(route)
    return valid_routes

相关工具推荐 #

• itertools：Python标准库自带，上述全排列方案就是使用该库的permutations方法，无需额外安装，适合小规模枚举需求。
• networkx：如果后续需要拓展最短路径筛选、路网关联等功能，可以使用这个图计算库，原生支持带约束的路径枚举。
• ortools：谷歌开源的运筹优化工具包，如果除了枚举还要做路径优选（比如总里程最短、耗时最少），该库的路径规划模块可以直接处理取派约束，无需手动全量枚举。

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