用于路径优化的遗传算法交叉算子比较分析：来自哈萨克斯坦阿斯塔纳和什姆肯特的案例研究

为何更智能的公交线路很重要

任何在公交站等候过久或需要频繁换乘的乘客都知道，穿越城市并不仅仅取决于距离。地图上看似相近的两点，如果没有合适的公交线路连接，也可能难以到达。本文探讨了一类受进化启发的搜索方法——遗传算法——如何被调优以设计更符合真实公交网络的线路，研究对象包括哈萨克斯坦的阿斯塔纳和什姆肯特等城市。工作聚焦于这些算法的一个关键环节：交叉（crossover）步骤，展示了明智选择该步骤如何在笨拙绕行和快速、现实的路线之间产生决定性差异。

从混乱的城市地图到智能搜索

传统的路线规划通常把城市当作旅客可以在任意两点间自由移动的空间，只关心物理距离。而真实的公交系统并非如此：你只能沿着实际运行的线路前进，任何缺失的连接或被迫绕道都会耗费时间和成本。作者通过把重要城市位置表示为点、道路与公交连接表示为边、把完整行程表示为访问每个点恰好一次的路径来建模这种现实。他们设定了两重目标：首先，避免没有直达公交的“非法”步骤；其次，在合法路线中选择总距离最短者。这就形成了一个困难的组合难题，随着城市规模增长，枚举所有可能性很快变得不可行。

进化如何帮助寻找更优路线

遗传算法通过模拟自然选择来应对此类难题。它们不再一次只尝试一条路线，而是维持一组候选路线的种群。在每一代中，更好的路线被优先保留，并通过混合与小幅变异现有路线生成新个体。关键的混合步骤——交叉——决定了如何把两个父路线的片段组合成新的子路线。对于公交规划而言，这一步至关重要：做得好会保留有用的连接模式；做得不好则可能破坏连接，产生忽视实际公交网络的路线。作者测试了九种不同的交叉方式，这些方式在保持站点顺序、站点的精确位置或站点之间实际连边的侧重点上各不相同。

测试多种混合路线的方法

为评估哪些交叉方式效果最佳，研究团队在来自科尼亚（此前研究的参考城市）以及阿斯塔纳和什姆肯特的真实交通数据上进行了大量实验。对每个城市，他们选取了14个重要目的地，将这些目的地与附近车站连接，并构建了三张关键数据表：位置间的距离、哪些站点对之间有直达公交、以及尝试在无公交路径上行驶时的惩罚值。随后他们在数百种设置下进行探索，变化包括种群规模、交叉使用的频率以及小幅随机改动（变异）的频率。对于每种设置，他们多次重复算法以抵消偶然性影响，并不仅测量最终路线的长度，还记录方法能否找到任何合法路线以及达到该点的速度。

现实可行出行的获胜策略

在三个城市的实验中，有一种交叉方式脱颖而出：边重组（edge recombination）。与主要关注站点顺序的方法不同，边重组更关注哪些站点是直接相连的，并在构建新路线时尽力保留这些连边。研究表明，这种以边为中心的策略更有可能产生可行的公交行程，更常能重新发现已知的最优路线，而且通常只需少数代就能做到。另一种称为基于顺序的交叉（order-based crossover）的方式表现也不错，且计算更快，在需要大量重复运行时提供了良好的折中。其他一些更激进重排站点的常见交叉方法往往表现较差，需要更多时间并产生较少高质量路线。

这对日常出行意味着什么

对非专业读者而言，结论是：遗传算法内部使用的“配方”会显著影响其设计现实公交路线的能力。通过偏好那些在保持真实连边的同时仍能探索新组合的交叉规则，规划者可以生成既遵循现有公交网络又保持较低总行程距离的路线。在小规模但现实的城市快照测试中，调优良好的遗传算法不仅能匹配精确数学方法找到的路线，而且在速度和可靠性上也具有优势。这表明，随着城市变得更加复杂并拥有更多数据，精心设计的进化搜索可以帮助交通机构规划出更直接、换乘更少且更合理利用车辆与燃料的路线。

引用: Kazbek, R., Sergaziyev, M., Kenzhe, D. et al. A comparative analysis of crossovers in genetic algorithms for route optimization: case studies from Astana and Shymkent, Kazakhstan. Sci Rep 16, 13816 (2026). https://doi.org/10.1038/s41598-026-43898-7

关键词: 公共交通路线, 遗传算法, 城市出行, 路线优化, 智慧城市规划