李萍 令曉明

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

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

DOI：10. 11907/rjdk. 191203

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）003-0078-04

0 引言

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

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

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

1 理論基礎(chǔ)

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

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

2.1 問題描述

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

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

5 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

（責(zé)任編輯：江 艷）