考虑双重权重的最优路径选择

李萍 令晓明

摘 要：为解决城市物流配送最优路径选取问题，从城市道路网络空间分布形态出发，综合考虑影响最短路径求解的多种因素，建立动态路网模型，并对经典最短路径算法进行改进。结合道路网络的几何性质，以实际路网为例，标记各路段交叉口作为结点，将实际路网部分转化为Manhattan型结构，同时分析相邻交叉口间距离和平均人口对路径选取的影响，通过重新定义考虑双重权重的最短路径权重与参考值[η]，对算法进行改进。利用改进算法迭代计算获得最短路径解，并对多个解的情况进行分析，分别比较两条路径的[η]值，并选取其中[η]值较大的一条路径作为最优规划路径。实验结果表明，路网结构转化及算法改进不仅可简化计算，同时参考值[η]的引入还可有效解决最短路径不唯一时最优路径的选取问题。

关键词：智能交通;有向图;最短路径;Manhattan距离;Floyd算法

DOI：10. 11907/rjdk. 191203

中图分类号：TP312文献标识码：A文章编号：1672-7800（2019）003-0078-04

0 引言

最短路径问题是图论理论研究的一个经典问题，由于现实中很多问题均可抽象为最短路径计算，因此最短路径算法被广泛应用于交通运输、计算机科学、电子信息、运筹学等领域。例如，为解决道路交通问题，可用有向图表示实际道路结构：结点代表城市，边代表城市之间的道路，权重代表道路长度，权重也可以是非距离的度量单位，如时间、成本、罚款、损失等。

经典图论与不断发展完善的算法有效結合，使新的最短路径算法不断涌现[3]。1959年，Dijkstra首次提出Dijkstra 算法，并用于求解单源最短路径问题，此后为寻找路网两结点间最短路径，最短路径相关算法不断更新优化，最常见的有Floyd算法、A*算法、蚁群算法（Ant Colony Optimization，ACO）、粒子群算法（Particle Swarm-Optimization，PSO）、遗传算法等。其中，Dijkstra图论中求取最短路径的经典算法被改进后，可以有效解决多邻接点问题和多条最短路径问题;Floyd算法利用动态规划思想，可有效求解带负权重图多源点之间的最短路径;A*算法是一种典型的启发式算法，无需对图中所有结点进行遍历，因此在寻找最短路径时，搜索速度更快。自20世纪90年代以来，群智能算法备受关注。蚁群算法由Marco Dorigo于1992年在其博士论文中提出，是一种概率型寻找优化路径的算法;粒子群算法通过模拟鸟集群飞行觅食的行为寻求最短路径，初期在保证粒子多样性的基础上，算法可尽快进入局部搜索，具有收敛非常快的特点;遗传算法（Genetic Algorithm）作为一种智能算法，通过模拟自然进化过程搜索最优解，是处理复杂问题满意解的最佳工具之一。实践证明，遗传算法可以有效解决组合优化中路径寻优问题。虽然以上算法可有效解决不同情况下最短路径问题，但在实际生活中最短路径往往不止一条，如何从众多最短路径中选出一条最优路径作为出行路线成为本文研究重点。

本文从最短路径算法基础理论入手，在研究各类最短路径算法的基础上，建立一种存在多条最短路径时，考虑双权重的Manhattan型路网结构路径寻优模型。其基本思路是首先根据路径规划要求， 以实际路网结构为例，通过引入结点，构造Manhattan型结构网络;然后， 综合考虑双重权重对路径选取的影响，通过重新定义最短路径矩阵，改进传统Floyd算法;最后，利用改进的算法求取最短路径。计算结果表明，当最短路径不止一条时，可引入参考值[η]，通过比较不同路径的[η]值作为最短路径不唯一时选取最优路径的依据。

1 理论基础

1.1 带权重的有向图

2 路网模型建立

2.1 问题描述

本文首先统计各可行路段间的实际路距，并根据几何性质，取两相邻交叉口的Manhattan距离作为影响路径选取的第一重权重，综合考虑各路段居民人口数对服务站选址的影响，并以其作为第二重权重求解双重权重的最优路径，统计数据如图3所示，其中实线表示各路段平均居民人口数，以百为单位，虚线表示相邻两结点间的Manhattan距离，以千为单位。

2.2 路网结构转化

5 结语

本文针对城市物流配送最优路径选取问题，从城市道路网络空间分布形态出发，根据路径规划要求， 以实际路网结构为例，构造Manhattan型结构，简化路网结构，并综合考虑路距和人口对路径选取的影响，通过重新计算最短路径权重矩阵，改进传统Floyd算法，同时对最短路径不止一条的情况进行分析，通过定义参考值[η]选取最短路线为最优可行路径。实验对比结果表明，路网结构转化及算法改进不仅简化了计算，同时参考值[η]的引入可有效解决最短路径不唯一时最优路径的选取问题。但当存在很多不确定因素时，比如在极端天气、交通事故等影响下，实际路网信息往往更加复杂，本文没有对突发情况进行分类，这是后续学习中需进一步研究的内容。

参考文献：

[1] 殷建平，徐云，王刚，等. 算法导论[M]. 第3版. 北京：机械工业出版社，2013.

[2] 宋青，汪小帆. 最短路径算法加速技术研究综[J]. 电子科技大报，2012，41（2）：176-184.

[3] 张志然，刘纪平，仇阿，等. 面向大规模道路网的最短路径近似算法[J]. 测绘学报，2019，48（1）：86-94.

[4] BERTSEKAS D P. Network optimization：continuous and discrete models[M].  Belmont：Athena Scientific， 1998.

[5] DIJKSTRA E W. A note on two problems in connexion with graphs[J].  Numerische Mathematik， 1959， 1（1）： 269-271.

[6] FLOYD R W. Algorithm 97： shortest path[J]. Communications of the ACM，1962，5（6）： 345.

[7] HART P E，NILSSON N J，RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics，1968，4（2）：100-107.

[8] COLORNI A，DORIGO M，MANIEZZO V. Distributed optimization by ant colonies[C]. the 1st European Conference on Artificial Life， 1991：134-142.

[9] MOHEMMED A W，SAHOO N C，GEOK T K. Solving shortest path problem using particle swarm optimization[J]. Applied Soft Computing，2008，8（4）：1643-1653.

[10] LI Q Q，CHEN B Y，WANG Y F，et al. A hybrid link-node approach for finding shortest paths in road networks with turn restrictions[J].  Transactions in GIS，2015，19（6）：915-929.

[11] 吳蓉，赖伟杰，孟佳娜，等. 基于复杂网络的中文微博网络结构研究[J]. 计算机时代，2019（1）：33-35+38.

[12] 刘婷婷，于卫红. 物流配送网络最短路线规划[J]. 电子商务，2018（12）：9-10+14.

[13] 刘宏志，高立群，欧阳海滨. 一类标准矩形网络节点间最短路径的求解方法[J]. 控制与决策，2016，31（4）：623-628.

[14] 马静，王佳斌，张雪. A*算法在无人车路径规划中的应用[J]. 计算机技术与发展，2016，26（11）：153-156.

[15] 郝自军，何尚录. 最短路问题的Floyd算法的若干讨论[J]. 重庆工学院学报：自然科学版，2008（5）：156-159.

[16] 赵宏伟，刘宇琦，董立岩，等. 智能交通混合动态路径优化算法[J]. 吉林大学学报：工学版，2018，48（4）：1214-1223.

[17] 林华珍，周根贵. 求解最短路问题的一种优化矩阵算法[J]. 长江大学学报：自科版，2007，4（4）：14-16.

[18] 徐庆征，柯熙政. 必经点最短路径问题模型及相应遗传算法研究[J]. 系统工程与电子技术，2009，31（2）：459-462.

[19] 费腾，张立毅. 现代智能优化算法研究[J]. 信息技术，2015（10）：26-29.

[20] 王云峰，孙毅. Dijkstra算法在应急救援中的应用[J]. 电子制作，2018（1）：59-60.

（责任编辑：江 艳）