考慮雙重權(quán)重的最優(yōu)路徑選擇

李萍 令曉明

摘 要：為解決城市物流配送最優(yōu)路徑選取問題，從城市道路網(wǎng)絡(luò)空間分布形態(tài)出發(fā)，綜合考慮影響最短路徑求解的多種因素，建立動態(tài)路網(wǎng)模型，并對經(jīng)典最短路徑算法進行改進。結(jié)合道路網(wǎng)絡(luò)的幾何性質(zhì)，以實際路網(wǎng)為例，標記各路段交叉口作為結(jié)點，將實際路網(wǎng)部分轉(zhuǎn)化為Manhattan型結(jié)構(gòu)，同時分析相鄰交叉口間距離和平均人口對路徑選取的影響，通過重新定義考慮雙重權(quán)重的最短路徑權(quán)重與參考值[η]，對算法進行改進。利用改進算法迭代計算獲得最短路徑解，并對多個解的情況進行分析，分別比較兩條路徑的[η]值，并選取其中[η]值較大的一條路徑作為最優(yōu)規(guī)劃路徑。實驗結(jié)果表明，路網(wǎng)結(jié)構(gòu)轉(zhuǎn)化及算法改進不僅可簡化計算，同時參考值[η]的引入還可有效解決最短路徑不唯一時最優(yōu)路徑的選取問題。

關(guān)鍵詞：智能交通;有向圖;最短路徑;Manhattan距離;Floyd算法

DOI：10. 11907/rjdk. 191203

中圖分類號：TP312文獻標識碼：A文章編號：1672-7800（2019）003-0078-04

0 引言

最短路徑問題是圖論理論研究的一個經(jīng)典問題，由于現(xiàn)實中很多問題均可抽象為最短路徑計算，因此最短路徑算法被廣泛應用于交通運輸、計算機科學、電子信息、運籌學等領(lǐng)域。例如，為解決道路交通問題，可用有向圖表示實際道路結(jié)構(gòu)：結(jié)點代表城市，邊代表城市之間的道路，權(quán)重代表道路長度，權(quán)重也可以是非距離的度量單位，如時間、成本、罰款、損失等。

經(jīng)典圖論與不斷發(fā)展完善的算法有效結(jié)合，使新的最短路徑算法不斷涌現(xiàn)[3]。1959年，Dijkstra首次提出Dijkstra 算法，并用于求解單源最短路徑問題，此后為尋找路網(wǎng)兩結(jié)點間最短路徑，最短路徑相關(guān)算法不斷更新優(yōu)化，最常見的有Floyd算法、A*算法、蟻群算法（Ant Colony Optimization，ACO）、粒子群算法（Particle Swarm-Optimization，PSO）、遺傳算法等。其中，Dijkstra圖論中求取最短路徑的經(jīng)典算法被改進后，可以有效解決多鄰接點問題和多條最短路徑問題;Floyd算法利用動態(tài)規(guī)劃思想，可有效求解帶負權(quán)重圖多源點之間的最短路徑;A*算法是一種典型的啟發(fā)式算法，無需對圖中所有結(jié)點進行遍歷，因此在尋找最短路徑時，搜索速度更快。自20世紀90年代以來，群智能算法備受關(guān)注。蟻群算法由Marco Dorigo于1992年在其博士論文中提出，是一種概率型尋找優(yōu)化路徑的算法;粒子群算法通過模擬鳥集群飛行覓食的行為尋求最短路徑，初期在保證粒子多樣性的基礎(chǔ)上，算法可盡快進入局部搜索，具有收斂非常快的特點;遺傳算法（Genetic Algorithm）作為一種智能算法，通過模擬自然進化過程搜索最優(yōu)解，是處理復雜問題滿意解的最佳工具之一。實踐證明，遺傳算法可以有效解決組合優(yōu)化中路徑尋優(yōu)問題。雖然以上算法可有效解決不同情況下最短路徑問題，但在實際生活中最短路徑往往不止一條，如何從眾多最短路徑中選出一條最優(yōu)路徑作為出行路線成為本文研究重點。

本文從最短路徑算法基礎(chǔ)理論入手，在研究各類最短路徑算法的基礎(chǔ)上，建立一種存在多條最短路徑時，考慮雙權(quán)重的Manhattan型路網(wǎng)結(jié)構(gòu)路徑尋優(yōu)模型。其基本思路是首先根據(jù)路徑規(guī)劃要求， 以實際路網(wǎng)結(jié)構(gòu)為例，通過引入結(jié)點，構(gòu)造Manhattan型結(jié)構(gòu)網(wǎng)絡(luò);然后， 綜合考慮雙重權(quán)重對路徑選取的影響，通過重新定義最短路徑矩陣，改進傳統(tǒng)Floyd算法;最后，利用改進的算法求取最短路徑。計算結(jié)果表明，當最短路徑不止一條時，可引入?yún)⒖贾礫η]，通過比較不同路徑的[η]值作為最短路徑不唯一時選取最優(yōu)路徑的依據(jù)。

1 理論基礎(chǔ)

1.1 帶權(quán)重的有向圖

2 路網(wǎng)模型建立

2.1 問題描述

本文首先統(tǒng)計各可行路段間的實際路距，并根據(jù)幾何性質(zhì)，取兩相鄰交叉口的Manhattan距離作為影響路徑選取的第一重權(quán)重，綜合考慮各路段居民人口數(shù)對服務(wù)站選址的影響，并以其作為第二重權(quán)重求解雙重權(quán)重的最優(yōu)路徑，統(tǒng)計數(shù)據(jù)如圖3所示，其中實線表示各路段平均居民人口數(shù)，以百為單位，虛線表示相鄰兩結(jié)點間的Manhattan距離，以千為單位。

2.2 路網(wǎng)結(jié)構(gòu)轉(zhuǎn)化

5 結(jié)語

本文針對城市物流配送最優(yōu)路徑選取問題，從城市道路網(wǎng)絡(luò)空間分布形態(tài)出發(fā)，根據(jù)路徑規(guī)劃要求， 以實際路網(wǎng)結(jié)構(gòu)為例，構(gòu)造Manhattan型結(jié)構(gòu)，簡化路網(wǎng)結(jié)構(gòu)，并綜合考慮路距和人口對路徑選取的影響，通過重新計算最短路徑權(quán)重矩陣，改進傳統(tǒng)Floyd算法，同時對最短路徑不止一條的情況進行分析，通過定義參考值[η]選取最短路線為最優(yōu)可行路徑。實驗對比結(jié)果表明，路網(wǎng)結(jié)構(gòu)轉(zhuǎn)化及算法改進不僅簡化了計算，同時參考值[η]的引入可有效解決最短路徑不唯一時最優(yōu)路徑的選取問題。但當存在很多不確定因素時，比如在極端天氣、交通事故等影響下，實際路網(wǎng)信息往往更加復雜，本文沒有對突發(fā)情況進行分類，這是后續(xù)學習中需進一步研究的內(nèi)容。

參考文獻：

[1] 殷建平，徐云，王剛，等. 算法導論[M]. 第3版. 北京：機械工業(yè)出版社，2013.

[2] 宋青，汪小帆. 最短路徑算法加速技術(shù)研究綜[J]. 電子科技大報，2012，41（2）：176-184.

[3] 張志然，劉紀平，仇阿，等. 面向大規(guī)模道路網(wǎng)的最短路徑近似算法[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] 吳蓉，賴偉杰，孟佳娜，等. 基于復雜網(wǎng)絡(luò)的中文微博網(wǎng)絡(luò)結(jié)構(gòu)研究[J]. 計算機時代，2019（1）：33-35+38.

[12] 劉婷婷，于衛(wèi)紅. 物流配送網(wǎng)絡(luò)最短路線規(guī)劃[J]. 電子商務(wù)，2018（12）：9-10+14.

[13] 劉宏志，高立群，歐陽海濱. 一類標準矩形網(wǎng)絡(luò)節(jié)點間最短路徑的求解方法[J]. 控制與決策，2016，31（4）：623-628.

[14] 馬靜，王佳斌，張雪. A*算法在無人車路徑規(guī)劃中的應用[J]. 計算機技術(shù)與發(fā)展，2016，26（11）：153-156.

[15] 郝自軍，何尚錄. 最短路問題的Floyd算法的若干討論[J]. 重慶工學院學報：自然科學版，2008（5）：156-159.

[16] 趙宏偉，劉宇琦，董立巖，等. 智能交通混合動態(tài)路徑優(yōu)化算法[J]. 吉林大學學報：工學版，2018，48（4）：1214-1223.

[17] 林華珍，周根貴. 求解最短路問題的一種優(yōu)化矩陣算法[J]. 長江大學學報：自科版，2007，4（4）：14-16.

[18] 徐慶征，柯熙政. 必經(jīng)點最短路徑問題模型及相應遺傳算法研究[J]. 系統(tǒng)工程與電子技術(shù)，2009，31（2）：459-462.

[19] 費騰，張立毅. 現(xiàn)代智能優(yōu)化算法研究[J]. 信息技術(shù)，2015（10）：26-29.

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

（責任編輯：江 艷）