基于隨機(jī)時(shí)變路網(wǎng)的運(yùn)輸路徑選擇*

劉 帥，唐伯明，劉 松

(1.重慶交通大學(xué) 土木工程學(xué)院，重慶 400074； 2.重慶交通大學(xué) 交通運(yùn)輸學(xué)院，重慶 400074)

基于隨機(jī)時(shí)變路網(wǎng)的運(yùn)輸路徑選擇*

劉 帥1，唐伯明1，劉 松2

(1.重慶交通大學(xué) 土木工程學(xué)院，重慶 400074； 2.重慶交通大學(xué) 交通運(yùn)輸學(xué)院，重慶 400074)

針對(duì)運(yùn)輸路網(wǎng)中各路段上的行駛時(shí)間受交通管理、交通擁擠、天氣變化等不確定性因素的影響而呈現(xiàn)出隨機(jī)時(shí)變的特點(diǎn)，引入了路網(wǎng)評(píng)審技術(shù)中的三時(shí)估值法，建立了隨機(jī)時(shí)變路網(wǎng)下以行駛時(shí)間最短為目標(biāo)的路徑優(yōu)化模型，提出了車輛跨時(shí)段行駛時(shí)路段的時(shí)間依賴函數(shù)，設(shè)計(jì)了動(dòng)態(tài)規(guī)劃標(biāo)號(hào)算法求解。算例求解優(yōu)化結(jié)果的對(duì)比分析驗(yàn)證了模型及算法的有效性。

交通運(yùn)輸工程；隨機(jī)時(shí)變；跨時(shí)段；動(dòng)態(tài)規(guī)劃

0 引 言

交通擁擠、交通事故等因素的不確定性，導(dǎo)致車輛在各路段行駛中的行駛成本、行駛時(shí)間等也具有不確定性，呈現(xiàn)出隨機(jī)時(shí)變特性。隨機(jī)時(shí)變路網(wǎng)模型由于考慮了現(xiàn)實(shí)路網(wǎng)的時(shí)變性與隨機(jī)性，能更好的反映實(shí)際交通路網(wǎng)狀態(tài)，其中如何合理的處理具有時(shí)變性和隨機(jī)性的路段權(quán)值是關(guān)鍵問題。

董振寧等[1]考慮了路段權(quán)值的隨機(jī)性，假設(shè)路段權(quán)值服從指數(shù)分布，以期望路長(zhǎng)最短為目標(biāo)對(duì)隨機(jī)路網(wǎng)最短路進(jìn)行優(yōu)化；范巍巍等[2]、鄭龍等[3]、周光發(fā)等[4]研究了帶約束條件的隨機(jī)路網(wǎng)最短路問題。但以上學(xué)者沒有考慮路段權(quán)值隨時(shí)間不同而呈現(xiàn)出的時(shí)變特點(diǎn)。賀政綱等[5]考慮了路段權(quán)值的時(shí)變特點(diǎn)，對(duì)行駛風(fēng)險(xiǎn)隨時(shí)間變化的帶時(shí)間窗的最短路進(jìn)行優(yōu)化；范文璟等[6]、劉麗萍等[7]考慮了在時(shí)變路網(wǎng)中帶約束條件的應(yīng)急救援路徑優(yōu)化；彭勇等[8]對(duì)時(shí)變路網(wǎng)中以配送完成時(shí)間最早為優(yōu)化目標(biāo)的車輛配送路徑優(yōu)化進(jìn)行了研究；王鶯等[9]研究了時(shí)變路網(wǎng)中，以運(yùn)輸成本和運(yùn)輸損耗為目標(biāo)的最短路問題。這些學(xué)者考慮了路段權(quán)值的時(shí)變性，但沒有考慮路段的隨機(jī)性。

將路網(wǎng)的隨機(jī)性和時(shí)變性特點(diǎn)同時(shí)加以考慮的學(xué)者不多，陳京榮等[10]考慮了路網(wǎng)的隨機(jī)性和時(shí)變性特點(diǎn)研究最短路問題；魏航等[11]考慮了路網(wǎng)的隨機(jī)時(shí)變特點(diǎn)對(duì)有時(shí)間窗限制的應(yīng)急路徑進(jìn)行優(yōu)化；曹慧等[12]利用魯棒優(yōu)化方法研究了隨機(jī)時(shí)變路網(wǎng)下的最短路徑問題。雖然以上學(xué)者同時(shí)考慮了路網(wǎng)的隨機(jī)性和時(shí)變性，但是沒有考慮隨機(jī)時(shí)變網(wǎng)絡(luò)中不可忽略的first input first output(FIFO)問題以及跨時(shí)段行駛問題。

筆者運(yùn)用計(jì)劃評(píng)審技術(shù)中解決非確定型統(tǒng)籌問題所采用的三時(shí)估計(jì)法來處理隨機(jī)時(shí)變路網(wǎng)路段權(quán)值問題。三時(shí)估計(jì)法是實(shí)際工程中估計(jì)工作持續(xù)時(shí)間的主要方法之一，是一種有效的工程項(xiàng)目進(jìn)度風(fēng)險(xiǎn)分析方法。車輛在道路上的行駛時(shí)間可認(rèn)為是車輛在道路上需要工作的時(shí)間，與工程項(xiàng)目工序完成時(shí)間一致，所以，三時(shí)估計(jì)法也可用于運(yùn)輸中的不確定性分析。筆者借鑒三時(shí)估計(jì)法和動(dòng)態(tài)規(guī)劃標(biāo)號(hào)法，尋求在隨機(jī)時(shí)變路網(wǎng)環(huán)境下，車輛從起點(diǎn)O到終點(diǎn)D，以行駛時(shí)間最短為目標(biāo)，滿足FIFO規(guī)則和車輛跨時(shí)段行駛的最短路線。

1 問題描述及條件假設(shè)

1.1 問題描述

1.2 條件假設(shè)

1) 各路段的交通狀況相互獨(dú)立。

3) 車輛在各節(jié)點(diǎn)處的等待時(shí)間為0。

2 問題建模

2.1 隨機(jī)時(shí)變路網(wǎng)下行程時(shí)間分析

路段的行程時(shí)間由于受交通事故、天氣變化等因素影響難以準(zhǔn)確估計(jì)而呈現(xiàn)出隨機(jī)時(shí)變特性，因此，筆者引入計(jì)劃評(píng)審技術(shù)中解決非確定型問題所采用的三時(shí)估計(jì)法來處理路段行程時(shí)間隨機(jī)時(shí)變的不確定性問題，把隨機(jī)時(shí)變路網(wǎng)轉(zhuǎn)化為確定性時(shí)變路網(wǎng)。將路段的時(shí)間分為悲觀時(shí)間、樂觀時(shí)間，及在正常情況下的最可能時(shí)間，再計(jì)算其期望時(shí)間和方差。

(1)

(2)

在隨機(jī)時(shí)變路網(wǎng)中，路段的權(quán)值與出發(fā)時(shí)間有關(guān)，因此，確定路網(wǎng)的時(shí)間依賴函數(shù)就非常重要。當(dāng)前，關(guān)于隨機(jī)時(shí)變路網(wǎng)中的時(shí)間依賴函數(shù)的研究大多還處于較為理想的狀態(tài)。MALANDRAKI C等[13]首次采用時(shí)間分段函數(shù)作為時(shí)間依賴函數(shù)來表示路段行程時(shí)間，如圖1。

圖1 行駛時(shí)間時(shí)間依賴函數(shù)Fig.1 Time-dependent function of travel time

圖1顯示路段(i，j) 在不同時(shí)段所需的行駛時(shí)間，如果1號(hào)車在 08：50 離開i，在09：50到達(dá)j；同時(shí)，2號(hào)車在09：00 離開i，卻在09：40到達(dá)j，比1號(hào)車早到，違反了FIFO原則。因此盡管時(shí)間分段法分段數(shù)越多越接近實(shí)際情況，但是該方法為了滿足路網(wǎng)的先入先出FIFO特性，需要假定車輛在節(jié)點(diǎn)處等待一定時(shí)間，這與實(shí)際情況不符。

K. SUNG等[14]證明了使用如圖2的行駛速度時(shí)間依賴模型滿足FIFO原則。

圖2 行駛速度時(shí)間依賴函數(shù)Fig.2 Time-dependent function of travel speed

為了使得車輛在隨機(jī)時(shí)變路網(wǎng)中的行駛時(shí)間滿足FIFO原則，筆者設(shè)計(jì)了以下方法計(jì)算路段(i，j)的行駛時(shí)間。

同理可得，車輛由節(jié)點(diǎn)i出發(fā)到達(dá)節(jié)點(diǎn)j所需跨越時(shí)段數(shù)N。

1) 如果車輛完全在k時(shí)段內(nèi)行駛完路段(i，j)，即N= 0，不跨時(shí)段行駛，由于假設(shè)在各個(gè)節(jié)點(diǎn)處等待時(shí)間為0，故節(jié)點(diǎn)的到達(dá)時(shí)間等于出發(fā)時(shí)間。則抵達(dá)節(jié)點(diǎn)j的時(shí)刻Tj為

(3)

2) 若車輛在路段(i，j)上行駛由k時(shí)段跨越到了k+1 時(shí)段，即N= 1，則到達(dá)j的時(shí)刻Tj為

(4)

命題若車輛在路段(i，j)上行駛從k時(shí)段跨越到了k+N(N≥2 )個(gè)時(shí)段，則到達(dá)j的時(shí)刻Tj為

(5)

推導(dǎo)

1)當(dāng)車輛從k時(shí)段跨越到了k+2個(gè)時(shí)段時(shí)，到達(dá)節(jié)點(diǎn)j的時(shí)刻Tj為

2)當(dāng)車輛從k時(shí)段跨越到了k+3個(gè)時(shí)段時(shí)，到達(dá)節(jié)點(diǎn)j的時(shí)刻Tj為

3)當(dāng)車輛從k時(shí)段跨越到了k+N個(gè)時(shí)段時(shí)，到達(dá)節(jié)點(diǎn)j的時(shí)刻Tj為

2.2 數(shù)學(xué)模型

設(shè)X是路徑可行解的集合，λ(λ∈X)是起點(diǎn)O和終點(diǎn)D之間的一條可行路徑，則所求問題的優(yōu)化模型為

(6)

約束條件如式(7)～式(9)：

(7)

(8)

(9)

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

由于考慮了路網(wǎng)的隨機(jī)性和時(shí)變性，隨機(jī)時(shí)變路網(wǎng)路徑求解算法比靜態(tài)路網(wǎng)復(fù)雜。隨機(jī)時(shí)變網(wǎng)絡(luò)已被證明是NP完全問題(non-deterministic polynomial complete problem)。筆者將其轉(zhuǎn)化為滿足FIFO 特性的確定型時(shí)變路網(wǎng)問題，可設(shè)計(jì)動(dòng)態(tài)規(guī)劃和標(biāo)號(hào)法求解。對(duì)于一個(gè)隨機(jī)時(shí)變的運(yùn)輸網(wǎng)絡(luò)，在求解過程中，通常可將其劃分為若干個(gè)階段，然后逐個(gè)階段由前往后推移，直至終點(diǎn)。用標(biāo)號(hào)法求解，先要設(shè)計(jì)標(biāo)號(hào)。給節(jié)點(diǎn)j標(biāo)號(hào)[(j，tij，zOj，Tj)]i，q，Ti，其中q為i所屬階段；Tj為由i到達(dá)j的時(shí)刻,Tj按式(4)～式(6)求得；Ti為到達(dá)i的時(shí)刻；tij為邊(i，j)的權(quán)值；zOj為在時(shí)間tj到達(dá)節(jié)點(diǎn)j的目標(biāo)值。這樣，基于動(dòng)態(tài)規(guī)劃和標(biāo)號(hào)法的求解步驟如下：

1) 對(duì)運(yùn)輸路網(wǎng)進(jìn)行階段的劃分，得到階段數(shù)Q，階段q的節(jié)點(diǎn)集合記作Nq。

2) 給出出發(fā)時(shí)間t0，并給起點(diǎn)O以固定標(biāo)號(hào)[(O，0，0，T0)]O，1，1，此時(shí)T0=t0，q= 1。

3) 尋求Nq和Nq+1中節(jié)點(diǎn)。Nq+1為Nq的前向節(jié)點(diǎn)集合，i∈Nq，j∈Nq+1，其中，i、j∈N，(i，j)∈E；獲得階段q的所有節(jié)點(diǎn)集合Nq。

5) 令q=q+1，執(zhí)行下一步。

6) 若q

7) 輸出到終點(diǎn)D最小值，即min(Z)，并回朔獲得出發(fā)時(shí)間為t0的最短路徑。

4 算 例

將一個(gè)具體的運(yùn)輸案例，抽象為隨機(jī)時(shí)變下運(yùn)輸路徑選擇問題。隨機(jī)時(shí)變路網(wǎng)如圖3。

圖3 隨機(jī)時(shí)變路網(wǎng)Fig.3 Stochastic time-dependent network

圖3給出了從起點(diǎn)O到終點(diǎn)D之間的運(yùn)輸網(wǎng)絡(luò)，各路段在不同時(shí)段所需的行駛時(shí)間如表1。其中A、B、C、u、d分別表示樂觀時(shí)間、最可能時(shí)間、悲觀時(shí)間、期望、方差。車輛在t0時(shí)，由O出發(fā)，到達(dá)目的地D，現(xiàn)希望尋求起點(diǎn)O到達(dá)目的地D所需行駛時(shí)間最少的線路。

表1 各條有向邊在不同時(shí)段的運(yùn)輸時(shí)間Table 1 Transportation time of each directed edge at different time-zone /min

1) 通過給出的運(yùn)輸網(wǎng)絡(luò)圖，由前向后劃分階段，得到求解過程中各個(gè)階段及其狀態(tài)，如表2。

2) 給定出發(fā)時(shí)刻t0，利用文中所給算法，用MATLAB編程求解，計(jì)算對(duì)比車輛在t0時(shí)，由O行駛到D的最短路徑和所需的最短時(shí)間。t0分別選取07：00、07：15、07：30，所得的最優(yōu)解如表3。

表2 各個(gè)階段和狀態(tài)Table 2 Different stages and status

表3 不同出發(fā)時(shí)刻最短路徑及其時(shí)間成本Table 3 The shortest path at different departure timeand its time cost

從表3可以看出，不同的出發(fā)時(shí)刻，所獲得的最短路徑時(shí)間成本以及行駛路徑不同，所需行駛時(shí)間及最短路徑會(huì)隨出行時(shí)間的變化而變化。

5 結(jié) 語

筆者對(duì)隨機(jī)時(shí)變路網(wǎng)環(huán)境中的運(yùn)輸行駛路線選擇問題進(jìn)行了研究，引入了三時(shí)估值法來處理路網(wǎng)的隨機(jī)時(shí)變特性，建立了隨機(jī)時(shí)變路網(wǎng)路線選擇模型，構(gòu)建了隨機(jī)時(shí)變路網(wǎng)下的行程時(shí)間依賴函數(shù)，并設(shè)計(jì)了求解算法，研究結(jié)果表明：路段行駛時(shí)間及最短路徑會(huì)隨著出發(fā)時(shí)刻的不同而不同。

[1] 董振寧，張召生.隨機(jī)網(wǎng)絡(luò)的最短路問題[J].山東大學(xué)學(xué)報(bào)(理學(xué)版)，2003，38(3)：6-9.

DONG Zhenning，ZHANG Zhaosheng. The shortest path problems in stochastic and time-dependent network[J].JournalofShandongUniversity(NaturalScience)，2003，38 (3)：6-9.

[2] 范巍巍，程琳.隨機(jī)路網(wǎng)的最短路徑問題研究[J].公路交通科技，2007，24(9)：112-115.

FAN Weiwei，CHENG Lin. The study on shortest path problems in stochastic traffic network[J].JournalofHighwayandTransportationResearchandDevelopment，2007，24(9)：112-115.

[3] 鄭龍，周經(jīng)倫，易凡，等.大規(guī)模隨機(jī)運(yùn)輸路網(wǎng)的路徑優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2009，29(10)：85-93.

ZHENG Long，ZHOU Jinglun，YI Fan，et al. Stochastic routing optimization of large-scale transportation network[J].SystemsEngineering-Theory&Practice，2009，29 (10)：85-93.

[4] 周光發(fā)，陳亮.隨機(jī)網(wǎng)絡(luò)最大概率路徑問題的模型與算法[J].解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，17(4)：391-395.

ZHOU Guangfa，CHEN Liang. Model and algorithm of maximum probability path problem in stochastic network[J].JournalofPLAUniversityofScienceandTechnology(NaturalScienceEdition)，2016，17 (4)：391-395.

[5] 賀政綱，宋金玉.時(shí)變條件下危險(xiǎn)廢棄物運(yùn)輸路徑選擇問題研究[J].中國安全科學(xué)學(xué)報(bào)，2014，24(12)：44-50.

HE Zhenggang，SONG Jinyu. Route planning for hazardous waste transportation as time varies[J].ChinaSafetyScienceJournal，2014，24(12)：44-50.

[6] 范文璟，馬祖軍.時(shí)變網(wǎng)絡(luò)環(huán)境下城市應(yīng)急救援路徑優(yōu)化[J].計(jì)算機(jī)應(yīng)用，2011，31(增刊1)：125-128.

FAN Wenjing，MA Zujun. Optimization of rescue path for urban emergency in time-varying networks[J].JournalofComputerApplication，2011，31 (sup1)：125-128.

[7] 劉麗萍，斯劍棟，謝文成.時(shí)變條件下的危險(xiǎn)品運(yùn)輸與應(yīng)急救援雙層規(guī)劃研究[J].科學(xué)管理研究，2014，6(20)：208-213.

LIU Liping，SI Jiandong，XIE Wencheng. Research on bi-level programming of hazardous materials transportation and emergency rescue in time-varying network[J].ScienceandTechnologyManagementResearch，2014，6(20)：208-213.

[8] 彭勇，謝祿江，劉松.時(shí)變單車路徑問題建模及算法設(shè)計(jì)[J].重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013，32(2)：263-266，334.

PENG Yong，XIE Lujiang，LIU Song. Route modeling and algorithm designing of time-dependent single vehicle[J].JournalofChongqingJiaotongUniversity(NaturalScience)，2013，32(2)：263-266，334.

[9] 王鶯，張治國，劉成華.時(shí)變條件下易逝品運(yùn)輸?shù)穆窂竭x擇[J].統(tǒng)計(jì)與決策，2009，10(10)：27-28.

WANG Ying，ZHANG Zhiguo，LIU Chenghua. Path selection of perishable goods transportation under time-varying conditions[J].StatisticsandDecision，2009，10 (10)：27-28.

[10] 陳京榮，俞建寧，李引珍.多屬性隨機(jī)時(shí)間依賴路網(wǎng)路徑優(yōu)化[J].西南交通大學(xué)學(xué)報(bào)，2012，47(2)：291-298.

CHEN Jingrong，YU Jianning，LI Yinzhen. Route optimization of multi-attribute random time-dependent road networks[J].JournalofSouthWestJiaotongUniversity，2012，47 (2)：291-298.

[11] 魏航，魏潔.隨機(jī)時(shí)變網(wǎng)絡(luò)下的應(yīng)急路徑選擇研究[J].系統(tǒng)工程學(xué)報(bào)，2009，24(1)：99-103.

WEI Hang，WEI Jie. Emergency path problem in stochastic and time-varying network[J].JournalofSystemsEngineering，2009，24(1)：99-103.

[12] 曹慧，段征宇，陳川.隨機(jī)時(shí)變路網(wǎng)環(huán)境下穩(wěn)健路徑選擇及實(shí)證研究[J].交通運(yùn)輸系統(tǒng)工程與信息，2014，14(5)：194-201.

CAO Hui，DUAN Zhengyu，CHEN Chuan. Empirical research on robust optimal path problem in stochastic time-dependent networks[J].JournalofTransportationSystemsEngineeringandInformationTechnology，2014，14(5)：194-201.

[13] MALANDRAKI C，DASKIN M S. Time dependent vehicle routing problems：formulations，properties and heuristic algorithms[J].TransportationScience，1992，26(3)：185-200.

[14] SUNG K，BELL M G H，SEONG M，et al. Shortest paths in a network with time-dependent flow speeds[J].EuropeanJournalofOperationalResearch，2000，121(1)：32-39.

Transportation Route Selection in Stochastic Time-Dependent Network

LIU Shuai1，TANG Boming1，LIU Song2

(1. School of Civil Engineering，Chongqing Jiaotong University，Chongqing 400074，P. R. China; 2. School of Traffic & Transportation，Chongqing Jiaotong University，Chongqing 400074，P. R. China)

The travel time at each section of road transportation network was affected by traffic management，traffic congestion，weather changes and other uncertainties，so it showed stochastic time-dependent characteristics. The three-time valuation method in road network evaluation technique was introduced，and a path optimization model in stochastic time-dependent road network to minimize the travel time was established. A time-dependent function of the road sections when the vehicle travelled inter-temporally was proposed. Moreover，an algorithm of dynamically programming and labeling was designed to solve the function. Through a comparative analysis of the optimization results of the application examples，the effectiveness of the proposed model and algorithm was verified.

traffic and transportation engineering; stochastic time-dependent; over time; dynamic programming

10.3969/j.issn.1674-0696.2017.12.18

2016-12-19；

2017-09-26

教育部人文社會(huì)科學(xué)研究規(guī)劃基金項(xiàng)目(17YJA630079)；重慶市人民政府發(fā)展研究中心項(xiàng)目(2016ZB-03)

劉 帥(1982—)，男，山東菏澤人，博士研究生，主要從事物流方面的研究。E-mail: wordday@sina.com。

唐伯明(1962—)，男，江蘇東臺(tái)人，教授，工學(xué)博士，博士生導(dǎo)師，主要從事交通運(yùn)輸工程方面的研究。E-mail: tbm@netease.com。

U491

A

1674-0696(2017)12-110-05

田文玉)