周冰 盧貝

摘 ?要：電商產(chǎn)業(yè)的崛起帶動(dòng)了物流行業(yè)的發(fā)展，雖然如今的物流行業(yè)已有了質(zhì)的提升，但由此帶來(lái)的問題也日益凸顯，路上的車輛越來(lái)越多，越來(lái)越擁堵。地下物流系統(tǒng)的發(fā)展能有效解決此類問題，同時(shí)也符合社會(huì)可持續(xù)發(fā)展的需求。該文主要使用Dijkstra算法，對(duì)物流配送路徑及節(jié)點(diǎn)的選擇進(jìn)行建模分析，求解出配送結(jié)點(diǎn)至各需求點(diǎn)的最短路徑及所經(jīng)結(jié)點(diǎn)，針對(duì)物流節(jié)點(diǎn)的選擇提供一種行之有效的解決方法。

關(guān)鍵詞：城市地下物流;最短路徑算法;Dijkstra

中圖分類號(hào)：TP391;F252 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 ?引 ?言

本文依托“新型智慧城市建設(shè)背景下新一代物流體系的研究與應(yīng)用”項(xiàng)目，基于對(duì)城市未來(lái)發(fā)展的展望和預(yù)測(cè)，構(gòu)建新一代智慧物流系統(tǒng)的架構(gòu)和體系仿真運(yùn)行模型，研究地下物流節(jié)點(diǎn)選取及配送路徑優(yōu)化。地下物流系統(tǒng)是新一代的智慧物流系統(tǒng)，它是將地面物流系統(tǒng)與地下物流系統(tǒng)整合，形成一種更高效、更環(huán)保、更節(jié)省物理資源的物流系統(tǒng)。發(fā)展地下物流系統(tǒng)，能有效地緩解城市交通的擁堵，實(shí)現(xiàn)城市的可持續(xù)發(fā)展。將城市地下物流系統(tǒng)從網(wǎng)絡(luò)層級(jí)上分為二級(jí)網(wǎng)絡(luò)，并從二級(jí)配送節(jié)點(diǎn)出發(fā)，將貨物至需求點(diǎn)所經(jīng)過的路徑及節(jié)點(diǎn)的選擇進(jìn)行了建模分析，通過求解，得到二級(jí)配送節(jié)點(diǎn)到覆蓋范圍內(nèi)每個(gè)需求點(diǎn)的最短路徑及所經(jīng)節(jié)點(diǎn)。

1 ?地下物流系統(tǒng)整體設(shè)計(jì)

要加強(qiáng)數(shù)字化、信息化的建設(shè)，整體規(guī)劃物流信息管理系統(tǒng)。對(duì)每一個(gè)物流中心、每一個(gè)配送節(jié)點(diǎn)、每一個(gè)轉(zhuǎn)運(yùn)點(diǎn)進(jìn)行統(tǒng)一標(biāo)準(zhǔn)格式的編碼，便于貨物的流轉(zhuǎn)（包括節(jié)點(diǎn)的選取和路徑的選擇）。對(duì)物流中心、配送節(jié)點(diǎn)、轉(zhuǎn)運(yùn)點(diǎn)的編碼要有明顯的字段，標(biāo)識(shí)節(jié)點(diǎn)的不同類型，對(duì)于不同的省市區(qū)的節(jié)點(diǎn)進(jìn)行編碼也要有標(biāo)識(shí)字段用于區(qū)分。此外還要大力推動(dòng)“一單、一碼、一單元”[1]，避免如今“四通一達(dá)”、菜鳥、順豐、京東、極兔等物流各自為戰(zhàn)，各自都有一套自己的物流系統(tǒng)，信息交流不通暢，導(dǎo)致重復(fù)建設(shè)，資源浪費(fèi)。

將每一個(gè)標(biāo)準(zhǔn)的物流包裹統(tǒng)一規(guī)劃為物流單元，每個(gè)物流單元都會(huì)被分配一個(gè)唯一的“數(shù)字身份證”，也就是一碼。每個(gè)物流單元都會(huì)被分配一個(gè)標(biāo)準(zhǔn)的電子貨單（數(shù)字通行證），也就是一單，實(shí)現(xiàn)物流與信息流的融合，形成數(shù)字化物流網(wǎng)絡(luò)。

整個(gè)城市地下物流系統(tǒng)的硬件組成部分，主要包括具體的物流中心、配送節(jié)點(diǎn)，支撐系統(tǒng)運(yùn)行的自動(dòng)分揀系統(tǒng)、存儲(chǔ)系統(tǒng)、集散系統(tǒng)等，以及地下物流管道、社區(qū)配送裝置等。

城市地下物流系統(tǒng)從網(wǎng)絡(luò)層級(jí)上劃分，可分為兩級(jí)，一級(jí)為物流中心，二級(jí)為配送結(jié)點(diǎn)。兩組一樣的層級(jí)劃分，每級(jí)之間都可進(jìn)行關(guān)聯(lián)轉(zhuǎn)運(yùn)，如圖1所示。

第一級(jí)為物流中心。規(guī)模龐大，負(fù)責(zé)各種包裹的分發(fā)轉(zhuǎn)運(yùn)。該物流中心可與其他城市物流中心對(duì)接，連接成網(wǎng)。物流中心與下一級(jí)的配送節(jié)點(diǎn)相連，使用地下物流傳輸貨物。

第二級(jí)為配送節(jié)點(diǎn)。配送節(jié)點(diǎn)與各個(gè)小區(qū)、商業(yè)聚集區(qū)、產(chǎn)業(yè)園直接或間接相連，使用地下物流系統(tǒng)傳輸貨物，并可通過社區(qū)配送管道直達(dá)用戶門口，如圖2所示。

地下物流傳輸還可以從以下方面進(jìn)行優(yōu)化。每個(gè)物流單元可配置物聯(lián)網(wǎng)芯片[2]，實(shí)現(xiàn)實(shí)時(shí)定位、采集該單元的位置信息。地下物流管道應(yīng)采用雙通道設(shè)計(jì)，雙向傳輸，可進(jìn)行物流配送，亦可實(shí)現(xiàn)物流收件。地下物流管道加設(shè)可尋址的信號(hào)傳輸裝置，方便發(fā)現(xiàn)故障、定位故障、解決故障。地下物流系統(tǒng)加入流量控制算法和擁塞處理算法，便于動(dòng)態(tài)規(guī)劃，提升物流傳輸效率。

2 ?網(wǎng)絡(luò)節(jié)點(diǎn)選擇

目前已有很多專家和學(xué)者對(duì)地下物流節(jié)點(diǎn)的選取進(jìn)行了研究，王蘇林等使用貪心遺傳算法對(duì)地下物流節(jié)點(diǎn)的選擇規(guī)劃進(jìn)行了研究[3]，何永貴使用基于成本優(yōu)化的算法對(duì)城市地下物流節(jié)點(diǎn)選址進(jìn)行了研究[4]，方龍祥分別使用基于貪心算法[5]和0～1整數(shù)規(guī)劃算法對(duì)城市地下物流系統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)選址進(jìn)行了研究[6]，李?yuàn)櫳菏褂没诘叵鹿艿牢锪鬟\(yùn)輸?shù)能壍谰€網(wǎng)規(guī)劃與線路設(shè)計(jì)研究[7]。本文采用求解最短路徑的經(jīng)典算法——Dijkstra算法對(duì)配送過程中路徑節(jié)點(diǎn)的選擇進(jìn)行了分析研究，實(shí)現(xiàn)了最短配送路徑的求解。

2.1 ?網(wǎng)絡(luò)節(jié)點(diǎn)選取背景

城市地下物流系統(tǒng)主要由一級(jí)物流中心、二級(jí)配送節(jié)點(diǎn)和各節(jié)點(diǎn)間的地下運(yùn)輸管道構(gòu)成。一級(jí)節(jié)點(diǎn)之間互通互達(dá)，形成網(wǎng)絡(luò)，并可相互之間傳輸貨物。二級(jí)節(jié)點(diǎn)只與本區(qū)域的上級(jí)節(jié)點(diǎn)相連。二級(jí)節(jié)點(diǎn)與貨物需求點(diǎn)直接相連或經(jīng)轉(zhuǎn)運(yùn)點(diǎn)間接相連。由于需求末端錯(cuò)綜復(fù)雜，地下物流管道的布置不可能都與二級(jí)節(jié)點(diǎn)直接相連，如圖3中的節(jié)點(diǎn)，二級(jí)節(jié)點(diǎn)0，要為需求點(diǎn)4配送貨物，可能的配送路線經(jīng)過了節(jié)點(diǎn)1、節(jié)點(diǎn)2、節(jié)點(diǎn)3，然后到達(dá)需求點(diǎn)4，我們稱節(jié)點(diǎn)1、節(jié)點(diǎn)2、節(jié)點(diǎn)3為轉(zhuǎn)運(yùn)點(diǎn)，也叫路徑節(jié)點(diǎn)。

城市的需求點(diǎn)非常多，分布多集中在小區(qū)，商業(yè)聚集區(qū)等。本文研究的網(wǎng)絡(luò)節(jié)點(diǎn)選取是在已知需求點(diǎn)和配送節(jié)點(diǎn)具體位置的情況下，如何選取合適的節(jié)點(diǎn)，實(shí)現(xiàn)最高的貨物運(yùn)轉(zhuǎn)效率。由于使用地下物流傳輸系統(tǒng)進(jìn)行傳輸，我們可以不必考慮堵車等其他因素造成的系統(tǒng)擁堵情況，那么最核心的問題就是如何在眾多的網(wǎng)絡(luò)節(jié)點(diǎn)中，查找出一個(gè)配送節(jié)點(diǎn)到需求點(diǎn)的最短路徑。

2.2 ?數(shù)據(jù)來(lái)源

我們對(duì)鄭州市的地下物流節(jié)點(diǎn)進(jìn)行了設(shè)計(jì)，并從地圖上選取0至9共10個(gè)節(jié)點(diǎn)，其中節(jié)點(diǎn)0為二級(jí)配送節(jié)點(diǎn)，節(jié)點(diǎn)1至9為需求節(jié)點(diǎn)，并且對(duì)各個(gè)節(jié)點(diǎn)間的距離通過地圖測(cè)量工具進(jìn)行了測(cè)量，單位為km，如圖3所示。

2.3 ?Dijkstra最短路徑建模

李健對(duì)Dijkstra最短路徑算法進(jìn)行了研究并優(yōu)化了該算法[8]，鄒佰翰等人研究了最短路徑算法在計(jì)算機(jī)網(wǎng)絡(luò)路由選擇中使用[9]。我們也使用Dijkstra算法對(duì)圖3所示節(jié)點(diǎn)進(jìn)行了建模分析。由圖3可得到如圖4所示的路徑圖。每條線都可以雙向傳輸，實(shí)現(xiàn)貨物的發(fā)件收件?，F(xiàn)對(duì)貨物的派發(fā)進(jìn)行模擬求解，分別求出配送節(jié)點(diǎn)0至其他各需求節(jié)點(diǎn)的最短路徑（至最終節(jié)點(diǎn)9結(jié)束）。如果是收件，用同樣的方法亦可求解。

2.4 ?求解

求從節(jié)點(diǎn)0出發(fā)至終點(diǎn)節(jié)點(diǎn)9的最短路徑。如表1所示，每一列為當(dāng)前步驟最短路徑求解結(jié)果，每經(jīng)一個(gè)步驟，都能求出當(dāng)前一步所對(duì)應(yīng)的最短路徑及所經(jīng)節(jié)點(diǎn)，最后一行vj就是該步驟所選中的最短路徑的結(jié)果。表格中的短橫線“----”表示，已經(jīng)求解出至該節(jié)點(diǎn)的最短路徑，并添加至已知結(jié)點(diǎn)內(nèi)，不用再計(jì)算該節(jié)點(diǎn)。

求解過程：設(shè)有已知集合S、未知集合T，初始情況S僅有v0節(jié)點(diǎn)，其余節(jié)點(diǎn)都在未知集合T里。從v0節(jié)點(diǎn)開始，一步一步求解能達(dá)到的最近的節(jié)點(diǎn)。最終可求出v0到其他各節(jié)點(diǎn)的最短路徑。

步驟1：已知集合S：v0。

未知集合T：v1，v2，v3，v4，v5，v6，v7，v8，v9。

求出從v0節(jié)點(diǎn)出發(fā)到能直接可達(dá)的各節(jié)點(diǎn)的距離，將其填在最終結(jié)果表中的步驟1列中，如果不能直接可達(dá)，則記錄為∞。

可得出最短路徑為，選出了v1節(jié)點(diǎn)，將該節(jié)點(diǎn)移入已知節(jié)點(diǎn)S中，同時(shí)將該節(jié)點(diǎn)從未知節(jié)點(diǎn)T中移除。

步驟2：已知集合S：v0，v1。

未知集合T：v2，v3，v4，v5，v6，v7，v8，v9。

以v1節(jié)點(diǎn)為中間節(jié)點(diǎn)，求出從v0節(jié)點(diǎn)出發(fā)經(jīng)v1節(jié)點(diǎn)到能直接可達(dá)的未知節(jié)點(diǎn)集合T中各節(jié)點(diǎn)的距離，填在最終結(jié)果表中的步驟2列中，如果不能直接可達(dá)，則記錄為∞。由于v1節(jié)點(diǎn)已在已知節(jié)點(diǎn)中，不用重新計(jì)算，直接加上“----”符號(hào)，作為不再計(jì)算的標(biāo)記。如果從v0出發(fā)，經(jīng)過中間節(jié)點(diǎn)v1，去未知節(jié)點(diǎn)中尋找，如果也不可達(dá)，把前一列的結(jié)果移入當(dāng)前單元格內(nèi)。

按上述規(guī)則，求解可達(dá)的每一個(gè)未知節(jié)點(diǎn)的距離。

可得出最短路徑為，選出了v2節(jié)點(diǎn)，將該節(jié)點(diǎn)移入已知節(jié)點(diǎn)S中，同時(shí)將該節(jié)點(diǎn)從未知節(jié)點(diǎn)T中移除。

步驟3：已知集合S：v0，v1，v2。

未知集合T：v3，v4，v5，v6，v7，v8，v9。

求出經(jīng)v2節(jié)點(diǎn)直接可達(dá)的未知集合中各節(jié)點(diǎn)的距離，填在最終結(jié)果表中的步驟3列中，如果不能直接可達(dá)，則記錄為∞。如果不可達(dá)，可從前一列中移植過來(lái)。

可得出最短路徑為，選出了v3節(jié)點(diǎn)，將該節(jié)點(diǎn)移入已知節(jié)點(diǎn)S中，同時(shí)將該節(jié)點(diǎn)從未知節(jié)點(diǎn)T中移除。

步驟4：已知集合S：v0，v1，v2，v3。

未知集合T：v4，v5，v6，v7，v8，v9。

求出經(jīng)v3節(jié)點(diǎn)直接可達(dá)的未知集合中各節(jié)點(diǎn)的距離，填在最終結(jié)果表中的步驟4列中，如果不能直接可達(dá)，則記錄為∞。如果不可達(dá)，可從前一列中移植過來(lái)。

可得出最短路徑為，選出了v7節(jié)點(diǎn)，將該節(jié)點(diǎn)移入已知節(jié)點(diǎn)S中，同時(shí)將該節(jié)點(diǎn)從未知節(jié)點(diǎn)T中移除。

步驟5：已知集合S：v0，v1，v2，v3，v7。

未知集合T：v4，v5，v6，v8，v9。

求出經(jīng)v7節(jié)點(diǎn)直接可達(dá)的未知集合中各節(jié)點(diǎn)的距離，填在最終結(jié)果表中的步驟5列中。

可得出最短路徑為，選出了v4節(jié)點(diǎn)，將該節(jié)點(diǎn)移入已知節(jié)點(diǎn)S中，同時(shí)將該節(jié)點(diǎn)從未知節(jié)點(diǎn)T中移除。

步驟6：已知集合S：v0，v1，v2，v3，v7，v4。

未知集合T：v5，v6，v8，v9。

求出經(jīng)v4節(jié)點(diǎn)直接可達(dá)的未知集合中各節(jié)點(diǎn)的距離，填在最終結(jié)果表中的步驟6列中。

可得出最短路徑為，選出了v5節(jié)點(diǎn)，將該節(jié)點(diǎn)移入已知節(jié)點(diǎn)S中，同時(shí)將該節(jié)點(diǎn)從未知節(jié)點(diǎn)T中移除。

步驟7：已知集合S：v0，v1，v2，v3，v7，v4，v5。

未知集合T：v6，v8，v9。

求出經(jīng)v5節(jié)點(diǎn)直接可達(dá)的未知集合中各節(jié)點(diǎn)的距離，填在最終結(jié)果表中的步驟7列中。

可得出最短路徑為，選出了v8節(jié)點(diǎn)，將該節(jié)點(diǎn)移入已知節(jié)點(diǎn)S中，同時(shí)將該節(jié)點(diǎn)從未知節(jié)點(diǎn)T中移除。

步驟8：已知集合S：v0，v1，v2，v3，v7，v4，v5，v8。

未知集合T：v6，v9。

求出經(jīng)v8節(jié)點(diǎn)直接可達(dá)的未知集合中各節(jié)點(diǎn)的距離，填在最終結(jié)果表中的步驟8列中。

可得出最短路徑為，選出了v6節(jié)點(diǎn)，將該節(jié)點(diǎn)移入已知節(jié)點(diǎn)S中，同時(shí)將該節(jié)點(diǎn)從未知節(jié)點(diǎn)T中移除。

步驟9：已知集合S：v0，v1，v2，v3，v7，v4，v5，v8，v6。

未知集合T：v9。

求出經(jīng)v6節(jié)點(diǎn)直接可達(dá)的未知集合中各節(jié)點(diǎn)的距離，填在最終結(jié)果表中的步驟9列中。

可得出最短路徑為，到達(dá)終點(diǎn)v9節(jié)點(diǎn)，求解結(jié)束。

從最終結(jié)果表的最后一行vj行中，可得到從v0出發(fā)點(diǎn)，到可達(dá)的各個(gè)需求點(diǎn)的最短路徑。

2.5 ?選擇結(jié)論

經(jīng)過最短路徑求解——Dijkstra算法的求解，得到配送節(jié)點(diǎn)v0至各節(jié)點(diǎn)的最短路徑以及所經(jīng)過的節(jié)點(diǎn)分別為：

從v0出發(fā)至v1節(jié)點(diǎn)：：6.8。

從v0出發(fā)至v2節(jié)點(diǎn)：：9.2。

從v0出發(fā)至v3節(jié)點(diǎn)：：9.6。

從v0出發(fā)至v4節(jié)點(diǎn)：：13.5。

從v0出發(fā)至v5節(jié)點(diǎn)：：18.1。

從v0出發(fā)至v6節(jié)點(diǎn)：：22.8。

從v0出發(fā)至v7節(jié)點(diǎn)：：10.6。

從v0出發(fā)至v8節(jié)點(diǎn)：：21.1。

從v0出發(fā)至v9節(jié)點(diǎn)：：29.1。

求出配送點(diǎn)至需求點(diǎn)的最短路徑后，可生成一張最短路徑表，并將該路徑表存入系統(tǒng)內(nèi)，當(dāng)配送路線出現(xiàn)故障或阻塞后，可重新生成最短路徑，更新最短路徑表。下次配送時(shí)可直接查表選擇最短路徑節(jié)點(diǎn)進(jìn)行配送，提升配送效率。

3 ?結(jié) ?論

本文通過針對(duì)城市中二級(jí)配送節(jié)點(diǎn)進(jìn)行配送時(shí)的節(jié)點(diǎn)選擇進(jìn)行建模，并使用最短路徑算法——Dijkstra算法，對(duì)模型數(shù)據(jù)進(jìn)行了分析。通過分析，可以得到從配送節(jié)點(diǎn)出發(fā)，到可達(dá)的每一個(gè)需求點(diǎn)的最短路徑，以及該路徑所經(jīng)過的中間節(jié)點(diǎn)。此外，提出路徑緩存的概念，將已計(jì)算的最短路徑存儲(chǔ)為最短路徑表，提升路徑選擇的效率。該方法適用于針對(duì)任何二級(jí)節(jié)點(diǎn)進(jìn)行配送時(shí)的節(jié)點(diǎn)選擇問題。

參考文獻(xiàn)：

[1] 吳曉釗，王繼祥.物聯(lián)網(wǎng)技術(shù)在物流業(yè)的應(yīng)用現(xiàn)狀與發(fā)展前景 [J].物流技術(shù)與應(yīng)用，2011，16（2）：53-56+59.

[2] 王繼祥.物聯(lián)網(wǎng)發(fā)展推動(dòng)中國(guó)智慧物流變革 [J].物流技術(shù)與應(yīng)用，2010，15（6）：30-35.

[3] 王蘇林，邱菲爾，陳凡，等.基于貪心遺傳的地下物流節(jié)點(diǎn)選擇規(guī)劃研究 [J].工業(yè)工程，2020，23（5）：88-95.

[4] 何永貴，周穎.基于成本優(yōu)化的城市地下物流節(jié)點(diǎn)選址研究 [J].管理現(xiàn)代化，2018，38（6）：66-69.

[5] 方龍祥，于雪雨.基于貪心算法的城市地下物流系統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)選址 [J].巢湖學(xué)院學(xué)報(bào)，2019，21（6）：51-58.

[6] 方龍祥，于雪雨.基于0-1整數(shù)規(guī)劃算法的城市地下物流系統(tǒng)網(wǎng)絡(luò)節(jié)點(diǎn)選址 [J].安徽工程大學(xué)學(xué)報(bào)，2019，34（5）：53-58.

[7] 李?yuàn)櫳?，劉延君，秦宇豪，?基于地下管道物流運(yùn)輸?shù)能壍谰€網(wǎng)規(guī)劃與線路設(shè)計(jì)研究 [J].中國(guó)管理信息化，2019，22（14）：92-93.

[8] 李健.基于Dijkstra最短路徑算法的優(yōu)化研究 [J].渭南師范學(xué)院學(xué)報(bào)，2009，24（5）：61-64.

[9] 鄒佰翰，張吉懿，苑曉兵.最短路徑算法在計(jì)算機(jī)網(wǎng)絡(luò)路由選擇中的應(yīng)用研究 [J].電聲技術(shù)，2020，44（2）：59-60+70.

作者簡(jiǎn)介：周冰（1981—），男，漢族，河南溫縣人，副教授，碩士，研究方向：智慧城市、計(jì)算機(jī)應(yīng)用。