基于Dijkstra算法的地下物流配送路徑優化研究
2021-10-19 13:22:52周冰盧貝
現代信息科技 2021年6期
周冰 盧貝
摘 ?要：電商產業的崛起帶動了物流行業的發展，雖然如今的物流行業已有了質的提升，但由此帶來的問題也日益凸顯，路上的車輛越來越多，越來越擁堵。地下物流系統的發展能有效解決此類問題，同時也符合社會可持續發展的需求。該文主要使用Dijkstra算法，對物流配送路徑及節點的選擇進行建模分析，求解出配送結點至各需求點的最短路徑及所經結點，針對物流節點的選擇提供一種行之有效的解決方法。
關鍵詞：城市地下物流;最短路徑算法;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 ?引 ?言
本文依托“新型智慧城市建設背景下新一代物流體系的研究與應用”項目，基于對城市未來發展的展望和預測，構建新一代智慧物流系統的架構和體系仿真運行模型，研究地下物流節點選取及配送路徑優化。地下物流系統是新一代的智慧物流系統，它是將地面物流系統與地下物流系統整合，形成一種更高效、更環保、更節省物理資源的物流系統。發展地下物流系統，能有效地緩解城市交通的擁堵，實現城市的可持續發展。將城市地下物流系統從網絡層級上分為二級網絡，并從二級配送節點出發，將貨物至需求點所經過的路徑及節點的選擇進行了建模分析，通過求解，得到二級配送節點到覆蓋范圍內每個需求點的最短路徑及所經節點。
1 ?地下物流系統整體設計
要加強數字化、信息化的建設，整體規劃物流信息管理系統。對每一個物流中心、每一個配送節點、每一個轉運點進行統一標準格式的編碼，便于貨物的流轉（包括節點的選取和路徑的選擇）。對物流中心、配送節點、轉運點的編碼要有明顯的字段，標識節點的不同類型，對于不同的省市區的節點進行編碼也要有標識字段用于區分。此外還要大力推動“一單、一碼、一單元”[1]，避免如今“四通一達”、菜鳥、順豐、京東、極兔等物流各自為戰，各自都有一套自己的物流系統，信息交流不通暢，導致重復建設，資源浪費。
將每一個標準的物流包裹統一規劃為物流單元，每個物流單元都會被分配一個唯一的“數字身份證”，也就是一碼。每個物流單元都會被分配一個標準的電子貨單（數字通行證），也就是一單，實現物流與信息流的融合，形成數字化物流網絡。
整個城市地下物流系統的硬件組成部分，主要包括具體的物流中心、配送節點，支撐系統運行的自動分揀系統、存儲系統、集散系統等，以及地下物流管道、社區配送裝置等。
城市地下物流系統從網絡層級上劃分，可分為兩級，一級為物流中心，二級為配送結點。兩組一樣的層級劃分，每級之間都可進行關聯轉運，如圖1所示。
第一級為物流中心。規模龐大，負責各種包裹的分發轉運。該物流中心可與其他城市物流中心對接，連接成網。物流中心與下一級的配送節點相連，使用地下物流傳輸貨物。
第二級為配送節點。配送節點與各個小區、商業聚集區、產業園直接或間接相連，使用地下物流系統傳輸貨物，并可通過社區配送管道直達用戶門口，如圖2所示。
地下物流傳輸還可以從以下方面進行優化。每個物流單元可配置物聯網芯片[2]，實現實時定位、采集該單元的位置信息。地下物流管道應采用雙通道設計，雙向傳輸，可進行物流配送，亦可實現物流收件。地下物流管道加設可尋址的信號傳輸裝置，方便發現故障、定位故障、解決故障。地下物流系統加入流量控制算法和擁塞處理算法，便于動態規劃，提升物流傳輸效率。
2 ?網絡節點選擇
目前已有很多專家和學者對地下物流節點的選取進行了研究，王蘇林等使用貪心遺傳算法對地下物流節點的選擇規劃進行了研究[3]，何永貴使用基于成本優化的算法對城市地下物流節點選址進行了研究[4]，方龍祥分別使用基于貪心算法[5]和0～1整數規劃算法對城市地下物流系統網絡節點選址進行了研究[6]，李姍珊使用基于地下管道物流運輸的軌道線網規劃與線路設計研究[7]。本文采用求解最短路徑的經典算法——Dijkstra算法對配送過程中路徑節點的選擇進行了分析研究，實現了最短配送路徑的求解。
2.1 ?網絡節點選取背景
城市地下物流系統主要由一級物流中心、二級配送節點和各節點間的地下運輸管道構成。一級節點之間互通互達，形成網絡，并可相互之間傳輸貨物。二級節點只與本區域的上級節點相連。二級節點與貨物需求點直接相連或經轉運點間接相連。由于需求末端錯綜復雜，地下物流管道的布置不可能都與二級節點直接相連，如圖3中的節點，二級節點0，要為需求點4配送貨物，可能的配送路線經過了節點1、節點2、節點3，然后到達需求點4，我們稱節點1、節點2、節點3為轉運點，也叫路徑節點。
城市的需求點非常多，分布多集中在小區，商業聚集區等。本文研究的網絡節點選取是在已知需求點和配送節點具體位置的情況下，如何選取合適的節點，實現最高的貨物運轉效率。由于使用地下物流傳輸系統進行傳輸，我們可以不必考慮堵車等其他因素造成的系統擁堵情況，那么最核心的問題就是如何在眾多的網絡節點中，查找出一個配送節點到需求點的最短路徑。
2.2 ?數據來源
我們對鄭州市的地下物流節點進行了設計，并從地圖上選取0至9共10個節點，其中節點0為二級配送節點，節點1至9為需求節點，并且對各個節點間的距離通過地圖測量工具進行了測量，單位為km，如圖3所示。
2.3 ?Dijkstra最短路徑建模
李健對Dijkstra最短路徑算法進行了研究并優化了該算法[8]，鄒佰翰等人研究了最短路徑算法在計算機網絡路由選擇中使用[9]。我們也使用Dijkstra算法對圖3所示節點進行了建模分析。由圖3可得到如圖4所示的路徑圖。每條線都可以雙向傳輸，實現貨物的發件收件。現對貨物的派發進行模擬求解，分別求出配送節點0至其他各需求節點的最短路徑（至最終節點9結束）。如果是收件，用同樣的方法亦可求解。
2.4 ?求解
求從節點0出發至終點節點9的最短路徑。如表1所示，每一列為當前步驟最短路徑求解結果，每經一個步驟，都能求出當前一步所對應的最短路徑及所經節點，最后一行vj就是該步驟所選中的最短路徑的結果。表格中的短橫線“----”表示，已經求解出至該節點的最短路徑，并添加至已知結點內，不用再計算該節點。
求解過程：設有已知集合S、未知集合T，初始情況S僅有v0節點，其余節點都在未知集合T里。從v0節點開始，一步一步求解能達到的最近的節點。最終可求出v0到其他各節點的最短路徑。
步驟1：已知集合S：v0。
未知集合T：v1，v2，v3，v4，v5，v6，v7，v8，v9。
求出從v0節點出發到能直接可達的各節點的距離，將其填在最終結果表中的步驟1列中，如果不能直接可達，則記錄為∞。
可得出最短路徑為
步驟2：已知集合S：v0，v1。
未知集合T：v2，v3，v4，v5，v6，v7，v8，v9。
以v1節點為中間節點，求出從v0節點出發經v1節點到能直接可達的未知節點集合T中各節點的距離，填在最終結果表中的步驟2列中，如果不能直接可達，則記錄為∞。由于v1節點已在已知節點中，不用重新計算，直接加上“----”符號，作為不再計算的標記。如果從v0出發，經過中間節點v1，去未知節點中尋找，如果也不可達，把前一列的結果移入當前單元格內。
按上述規則，求解可達的每一個未知節點的距離。
可得出最短路徑為
步驟3：已知集合S：v0，v1，v2。
未知集合T：v3，v4，v5，v6，v7，v8，v9。
求出經v2節點直接可達的未知集合中各節點的距離，填在最終結果表中的步驟3列中，如果不能直接可達，則記錄為∞。如果不可達，可從前一列中移植過來。
可得出最短路徑為
步驟4：已知集合S：v0，v1，v2，v3。
未知集合T：v4，v5，v6，v7，v8，v9。
求出經v3節點直接可達的未知集合中各節點的距離，填在最終結果表中的步驟4列中，如果不能直接可達，則記錄為∞。如果不可達，可從前一列中移植過來。
可得出最短路徑為
步驟5：已知集合S：v0，v1，v2，v3，v7。
未知集合T：v4，v5，v6，v8，v9。
求出經v7節點直接可達的未知集合中各節點的距離，填在最終結果表中的步驟5列中。
可得出最短路徑為
步驟6：已知集合S：v0，v1，v2，v3，v7，v4。
未知集合T：v5，v6，v8，v9。
求出經v4節點直接可達的未知集合中各節點的距離，填在最終結果表中的步驟6列中。
可得出最短路徑為
步驟7：已知集合S：v0，v1，v2，v3，v7，v4，v5。
未知集合T：v6，v8，v9。
求出經v5節點直接可達的未知集合中各節點的距離，填在最終結果表中的步驟7列中。
可得出最短路徑為
步驟8：已知集合S：v0，v1，v2，v3，v7，v4，v5，v8。
未知集合T：v6，v9。
求出經v8節點直接可達的未知集合中各節點的距離，填在最終結果表中的步驟8列中。
可得出最短路徑為
步驟9：已知集合S：v0，v1，v2，v3，v7，v4，v5，v8，v6。
未知集合T：v9。
求出經v6節點直接可達的未知集合中各節點的距離，填在最終結果表中的步驟9列中。
可得出最短路徑為
從最終結果表的最后一行vj行中，可得到從v0出發點，到可達的各個需求點的最短路徑。
2.5 ?選擇結論
經過最短路徑求解——Dijkstra算法的求解，得到配送節點v0至各節點的最短路徑以及所經過的節點分別為：
從v0出發至v1節點：
從v0出發至v2節點：
從v0出發至v3節點：
從v0出發至v4節點：
從v0出發至v5節點：
從v0出發至v6節點：
從v0出發至v7節點：
從v0出發至v8節點：
從v0出發至v9節點：
求出配送點至需求點的最短路徑后，可生成一張最短路徑表，并將該路徑表存入系統內，當配送路線出現故障或阻塞后，可重新生成最短路徑，更新最短路徑表。下次配送時可直接查表選擇最短路徑節點進行配送，提升配送效率。
3 ?結 ?論
本文通過針對城市中二級配送節點進行配送時的節點選擇進行建模，并使用最短路徑算法——Dijkstra算法，對模型數據進行了分析。通過分析，可以得到從配送節點出發，到可達的每一個需求點的最短路徑，以及該路徑所經過的中間節點。此外，提出路徑緩存的概念，將已計算的最短路徑存儲為最短路徑表，提升路徑選擇的效率。該方法適用于針對任何二級節點進行配送時的節點選擇問題。
參考文獻：
[1] 吳曉釗，王繼祥.物聯網技術在物流業的應用現狀與發展前景 [J].物流技術與應用，2011，16（2）：53-56+59.
[2] 王繼祥.物聯網發展推動中國智慧物流變革 [J].物流技術與應用，2010，15（6）：30-35.
[3] 王蘇林，邱菲爾，陳凡，等.基于貪心遺傳的地下物流節點選擇規劃研究 [J].工業工程，2020，23（5）：88-95.
[4] 何永貴，周穎.基于成本優化的城市地下物流節點選址研究 [J].管理現代化，2018，38（6）：66-69.
[5] 方龍祥，于雪雨.基于貪心算法的城市地下物流系統網絡節點選址 [J].巢湖學院學報，2019，21（6）：51-58.
[6] 方龍祥，于雪雨.基于0-1整數規劃算法的城市地下物流系統網絡節點選址 [J].安徽工程大學學報，2019，34（5）：53-58.
[7] 李姍珊，劉延君，秦宇豪，等.基于地下管道物流運輸的軌道線網規劃與線路設計研究 [J].中國管理信息化，2019，22（14）：92-93.
[8] 李健.基于Dijkstra最短路徑算法的優化研究 [J].渭南師范學院學報，2009，24（5）：61-64.
[9] 鄒佰翰，張吉懿，苑曉兵.最短路徑算法在計算機網絡路由選擇中的應用研究 [J].電聲技術，2020，44（2）：59-60+70.
作者簡介：周冰（1981—），男，漢族，河南溫縣人，副教授，碩士，研究方向：智慧城市、計算機應用。
