考慮路段突發(fā)性堵塞的旅行商問題與算法*

孫璐璐，蘇 兵，邵 郁，姬 浩，張 萌

(1.西安工業(yè)大學(xué) 經(jīng)濟管理學(xué)院，西安 710021；2.西安交通大學(xué) 管理學(xué)院，西安 710049)

經(jīng)典旅行商問題(Traveling Salesman Problem，TSP)指在交通網(wǎng)絡(luò)中路段權(quán)值(一般指長度/通行時間等)確定的情形下旅行者從起點出發(fā)且經(jīng)過每個中間節(jié)點只一次最后回到起點的最短路徑選擇問題[1]。有研究對經(jīng)典TSP問題的求解算法進行改進[2-4]，有研究考慮包含優(yōu)先級約束的TSP問題[5]，包含隨機客戶的選擇性TSP問題[6]，環(huán)形路網(wǎng)上以總服務(wù)時間盡可能短為目標(biāo)的在線TSP問題[7]，帶有線性懲罰的在線TSP問題[8]，有服務(wù)時長和服務(wù)可選擇性的在線TSP問題[9]等。實際交通網(wǎng)絡(luò)中路段經(jīng)常發(fā)生堵塞，現(xiàn)有TSP問題的相關(guān)研究均未考慮路段發(fā)生堵塞的情形。旅行者一旦遭遇突發(fā)性堵塞，在不考慮堵塞情形下所選擇的旅行路徑就會失效，并且?guī)頃r間損失；已有研究考慮路段突發(fā)性堵塞的路徑選擇主要為替代路徑[10]、繞行路徑[11-12]、最優(yōu)安全路徑[13-14]和最優(yōu)抗風(fēng)險路徑[15-16]等，均未考慮TSP問題的特點，即要求路徑必經(jīng)中間節(jié)點，無法滿足實際需求。

本文針對考慮路段突發(fā)性堵塞的TSP問題，基于交通網(wǎng)絡(luò)中任意路段均可能發(fā)生堵塞的情形，在旅行者出發(fā)前選擇一條從起點出發(fā)且經(jīng)過所有必經(jīng)中間節(jié)點后到達(dá)終點的抗堵塞路徑，使得遭遇突發(fā)性堵塞所帶來的時間損失盡可能小。文中提出路段堵塞所帶來時間損失的度量指標(biāo)：路段堵塞損失值，建立最優(yōu)抗堵塞旅行路徑選擇模型并設(shè)計算法求解，為旅行者出發(fā)前的路徑選擇提供決策依據(jù)。

1 問題描述及相關(guān)定義

2 最優(yōu)抗堵塞旅行路徑選擇模型

根據(jù)定義1，提出路段堵塞所帶來時間損失的度量指標(biāo)：路段堵塞損失值，有定義2。

網(wǎng)絡(luò)中存在多條從v1出發(fā)且經(jīng)過V′中所有節(jié)點后到達(dá)vn的路徑，每條路徑均可計算其抗堵塞關(guān)鍵路段；比較所有抗堵塞關(guān)鍵路段的路段堵塞損失值，可得出最小路段堵塞損失值；包含最小路段堵塞損失值所對應(yīng)路段的路徑稱為抗堵塞旅行路徑，有定義4。

網(wǎng)絡(luò)中可能存在多條抗堵塞旅行路徑，因而稱通行時間最短的抗堵塞旅行路徑為最優(yōu)抗堵塞旅行路徑，有定義5。

3 最優(yōu)抗堵塞旅行路徑的求解

求解最優(yōu)抗堵塞旅行路徑可以通過計算出網(wǎng)絡(luò)中的每條滿足條件的旅行路徑，比較每條路徑的抗堵塞關(guān)鍵路段的堵塞損失值大小，并結(jié)合路徑自身的通行時間求出最優(yōu)抗堵塞旅行路徑；但是該方法的時間復(fù)雜度很高。通過分析最優(yōu)抗堵塞旅行路徑選擇模型可以看出，求解最優(yōu)抗堵塞旅行路徑的關(guān)鍵是求出抗堵塞關(guān)鍵路段。通過分析網(wǎng)絡(luò)中路段的性質(zhì)，排除不可能成為抗堵塞關(guān)鍵路段的路段，可以有效降低算法的時間復(fù)雜性。

通過觀察和分析，發(fā)現(xiàn)網(wǎng)絡(luò)中存在一類特殊路段，此類路段的通行時間大于其兩個端點間最短路徑的通行時間。一旦旅行者到達(dá)這類路段的起始節(jié)點時遭遇堵塞，可選擇路段的兩個端點之間的最短路徑進行繞行，使得路段堵塞損失值第2部分L″的值為0。稱這類路段為最大后悔路段，有定義6。

定義6 最大后悔路段。對于某路段eab，如果其通行時間嚴(yán)格大于兩個端點之間的最短路徑通行時間，即tab>TG(va,vb|SP)，則稱這條路段為最大后悔路段Leab。

由定義6可知，與最大后悔路段的路段堵塞損失值相關(guān)的僅有起點v1到該路段起始節(jié)點之間的路徑，因此最大后悔路段在該路徑上越靠近終點，其路段堵塞損失值就越大。給出如下定理1，即最大后悔路段的特殊性質(zhì)。

由情形1可知Lab=0，對于en-1,n，由于其非最大后悔路段，故其繞行路徑的通行時間大于G中從vn-1到vn的最短路徑通行時間，所以有Ln-1,n>0。

由定理1可以得出推論1。

通過對交通網(wǎng)絡(luò)中特殊路段分析可知，最大后悔路段非抗堵塞關(guān)鍵路段，因此抗堵塞關(guān)鍵路段存在于以vn為根的最短路徑樹上。在設(shè)計算法時，由于要求旅行者經(jīng)過k個必經(jīng)中間節(jié)點，則計算最短路徑樹時不能將起點、k個必經(jīng)中間節(jié)點、終點很好地連結(jié)在一起，除非k個必經(jīng)中間節(jié)點恰好位于在從起點到終點的最短路徑上。鑒于此，需要求出從起點經(jīng)過k個必經(jīng)中間節(jié)點到達(dá)終點的最短路徑，并從最短路徑上的路段出發(fā)逐步計算出最優(yōu)抗堵塞旅行路徑。

最優(yōu)抗堵塞旅行路徑的算法A思想為：計算從起點經(jīng)過k個必經(jīng)中間節(jié)點后到達(dá)終點的最短路徑及其抗堵塞關(guān)鍵路段，將交通網(wǎng)絡(luò)中的最大后悔路段從最優(yōu)解排除。刪除這條抗堵塞關(guān)鍵路段，在剩余的交通網(wǎng)絡(luò)中依次計算最短路徑及抗堵塞關(guān)鍵路段，并和前一次計算所得結(jié)果比較堵塞損失值，若后者不小于前者，則算法結(jié)束；若后者小于前者，則刪除抗堵塞關(guān)鍵路段并繼續(xù)迭代，直到滿足后者不小于前者為止。此時交通網(wǎng)絡(luò)中的最短路徑即為最優(yōu)抗堵塞旅行路徑。

計算最優(yōu)抗堵塞旅行路徑的算法A步驟為

3) 輸出pk-1；

5)令P1=dist(v1,V1)+pk-1+dist(vn,Vn)，j=2tok-1：

Pj=dist(v1,Vj)+pk-1-dist(Vj-1,Vj)+dist(pn-1(first),pn-1(last))+dist(Vj-1+vn)；

τ=q-1，否則轉(zhuǎn)入10)；

定理2在n個節(jié)點和m條路段的無向網(wǎng)絡(luò)上，從起點v1經(jīng)過k個必經(jīng)中間節(jié)點到終點vn的最優(yōu)抗堵塞旅行路徑可在O(kn3)時間內(nèi)輸出。

4 實例分析

實例1和2均為合肥市的局部路網(wǎng)，其中實例1包含單個必經(jīng)中間節(jié)點，實例2包含多個必經(jīng)中間節(jié)點。

1) 實例1 為單個必經(jīng)中間節(jié)點服務(wù)

合肥市局部路網(wǎng)和抽象圖如圖1和圖2所示。圖2中各條路段的權(quán)值表示圖1中相應(yīng)路段的通行時間，且任意一條路段均可能發(fā)生堵塞；標(biāo)出的節(jié)點為必經(jīng)中間節(jié)點?，F(xiàn)需選擇一條抗堵塞路徑，起點為肥東新周谷堆農(nóng)產(chǎn)品市場v1，必須經(jīng)過網(wǎng)絡(luò)中的餐館v10并為其配送農(nóng)產(chǎn)品，最后前往位于長江東路與銅陵路交叉口的終點v16，目標(biāo)是為運輸車輛(即旅行者)在出發(fā)前選擇一條抗堵塞路徑。

圖1 合肥市局部路網(wǎng)(為單個必經(jīng)中間節(jié)點服務(wù))

圖2 合肥市局部路網(wǎng)抽象圖(為單個必經(jīng)中間節(jié)點服務(wù))

2) 實例2 為多個必經(jīng)中間節(jié)點服務(wù)

合肥市局部路網(wǎng)和抽象圖如圖3和圖4所示。圖4中各條路段的權(quán)值表示圖3中相應(yīng)路段的通行時間，且任意一條路段均可能發(fā)生堵塞；標(biāo)出的節(jié)點為必經(jīng)中間節(jié)點?，F(xiàn)需選擇一條抗堵塞路徑，起點為肥東新周谷堆農(nóng)產(chǎn)品市場v1，必須經(jīng)過網(wǎng)絡(luò)中的v5、v7、v10和v15這4個餐館并為其配送農(nóng)產(chǎn)品，最后前往位于長江東路與銅陵路交叉口的終點v16，目標(biāo)是為運輸車輛(即旅行者)在出發(fā)前選擇一條抗堵塞路徑。

圖3 合肥市局部路網(wǎng)(為多個必經(jīng)中間節(jié)點服務(wù))

圖4 合肥市局部路網(wǎng)抽象圖(為多個必經(jīng)中間節(jié)點服務(wù))

5 結(jié) 語

研究發(fā)現(xiàn)旅行者從起點出發(fā)為必經(jīng)中間節(jié)點服務(wù)后到達(dá)終點的過程中，經(jīng)常會遭遇突發(fā)性堵塞，由于堵塞發(fā)生的位置具有不可預(yù)知性且會導(dǎo)致路段無法通行，會給旅行者帶來時間損失。在旅行者出發(fā)前選擇一條從起點出發(fā)且經(jīng)過所有必經(jīng)中間節(jié)點后到達(dá)終點的抗堵塞路徑，使得路段突發(fā)性堵塞所帶來時間損失盡可能小，具有重要的意義。研究結(jié)果針對交通網(wǎng)絡(luò)中任意路段均可能發(fā)生堵塞的旅行商問題，提出度量路段堵塞所帶來時間損失的指標(biāo)：路段堵塞損失值，并給出路段堵塞損失值的定義，給出路段堵塞損失值的具體計算方法。以降低路段堵塞所帶來的時間損失為目標(biāo)，建立了最優(yōu)抗堵塞旅行路徑選擇模型。文中研究設(shè)計了時間復(fù)雜性為O(kn3)的算法進行求解，即分別計算起點到某個中間節(jié)點的局部路徑、連接所有必經(jīng)中間節(jié)點的局部路徑及某一必經(jīng)中間節(jié)點到終點的局部路徑，將這三段局部路徑連接在一起得到從起點出發(fā)經(jīng)過多個必經(jīng)中間節(jié)點后到達(dá)終點的最短路徑。計算任一路徑上每一條路段的堵塞損失值并找出最大值，每一條路徑均可找出該最大值，從這些最大值中找出最小值，結(jié)合抗堵塞旅行路徑本身的長度選擇出最優(yōu)抗堵塞旅行路徑。本文為旅行者在交通網(wǎng)絡(luò)中任一路段均可能發(fā)生突發(fā)性堵塞的條件下選擇旅行路徑，提供了一種新的思路，為交通網(wǎng)絡(luò)管理提供了理論依據(jù)和實踐借鑒。