交通网络旅行商路径优化的遗传禁忌搜索算法

作者：余丽; 陆锋; 杨林

来源：测绘学报, 2014, 43(11): 1197-1203.

DOI：10.13485/j.cnki.11-2089.2014.0184

• 旅行商问题
• 交通网络
• 禁忌搜索
• 遗传算法

旅行商路径优化问题是经典的网络分析问题之一,主要通过智能优化方法获得近似最优解。然而,单一智能优化方法存在运算量过大、参数选择苛刻、对初值依赖性强等缺陷,很难快速实现全局优化。本文结合遗传算法的全局寻优能力和禁忌搜索的记忆功能,提出一种基于分散集中策略的遗传禁忌搜索算法,即采用遗传变异算子作为分散策略构造邻域,开辟新的搜索空间,有效提升获得全局最优解的概率;将禁忌搜索作为集中策略进行局部寻优,避免迂回探测,充分体现禁忌搜索较强的"爬山"能力,并通过实际交通网络和不同规模的节点集合,从求解精度、稳定性和效率3个方面对算法进行评价。结果表明,本文提出的交通网络旅行商路径优化的遗传禁忌搜索算法平均求解精度比禁忌搜索算法提高了9%,略优于ArcGIS;当与ArcGIS求解的TSP路径长度差异在1%以内时,禁忌搜索算法已经难以获得对应精度的TSP路径,而遗传禁忌搜索算法效率比遗传算法提高了50%,且遗传禁忌搜索算法具有很好的并行化潜力。

• 单位
  中国科学院大学; 地理信息工程国家重点实验室; 资源与环境信息系统国家重点实验室; 中国科学院地理科学与资源研究所