基于Dijkstra算法的地下物流配送路徑優(yōu)化研究
2021-10-19 13:22:52周冰盧貝
現(xiàn)代信息科技 2021年6期
周冰 盧貝
摘 ?要：電商產(chǎn)業(yè)的崛起帶動了物流行業(yè)的發(fā)展，雖然如今的物流行業(yè)已有了質(zhì)的提升，但由此帶來的問題也日益凸顯，路上的車輛越來越多，越來越擁堵。地下物流系統(tǒng)的發(fā)展能有效解決此類問題，同時也符合社會可持續(xù)發(fā)展的需求。該文主要使用Dijkstra算法，對物流配送路徑及節(jié)點的選擇進行建模分析，求解出配送結(jié)點至各需求點的最短路徑及所經(jīng)結(jié)點，針對物流節(jié)點的選擇提供一種行之有效的解決方法。
關鍵詞：城市地下物流;最短路徑算法;Dijkstra
中圖分類號：TP391;F252 ? ? 文獻標識碼：A 文章編號：2096-4706（2021）06-0091-05
Research on Underground Logistics Distribution Path Optimization Based on Dijkstra Algorithm
ZHOU Bing，LU Bei
（School of Information Engineering，Jiaozuo University，Jiaozuo ?454000，China）
Abstract：The rise of E-commerce industry has led to the rapid development of logistics industry. Although todays logistics industry has been improved in quality，but the resulting problems are also increasingly prominent. More and more vehicles appears on the road，more and more congestion. The development of underground logistics system can solve such problems effectively. At the same time it also meets the need of social sustainable development. This paper mainly uses Dijkstra algorithm to model and analyze the choice of logistics distribution path and node，and solves the shortest path and the nodes passed by from distribution node to each demand point. It provides an effective solution for the selection of logistics nodes.
Keywords：urban underground logistics;shortest path algorithm;Dijkstra
0 ?引 ?言
本文依托“新型智慧城市建設背景下新一代物流體系的研究與應用”項目，基于對城市未來發(fā)展的展望和預測，構(gòu)建新一代智慧物流系統(tǒng)的架構(gòu)和體系仿真運行模型，研究地下物流節(jié)點選取及配送路徑優(yōu)化。地下物流系統(tǒng)是新一代的智慧物流系統(tǒng)，它是將地面物流系統(tǒng)與地下物流系統(tǒng)整合，形成一種更高效、更環(huán)保、更節(jié)省物理資源的物流系統(tǒng)。發(fā)展地下物流系統(tǒng)，能有效地緩解城市交通的擁堵，實現(xiàn)城市的可持續(xù)發(fā)展。將城市地下物流系統(tǒng)從網(wǎng)絡層級上分為二級網(wǎng)絡，并從二級配送節(jié)點出發(fā)，將貨物至需求點所經(jīng)過的路徑及節(jié)點的選擇進行了建模分析，通過求解，得到二級配送節(jié)點到覆蓋范圍內(nèi)每個需求點的最短路徑及所經(jīng)節(jié)點。
1 ?地下物流系統(tǒng)整體設計
要加強數(shù)字化、信息化的建設，整體規(guī)劃物流信息管理系統(tǒng)。對每一個物流中心、每一個配送節(jié)點、每一個轉(zhuǎn)運點進行統(tǒng)一標準格式的編碼，便于貨物的流轉(zhuǎn)（包括節(jié)點的選取和路徑的選擇）。對物流中心、配送節(jié)點、轉(zhuǎn)運點的編碼要有明顯的字段，標識節(jié)點的不同類型，對于不同的省市區(qū)的節(jié)點進行編碼也要有標識字段用于區(qū)分。此外還要大力推動“一單、一碼、一單元”[1]，避免如今“四通一達”、菜鳥、順豐、京東、極兔等物流各自為戰(zhàn)，各自都有一套自己的物流系統(tǒng)，信息交流不通暢，導致重復建設，資源浪費。
將每一個標準的物流包裹統(tǒng)一規(guī)劃為物流單元，每個物流單元都會被分配一個唯一的“數(shù)字身份證”，也就是一碼。每個物流單元都會被分配一個標準的電子貨單（數(shù)字通行證），也就是一單，實現(xiàn)物流與信息流的融合，形成數(shù)字化物流網(wǎng)絡。
整個城市地下物流系統(tǒng)的硬件組成部分，主要包括具體的物流中心、配送節(jié)點，支撐系統(tǒng)運行的自動分揀系統(tǒng)、存儲系統(tǒng)、集散系統(tǒng)等，以及地下物流管道、社區(qū)配送裝置等。
城市地下物流系統(tǒng)從網(wǎng)絡層級上劃分，可分為兩級，一級為物流中心，二級為配送結(jié)點。兩組一樣的層級劃分，每級之間都可進行關聯(lián)轉(zhuǎn)運，如圖1所示。
第一級為物流中心。規(guī)模龐大，負責各種包裹的分發(fā)轉(zhuǎn)運。該物流中心可與其他城市物流中心對接，連接成網(wǎng)。物流中心與下一級的配送節(jié)點相連，使用地下物流傳輸貨物。
第二級為配送節(jié)點。配送節(jié)點與各個小區(qū)、商業(yè)聚集區(qū)、產(chǎn)業(yè)園直接或間接相連，使用地下物流系統(tǒng)傳輸貨物，并可通過社區(qū)配送管道直達用戶門口，如圖2所示。
地下物流傳輸還可以從以下方面進行優(yōu)化。每個物流單元可配置物聯(lián)網(wǎng)芯片[2]，實現(xiàn)實時定位、采集該單元的位置信息。地下物流管道應采用雙通道設計，雙向傳輸，可進行物流配送，亦可實現(xiàn)物流收件。地下物流管道加設可尋址的信號傳輸裝置，方便發(fā)現(xiàn)故障、定位故障、解決故障。地下物流系統(tǒng)加入流量控制算法和擁塞處理算法，便于動態(tài)規(guī)劃，提升物流傳輸效率。
2 ?網(wǎng)絡節(jié)點選擇
目前已有很多專家和學者對地下物流節(jié)點的選取進行了研究，王蘇林等使用貪心遺傳算法對地下物流節(jié)點的選擇規(guī)劃進行了研究[3]，何永貴使用基于成本優(yōu)化的算法對城市地下物流節(jié)點選址進行了研究[4]，方龍祥分別使用基于貪心算法[5]和0～1整數(shù)規(guī)劃算法對城市地下物流系統(tǒng)網(wǎng)絡節(jié)點選址進行了研究[6]，李姍珊使用基于地下管道物流運輸?shù)能壍谰€網(wǎng)規(guī)劃與線路設計研究[7]。本文采用求解最短路徑的經(jīng)典算法——Dijkstra算法對配送過程中路徑節(jié)點的選擇進行了分析研究，實現(xiàn)了最短配送路徑的求解。
2.1 ?網(wǎng)絡節(jié)點選取背景
城市地下物流系統(tǒng)主要由一級物流中心、二級配送節(jié)點和各節(jié)點間的地下運輸管道構(gòu)成。一級節(jié)點之間互通互達，形成網(wǎng)絡，并可相互之間傳輸貨物。二級節(jié)點只與本區(qū)域的上級節(jié)點相連。二級節(jié)點與貨物需求點直接相連或經(jīng)轉(zhuǎn)運點間接相連。由于需求末端錯綜復雜，地下物流管道的布置不可能都與二級節(jié)點直接相連，如圖3中的節(jié)點，二級節(jié)點0，要為需求點4配送貨物，可能的配送路線經(jīng)過了節(jié)點1、節(jié)點2、節(jié)點3，然后到達需求點4，我們稱節(jié)點1、節(jié)點2、節(jié)點3為轉(zhuǎn)運點，也叫路徑節(jié)點。
城市的需求點非常多，分布多集中在小區(qū)，商業(yè)聚集區(qū)等。本文研究的網(wǎng)絡節(jié)點選取是在已知需求點和配送節(jié)點具體位置的情況下，如何選取合適的節(jié)點，實現(xiàn)最高的貨物運轉(zhuǎn)效率。由于使用地下物流傳輸系統(tǒng)進行傳輸，我們可以不必考慮堵車等其他因素造成的系統(tǒng)擁堵情況，那么最核心的問題就是如何在眾多的網(wǎng)絡節(jié)點中，查找出一個配送節(jié)點到需求點的最短路徑。
2.2 ?數(shù)據(jù)來源
我們對鄭州市的地下物流節(jié)點進行了設計，并從地圖上選取0至9共10個節(jié)點，其中節(jié)點0為二級配送節(jié)點，節(jié)點1至9為需求節(jié)點，并且對各個節(jié)點間的距離通過地圖測量工具進行了測量，單位為km，如圖3所示。
2.3 ?Dijkstra最短路徑建模
李健對Dijkstra最短路徑算法進行了研究并優(yōu)化了該算法[8]，鄒佰翰等人研究了最短路徑算法在計算機網(wǎng)絡路由選擇中使用[9]。我們也使用Dijkstra算法對圖3所示節(jié)點進行了建模分析。由圖3可得到如圖4所示的路徑圖。每條線都可以雙向傳輸，實現(xiàn)貨物的發(fā)件收件?，F(xiàn)對貨物的派發(fā)進行模擬求解，分別求出配送節(jié)點0至其他各需求節(jié)點的最短路徑（至最終節(jié)點9結(jié)束）。如果是收件，用同樣的方法亦可求解。
2.4 ?求解
求從節(jié)點0出發(fā)至終點節(jié)點9的最短路徑。如表1所示，每一列為當前步驟最短路徑求解結(jié)果，每經(jīng)一個步驟，都能求出當前一步所對應的最短路徑及所經(jīng)節(jié)點，最后一行vj就是該步驟所選中的最短路徑的結(jié)果。表格中的短橫線“----”表示，已經(jīng)求解出至該節(jié)點的最短路徑，并添加至已知結(jié)點內(nèi)，不用再計算該節(jié)點。
求解過程：設有已知集合S、未知集合T，初始情況S僅有v0節(jié)點，其余節(jié)點都在未知集合T里。從v0節(jié)點開始，一步一步求解能達到的最近的節(jié)點。最終可求出v0到其他各節(jié)點的最短路徑。
步驟1：已知集合S：v0。
未知集合T：v1，v2，v3，v4，v5，v6，v7，v8，v9。
求出從v0節(jié)點出發(fā)到能直接可達的各節(jié)點的距離，將其填在最終結(jié)果表中的步驟1列中，如果不能直接可達，則記錄為∞。
可得出最短路徑為
步驟2：已知集合S：v0，v1。
未知集合T：v2，v3，v4，v5，v6，v7，v8，v9。
以v1節(jié)點為中間節(jié)點，求出從v0節(jié)點出發(fā)經(jīng)v1節(jié)點到能直接可達的未知節(jié)點集合T中各節(jié)點的距離，填在最終結(jié)果表中的步驟2列中，如果不能直接可達，則記錄為∞。由于v1節(jié)點已在已知節(jié)點中，不用重新計算，直接加上“----”符號，作為不再計算的標記。如果從v0出發(fā)，經(jīng)過中間節(jié)點v1，去未知節(jié)點中尋找，如果也不可達，把前一列的結(jié)果移入當前單元格內(nèi)。
按上述規(guī)則，求解可達的每一個未知節(jié)點的距離。
可得出最短路徑為
步驟3：已知集合S：v0，v1，v2。
未知集合T：v3，v4，v5，v6，v7，v8，v9。
求出經(jīng)v2節(jié)點直接可達的未知集合中各節(jié)點的距離，填在最終結(jié)果表中的步驟3列中，如果不能直接可達，則記錄為∞。如果不可達，可從前一列中移植過來。
可得出最短路徑為
步驟4：已知集合S：v0，v1，v2，v3。
未知集合T：v4，v5，v6，v7，v8，v9。
求出經(jīng)v3節(jié)點直接可達的未知集合中各節(jié)點的距離，填在最終結(jié)果表中的步驟4列中，如果不能直接可達，則記錄為∞。如果不可達，可從前一列中移植過來。
可得出最短路徑為
步驟5：已知集合S：v0，v1，v2，v3，v7。
未知集合T：v4，v5，v6，v8，v9。
求出經(jīng)v7節(jié)點直接可達的未知集合中各節(jié)點的距離，填在最終結(jié)果表中的步驟5列中。
可得出最短路徑為
步驟6：已知集合S：v0，v1，v2，v3，v7，v4。
未知集合T：v5，v6，v8，v9。
求出經(jīng)v4節(jié)點直接可達的未知集合中各節(jié)點的距離，填在最終結(jié)果表中的步驟6列中。
可得出最短路徑為
步驟7：已知集合S：v0，v1，v2，v3，v7，v4，v5。
未知集合T：v6，v8，v9。
求出經(jīng)v5節(jié)點直接可達的未知集合中各節(jié)點的距離，填在最終結(jié)果表中的步驟7列中。
可得出最短路徑為
步驟8：已知集合S：v0，v1，v2，v3，v7，v4，v5，v8。
未知集合T：v6，v9。
求出經(jīng)v8節(jié)點直接可達的未知集合中各節(jié)點的距離，填在最終結(jié)果表中的步驟8列中。
可得出最短路徑為
步驟9：已知集合S：v0，v1，v2，v3，v7，v4，v5，v8，v6。
未知集合T：v9。
求出經(jīng)v6節(jié)點直接可達的未知集合中各節(jié)點的距離，填在最終結(jié)果表中的步驟9列中。
可得出最短路徑為
從最終結(jié)果表的最后一行vj行中，可得到從v0出發(fā)點，到可達的各個需求點的最短路徑。
2.5 ?選擇結(jié)論
經(jīng)過最短路徑求解——Dijkstra算法的求解，得到配送節(jié)點v0至各節(jié)點的最短路徑以及所經(jīng)過的節(jié)點分別為：
從v0出發(fā)至v1節(jié)點：
從v0出發(fā)至v2節(jié)點：
從v0出發(fā)至v3節(jié)點：
從v0出發(fā)至v4節(jié)點：
從v0出發(fā)至v5節(jié)點：
從v0出發(fā)至v6節(jié)點：
從v0出發(fā)至v7節(jié)點：
從v0出發(fā)至v8節(jié)點：
從v0出發(fā)至v9節(jié)點：
求出配送點至需求點的最短路徑后，可生成一張最短路徑表，并將該路徑表存入系統(tǒng)內(nèi)，當配送路線出現(xiàn)故障或阻塞后，可重新生成最短路徑，更新最短路徑表。下次配送時可直接查表選擇最短路徑節(jié)點進行配送，提升配送效率。
3 ?結(jié) ?論
本文通過針對城市中二級配送節(jié)點進行配送時的節(jié)點選擇進行建模，并使用最短路徑算法——Dijkstra算法，對模型數(shù)據(jù)進行了分析。通過分析，可以得到從配送節(jié)點出發(fā)，到可達的每一個需求點的最短路徑，以及該路徑所經(jīng)過的中間節(jié)點。此外，提出路徑緩存的概念，將已計算的最短路徑存儲為最短路徑表，提升路徑選擇的效率。該方法適用于針對任何二級節(jié)點進行配送時的節(jié)點選擇問題。
參考文獻：
[1] 吳曉釗，王繼祥.物聯(lián)網(wǎng)技術(shù)在物流業(yè)的應用現(xiàn)狀與發(fā)展前景 [J].物流技術(shù)與應用，2011，16（2）：53-56+59.
[2] 王繼祥.物聯(lián)網(wǎng)發(fā)展推動中國智慧物流變革 [J].物流技術(shù)與應用，2010，15（6）：30-35.
[3] 王蘇林，邱菲爾，陳凡，等.基于貪心遺傳的地下物流節(jié)點選擇規(guī)劃研究 [J].工業(yè)工程，2020，23（5）：88-95.
[4] 何永貴，周穎.基于成本優(yōu)化的城市地下物流節(jié)點選址研究 [J].管理現(xiàn)代化，2018，38（6）：66-69.
[5] 方龍祥，于雪雨.基于貪心算法的城市地下物流系統(tǒng)網(wǎng)絡節(jié)點選址 [J].巢湖學院學報，2019，21（6）：51-58.
[6] 方龍祥，于雪雨.基于0-1整數(shù)規(guī)劃算法的城市地下物流系統(tǒng)網(wǎng)絡節(jié)點選址 [J].安徽工程大學學報，2019，34（5）：53-58.
[7] 李姍珊，劉延君，秦宇豪，等.基于地下管道物流運輸?shù)能壍谰€網(wǎng)規(guī)劃與線路設計研究 [J].中國管理信息化，2019，22（14）：92-93.
[8] 李健.基于Dijkstra最短路徑算法的優(yōu)化研究 [J].渭南師范學院學報，2009，24（5）：61-64.
[9] 鄒佰翰，張吉懿，苑曉兵.最短路徑算法在計算機網(wǎng)絡路由選擇中的應用研究 [J].電聲技術(shù)，2020，44（2）：59-60+70.
作者簡介：周冰（1981—），男，漢族，河南溫縣人，副教授，碩士，研究方向：智慧城市、計算機應用。
