Python ALNS启发式VRP实现中s_star内存共享赋值问题求助

核心问题原因：浅拷贝导致的引用共享 #

你的代码中所有对象复制都使用了copy.copy()，但VRP的解结构通常是嵌套可变类型（比如存储车辆路径的列表的列表，格式类似[[0,1,3,0], [0,2,4,0]]）：

• copy.copy()是浅拷贝，只会复制外层容器，内部的子列表仍然是原对象的引用；
• 当你修改s_new（执行移除/插入客户操作）时，实际是在修改与s、s_star共享的内部子列表，这会直接同步改变s_star的内容——哪怕你还没执行s_star = s_new.copy()的更新逻辑；
• 这就是为什么你会看到「尚未更新s_star时，s_star与s_new值相同」的现象，最终导致s_star被后续的解持续覆盖，无法保留真正的最优解。

修复方案：改用深拷贝断开引用 #

将所有copy.copy()替换为copy.deepcopy()，确保复制整个嵌套结构，彻底断开所有对象间的引用关联：

修改后的关键代码片段 #

import copy

def run_heuristic(num_customers, num_vehicles, num_iterations, distance_matrix):
    num_of_solutions = 0
    start = time.time()

    s = construct_initial_solution(num_customers, num_vehicles)
    prev_obj_cost = evaluate_solution(s, distance_matrix)
    print("Initial solution", s)
    print("Objective value: ", prev_obj_cost)
    print(" ")
    # 初始最优解用深拷贝
    s_star = copy.deepcopy(s)
    s_star_obj = evaluate_solution(s, distance_matrix)

    for segment in range(1, 4):
        operator_scores = {op: 0 for op in insertion_operators + removal_operators}
        operator_attempts = {op: 0 for op in insertion_operators + removal_operators}

        iteration = 1

        while iteration <= num_iterations:
            customers_to_remove = random.randint(2, 5)
            insert, removal = choose_operator()
            # 新解用深拷贝创建，与当前解彻底独立
            s_new = copy.deepcopy(s)

            s_new, removed = removal(s_new, customers_to_remove)
            s_new = do_insertion(insert, s_new, removed)

            if check_feasibility(s_new):
                print("Feasible Solution after insertion: ", s_new)
                obj_cost = evaluate_solution(s_new, distance_matrix)
                print("Objective value: ", obj_cost)
                print("s_star: ", s_star, s_star_obj)
                print(" ")

                solution_key = (insert, removal, obj_cost)
                is_accepted_solution = solution_key not in explored_solutions[(insert, removal)]

                if is_accepted_solution:
                    explored_solutions[(insert, removal)].add(solution_key)

                    if obj_cost < s_star_obj:
                        # 更新最优解时用深拷贝
                        s_star = copy.deepcopy(s_new)
                        s_star_obj = evaluate_solution(s_new, distance_matrix)
                        operator_scores[removal] += 33
                        operator_scores[insert] += 33
                    elif obj_cost > prev_obj_cost:
                        # 更新当前解时用深拷贝
                        s = copy.deepcopy(s_new)
                        operator_scores[removal] += 9
                        operator_scores[insert] += 9
                    elif obj_cost <= prev_obj_cost:
                        # 更新当前解时用深拷贝
                        s = copy.deepcopy(s_new)
                        operator_scores[removal] += 13
                        operator_scores[insert] += 13

                    operator_attempts[insert] += 1
                    operator_attempts[removal] += 1

                # 数值类型直接赋值即可，无需拷贝
                prev_obj_cost = obj_cost

                iteration += 1

            num_of_solutions += 1

    # 后续输出代码保持不变
    end = time.time()
    print("*********************************************************************************")
    print("Final solution: ", s_star)
    print("Objective value: ", s_star_obj)
    print("Computation time: ", end - start)
    print("Number of solution explored: ", num_of_solutions)
    print("*********************************************************************************")
    return None 

额外检查点 #

1. 确认removal和do_insertion函数是否为原地修改传入的列表：如果这些函数直接修改输入对象而非返回新对象，浅拷贝的问题会被放大，深拷贝可以彻底解决此类问题；
2. explored_solutions的逻辑不会导致s_star被覆盖，但如果存在误判「已探索解」的情况，可能会错过最优解的更新，可后续验证该字典的存储逻辑。

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