engine.ca
压缩退火求解器（Compressed Annealing），基于模拟退火框架的 TSPTW 求解。
Attributes
Classes
压缩退火求解器（Compressed Annealing）。 |
Functions
|
Numba JIT 编译的适应度计算内核（与 VNS 共享相同逻辑）。 |
Module Contents
- engine.ca.CA_DEFAULT_PARAMS
- engine.ca._cal_fitness_numba(line, cost_mat, travel_speed, penalty_weight, early_wait_weight, late_return_weight, depot_index, spots_start, spots_end, spots_stay, use_real_time_matrix=False)
Numba JIT 编译的适应度计算内核（与 VNS 共享相同逻辑）。
沿路径逐段模拟行程，累计总成本与时间惩罚。 路径必须从 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.ca.CASolver(city_indices: list[int], spots_dict: dict, 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)
压缩退火求解器（Compressed Annealing）。
基于模拟退火框架，引入压缩系数动态调节距离成本与时间惩罚之间的权重比例。 搜索初期偏向探索可行域之外的区域，后期逐渐收紧至可行解。
增强特性： - 时间窗引导邻域：针对违规最严重的节点执行重定位扰动（加速不可行解修复） - 压缩系数动态增长：初期惩罚权重小（允许探索不可行区域），后期逐渐增大至与原始成本一致 - 2-opt 精细化：主循环结束后对最优解执行 First Improvement 2-opt 局部搜索
- 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
- _cal_fitness(line: list[int], cost_mat: numpy.ndarray)
直接调用 Numba 内核评估路径成本
CA 单次运行中几乎不会重复评估同一解，故不设缓存。
- Args:
line: 路径列表（含起终点的完整路径）。 cost_mat: 距离/旅行时间矩阵。
- Returns:
Tuple[float, float, float]: (总成本, 旅行累积值, 时间惩罚).
- _initial_solution() list[int]
按时间窗起始时间排序生成初始解（启发式效果优于随机）
- Returns:
list[int]: 闭合路径 [depot, ...景点..., depot]。
- _standard_neighbor(solution: list[int], temp_ratio: float)
标准邻域生成器。
根据当前退火温度比例选择不同类型的变异： - 高温段（temp_ratio > 0.7）：大范围反转 - 中温段（temp_ratio > 0.3）：交换两点 - 低温段：插入操作（精细化微调）
- _time_window_guided_neighbor(solution: list[int], cost_mat: numpy.ndarray, temp_ratio: float)
时间窗引导邻域生成。
识别违反时间窗最严重的节点，将其重定位到路径中另一随机位置。 适用于搜索早期快速修正不可行解。
- _get_neighbor(solution: list[int], iteration: int, max_iter: int, cost_mat: numpy.ndarray)
混合邻域选择：50% 概率使用时间窗引导，50% 使用标准邻域
- Args:
solution: 当前解路径。 iteration: 当前迭代次数。 max_iter: 总迭代次数。 cost_mat: 距离矩阵。
- Returns:
List[int]: 新邻居解路径。
- _local_search_2opt(solution: list[int], cost_mat: numpy.ndarray, max_iter: int = 20)
2-opt 局部搜索（First Improvement）。
使用 First Improvement 而非 Best Improvement 策略： 找到首个改善即接受，牺牲单步最优性换取更快的整体收敛速度。
- solve(cost_mat: numpy.ndarray)
执行压缩退火主循环。
- Args:
cost_mat: 距离矩阵。
- Returns:
- dict: 包含以下键：
best_solution (List[int]): 最优路径（含起终点）。
best_cost (float): 最优总成本（旅行累积值 + 时间惩罚，单位由输入矩阵决定）。
best_distance (float): 旅行累积值。标准模式 = 总距离；真实模式 = 总旅行时间。
best_penalty (float): 最优路径总时间惩罚。
convergence_history (List[float]): 收敛曲线，每轮迭代后的最优成本。