engine.vns ========== .. py:module:: engine.vns .. autoapi-nested-parse:: 变邻域搜索求解器（VNS），集成多种邻域算子和自适应权重机制。 Attributes ---------- .. autoapisummary:: engine.vns.VNS_DEFAULT_PARAMS engine.vns.EARLY_EXPLORE_RATIO engine.vns.VIOLATOR_TARGET_PROB engine.vns.DYNAMIC_STRENGTHEN_AFTER engine.vns.WEIGHT_REWARD_FACTOR Classes ------- .. autoapisummary:: engine.vns.VNSSolver Functions --------- .. autoapisummary:: engine.vns._cal_fitness_numba Module Contents --------------- .. py:data:: VNS_DEFAULT_PARAMS .. py:data:: EARLY_EXPLORE_RATIO :value: 0.3 .. py:data:: VIOLATOR_TARGET_PROB :value: 0.6 .. py:data:: DYNAMIC_STRENGTHEN_AFTER :value: 10 .. py:data:: WEIGHT_REWARD_FACTOR :value: 1.02 .. py:function:: _cal_fitness_numba(line: numpy.ndarray, cost_mat: numpy.ndarray, travel_speed: float, penalty_weight: float, early_wait_weight: float, late_return_weight: float, depot_index: int, spots_start: numpy.ndarray, spots_end: numpy.ndarray, spots_stay: numpy.ndarray, use_real_time_matrix: bool = False) -> Tuple[float, float, float] Numba JIT 编译的适应度计算内核。 沿路径逐段模拟行程，累计总成本与时间惩罚。 路径必须从 depot 出发并回到 depot，长度不足 3 时返回极大惩罚值。 两种矩阵模式： - use_real_time_matrix=False（默认，标准数据集）：矩阵元素为距离，travel_time = d / travel_speed - use_real_time_matrix=True（高德真实数据）：矩阵元素为旅行时间（小时），travel_time = d Args: line: 路径数组（含起终点的完整路径）。 cost_mat: 距离/旅行时间矩阵。 travel_speed: 旅行速度（距离/时间单位）。use_real_time_matrix=True 时该参数无效。 penalty_weight: 迟到惩罚权重。 early_wait_weight: 早到等待惩罚权重。 late_return_weight: 晚归惩罚权重。 depot_index: 起终点索引。 spots_start: 各景点时间窗开始时间数组。 spots_end: 各景点时间窗结束时间数组。 spots_stay: 各景点停留时长数组。 use_real_time_matrix: 矩阵是否为旅行时间（避免 d / travel_speed 重复计算）。 Returns: Tuple[float, float, float]: (总成本, 旅行累积值, 时间惩罚). 旅行累积值：标准模式下为总距离，真实模式下为总旅行时间。 .. py:class:: VNSSolver(city_indices: list[int], spots_dict: dict[int, backend.typedefs.SpotDict], travel_speed: float = 1.0, penalty_weight: float = 100.0, early_wait_weight: float = 0.1, late_return_weight: float = 50.0, depot_index: int = 0, use_real_time_matrix: bool = False, **kwargs) 变邻域搜索求解器（Variable Neighborhood Search）。 集成多种邻域结构（swap/inversion/insert/2opt）与 VND 局部搜索， 通过 SA 准则控制扰动接受，并维护精英池保留历史最优解。 增强特性： - SA 混合接受准则：改善解直接接受，劣化解按概率接受（避免陷入局部最优） - 压缩退火：penalty 权重从 0.1 线性增长至 1.0（早期允许探索不可行区域，后期收敛到可行解） - 早期定向约束扰动：迭代前期针对违规时间窗的节点执行针对性扰动（加速可行解发现） - 自适应算子权重：根据历史成功率动态调节各邻域算子的被选中概率（加速收敛） - 精英池后优化：主循环结束后对精英池中的多组候选解执行 VND，提升最终解稳定性 .. py:attribute:: city_indices .. py:attribute:: num_cities .. py:attribute:: spots_dict .. py:attribute:: travel_speed :value: 1.0 .. py:attribute:: penalty_weight :value: 100.0 .. py:attribute:: early_wait_weight :value: 0.1 .. py:attribute:: late_return_weight :value: 50.0 .. py:attribute:: depot_index :value: 0 .. py:attribute:: use_real_time_matrix :value: False .. py:attribute:: params .. py:attribute:: spots_start .. py:attribute:: spots_end .. py:attribute:: spots_stay .. py:attribute:: fitness_cache .. py:attribute:: elite_pool :value: [] .. py:attribute:: operator_weights .. py:attribute:: last_operator :type: str | None :value: None .. py:method:: _cal_fitness(line: list[int], cost_mat: numpy.ndarray) -> Tuple[float, float, float] 带缓存的适应度计算，避免重复触发 Numba 调用的开销 Args: line: 路径列表（含起终点的完整路径）。 cost_mat: 距离/旅行时间矩阵。 Returns: Tuple[float, float, float]: (总成本, 旅行累积值, 时间惩罚). .. py:method:: _init_nearest_neighbor(cost_mat: numpy.ndarray) -> list[int] 最近邻贪心初始解：从未访问节点中选成本最小的加入路径。 .. py:method:: _init_time_window() -> list[int] 按时间窗起始排序生成初始解（启发式，起终点闭合路径）。 .. py:method:: _init_random() -> list[int] 随机排列初始解：提供种群多样性，防止陷入局部最优。 .. py:method:: _swap(route: list[int]) -> list[int] Swap 算子：随机交换两个内部节点，改变路径结构。 Args: route: 当前路径。 Returns: List[int]: 扰动后的路径。 .. py:method:: _inversion(route: list[int]) -> list[int] Inversion 算子：反转内部一段子序列，改变路径拓扑。 Args: route: 当前路径。 Returns: List[int]: 扰动后的路径。 .. py:method:: _insert(route: list[int]) -> list[int] Insert 算子：随机删除一个节点并插入到另一位置，改变路径结构。 Args: route: 当前路径。 Returns: List[int]: 扰动后的路径。 .. py:method:: _2opt(route: list[int]) -> list[int] 2-opt 算子：反转内部两个切割点之间的子序列，消除路径交叉。 Args: route: 当前路径。 Returns: List[int]: 扰动后的路径。 .. py:method:: _shaking(solution, k, cost_mat, iter_ratio=0.5) 执行 k 步抖动。 搜索早期优先对违反时间窗的节点做针对性扰动， 后期退化到随机算子 + 自适应权重。 Args: solution: 当前解路径。 k: 抖动步数。 cost_mat: 距离矩阵。 iter_ratio: 当前迭代进度比例（0~1）。 Returns: Tuple[List[int], str | None]: (抖动后的解, 最后使用的算子名称). .. py:method:: _perturb_around(route, target, op) 针对特定节点进行扰动（对其附近片段操作） Args: route: 当前路径。 target: 目标节点索引。 op (str): 使用的扰动算子，可选 'swap'/'inversion'/'insert'。 Returns: List[int]: 扰动后的路径。 .. py:method:: _local_search(solution, cost_mat, move_type) 指定邻域类型的第一改善型局部搜索。 遍历所有合法操作对，找到第一个改善即返回（First Improvement）。 Args: solution: 当前解路径。 cost_mat: 距离矩阵。 move_type (str): 邻域类型，可选 'swap'/'inversion'/'insert'/'2opt'。 Returns: List[int]: 局部搜索后的路径。 .. py:method:: _vnd(solution, cost_mat) 变邻域下降（Variable Neighborhood Descent）。 依次尝试 swap → inversion → insert → 2opt， 任一邻域改善则回到第一个邻域重新搜索。 Args: solution: 当前解路径。 cost_mat: 距离矩阵。 Returns: List[int]: VND 优化后的路径。 .. py:method:: _update_elite(solution, cost) 将解加入精英池，超出容量时替换最差者。 Args: solution: 当前解路径。 cost: 当前解成本。 .. py:method:: get_elite_pool() 返回精英池（(解, 成本) 列表） .. py:method:: solve(cost_mat, initial_solution=None) 执行 VNS 主循环。 Args: cost_mat: 距离矩阵。 initial_solution: 可选的初始解，None 则自动择优选取。 Returns: dict: 包含以下键： - best_solution (List[int]): 最优路径（含起终点）。 - best_cost (float): 最优总成本（旅行累积值 + 时间惩罚，单位由输入矩阵决定）。 - best_distance (float): 旅行累积值。标准模式 = 总距离；真实模式 = 总旅行时间。 - best_penalty (float): 最优路径总时间惩罚。 - convergence_history (List[float]): 收敛曲线，每轮迭代后的最优成本。