NetworkX卡车路径优化数据预处理问题求助

问题背景 #

初始子路径数据如下：

Vehicle       Route  
0       V0   [0,3](V0) 
1       V0   [3,0](V0)  
2       V1   [0,3](V1) 
3       V1   [0,8](V1) 
4       V1   [2,0](V1) 
5       V1   [3,2](V1) 
6       V1   [8,0](V1) 

需求是：

• 为每辆卡车拼接出所有以0开头、0结尾的完整闭环路径
• 子路径必须首尾衔接（前一个子路径的终点是下一个子路径的起点）

预期最终结果：

{'V0': [0,3,0], 'V1': [[0,3,2,0], [0,8,0]]}

原代码存在的问题：

• 未正确校验当前路径的最后节点与下一个子路径起点的匹配关系，导致错误拼接
• 处理子路径时重复添加节点（例如将3,0的3重复加入路径）
• 未区分独立的闭环路径，强行将所有子路径拼接成单一路径，不符合需求

解决方案代码 #

tours = {'V0': ['0,3', '3,0'], 'V1': ['0,3', '0,8', '2,0', '3,2', '8,0']}

def convert_to_pair(s):
    # 将字符串子路径转换为(起点, 终点)元组
    return tuple(map(int, s.split(',')))

def process_vehicle_routes(subpaths):
    path_pairs = [convert_to_pair(p) for p in subpaths]
    used_indices = set()  # 跟踪已使用的子路径索引，避免重复使用
    complete_routes = []
    
    # 遍历所有子路径，寻找新路径的起点（以0开头且未被使用）
    for idx, (start, end) in enumerate(path_pairs):
        if idx in used_indices or start != 0:
            continue
        
        # 初始化当前路径
        current_route = [start, end]
        used_indices.add(idx)
        last_node = end
        
        # 循环寻找衔接的子路径，直到回到0节点
        while last_node != 0:
            found_next = False
            for next_idx, (next_start, next_end) in enumerate(path_pairs):
                if next_idx not in used_indices and next_start == last_node:
                    current_route.append(next_end)
                    used_indices.add(next_idx)
                    last_node = next_end
                    found_next = True
                    break
            if not found_next:
                # 若输入数据合法，此处不会触发；可根据需求添加异常处理
                break
        
        # 仅保留以0结尾的完整闭环路径
        if current_route[-1] == 0:
            complete_routes.append(current_route)
    
    # 适配预期格式：单路径返回列表，多路径返回列表的列表
    return complete_routes if len(complete_routes) > 1 else complete_routes[0] if complete_routes else []

# 生成最终结果
final_tours = {vehicle: process_vehicle_routes(paths) for vehicle, paths in tours.items()}
print(final_tours)

代码说明 #

1. 子路径转换：convert_to_pair函数将字符串格式的子路径转为元组，方便快速获取起点和终点
2. 已使用跟踪：used_indices集合记录已被加入路径的子路径索引，确保每个子路径只属于一条完整路径
3. 路径拼接逻辑：
   • 外层循环筛选所有以0开头的未使用子路径，作为新路径的起点
   • 内层循环持续寻找与当前路径最后节点匹配的未使用子路径，直到路径回到0节点
4. 格式适配：根据生成的完整路径数量，返回对应格式（单路径直接返回列表，多路径返回列表的列表）

运行代码后将得到预期结果：

{'V0': [0, 3, 0], 'V1': [[0, 3, 2, 0], [0, 8, 0]]}

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