考慮雙重權重的最優路徑選擇

李萍 令曉明

摘 要：為解決城市物流配送最優路徑選取問題，從城市道路網絡空間分布形態出發，綜合考慮影響最短路徑求解的多種因素，建立動態路網模型，并對經典最短路徑算法進行改進。結合道路網絡的幾何性質，以實際路網為例，標記各路段交叉口作為結點，將實際路網部分轉化為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.

（責任編輯：江 艷）