基于Dijkstra算法的城市物流公交系統優化

王樹梅，黃 石，臧禹順

(1.江蘇師范大學 計算機科學與技術學院，江蘇 徐州 221116; 2.山東三四物流服務有限公司，山東 單縣 274300)

0 引 言

隨著國家的產業升級，城鎮化建設，三四線城市逐漸成為生產基地和相對集中的生活中心，每天需要消耗大量的生產資料和生活資料，而產成品又要不斷地運到全國各地，因此對物流運輸服務提出了更高的需求。另一方面，國內物流行業生產力過于分散，最大的物流公司業務占比不到4%的全國物流份額，運輸車輛空返率高，物流行業信息化水平差，除了一些快遞公司的信息化水平基本滿足客戶需求外，普通的物流公司大多數還是處于手工記錄單據的狀態。

基于以上問題，許多專家提出了諸多物流路徑優化算法[1-9]。文獻[10]提出了基于蟻群算法的物流配送路徑優化算法，以成本最小化和最大限度減少碳排放量構建了一種路徑規劃多目標優化模型。文獻[11]針對冷鏈配送時效性強的特性問題，建立冷鏈配送路徑多目標優化模型，運用遺傳算法對模型進行求解。文獻[12]針對物流領域降低配送成本、提升配送效率的需求，通過數學建模的方式，將物流路徑優化問題轉化為數學研究領域經典的旅行商問題。文獻[13]結合客戶的消費行為將客戶分為多個層級，根據每層級客戶的特點設置超時懲罰成本，構建出基于客戶分類的即時配送路徑優化模型。文獻[14]針對航空物流領域對路徑進行精確計算以降低配送成本的需求，對路徑的優化方法進行了研究。文獻[15]提出了基于A*算法的民航物流運輸路徑優化算法，實現了民航物流路徑的最優規劃。

文中提出了基于移動互聯網的信息化平臺的物流公交優化算法，通過該平臺實現社會物流的信息共享，資源整合，使同一流向的貨物能夠共享運力，提高整體社會物流的效率。為了實現這一信息平臺，在始端的發貨接貨和末端的送貨收貨，就成為非常關鍵的環節。在整個平臺中，城市物流公交模塊就是為了解決物流系統的兩端而設計開發的，該模塊處于對整個社會物流信息的收集及整合的始端，能高效地處理這些數據尤為重要。

1 最短路徑問題

交通運輸網絡可以表示為一個帶權圖，用圖的頂點表示城市，用圖的邊表示城市之間的交通運輸路線，各邊的權值表示該路線的長度或沿此路線運輸所需要的時間或運費等。傳統意義上的單源最短路徑問題是基于有向帶權圖所表示的交通網絡，文中對此算法稍作修改，可以適用于帶權無向連通圖，且在參數里設置了起點和終點，函數返回兩點之間的最短距離。根據修改后的最短路徑算法，輸入任意兩個頂點的信息即可求出它們之間的最短距離或者最小代價。

數據結構[16]上也有一多源多目標FLOYD算法，這個算法通過兩個循環嵌套將所有頂點之間的最短路徑計算出來，這個算法的時間復雜度為O(n3)，算法效率較低。這個算法也可以滿足文中物流最短路徑的需求，但事實上物流最短路徑需要的是當前兩個城市之間的最短路徑，不需要將其他所有城市的最短路徑都求出來。因此，文中對Dijkstra算法進行修改，圖是帶權無向連通圖，權是城市之間的距離，輸入圖中任意兩個頂點，輸出兩個頂點的最短距離以及最短路徑。具體步驟如下：

給定帶權連通無向圖Graph(V,E)，v和k是圖G的兩個頂點，下面是求圖G中v和k之間的最短路徑算法Dijkstra(G,v,k)。

(1)初始時，頂點集合S只包含頂點v，即S={v},v到自己的距離為0。頂點集合U包含除v以外的其他頂點，k在集合U中，v到U中各頂點的距離為邊上的權(若頂點之間 有邊)或∞(頂點之間無邊)。

(2)從U中選取一個頂點u，它是v到U中距離最小的一個頂點，然后把頂點u加入到S中。

(3)以頂點u為新考慮的中間點，修改v到U中各頂點j(j∈U)的距離，若從v到j經過u的距離(圖1中為cvu+wuj)比原來不經過頂點u的距離(圖1中為cvj)更短，則修改v到j的最短距離值(圖1中修改為cvu+wuj)。

(4)判斷j==k，如果是則循環退出，v到k的最短路徑即求出，否則轉(2)。

圖1 頂點v到頂點j的路徑比較

偽代碼描述如下：

(1)初始化：S←{v}；

dist[j]←Edge[v][j]，j為除v以外的其他頂點,j∈V-S;

Edge[][]為圖G的鄰接矩陣。

(2)求出最短路徑的長度：dist[u]←min{dist[j]}，j∈V-S;

S←S∪{u};

(3)修改：dist[j]←{dist[j],dist[u]+Edge[u][j]}，對于每一個j∈V-S;

(4)判斷：若j=k，則算法結束，否則轉(2).

2 城市物流公交優化算法

城市物流公交是將位于不同城市的物流信息進行共享，物流資源進行優化使用，達到節約成本的目的。本模塊算法包括兩個部分，分別是貨車分配和貨車回收。

2.1 貨車分配問題

貨車分配問題分為三種情況，一是所有貨車Ti(1≤i≤n)和貨物G都在同一個城市，根據現有貨車的可載重量和可載體積進行資源利用最大化分配送貨車。二是貨車分散在不同的城市，貨物在其中一個城市，在這種情況下除了考慮貨車的可載重量和可載體積以外，還要將貨車送貨的距離考慮在內。三是貨車分布在不同城市，貨物也分布在不同城市，這是一種比較復雜的情況，在重量和體積都滿足的前提下，距離近的貨車優先被選中。

這里引入一個利用率(UR)的概念，貨車利用率的計算與貨車可載重量(TW)、貨車可載體積(TV)、貨物可載重量(GW)和貨物可載體積(GV)都有關系。在貨車體積和重量都滿足的前提下，計算貨車的利用率。在計算貨車利用率之前，需要先判斷體積是否滿足條件，若不滿足則此車排除，若滿足則再判斷重量是否滿足，若滿足則計算該車利用率，否則排除該車。在計算每輛貨車的UR之前，需要判斷貨車的狀態，設其狀態值為1時貨車在用，狀態值為0時貨車空閑。

(1)

(1)貨車分配問題一。

這種情況是比較簡單的一種，貨車和貨物均在同一城市，需要計算各個貨車利用率，選取利用率最大的貨車即可。如圖2所示，UR1,UR2,…,URn分別為貨車T1,T2,…,Tn根據式(1)計算出來的利用率，當體積或重量不滿足條件時，利用率為0。

URmax=MAX{UR1,UR2,…,URn}

(2)

設Ti的利用率最大，則第i輛貨車被選中作為送貨車送貨。

圖2 貨車分配問題一模型

(2)貨車分配問題二。

當貨車分散在不同的城市，貨物與貨車也不在同一個城市，如何選取貨車進行送貨。這類問題模型如圖3所示。這種情況下不但要考慮貨車可載體積和重量，也即是貨車利用率，還要考慮送貨距離。這里設定，當利用率都大于0時，按照距離遠近優先選取貨車。

圖3 貨車分配問題二模型

貨車T1,T2,…,Tn分別在A1,A2,…,An城市，貨物G在B城市，需要送到C城市?，F在從T1,T2,…,Tn中選取一輛貨車進行送貨，貨車選取步驟如下：

①當貨車狀態值為0時，根據式(1)貨物的重量和體積計算出每輛貨車的利用率UR1,UR2,…,URn；

②在所有利用率UR中挑選出利用率大于0的貨車Tk1,Tk2,…,Tkm；

③利用式(4)計算貨車Tk1,Tk2,…,Tkm到貨物的最短路徑距離Dk1,Dk2,…,Dkm；

④在Dk1,Dk2,…,Dkm中找出最小值對應的貨車Tp即為最終選車結果。

設Tk1,Tk2,…,Tkm的利用率大于0，在計算貨車和貨物之間的距離時，利用改進后的Dijkstra算法求出各個貨車到貨物的最短路徑長度Dk1,Dk2,…,Dkm。

Dmin=MIN{Dk1,Dk2,…,Dkm}

(3)

Dki=Dijkstra(G,Aki,B)

(4)

(3)貨車分配問題三。

這種情況下貨車和貨物都在不同的城市，如何給每一個貨物分配到最合適的貨車。這種問題模型如圖4所示。這是一種比較復雜的情況，這里采取的方案先構造利用率矩陣，在矩陣中尋找利用率大于0的貨車，再在這些貨車中計算最小路徑矩陣，具體步驟如下:

圖4 貨車分配問題三模型

①當貨車狀態為空閑時，即其狀態值為0，根據式(1)計算利用率矩陣UMn*m，其中URij為貨車Ti(1≤i≤n)與貨物Gj(1≤j≤m)之間的利用率。

(5)

② If(URij>0)，計算Dij(Dij為Ai到Bj的最短路徑長度)，否則，Dij=∞，得到矩陣Dn*m：

(6)

③計算矩陣Dn*m的第j列的最小值：MDj=MIN{Dij,1≤i≤n} =Dpj，則給貨車Tp分配的貨物是Gj。最短路徑長度最小值向量為：

MD={MD1,MD2,…,MDm}

(7)

式(7)的結果為不同地點的n輛貨車m個貨物的最終分配結果，這種結果的前提是首先考慮距離，其次考慮利用率。

2.2 貨車回收問題

系統里貨車信息包括貨車的編號、可載重量、可載體積、出發地、目的地和狀態，貨車在使用過程中，這些關鍵字的值都會發生變化，狀態值為1。使用完畢需要在系統里對貨車信息進行初始化，也即是貨車的回收，將貨車的狀態值State改為0，可載重量TW和可載體積TV改為初始值。這里需要注意的是，為了提高貨車的利用率UR，回收貨車時，將其目的地End改為出發地Start，這樣避免了貨車跑空車，就可以在目的地再次為貨車分配貨源，提高了貨車的使用率。貨車的回收過程如圖5所示。

圖5 貨車回收過程示意圖

3 實驗數據分析

以圖6城市物流交通網絡示意圖為例，測試以下貨車分配和回收算法。貨車1-4的可載重量分別是6噸、11噸、15噸和19噸，可載體積分別是15方、30方、40方和50方。貨物1-3的重量分別是10噸、15噸和5噸，體積分別為25方、30方和13方。

圖6 城市物流交通網絡示意圖

(1)貨車分配問題一。

貨車1、貨車2、貨車3和貨物1均在A城市，現在從三輛貨車里選出一輛運送貨物1。這種情況只需計算三輛車相對貨物的利用率，選擇利用率最大的車。三輛車的利用率分別是0、1.74和1.29，利用率最大的是貨車2，所以對貨物1分配的車是貨車2。

(2)貨車分配問題二。

貨車1、貨車2、貨車3和貨物1分別在A、B、C、D城市，從三輛貨車里選出一輛運送貨物1。三輛車的利用率分別是0、1.74、1.29，也即是只有貨車2和貨車3滿足運送貨物1的條件，而貨車2和貨車3距離貨物1的最短距離分別是170公里和200公里，選擇距離最近的貨車，因此分配貨車2運送貨物1。

(3)貨車分配問題三。

表1是貨車初始化數據，A B C D E F表示6個不同位置的城市。貨車1初始載重量為10噸，可載體積為12方，所在地是A城市。貨車2初始載重量為20噸，可載體積為35方，所在地是B城市。貨車3初始載重量為15噸，可載體積為21方，所在地是C城市。貨車4初始載重量為30噸，可載體積為35方，所在地是D城市。

現在貨物1在E城市，利用式(1)分別計算出各個貨車相對貨物1的利用率，分別是0、1.74、1.29、1.02，也即是貨車2-4都滿足條件。再采用Dijkstra算法計算出貨車2-4至貨物1的最短距離，分別是70公里、90公里和30公里。綜合利用率和距離數據，在利用率都滿足條件的前提下，選擇距離最近的貨車，因此選擇貨車4作為運送貨物1的車。貨車4被選上后，修改其使用狀態為1，并且再計算其他貨物的利用率時自動為0，距離自動為∞。

貨物2在F城市，重量是15噸，體積是30方，需要分配貨車。由于貨車4已被分配給貨物1，所以在剩下的三輛車里進行選擇。貨車1、貨車2和貨車3相對貨物2的利用率分別是0、0和1.75，從利用率上看只有貨車3滿足條件，選擇利用率大于0的貨車3作為運送貨物2的車，修改貨車3的使用狀態為1。

貨物3在E城市，重量是5噸，體積是13方。由于貨車3和貨車4已分配出去，剩下貨車1和貨車2。貨車1和貨車2相對貨物3的利用率分別是1.70和0.88，最短距離是20公里和70公里。貨車1的利用率較大，而且距離貨物3最近，所以選擇貨車1作為運送貨物3的車。貨車1、3、4被分配后各項數據改變如表2所示。

表1 貨車初始化數據

表2 貨車分配后的數據

(4)貨車回收。

對表2中的貨車1、3、4進行回收，經確認貨物已送達目的地后，對三輛車進行回收，回收后的各輛貨車各項數據進行修改。修改后的數據如表3所示，貨車1、3、4的可載重量恢復到初始狀態，貨車使用狀態值均改為0，起點和終點均是各輛貨車送達貨物的城市，距離也初始化為0。通過對貨車的回收，可以使貨車及時被再次使用。

表3 貨車回收后的數據

4 結束語

在移動互聯網背景下，為了提高物流效率，充分利用物流運輸資源，提出了本算法。通過實驗數據可以看出，該算法在同地多車一貨、同地多車和異地一貨、異地多車多貨三個貨車分配問題上實現了利用率和距離的優化。在系統的接收端，對貨車的及時回收和再使用在貨車回收算法中得到了實現。在后面的研發過程中，會繼續優化發送端和接收端之間的協調和優化，提高平臺的使用效率。