基于Dijkstra算法的城市物流公交系統(tǒng)優(yōu)化

王樹梅，黃 石，臧禹順

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

0 引 言

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

基于以上問題，許多專家提出了諸多物流路徑優(yōu)化算法[1-9]。文獻(xiàn)[10]提出了基于蟻群算法的物流配送路徑優(yōu)化算法，以成本最小化和最大限度減少碳排放量構(gòu)建了一種路徑規(guī)劃多目標(biāo)優(yōu)化模型。文獻(xiàn)[11]針對冷鏈配送時效性強(qiáng)的特性問題，建立冷鏈配送路徑多目標(biāo)優(yōu)化模型，運用遺傳算法對模型進(jìn)行求解。文獻(xiàn)[12]針對物流領(lǐng)域降低配送成本、提升配送效率的需求，通過數(shù)學(xué)建模的方式，將物流路徑優(yōu)化問題轉(zhuǎn)化為數(shù)學(xué)研究領(lǐng)域經(jīng)典的旅行商問題。文獻(xiàn)[13]結(jié)合客戶的消費行為將客戶分為多個層級，根據(jù)每層級客戶的特點設(shè)置超時懲罰成本，構(gòu)建出基于客戶分類的即時配送路徑優(yōu)化模型。文獻(xiàn)[14]針對航空物流領(lǐng)域?qū)β窂竭M(jìn)行精確計算以降低配送成本的需求，對路徑的優(yōu)化方法進(jìn)行了研究。文獻(xiàn)[15]提出了基于A*算法的民航物流運輸路徑優(yōu)化算法，實現(xiàn)了民航物流路徑的最優(yōu)規(guī)劃。

文中提出了基于移動互聯(lián)網(wǎng)的信息化平臺的物流公交優(yōu)化算法，通過該平臺實現(xiàn)社會物流的信息共享，資源整合，使同一流向的貨物能夠共享運力，提高整體社會物流的效率。為了實現(xiàn)這一信息平臺，在始端的發(fā)貨接貨和末端的送貨收貨，就成為非常關(guān)鍵的環(huán)節(jié)。在整個平臺中，城市物流公交模塊就是為了解決物流系統(tǒng)的兩端而設(shè)計開發(fā)的，該模塊處于對整個社會物流信息的收集及整合的始端，能高效地處理這些數(shù)據(jù)尤為重要。

1 最短路徑問題

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

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

給定帶權(quán)連通無向圖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中各頂點的距離為邊上的權(quán)(若頂點之間 有邊)或∞(頂點之間無邊)。

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

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

(4)判斷j==k，如果是則循環(huán)退出，v到k的最短路徑即求出，否則轉(zhuǎn)(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，則算法結(jié)束，否則轉(zhuǎn)(2).

2 城市物流公交優(yōu)化算法

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

2.1 貨車分配問題

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

這里引入一個利用率(UR)的概念，貨車?yán)寐实挠嬎闩c貨車可載重量(TW)、貨車可載體積(TV)、貨物可載重量(GW)和貨物可載體積(GV)都有關(guān)系。在貨車體積和重量都滿足的前提下，計算貨車的利用率。在計算貨車?yán)寐手埃枰扰袛囿w積是否滿足條件，若不滿足則此車排除，若滿足則再判斷重量是否滿足，若滿足則計算該車?yán)寐剩駝t排除該車。在計算每輛貨車的UR之前，需要判斷貨車的狀態(tài)，設(shè)其狀態(tài)值為1時貨車在用，狀態(tài)值為0時貨車空閑。

(1)

(1)貨車分配問題一。

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

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

(2)

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

圖2 貨車分配問題一模型

(2)貨車分配問題二。

當(dāng)貨車分散在不同的城市，貨物與貨車也不在同一個城市，如何選取貨車進(jìn)行送貨。這類問題模型如圖3所示。這種情況下不但要考慮貨車可載體積和重量，也即是貨車?yán)寐剩€要考慮送貨距離。這里設(shè)定，當(dāng)利用率都大于0時，按照距離遠(yuǎn)近優(yōu)先選取貨車。

圖3 貨車分配問題二模型

貨車T1,T2,…,Tn分別在A1,A2,…,An城市，貨物G在B城市，需要送到C城市。現(xiàn)在從T1,T2,…,Tn中選取一輛貨車進(jìn)行送貨，貨車選取步驟如下：

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

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

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

④在Dk1,Dk2,…,Dkm中找出最小值對應(yīng)的貨車Tp即為最終選車結(jié)果。

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

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

(3)

Dki=Dijkstra(G,Aki,B)

(4)

(3)貨車分配問題三。

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

圖4 貨車分配問題三模型

①當(dāng)貨車狀態(tài)為空閑時，即其狀態(tài)值為0，根據(jù)式(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)的結(jié)果為不同地點的n輛貨車m個貨物的最終分配結(jié)果，這種結(jié)果的前提是首先考慮距離，其次考慮利用率。

2.2 貨車回收問題

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

圖5 貨車回收過程示意圖

3 實驗數(shù)據(jù)分析

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

圖6 城市物流交通網(wǎng)絡(luò)示意圖

(1)貨車分配問題一。

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

(2)貨車分配問題二。

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

(3)貨車分配問題三。

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

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

貨物2在F城市，重量是15噸，體積是30方，需要分配貨車。由于貨車4已被分配給貨物1，所以在剩下的三輛車?yán)镞M(jìn)行選擇。貨車1、貨車2和貨車3相對貨物2的利用率分別是0、0和1.75，從利用率上看只有貨車3滿足條件，選擇利用率大于0的貨車3作為運送貨物2的車，修改貨車3的使用狀態(tài)為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被分配后各項數(shù)據(jù)改變?nèi)绫?所示。

表1 貨車初始化數(shù)據(jù)

表2 貨車分配后的數(shù)據(jù)

(4)貨車回收。

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

表3 貨車回收后的數(shù)據(jù)

4 結(jié)束語

在移動互聯(lián)網(wǎng)背景下，為了提高物流效率，充分利用物流運輸資源，提出了本算法。通過實驗數(shù)據(jù)可以看出，該算法在同地多車一貨、同地多車和異地一貨、異地多車多貨三個貨車分配問題上實現(xiàn)了利用率和距離的優(yōu)化。在系統(tǒng)的接收端，對貨車的及時回收和再使用在貨車回收算法中得到了實現(xiàn)。在后面的研發(fā)過程中，會繼續(xù)優(yōu)化發(fā)送端和接收端之間的協(xié)調(diào)和優(yōu)化，提高平臺的使用效率。