王樹梅，黃 石，臧禹順

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

0 引 言

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

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

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

1 最短路徑問題

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

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

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

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

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

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

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

圖1 頂點(diǎn)v到頂點(diǎn)j的路徑比較

偽代碼描述如下：

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

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

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

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

S←S∪{u};

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

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

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

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

2.1 貨車分配問題

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

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

(1)

(1)貨車分配問題一。

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

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

(2)

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

圖2 貨車分配問題一模型

(2)貨車分配問題二。

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

圖3 貨車分配問題二模型

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

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

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

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

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

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

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

(3)

Dki=Dijkstra(G,Aki,B)

(4)

(3)貨車分配問題三。

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

圖4 貨車分配問題三模型

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

(5)

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

(6)

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

MD={MD1,MD2,…,MDm}

(7)

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

2.2 貨車回收問題

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

圖5 貨車回收過程示意圖

3 實(shí)驗(yàn)數(shù)據(jù)分析

以圖6城市物流交通網(wǎng)絡(luò)示意圖為例，測(cè)試以下貨車分配和回收算法。貨車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出一輛運(yùn)送貨物1。這種情況只需計(jì)算三輛車相對(duì)貨物的利用率，選擇利用率最大的車。三輛車的利用率分別是0、1.74和1.29，利用率最大的是貨車2，所以對(duì)貨物1分配的車是貨車2。

(2)貨車分配問題二。

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

(3)貨車分配問題三。

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

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

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

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

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

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

(4)貨車回收。

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

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

4 結(jié)束語

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