基于道路堵塞及顧客時(shí)間要求的快件配送最優(yōu)路徑選擇

樊相宇， 梁日麗， 武小平

(1.西安郵電大學(xué) a.郵政研究院； b.現(xiàn)代郵政學(xué)院，陜西 西安 710061)

0 引言

現(xiàn)如今，網(wǎng)絡(luò)購物已經(jīng)非常普遍，要實(shí)現(xiàn)物品實(shí)體從供給地流向接收地，快遞配送是一個(gè)必不可少的環(huán)節(jié)，不論是干線的配送還是最后一公里的配送，都會(huì)涉及到快遞網(wǎng)絡(luò)。快遞網(wǎng)絡(luò)是快遞配送的基礎(chǔ)，交通網(wǎng)絡(luò)又是快遞網(wǎng)絡(luò)的基礎(chǔ)，目前，由于我國(guó)道路基礎(chǔ)設(shè)施還不夠完善，在配送過程中，經(jīng)常會(huì)存在中斷點(diǎn)、擁堵點(diǎn)等不暢通的點(diǎn)[1]，在確定配送路徑時(shí)，需要繞過這些點(diǎn)，選擇最優(yōu)路徑而不是理論上的最短路徑進(jìn)行配送。

對(duì)于交通網(wǎng)絡(luò)的研究，學(xué)者們提出了最短路的關(guān)鍵邊問題[2]和最長(zhǎng)繞行路關(guān)鍵邊問題[3]，他們給的定義分別為在一個(gè)至少2-Edges連通的網(wǎng)絡(luò)G(V,E)中，至少存在一條邊e*，當(dāng)從G(V,E)中刪除e*時(shí)，使得起點(diǎn)s至終點(diǎn)t的最短路徑長(zhǎng)度增至最大，稱邊e為該最短路徑的關(guān)鍵邊；最長(zhǎng)繞行路關(guān)鍵邊是網(wǎng)絡(luò)上最短路徑上的某條邊，若將其刪除后，從中斷點(diǎn)至終止點(diǎn)的路徑長(zhǎng)度增至最大，關(guān)鍵邊的兩種定義都沒有從全局考慮，也沒有結(jié)合實(shí)際問題，且是一種完全信息下的決策。另一方面，是不完全信息下的實(shí)時(shí)關(guān)鍵邊[4]和關(guān)鍵路徑問題[5～8]，這些內(nèi)容都只是單純的研究關(guān)鍵邊或者關(guān)鍵路徑，沒有將兩者結(jié)合起來。王華[9]、李杰[10]等人將最短路徑算法應(yīng)用到物流配送最短路徑選擇中，受到前人研究的啟發(fā)，文中將關(guān)鍵邊和最優(yōu)路徑結(jié)合起來，針對(duì)快遞“最后一公里”配送，設(shè)計(jì)了發(fā)生道路中斷時(shí)，關(guān)鍵邊及備用路徑的算法。

文中首先研究了完全信息下的最長(zhǎng)繞行路關(guān)鍵邊問題，找到網(wǎng)絡(luò)的關(guān)鍵邊之后，對(duì)關(guān)鍵邊實(shí)時(shí)監(jiān)控，接著研究不完全信息下的最優(yōu)路徑，網(wǎng)絡(luò)原始最短路徑上其他各邊的信息不完全，但關(guān)鍵邊上的信息是完全的，當(dāng)中斷發(fā)生在關(guān)鍵邊之時(shí)，車輛出發(fā)前可獲得道路中斷信息，可從起點(diǎn)處重新選擇路徑，避免出行者遭受最大損失。文中沒有只考慮一條關(guān)鍵路徑，借助k條最短路徑[11]的思想，給出了每條邊中斷后對(duì)應(yīng)的一組備用路徑，選擇運(yùn)輸時(shí)間小于或等于顧客可等待時(shí)間的路徑為有效路徑，考慮網(wǎng)絡(luò)中各邊上商場(chǎng)學(xué)校等場(chǎng)所某時(shí)人流量的情況，從有效路徑中選擇最優(yōu)路徑。

1 快件配送最優(yōu)路徑模型及定義

1.1 快件配送最優(yōu)路徑模型

文中結(jié)合實(shí)際道路網(wǎng)，考慮道路中斷，將實(shí)際交通網(wǎng)絡(luò)抽象為平面網(wǎng)絡(luò)圖，交叉路口為平面網(wǎng)絡(luò)圖的節(jié)點(diǎn)，實(shí)際路段為平面網(wǎng)絡(luò)圖的邊，邊上的權(quán)為實(shí)際路段的行使時(shí)間(道路正常時(shí)行駛的平均時(shí)間)[8]，文中所提的最短路為時(shí)間最短，記交通網(wǎng)絡(luò)平面圖為G(V,E,C)，簡(jiǎn)稱交通網(wǎng)絡(luò)，其中V={S,V1,V2,…,Vn-2,t}為節(jié)點(diǎn)集合，E={e1，e2，…，em}為邊的集合，S表示交通網(wǎng)絡(luò)的起始點(diǎn)(配送中心)，t表示交通網(wǎng)絡(luò)終止點(diǎn)(顧客要求送達(dá)點(diǎn))，m為網(wǎng)絡(luò)中邊的條數(shù)，n為節(jié)點(diǎn)的個(gè)數(shù)，C為邊的權(quán)重。

研究的假設(shè)條件為：

(1) 假設(shè)車輛一直沿著運(yùn)輸方向走，不會(huì)返回，中斷點(diǎn)之前車輛在最短路上行駛，在十字路口處等待綠燈的時(shí)間忽略不計(jì)。即文中研究有向網(wǎng)絡(luò)，若是無向網(wǎng)絡(luò)，可將無向圖的邊轉(zhuǎn)換為同樣邊長(zhǎng)的兩條反向邊。

(2)顧客可等待時(shí)間T為定值(T>hG(s,t))。

(3)車輛行駛到中斷邊的起始點(diǎn)才可獲得道路是否發(fā)生中斷(關(guān)鍵邊除外)。

(4)中斷只發(fā)生在最短路上，且一次只有一條邊中斷。

(5)一個(gè)網(wǎng)絡(luò)圖只考慮有一個(gè)人流量密集的場(chǎng)所(人流量密集場(chǎng)所用F表示)。

若關(guān)鍵邊中斷，整個(gè)配送時(shí)間最長(zhǎng)，為了避免造成顧客不滿意甚至投訴，配送企業(yè)可對(duì)關(guān)鍵邊進(jìn)行實(shí)時(shí)監(jiān)控(如裝置攝像頭)，以便隨時(shí)掌握路況，降低企業(yè)損失。若關(guān)鍵邊出現(xiàn)了中斷，配送人員可以重新選擇從起始點(diǎn)s到終點(diǎn)t的最短路徑，與最短路上的其他邊不同，只有到達(dá)中斷邊的起始點(diǎn)才可獲得道路是否發(fā)生中斷。

1.2 定義

定義1備用路徑：在具有至少2邊連通的網(wǎng)絡(luò)G(V,E)中，最短路徑表示為PG(s,t)，最短路徑上的運(yùn)輸時(shí)間表示為hG(s,t)，設(shè)最短路徑對(duì)應(yīng)的任意一條邊為ex(u,v)(x=1,2…k，k為最短路上邊的條數(shù))，由于突發(fā)事件，邊ex(u,v)發(fā)生中斷，即從PG(s,t)中刪除邊ex，與ex邊相鄰的兩個(gè)端點(diǎn)為(u,v)，u點(diǎn)靠近起點(diǎn)s，v點(diǎn)靠近終止點(diǎn)t，起始點(diǎn)s到終止點(diǎn)t的所有路徑稱為備用路徑，記為PG-ex(s,t)b，備用路徑上的運(yùn)輸時(shí)間記為hG-ex(s,t)b，備用路徑必須滿足①hG-ex(s,t)b>hG(s,t)，②備用路徑與最短路徑至少有一個(gè)點(diǎn)或者邊不相同。

定義2關(guān)鍵邊：從PG(s,t)中刪除邊ex后，最短路徑記為PG-ex(s,t)，最短路徑上的運(yùn)輸時(shí)間記為hG-ex(s,t)。繞行時(shí)間記為hex：hex=hG-ex(s,t)-hG(s,t)。取各中斷邊對(duì)應(yīng)的繞行時(shí)間最大值max{hex}對(duì)應(yīng)的邊e*=(u*,v*)為關(guān)鍵邊。

定義3有效路徑：若備用路徑上的運(yùn)輸時(shí)間hG-ex(s,t)b小于或等于顧客可等待時(shí)間T，則備用路徑PG-ex(s,t)b對(duì)應(yīng)的配送路徑稱為有效路徑，記作PG-ex(s,t)y。顧客可等待時(shí)間T，T(T>hG(s,t))為發(fā)生中斷后顧客需要等待的總時(shí)間。

定義4最優(yōu)路徑：假設(shè)ex中斷，有效路徑為dx1,dx2,…,dxp，若①dx1,dx2,…,dxp的路段中不包含F(xiàn)(人流量密集場(chǎng)所用F表示，例如商場(chǎng))，則最優(yōu)路徑為min{tx1,tx2,…,txp}對(duì)應(yīng)的配送路徑，②dxp中包含F(xiàn)，dx1,dx2,…,dxp-1的路段不包含F(xiàn)，如果F所在的邊eij(i=1,2,…n，j=1,2,…n)堵，則最優(yōu)路徑為min{tx1,tx2,…,txp-1}對(duì)應(yīng)的配送路徑，如果F所在的邊eij不堵，則最優(yōu)路徑為min{tx1,tx2,…,txp}對(duì)應(yīng)的配送路徑，最優(yōu)路徑記作記為PG-ex(s,t)z。

2 算法設(shè)計(jì)

在一個(gè)邊數(shù)為m，節(jié)點(diǎn)數(shù)為n的交通網(wǎng)絡(luò)中，像學(xué)校、商場(chǎng)之類人流量密集的場(chǎng)所一定會(huì)在某條邊上(假設(shè)人流量密集的場(chǎng)所F在邊eij上)，在某些時(shí)間段(例如節(jié)假日)對(duì)道路交通造成影響。配送車輛根據(jù)網(wǎng)絡(luò)未發(fā)生中斷時(shí)計(jì)算出來的最短路徑前進(jìn)，當(dāng)行駛到某一節(jié)點(diǎn)處，網(wǎng)絡(luò)發(fā)生中斷無法通行時(shí)，最快捷的辦法就是以車輛當(dāng)前行駛位置為源點(diǎn)，終點(diǎn)不發(fā)生變化，仍為顧客需求點(diǎn)，將鄰接矩陣中斷邊的權(quán)值用Inf表示，重新調(diào)用Dijkstra算法計(jì)算新的最短路徑。

2.1 最短時(shí)間計(jì)算

網(wǎng)絡(luò)發(fā)生中斷后，對(duì)應(yīng)的最短運(yùn)行時(shí)間為hG-ex(s,t)，起點(diǎn)s到點(diǎn)u的配送時(shí)間可以直接得到，只要得到點(diǎn)u到終止點(diǎn)t的最短配送路徑及時(shí)間，即可根據(jù)李銀珍和郭耀煌[12]提出的子樹連接思想，得到網(wǎng)絡(luò)中斷后的最短路徑及配送時(shí)間。

當(dāng)最短路上邊ex(u,v)中斷時(shí)，u點(diǎn)靠近起點(diǎn)s，可將網(wǎng)絡(luò)圖分為兩部分，如圖1所示，以終點(diǎn)t為根的最短路徑樹和以u(píng)為根的最短路徑子樹，設(shè)M(t)是從終點(diǎn)可以直接到達(dá)點(diǎn)而不通過邊ex(u,v)的點(diǎn)集，N(u)=V-M(t)為網(wǎng)絡(luò)圖中剩余點(diǎn)的集合，根據(jù)子樹連通可得到如下的計(jì)算公式:

圖1 最短路徑示意圖

hG-ex(u,t)=min{hG-ex(u,x)+w(x,y)+hG-ex(y,t)}

因?yàn)閤εN(u)，所以hG-ex(u,x)=hG(u,x)=hG(t,x)-hG(t,u)。因?yàn)閥εM(t)，所以hG-ex(y,t)=hG(y,t)。

hG-ex(u,t)=min{hG-ex(u,x)+w(x,y)+hG-ex(y,t)}=min{hG(t,x)-hG(t,u)+w(x,y)+hG(y,t)}，其中xεN(u)且yεM(t)。即最短時(shí)間hG-ex(s,t)=hG(s,u)+hG-ex(u,t)。

2.2 算法設(shè)計(jì)

第一步：先根據(jù)初始網(wǎng)絡(luò)圖使用Dijkstra算法確定網(wǎng)絡(luò)的最短路徑PG(s,t)。

此時(shí)，網(wǎng)絡(luò)沒有發(fā)生中斷，根據(jù)各條邊的權(quán)值求出網(wǎng)絡(luò)最短路徑，令PG(s,t)=(a,b,c)。

第二步：確定網(wǎng)絡(luò)關(guān)鍵邊e*=(u*,v*)。

由第一步可知網(wǎng)絡(luò)的最短路徑為a-b-c，當(dāng)邊eab、ebc發(fā)生中斷時(shí)(此時(shí)不考慮網(wǎng)絡(luò)中存在擁堵點(diǎn)及顧客時(shí)間要求)，應(yīng)用關(guān)鍵邊算法及最短時(shí)間公式hG-ex(s,t)=hG(s,u)+hG-ex(u,t)，繞行時(shí)間公式hex=hG-ex(s,t)-hG(s,t)求出繞行時(shí)間的最大值max{hex}，繞行時(shí)間最大值對(duì)應(yīng)的中斷邊為關(guān)鍵邊e*=(u*,v*)。

第三步：確定網(wǎng)絡(luò)最優(yōu)路徑。

由第二步可得網(wǎng)絡(luò)關(guān)鍵邊為e*=(u*,v*)，由于關(guān)鍵邊上路況已知，關(guān)鍵邊中斷，應(yīng)用備用路徑算法求出備用路徑為PG-e*(s,t)b，e1邊中斷，備用路徑為PG-e1(u,t)b=PG-e1(s,t)b，其他邊中斷，備用路徑為PG-ex(s,t)b=PG(s,u)+PG-ex(u,t)，備用路徑PG-ex(s,t)b對(duì)應(yīng)的運(yùn)輸時(shí)間為hG-ex(s,t)b，hG-ex(s,t)b=hG(s,u)+hG-ex(u,t)若hG-ex(s,t)b

情形1F在非最短路徑eij上：

第一種；e*和e1發(fā)生中斷，最優(yōu)路徑算法(3)中的u點(diǎn)是起點(diǎn)s。

第二種；最短路上其他邊ex中斷，最優(yōu)路徑算法(3)中的u點(diǎn)就是中斷邊的起點(diǎn)u。

情形1結(jié)論：

備用路徑時(shí)間tx1,tx2,…,txp,…,txL，假設(shè){tx1,tx2,…,txp}T，則有效路徑為dx1,dx2,…,dxp，若①dx1,dx2,…,dxp的路段中不包含F(xiàn)，則最優(yōu)路徑為min{tx1,tx2,…,txp}對(duì)應(yīng)的配送路徑，②dxp中包含F(xiàn)，dx1,dx2,…,dxp-1的路段不包含F(xiàn)，如果F所在的邊eij堵，則最優(yōu)路徑為min{tx1,tx2,…,txp-1}對(duì)應(yīng)的配送路徑，如果F所在的邊eij不堵，則最優(yōu)路徑為min{tx1,tx2,…,txp}對(duì)應(yīng)的配送路徑。

情形2F在最短路徑eij上：

A；F所在邊及所在邊之前的路段中斷，最優(yōu)路徑求解方法及結(jié)論同情形1。

B；F所在邊之后的路段中斷，最優(yōu)路徑算法(3)中的u點(diǎn)是F所在邊的起點(diǎn)i，結(jié)論同情形1。

2.3 算法正確性分析

如圖2所示的配送交通網(wǎng)絡(luò)，網(wǎng)絡(luò)中的三角形滿足兩邊之和大于第三邊，兩邊之差小于第三邊，Ci表示各邊的運(yùn)輸時(shí)間，假設(shè)C1+C6

圖2 配送網(wǎng)格

(1) 關(guān)鍵邊

假設(shè)網(wǎng)絡(luò)最短路徑PG(s,t)=(1,3,5)，則最短時(shí)間hG(s,t)=C2+C7，k=2，令e13=e1,e35=e2。

當(dāng)邊e13中斷時(shí)，因?yàn)閡=s，所以最短路PG-e1(s,t)=(1,2,5)，最短時(shí)間hG-e1(s,t)=hG(s,s)+hG-e1(s,t)=C1+C6，繞行時(shí)間he1=hG-e1(s,t)-hG(s,t)=C1+C6-C2-C7。

當(dāng)邊e35中斷時(shí)，由假設(shè)可知PG-e2(u,t)=(3,2,5)，所以最短路PG-e2(s,t)=(1,3,2,5)，最短時(shí)間hG-e2(s,t)=hG(s,u)+hG-e2(u,t)=C2+C4+C6，繞行時(shí)間he2=hG-e2(s,t)-hG(s,t)=C2+C4+C6-C2-C7。因?yàn)镃2+C4>C1，由max{hex}可知，關(guān)鍵邊e*=e2=(3,5)=e35。

(2)最優(yōu)路徑

情形1假設(shè)F在非最短路徑邊e12上：

當(dāng)邊e1中斷時(shí)，網(wǎng)絡(luò)備用路徑PG-e1(s,t)b為1-2-5和1-4-5，對(duì)應(yīng)的運(yùn)輸時(shí)間hG-e1(s,t)b為t11=C1+C6和t12=C3+C8，由假設(shè)可知，t11

當(dāng)邊e2中斷時(shí)，網(wǎng)絡(luò)備用路徑PG-e2(s,t)b為1-3-2-5、1-3-4-5、1-2-5和1-4-5，對(duì)應(yīng)的運(yùn)輸時(shí)間hG-e2(s,t)b為t21=C2+C4+C6、t22=C2+C5+C8、t23=C1+C6和t24=C3+C8，由假設(shè)可知，t23

情形2假設(shè)F在最短路徑邊e13上：

當(dāng)邊e1中斷時(shí)，網(wǎng)絡(luò)備用路徑PG-e1(s,t)b為1-2-5和1-4-5，對(duì)應(yīng)的運(yùn)輸時(shí)間hG-e1(s,t)b為t11=C1+C6和t12=C3+C8，由假設(shè)可知，t11

當(dāng)邊e2中斷時(shí)，網(wǎng)絡(luò)備用路徑PG-e2(s,t)b為1-3-2-5、1-3-4-5、1-2-5和1-4-5，對(duì)應(yīng)的運(yùn)輸時(shí)間hG-e2(s,t)b為t21=C2+C4+C6、t22=C2+C5+C8、t23=C1+C6和t24=C3+C8，由假設(shè)可知，t23

以上求解關(guān)鍵邊及備用路徑算法的思路，是對(duì)于三角不等式的應(yīng)用，在求解關(guān)鍵邊時(shí)，使用Matlab軟件運(yùn)行Dijkstra算法代碼，逐次斷開最短路上各條邊，應(yīng)用繞行時(shí)間計(jì)算公式，確定出關(guān)鍵邊，沒有改變Dijkstra算法本身的計(jì)算邏輯，所以關(guān)鍵邊算法的正確性是毋庸置疑的。同理，備用路徑的算法也一樣。

2.4 算法具體步驟及復(fù)雜性分析

(1)關(guān)鍵邊算法

1)利用Dijkstra算法確定網(wǎng)絡(luò)的最短路徑PG(s,t)；

2)令x=1；

3)從PG(s,t)中刪除邊ex，與ex邊相鄰的兩個(gè)端點(diǎn)為(u,v)，u點(diǎn)靠近起點(diǎn)s，v點(diǎn)靠近終止點(diǎn)t；

4)用Dijkstra算法求出新的起始點(diǎn)u到終止點(diǎn)t的最短路徑PG-ex(u,t)，對(duì)應(yīng)的最短運(yùn)行時(shí)間為hG-ex(u,t)；

5)s到t的最短時(shí)間hG-ex(s,t)=hG(s,u)+hG-ex(u,t)，繞行時(shí)間hex=hG-ex(s,t)-hG(s,t)；

6)更新x，令x=x+1，返回到3)；

7)如果x=k+1，則算法結(jié)束，取繞行時(shí)間最大值max{hex}對(duì)應(yīng)的邊e*=(u*,v*)為關(guān)鍵邊。

步驟1)調(diào)用Dijkstra算法，最大計(jì)算量為O(n2)；2)-6)步驟為循環(huán)計(jì)算，循環(huán)數(shù)是k，由最短路徑的定義可知，k<=n-1，3)中有刪除k(k

(2)備用路徑算法

在路段距離一定的條件下，最短路上各條邊發(fā)生中斷后，調(diào)整備用路徑的起始點(diǎn)，尋找可到達(dá)終止點(diǎn)的所有路徑。

1)調(diào)用findPath()函數(shù)知網(wǎng)絡(luò)的最短路徑為PG(s,t)；

2)令x=1；

3)從PG(s,t)中刪除邊ex，與ex邊相鄰的兩個(gè)端點(diǎn)為(u,v)，u點(diǎn)靠近起點(diǎn)s，v點(diǎn)靠近終止點(diǎn)t；

4)用代碼獲得新的起始點(diǎn)u到終止點(diǎn)t的路徑PG-ex(u,t)，對(duì)應(yīng)的運(yùn)輸時(shí)間為hG-ex(u,t)，備用路徑為PG-ex(s,t)b=PG(s,u)+PG-ex(u,t)，備用路徑PG-ex(s,t)b對(duì)應(yīng)的運(yùn)輸時(shí)間為hG-ex(s,t)b，hG-ex(s,t)b=hG(s,u)+hG-ex(u,t)；

5)若hG-ex(s,t)b

6)更新x，令x=x+1，返回到2)；

7)如果x=k+1，則算法結(jié)束。

步驟1)中調(diào)用findPath()函數(shù)，最大計(jì)算量為O(n)；2)-6)步驟是循環(huán)計(jì)算，循環(huán)數(shù)是k，由最短路徑的定義可知，k<=n-1，3)中有刪除k(k

3 算例分析

圖3為某配送中心負(fù)責(zé)的配送交通網(wǎng)絡(luò)圖，快遞人員從圖中的起始點(diǎn)s(配送中心)出發(fā)，到達(dá)目的地t點(diǎn)(顧客要求送達(dá)點(diǎn))，車輛沿著s到t的最短路徑行駛，為了滿足顧客的時(shí)效要求(顧客可等待時(shí)間T=36)，及時(shí)給顧客配送到家，求解網(wǎng)絡(luò)最優(yōu)路徑。

圖3 配送網(wǎng)格

首先求解網(wǎng)絡(luò)的最短路徑，使用Matlab軟件運(yùn)行代碼，求出網(wǎng)絡(luò)的最短路徑為PG(s,t)={1,3,6,8}，hG(s,t)=26，所以k=3，且e1=(1,3)，e2=(3,6)，e3=(6,8)。然后根據(jù)關(guān)鍵邊的求解步驟，當(dāng)邊ex中斷時(shí)，將鄰接矩陣中ex邊的權(quán)值用Inf表示，即為不能通行，用Dijkstra算法求出新的起始點(diǎn)u到終止點(diǎn)t的最短路徑PG-ex(u,t)，對(duì)應(yīng)的最短運(yùn)行時(shí)間為hG-ex(u,t)，s到t的最短時(shí)間hG-ex(s,t)=hG(s,u)+hG-ex(u,t)。關(guān)鍵邊的計(jì)算結(jié)果如表1所示：

表1 關(guān)鍵邊計(jì)算結(jié)果

當(dāng)邊e1中斷后，將鄰接矩陣中e1邊的權(quán)值用Inf表示，用Matlab軟件運(yùn)行代碼，求出網(wǎng)絡(luò)的最短路徑PG-e1(s,t)={1,2,7,8}，最短時(shí)間hG-e1(s,t)=hG(s,u)+hG-e1(u,t)=0+32=32，所以繞行時(shí)間h1=hG-e1(s,t)-hG(s,t)=32-26=6，以此類推，得出繞行時(shí)間最大值為10，邊e2=(3,6)為關(guān)鍵邊，沒考慮道路堵塞情況及顧客時(shí)間要求的最優(yōu)路最優(yōu)路徑，也即理論上的最優(yōu)路徑為1-2-7-8、1-3-4-5-8和1-3-6-7-8。

最后求解最優(yōu)路徑，由于網(wǎng)絡(luò)上一定會(huì)有學(xué)校、商場(chǎng)之類人流量大的場(chǎng)所，F(xiàn)可能在最短路徑上，也可能在非最短路徑上，根據(jù)文中的方法，求解情形1。

假設(shè)F在邊e12上，由第一問可知，網(wǎng)絡(luò)的最短路徑為PG(s,t)={1,3,6,8 }，hG(s,t)=26，且e1=(1,3)，e2=(3,6)，e3=(6,8)。當(dāng)邊ex中斷時(shí)，將鄰接矩陣中ex邊的權(quán)值用Inf表示，即為不能通行，用代碼獲得新的起始點(diǎn)u到終止點(diǎn)t的路徑PG-ex(u,t)，對(duì)應(yīng)的運(yùn)輸時(shí)間為hG-ex(u,t)，則備用路徑為PG-ex(s,t)b=PG(s,u)+PG-ex(u,t)，備用路徑PG-ex(s,t)b對(duì)應(yīng)的運(yùn)輸時(shí)間為hG-ex(s,t)b，hG-ex(s,t)b=hG(s,u)+hG-ex(u,t)，最優(yōu)路徑的計(jì)算結(jié)果如表2所示。邊ex中斷時(shí)路徑PG-ex(u,t)b及運(yùn)輸時(shí)間hG-ex(u,t)，Matlab運(yùn)行結(jié)果如圖4，圖5，圖6。

圖4 邊e1中斷

圖5 邊e2中斷

圖6 邊e3中斷

表2 情形1最優(yōu)路徑計(jì)算結(jié)果

顧客可等待時(shí)間為36，當(dāng)邊e1 中斷時(shí)，將鄰接矩陣中邊e1=(1,3)邊的權(quán)值用Inf表示，使用Matlab軟件運(yùn)行代碼，求出備用路徑，備用路徑中運(yùn)輸時(shí)間小于顧客可等待時(shí)間36的路徑，即為有效路徑1-2-7-8 和1-4-5-8，比如非節(jié)假日e12處不堵：1-2-7-8為最優(yōu)路徑，節(jié)假日e12處堵：1-4-5-8為最優(yōu)路徑。由于e2邊為關(guān)鍵邊，所以路況實(shí)時(shí)可知，一旦e2邊中斷，求出s到t的備用路徑，結(jié)果與e1邊中斷結(jié)果相同。 由于e3邊中斷后，得到的有效路徑不經(jīng)過邊e12，所以取時(shí)間最短的路徑。

求解情形2，F(xiàn)在最短路徑eij上，假設(shè)F在邊e36上，根據(jù)文中方法，e1、e2中斷，備用路徑的計(jì)算方法同第一問，結(jié)果如圖3、圖4，由于有效路徑不經(jīng)過邊e36，所以不考慮e36是否堵，直接取最短時(shí)間。由于e3在F所在邊e36之后，所以備用路徑為起點(diǎn)1(s) 到頂點(diǎn)3處的路徑加上3處到終止點(diǎn)8(t)，結(jié)果如圖7。

圖7 邊e3中斷

表3 情形2最優(yōu)路徑計(jì)算結(jié)果

表1中的最短路徑即理論上的最優(yōu)路徑，但表2表3的結(jié)果發(fā)現(xiàn)考慮了道路堵塞情況及顧客時(shí)間要求的最優(yōu)路徑已不再是理論上的最優(yōu)路徑。

4 結(jié)論

本文研究了在時(shí)間窗及路段堵塞約束下的最優(yōu)路徑，配送企業(yè)應(yīng)找到某個(gè)配送網(wǎng)絡(luò)的關(guān)鍵邊(中斷會(huì)造成最大損失)，對(duì)關(guān)鍵邊進(jìn)行實(shí)時(shí)的監(jiān)控，為配送人員提供一個(gè)精確的路況。綜合考慮各路段堵塞及客戶時(shí)間要求，找到網(wǎng)絡(luò)中配送時(shí)間最短路徑即最優(yōu)路徑，這樣既減少了快遞公司配送的成本，又保障了客戶的滿意度。

本文的研究沒有將客戶的時(shí)間窗變動(dòng)考慮在內(nèi)，然而在實(shí)際的配送中，同一顧客，因自己的心情、理性程度、性格、工作等情況每次可接受的額外等待時(shí)間不會(huì)是一個(gè)定值，會(huì)有一定幅度的變動(dòng)。另外，最短路上發(fā)生中斷，車輛繞行到其他路徑上，其他路徑不一定暢通，車輛的行駛時(shí)間也是一個(gè)不確定的量，因此，下一步的研究方向?qū)⑹菍⒖蛻舻臅r(shí)間窗變動(dòng)考慮在內(nèi)的快件配送最優(yōu)路徑選擇問題。