基于隨機時變路網的運輸路徑選擇*

劉 帥，唐伯明，劉 松

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

基于隨機時變路網的運輸路徑選擇*

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

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

針對運輸路網中各路段上的行駛時間受交通管理、交通擁擠、天氣變化等不確定性因素的影響而呈現出隨機時變的特點，引入了路網評審技術中的三時估值法，建立了隨機時變路網下以行駛時間最短為目標的路徑優化模型，提出了車輛跨時段行駛時路段的時間依賴函數，設計了動態規劃標號算法求解。算例求解優化結果的對比分析驗證了模型及算法的有效性。

交通運輸工程；隨機時變；跨時段；動態規劃

0 引 言

交通擁擠、交通事故等因素的不確定性，導致車輛在各路段行駛中的行駛成本、行駛時間等也具有不確定性，呈現出隨機時變特性。隨機時變路網模型由于考慮了現實路網的時變性與隨機性，能更好的反映實際交通路網狀態，其中如何合理的處理具有時變性和隨機性的路段權值是關鍵問題。

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

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

筆者運用計劃評審技術中解決非確定型統籌問題所采用的三時估計法來處理隨機時變路網路段權值問題。三時估計法是實際工程中估計工作持續時間的主要方法之一，是一種有效的工程項目進度風險分析方法。車輛在道路上的行駛時間可認為是車輛在道路上需要工作的時間，與工程項目工序完成時間一致，所以，三時估計法也可用于運輸中的不確定性分析。筆者借鑒三時估計法和動態規劃標號法，尋求在隨機時變路網環境下，車輛從起點O到終點D，以行駛時間最短為目標，滿足FIFO規則和車輛跨時段行駛的最短路線。

1 問題描述及條件假設

1.1 問題描述

1.2 條件假設

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

3) 車輛在各節點處的等待時間為0。

2 問題建模

2.1 隨機時變路網下行程時間分析

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

(1)

(2)

在隨機時變路網中，路段的權值與出發時間有關，因此，確定路網的時間依賴函數就非常重要。當前，關于隨機時變路網中的時間依賴函數的研究大多還處于較為理想的狀態。MALANDRAKI C等[13]首次采用時間分段函數作為時間依賴函數來表示路段行程時間，如圖1。

圖1 行駛時間時間依賴函數Fig.1 Time-dependent function of travel time

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

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

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

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

同理可得，車輛由節點i出發到達節點j所需跨越時段數N。

1) 如果車輛完全在k時段內行駛完路段(i，j)，即N= 0，不跨時段行駛，由于假設在各個節點處等待時間為0，故節點的到達時間等于出發時間。則抵達節點j的時刻Tj為

(3)

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

(4)

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

(5)

推導

1)當車輛從k時段跨越到了k+2個時段時，到達節點j的時刻Tj為

2)當車輛從k時段跨越到了k+3個時段時，到達節點j的時刻Tj為

3)當車輛從k時段跨越到了k+N個時段時，到達節點j的時刻Tj為

2.2 數學模型

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

(6)

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

(7)

(8)

(9)

3 算法設計

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

1) 對運輸路網進行階段的劃分，得到階段數Q，階段q的節點集合記作Nq。

2) 給出出發時間t0，并給起點O以固定標號[(O，0，0，T0)]O，1，1，此時T0=t0，q= 1。

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

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

6) 若q

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

4 算 例

將一個具體的運輸案例，抽象為隨機時變下運輸路徑選擇問題。隨機時變路網如圖3。

圖3 隨機時變路網Fig.3 Stochastic time-dependent network

圖3給出了從起點O到終點D之間的運輸網絡，各路段在不同時段所需的行駛時間如表1。其中A、B、C、u、d分別表示樂觀時間、最可能時間、悲觀時間、期望、方差。車輛在t0時，由O出發，到達目的地D，現希望尋求起點O到達目的地D所需行駛時間最少的線路。

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

1) 通過給出的運輸網絡圖，由前向后劃分階段，得到求解過程中各個階段及其狀態，如表2。

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

表2 各個階段和狀態Table 2 Different stages and status

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

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

5 結 語

筆者對隨機時變路網環境中的運輸行駛路線選擇問題進行了研究，引入了三時估值法來處理路網的隨機時變特性，建立了隨機時變路網路線選擇模型，構建了隨機時變路網下的行程時間依賴函數，并設計了求解算法，研究結果表明：路段行駛時間及最短路徑會隨著出發時刻的不同而不同。

[1] 董振寧，張召生.隨機網絡的最短路問題[J].山東大學學報(理學版)，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].公路交通科技，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].系統工程理論與實踐，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] 周光發，陳亮.隨機網絡最大概率路徑問題的模型與算法[J].解放軍理工大學學報(自然科學版)，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] 賀政綱，宋金玉.時變條件下危險廢棄物運輸路徑選擇問題研究[J].中國安全科學學報，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] 范文璟，馬祖軍.時變網絡環境下城市應急救援路徑優化[J].計算機應用，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] 劉麗萍，斯劍棟，謝文成.時變條件下的危險品運輸與應急救援雙層規劃研究[J].科學管理研究，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] 彭勇，謝祿江，劉松.時變單車路徑問題建模及算法設計[J].重慶交通大學學報(自然科學版)，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] 王鶯，張治國，劉成華.時變條件下易逝品運輸的路徑選擇[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].西南交通大學學報，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].系統工程學報，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].交通運輸系統工程與信息，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

教育部人文社會科學研究規劃基金項目(17YJA630079)；重慶市人民政府發展研究中心項目(2016ZB-03)

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

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

U491

A

1674-0696(2017)12-110-05

田文玉)