基于粒子群优化的车辆路径规划（VRP）性能优化问询

我是计算机科学专业学生，目前基于The Jin Ai与Voratas Kachitvichyanuku的论文，实现带装卸点的车辆路径规划（VRP）的粒子群优化（PSO）算法。我的实现思路：

• 修改了解表示，将每个客户拆分为pickup（.1）和drop-off（.2）点
• 通过客户与仓库的距离生成客户优先级矩阵，结合车辆与客户的距离生成车辆优先级矩阵
• 构建路径时尝试所有客户分配组合及插入位置，选择成本最小的路径

但现在遇到性能瓶颈：随着客户与车辆数量增加，单粒子计算时间呈指数增长，全种群多迭代下问题更突出。附上核心实现代码，求性能优化的替代方案或改进思路。

def construct_routes_v2(customer_priority, vehicle_priority, vehicle_ref_points, capacity, customer_depart_loc_input, customer_arrive_loc_input):
    # Loop for each population
    for index, customer in enumerate(customer_priority):
        # Vehicle order is retrieving the vehicle priority matrix of the index (From population)
        vehicle_order = vehicle_priority[index]
        # vehicle_order[0] to get the number of vehicles
        pending_compute = list([] for _ in range(len(vehicle_order[0])))
        # format from customer priority: 1 -> 1.1, 1.2
        reformat_customer_priority = []
        for customer_id in customer:
            reformat_customer_priority.append(f'{customer_id}.1')
            reformat_customer_priority.append(f'{customer_id}.2')     
        # Tracking control for each customer to be used in assigning .2 to the vehicle
        customer_vehicle_tracker = []
        for i in reformat_customer_priority:
            if i.endswith('.1'):
                customer_index = int(i.split('.')[0])
                vehicle_customer = vehicle_order[customer_index - 1]
                min_index = None
                min_cost = float('inf')
                min_vehicle_pref = None
                # Loop for each vehicle
                for vehicle_pref in vehicle_customer:
                    if len(pending_compute[vehicle_pref]) == 0:
                        pending_compute[vehicle_pref].append(i)
                        cost = compute_cost_v2(pending_compute[vehicle_pref], customer_depart_loc_input, customer_arrive_loc_input, vehicle_ref_points, vehicle_pref)
                        if cost < min_cost:
                            min_cost = cost
                            min_vehicle_pref = vehicle_pref
                            min_index = pending_compute[vehicle_pref]     
                        # Remove the case (element) that is not min cost
                        for j in range(len(pending_compute)):
                            if j != min_vehicle_pref:
                                if i in pending_compute[j]:
                                    pending_compute[j].remove(i)    
                    else:
                        for j in range(len(pending_compute[vehicle_pref]) + 1):
                            temp_route = pending_compute[vehicle_pref].copy()
                            temp_route.insert(j, i)
                            cost = compute_cost_v2(temp_route, customer_depart_loc_input, customer_arrive_loc_input, vehicle_ref_points, vehicle_pref)
                            if cost < min_cost:
                                min_cost = cost
                                min_vehicle_pref = vehicle_pref
                                min_index = temp_route
                pending_compute[min_vehicle_pref] = min_index
                customer_vehicle_tracker.append([customer_index, min_vehicle_pref])
            else:
                customer_index = int(i.split('.')[0])
                # Customer Vehicle Tracker: [[2, 2]]
                if customer_index == customer_vehicle_tracker[-1][0]:
                    customer_vehicle_pref = customer_vehicle_tracker[-1][1]
                # Visit the route that containing the customer only
                vehicle_customer_route = pending_compute[customer_vehicle_pref]
                # Find the position of the corresponding pickup (.1)
                pickup_position = None
                for j, customer_in_route in enumerate(vehicle_customer_route):
                    if customer_in_route == f'{customer_index}.1':
                        pickup_position = j
                        break
                min_index = None
                min_cost = float('inf')
                min_vehicle_pref = None
                if pickup_position is not None:
                    for j in range(pickup_position + 1, len(vehicle_customer_route) + 1):
                        temp_route = vehicle_customer_route.copy()
                        temp_route.insert(j, i)
                        cost = compute_cost_v2(temp_route, customer_depart_loc_input, customer_arrive_loc_input, vehicle_ref_points, customer_vehicle_pref)
                        if cost < min_cost:
                            min_cost = cost
                            min_vehicle_pref = customer_vehicle_pref
                            min_index = temp_route
                pending_compute[min_vehicle_pref] = min_index   
        # Validate Candidate (Checking constraints)
        pending_compute = validate_candidate_v2(pending_compute, capacity, customer_depart_loc_input, customer_arrive_loc_input, vehicle_ref_points)
        return pending_compute

说明：compute_cost_v2用于计算点间欧氏距离，validate_candidate_v2用于校验路径容量约束，调整不满足的路径。

1. 减少路径成本计算的冗余操作 #

• 增量计算成本：当前每次插入节点都重新计算整条路径的成本，完全可以用增量方式：假设原有路径成本为C，插入节点i到位置j，只需要计算原路径中j-1到j的距离，替换为j-1到i、i到j的距离，差值加上原成本就是新路径的成本，避免重复计算所有点对距离。
• 预计算距离矩阵：提前把所有点（仓库、pickup、drop-off）之间的欧氏距离计算好存成二维数组，用的时候直接查表，不用每次调用compute_cost_v2时实时计算。

2. 简化路径构建的遍历逻辑 #

• 限制车辆候选范围：当前对所有车辆尝试分配，可基于车辆优先级矩阵只取前N个（比如前3）优先级最高的车辆，不用遍历全部车辆，牺牲极小精度换大幅速度提升。
• 减少插入位置的遍历：对于pickup节点，不用尝试所有插入位置，可采用启发式插入（比如插入到使路径成本增量最小的位置，而非遍历所有位置后再选）；对于drop-off节点，除了必须在pickup之后，可只考虑pickup附近的几个位置（比如pickup后1-3个位置），而非从pickup到路径末尾全遍历。

3. 数据结构与代码层面的优化 #

• 替换字符串标识为整数：当前用'1.1'这种字符串标识节点，拆分、比较都耗时，可把每个节点映射成唯一整数（比如pickup节点用2id-1，drop-off用2id），整数操作比字符串快得多。
• 减少列表拷贝：当前每次插入都copy()整个路径列表，可改用链表结构或者只记录路径的插入位置，最后再生成完整路径，避免频繁的列表拷贝操作。
• 向量化计算：如果使用numpy库，把距离矩阵、路径成本计算改成向量化操作，比Python循环快一个数量级以上。

4. PSO算法层面的优化 #

• 粒子种群规模与迭代次数调优：不需要太大的种群规模（比如20-50个粒子足够），迭代次数根据问题规模动态调整，比如当连续N代最优解无变化时提前终止迭代。
• 引入局部搜索算子：不用每个粒子都从头构建路径，可对当前最优粒子进行局部优化（比如2-opt交换），然后作为新粒子加入种群，减少无效的路径构建操作。

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