🌕✨ 值此花好月圆之夜，祝各位读者中秋节快乐！月圆人圆事事圆，科研顺利、心想事成 ！

原文链接见文末

一、研究背景与问题提出

随着城市化推进和道路交通复杂度增加，动态路径推荐成为智能交通系统的核心功能。传统最短路径算法（如Dijkstra、Bellman‑Ford和A*）在静态网络中表现良好，但在实时变化的拥堵环境下存在以下问题：

• 仅考虑物理距离而忽略实时交通条件，导致推荐路线不一定最优。
• 静态启发式策略容易陷入局部最优，无法跳出拥堵区域。
• 在大规模动态网络中计算复杂度高，可扩展性有限。

下图展示了从起点 S 到终点 D 的多条可选路线，尽管路2最短，但由于拥堵严重，路线3（绿色）反而在时间上更优：

1.1 研究目标

为解决以上问题，本文提出Tabu‑A*混合算法，通过引入A*启发式估计与Tabu Search全局搜索能力，实现对动态交通网络的最优路径推荐。具体目标包括：

• 在考虑历史速度与实时道路信息的情况下，生成包含距离与时间两类权重的路网图。
• 引入Tabu Search避免搜索陷入局部最优，并用A*估计函数优化Tabu搜索过程。
• 通过参数敏感性分析和与基准算法的对比，验证算法的效率和适用性。

1.2 主要贡献

文中总结的贡献如下：

• 提出Tabu‑A*：将Tabu搜索与A*结合，用于塞萨洛尼基城市的路径推荐。
• 优化适应度更新规则：利用每轮迭代得到的最优路径更新Tabu搜索的适应度，加速收敛。
• 融入速度与距离数据：建立包含道路长度和时间的时空图，提高算法对交通变化的适应性。
• 实验验证优越性：通过真实数据比较Tabu‑A*与A*、Dijkstra和Bellman‑Ford，在路径长度和旅行时间上均取得显著提升。

二、数据与特征工程

2.1 数据来源与预处理

研究使用了塞萨洛尼基智慧交通实验室公开的两类数据集：

• Distance‑osm‑base‑network：包含路段唯一编号（Link‑ID）、长度、经纬度等静态信息。
• Network‑speed‑historical：记录不同时间戳下路段速度及方向，每天提供15 分钟分辨率的历史速度。

采集数据主要来自出租车浮动车数据（GPS定位每10–12 秒或每100 米记录一次）和主要交叉口的蓝牙探测器，能反映实时交通情况。预处理步骤包括：

• 关联路段编号、时间戳与速度信息，计算每个路段的行驶时间：

• 按照研究时间窗生成新的距离图和时间图，以便构建含距离权重与时间权重的无向加权图。

2.2 路网表示与图构建

数据经过处理后，用无向图表示路网，其中顶点表示交叉口，边表示路段。对于每条边可生成两种权重：

• 距离图：边权为物理长度，用于计算最短距离。
• 时间图：边权为对应时间窗的行驶时间，用于计算最短时间。

下图展示了无向加权图及其邻接矩阵：

三、算法设计与改进

3.1 系统模型

整个系统从数据集到推荐路径的流程如图所示。流程包括数据预处理、生成距离‑速度图、算法实现及路径生成等步骤：

3.2 A*与Tabu搜索概述

Tabu搜索是一种元启发式优化算法，通过保持“禁忌表”记录已探索的劣解，从而避免循环搜索，并在全局范围探索更优解。然而，Tabu搜索缺乏有效的启发式指导，收敛速度较慢。

3.3 混合Tabu‑A*算法

5. 适应度更新：遍历一条路径后，对经过的边更新适应度

其中  为迭代中找到的最佳路径代价， 为更新系数。适应度越高的边将在后续迭代中更有可能被选中。

6. A*启发式引导：对于未探索的节点，A*的估计函数提供代价下界，引导搜索朝向潜在优解。
7. 禁忌表更新：已访问且非改进边加入禁忌表，以避免重复探索。
8. 终止条件：达到最大迭代次数或适应度收敛时，输出最佳路径。

通过在Tabu搜索中动态更新启发式估计与适应度，Tabu‑A*能平衡全局搜索和局部探索，实现快速收敛并避免局部最优。

3.4 参数敏感性分析

作者对关键参数 、 和  进行了方差分析（ANOVA）。结果显示：

•  和  对算法性能影响显著（p < 0.001）， 是影响最大的因素。
•  作为适应度缩放因子，对性能影响不显著，但  与  的交互项显著，表明需要同时调节。
• 敏感性分析验证了算法的鲁棒性：在较宽参数范围内表现稳定，但需避免极端值。

四、实验设计与结果分析

4.1 实验设置

• 场景定义：选择塞萨洛尼基市中心的四个出行场景，每个场景包含起点与终点（见论文Table 1）。
• 评估指标：比较最短路（Shortest Route)与推荐路（Recommended Route）在路径长度与出行时间上的差异；与基准算法（A*、Dijkstra、Bellman‑Ford）比较推荐路线的平均长度和平均时间。
• 时间窗口：将一天划分为多个时段（如00:00–06:45、07:00–09:45等），分析高峰与非高峰的表现。

4.2 可视化分析

图4展示了某个具体路网中最短路径（红线）与推荐路径（绿线）的对比。推荐路径尽管在物理距离上更长，却通过避开拥堵达到更短的旅行时间：

进一步地，作者在四个出行场景上绘制了2D路径图（图5），直观展示每个场景的最短路径和推荐路径：

4.3 推荐路径与最短路比较

• 路径长度分析：图6显示推荐路径和最短路径在不同时间段的平均长度。高峰时段（07:00–09:45、17:00–19:45）推荐路径长度增加，但仍优于最短路径的运行结果：

• 旅行时间分析：图7对比了四个场景在不同时间段的平均旅行时间，推荐路径在各时间段均显著缩短出行时间：

结果表明，虽然推荐路径可能更长，但由于绕过拥堵，其平均旅行时间明显优于最短路径。尤其在高峰期，推荐路径能缩短超过70%的旅行时间。

4.4 与基准算法的比较

• 最短路径长度：图8比较了Tabu‑A*、A*、Dijkstra和Bellman‑Ford生成的最短路径长度。Tabu‑A*在各场景中生成的最短路径普遍较短，说明其启发式估计提升了搜索效率：

• 推荐路径平均长度：图9展示了推荐路径在不同时间段的平均长度，Tabu‑A*在四个场景中均优于基准算法，说明其能在拥堵条件下找到更有效的绕行路线：

• 最短路径旅行时间：图10展示了24 小时内四个场景最短路径的旅行时间对比。Tabu‑A*曲线始终低于A*，尤其在高峰期差异明显，验证了时间敏感性优势：

• 推荐路径平均旅行时间：图11对比了Tabu‑A*与基准算法在推荐路径的平均旅行时间，Tabu‑A*在四个场景和各时间段均表现最优：

• 迭代次数对性能的影响：图12考察了不同迭代次数对路径长度和执行时间的影响。随着迭代次数增加，路径长度迅速下降但计算时间上升，前几次迭代贡献最大。图中蓝色虚线为Tabu‑A*，红色虚线为A*：

4.5 结果总结

通过综合比较，Tabu‑A*在测试场景中达到：

• 平均旅行时间节约：最高节约78.77%，平均节约65.77%。
• 路径长度优势：在多时段、多场景下均生成更短的实际行驶路径。
• 适应性强：在非高峰期，推荐路径与最短路径近似；高峰期则自动选择避开拥堵的路线。

五、结论与未来展望

5.1 研究结论

1. 混合算法的有效性：Tabu‑A*通过结合A*的启发式估计与Tabu搜索的全局探索，能在动态交通网络中快速收敛，避免局部最优，推荐出更适宜的路径。
2. 时空数据的重要性：利用历史速度和实时路网信息建立距离‑时间图，使算法能更精准地反映交通状态。
3. 性能优于传统方法：与A*、Dijkstra和Bellman‑Ford比较，Tabu‑A*在路径长度和旅行时间上均表现出明显优势，尤其在交通高峰期间。
4. 参数调节的必要性：敏感性分析表明，适配度权重  与启发式权重  必须合理调节，以平衡历史经验与启发式信息。

5.2 局限与未来工作

作者指出以下局限并提出未来改进方向：

• 计算开销：Tabu搜索属于元启发式算法，计算时间相对贪婪算法更长，实时应用需进一步优化。
• 缺乏实时适应性：当前框架主要依赖历史数据，未来将引入实时事件（事故、封路等）快速调整路线。
• 可扩展性研究：探索分布式或层次化实现以适应更大规模网络，研究多准则优化（燃油消耗、安全性等）。
• 多场景适配：将算法扩展到行人路径规划、物流配送等不同应用领域，并在更大的城市网络进行验证。