engine.vns

变邻域搜索求解器（VNS），集成多种邻域算子和自适应权重机制。

Attributes

VNS_DEFAULT_PARAMS

EARLY_EXPLORE_RATIO

VIOLATOR_TARGET_PROB

DYNAMIC_STRENGTHEN_AFTER

WEIGHT_REWARD_FACTOR

Classes

VNSSolver

变邻域搜索求解器（Variable Neighborhood Search）。

Functions

_cal_fitness_numba(→ Tuple[float, float, float])

Numba JIT 编译的适应度计算内核。

Module Contents

engine.vns.VNS_DEFAULT_PARAMS
engine.vns.EARLY_EXPLORE_RATIO = 0.3
engine.vns.VIOLATOR_TARGET_PROB = 0.6
engine.vns.DYNAMIC_STRENGTHEN_AFTER = 10
engine.vns.WEIGHT_REWARD_FACTOR = 1.02
engine.vns._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]: (总成本, 旅行累积值, 时间惩罚).

旅行累积值：标准模式下为总距离，真实模式下为总旅行时间。

class engine.vns.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，提升最终解稳定性

city_indices
num_cities
spots_dict
travel_speed = 1.0
penalty_weight = 100.0
early_wait_weight = 0.1
late_return_weight = 50.0
depot_index = 0
use_real_time_matrix = False
params
spots_start
spots_end
spots_stay
fitness_cache
elite_pool = []
operator_weights
last_operator: str | None = None
_cal_fitness(line: list[int], cost_mat: numpy.ndarray) → Tuple[float, float, float]

带缓存的适应度计算，避免重复触发 Numba 调用的开销

Args:

line: 路径列表（含起终点的完整路径）。 cost_mat: 距离/旅行时间矩阵。

Returns:

Tuple[float, float, float]: (总成本, 旅行累积值, 时间惩罚).

_init_nearest_neighbor(cost_mat: numpy.ndarray) → list[int]

最近邻贪心初始解：从未访问节点中选成本最小的加入路径。

_init_time_window() → list[int]

按时间窗起始排序生成初始解（启发式，起终点闭合路径）。

_init_random() → list[int]

随机排列初始解：提供种群多样性，防止陷入局部最优。

_swap(route: list[int]) → list[int]

Swap 算子：随机交换两个内部节点，改变路径结构。

Args:

route: 当前路径。

Returns:

List[int]: 扰动后的路径。

_inversion(route: list[int]) → list[int]

Inversion 算子：反转内部一段子序列，改变路径拓扑。

Args:

route: 当前路径。

Returns:

List[int]: 扰动后的路径。

_insert(route: list[int]) → list[int]

Insert 算子：随机删除一个节点并插入到另一位置，改变路径结构。

Args:

route: 当前路径。

Returns:

List[int]: 扰动后的路径。

_2opt(route: list[int]) → list[int]

2-opt 算子：反转内部两个切割点之间的子序列，消除路径交叉。

Args:

route: 当前路径。

Returns:

List[int]: 扰动后的路径。

_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]: (抖动后的解, 最后使用的算子名称).

_perturb_around(route, target, op)

针对特定节点进行扰动（对其附近片段操作）

Args:

route: 当前路径。 target: 目标节点索引。 op (str): 使用的扰动算子，可选 'swap'/'inversion'/'insert'。

Returns:

List[int]: 扰动后的路径。

指定邻域类型的第一改善型局部搜索。

遍历所有合法操作对，找到第一个改善即返回（First Improvement）。

Args:

solution: 当前解路径。 cost_mat: 距离矩阵。 move_type (str): 邻域类型，可选 'swap'/'inversion'/'insert'/'2opt'。

Returns:

List[int]: 局部搜索后的路径。

_vnd(solution, cost_mat)

变邻域下降（Variable Neighborhood Descent）。

依次尝试 swap → inversion → insert → 2opt， 任一邻域改善则回到第一个邻域重新搜索。

Args:

solution: 当前解路径。 cost_mat: 距离矩阵。

Returns:

List[int]: VND 优化后的路径。

_update_elite(solution, cost)

将解加入精英池，超出容量时替换最差者。

Args:

solution: 当前解路径。 cost: 当前解成本。

get_elite_pool()

返回精英池（(解, 成本) 列表）

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]): 收敛曲线，每轮迭代后的最优成本。