考慮路段擁堵的最短時(shí)間流優(yōu)化問題*

黃宇達(dá)　李學(xué)威　趙紅專　王迤冉

(1.周口職業(yè)技術(shù)學(xué)院信息工程系　周口　466000)(2.重慶大學(xué)自動(dòng)化學(xué)院　重慶　400044) (3.周口師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　周口　466000)

?

考慮路段擁堵的最短時(shí)間流優(yōu)化問題*

黃宇達(dá)1李學(xué)威1趙紅專2王迤冉3

(1.周口職業(yè)技術(shù)學(xué)院信息工程系周口466000)(2.重慶大學(xué)自動(dòng)化學(xué)院重慶400044) (3.周口師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院周口466000)

針對以往對交通網(wǎng)絡(luò)系統(tǒng)中路網(wǎng)時(shí)間流問題沒有考慮網(wǎng)絡(luò)擁塞的情況,研究了決策者如何制定最短時(shí)間流的決策問題,建立了靜態(tài)數(shù)學(xué)規(guī)劃模型,給出了模型的算法,討論了算法的復(fù)雜性。隨后,又對網(wǎng)絡(luò)時(shí)間流問題進(jìn)行了進(jìn)一步的深入研究,分析了動(dòng)態(tài)堵塞情形下的時(shí)間流特性,考慮交通網(wǎng)絡(luò)堵塞程度對通過時(shí)間的影響,引進(jìn)堵塞系數(shù),構(gòu)造動(dòng)態(tài)時(shí)間函數(shù),建立了在動(dòng)態(tài)堵塞情況下的最短時(shí)間流模型,并給出了模型的算法,同時(shí)用算例驗(yàn)證了方法的有效性。

路段擁堵; 最短時(shí)間流; 預(yù)估時(shí)間; 堵塞系數(shù)

Class NumberTN915.01

1　引言

最短時(shí)間流問題作為一個(gè)經(jīng)典問題一直存在于網(wǎng)絡(luò)通信、交通運(yùn)輸以及工程規(guī)劃等領(lǐng)域。目前,由于實(shí)際生活中的交通、信息傳輸?shù)染W(wǎng)絡(luò)系統(tǒng)中堵塞現(xiàn)象日益嚴(yán)重,有關(guān)網(wǎng)絡(luò)系統(tǒng)中流量堵塞程度問題的研究也逐漸受到關(guān)注。又由于經(jīng)典網(wǎng)絡(luò)流理論已不能解決社會(huì)和管理實(shí)踐中所遇到的一些新問題,它需要向新的方向發(fā)展,這就迫切需要一套完整的有關(guān)堵塞流的理論體系。堵塞流理論便是以解決這些問題為目的而構(gòu)建的。堵塞流理論是網(wǎng)絡(luò)流規(guī)劃理論中的非確定性、隨機(jī)多值性研究領(lǐng)域中的一個(gè)新分支,它是網(wǎng)絡(luò)流理論研究中的一個(gè)具有開拓性和創(chuàng)新性的前沿領(lǐng)域[1～2]。以往對交通網(wǎng)絡(luò)系統(tǒng)中路網(wǎng)容量和時(shí)間流問題的研究中,大都是從網(wǎng)絡(luò)最大流的角度出發(fā)進(jìn)行研究的。

在現(xiàn)實(shí)交通系統(tǒng)中,當(dāng)交通網(wǎng)絡(luò)系統(tǒng)具備由于不同主體出行行為的選擇不同造成交通流動(dòng)的隨機(jī)性或交通網(wǎng)絡(luò)結(jié)構(gòu)的不合理等堵塞條件時(shí),堵塞現(xiàn)象就可能會(huì)發(fā)生。這時(shí)在網(wǎng)絡(luò)中就產(chǎn)生了堵塞流動(dòng),造成交通網(wǎng)絡(luò)系統(tǒng)的堵塞。譬如在交通擁擠和緊急疏散網(wǎng)絡(luò)中,擁擠的車輛和慌亂的人群不會(huì)按照指定的規(guī)則運(yùn)動(dòng),在網(wǎng)絡(luò)中常發(fā)生堵塞,交通個(gè)體無法繼續(xù)向前移動(dòng),而各流動(dòng)單元又不愿意向回撤退,產(chǎn)生堵塞流動(dòng),此時(shí)網(wǎng)絡(luò)中的流量已達(dá)到飽和,不能再增加[3～5]。堵塞流動(dòng)也是交通網(wǎng)絡(luò)系統(tǒng)中常見的一類流動(dòng),然而以往對路網(wǎng)容量和時(shí)間流問題的研究主要沒有考慮交通網(wǎng)絡(luò)系統(tǒng)堵塞的情況。

因此,本文從網(wǎng)絡(luò)系統(tǒng)堵塞的角度研究了最短時(shí)間流問題。在研究路段擁堵的最短時(shí)間流模型的基礎(chǔ)上,設(shè)計(jì)了考慮路段擁堵的最短時(shí)間流的預(yù)估時(shí)間增量比較算法,最后通過算例分析進(jìn)一步驗(yàn)證了算法的有效性。

2　考慮路段擁堵的最短時(shí)間流模型

為了模型研究方便,給出以下定義[7]:

定義1:基本路徑Pk是指路網(wǎng)N中任意一條由υs到υe的通路,通路上的每條弧方向與流向一致。

定義2:沿任意通路上的單位流動(dòng)稱為單位基本流。

定義3:某可行流f是無環(huán)流,若它至少可以用一種由單位基本流的線性關(guān)系表示,即f=α1ξ1+α2ξ2+…+αmξm,ξi(i=1,2,…,m)有m條單位基本流,αi(i=1,2,…,m)是非負(fù)數(shù)。

若可行流f由m條基本流構(gòu)成,則可行流f通過網(wǎng)絡(luò)的時(shí)間為其中最長的基本流的時(shí)間。

定義5:可行流f的時(shí)間為

(1)

其中,f+為f正向路。

在經(jīng)典的網(wǎng)絡(luò)流理論中,一般只考慮流通能力問題,與時(shí)間無關(guān)。而在以時(shí)間為優(yōu)化目標(biāo)的網(wǎng)絡(luò)流規(guī)劃中,路段內(nèi)形成的擁堵則直接影響交通流的速度,因此不能忽略形成的擁堵對通過時(shí)間的影響。

當(dāng)流動(dòng)主題的流量從0開始時(shí),交通流主體通行率高,流動(dòng)快;隨著流量的加大,流速開始受到逐漸形成的擁堵的影響而變慢。所以,通過每一段路的時(shí)間是通過該路段流量的函數(shù)?？梢杂媒泼枋龊瘮?shù)表示:

(2)

結(jié)合以上定義,路段擁堵最短時(shí)間流問題可以表達(dá)成:

(3)

3　考慮路段擁堵的最短時(shí)間流的預(yù)估時(shí)間增量比較算法

若把時(shí)間作為各弧段的一個(gè)權(quán)值,那么容易聯(lián)想到類似算法就是經(jīng)典網(wǎng)絡(luò)流理論中的最小費(fèi)用流算法。基本思路是:從零流量開始f(0),首先對當(dāng)前流f(0)構(gòu)造所有可能增加流量的增廣鏈,然后在這些可能的增廣鏈中采用最短路徑算法求出最小費(fèi)用增廣鏈。在此鏈上增加流量,獲得流量為f(1)的最小費(fèi)用流。同樣,對f(1)再構(gòu)造所有可能增加流量的增廣鏈,并在其中費(fèi)用最小的增廣鏈繼續(xù)增加流量,獲得流量為f(2)的最小費(fèi)用流[10]。如此反復(fù)類推,直到網(wǎng)絡(luò)中不存在增廣鏈。在此思路中將費(fèi)用推廣到時(shí)間,得到的就是最短時(shí)間流。但計(jì)算方法有一些改變。

3.1構(gòu)造基于最小費(fèi)用流算法的增量網(wǎng)絡(luò)

定義6:增量網(wǎng)絡(luò)是指對于給定的帶起點(diǎn)υs和終點(diǎn)υe的路網(wǎng)N=(V,A,C,T)以及N上的可行流f,假定A+(f)={(υi,υj)|(υi,υj)∈A,fij0}。因?yàn)镹中任何一對頂點(diǎn)之間最多有一條弧,從而可以得到A+(f)∩A-(f)=?,令A(yù)(f)=A+(f)∪A-(f),且?(υi,υj)∈A(f),于是:

(4)

從而得到網(wǎng)絡(luò)N的關(guān)于流f的增量網(wǎng)絡(luò)N(f)=(V,A(f),C(f),T(f))。

基于求解最小費(fèi)用流的賦權(quán)圖算法,得到最短時(shí)間流算法的基本思想為:從零流量開始f(0),在從起點(diǎn)到終點(diǎn)的所有可能增加流量的增廣路徑中尋求總時(shí)間最短的路徑,并在此路徑上增加流量,獲得流量為f(1)的最短時(shí)間流。再對f(1)尋求所有可能增加流量的增廣路徑,并在其中總時(shí)間最短的增廣路徑上繼續(xù)增加流量,得到流量為f(2)的最短時(shí)間流。不斷重復(fù)以上過程,直到網(wǎng)路中不再存在增廣路徑,無法增加流量,搜索結(jié)束。上述過程的每一步都是對當(dāng)前最短時(shí)間流尋找最短時(shí)間的增廣路徑并進(jìn)行增流,按照定義5,新的增廣路時(shí)間為增流后總流量通過該網(wǎng)絡(luò)的最短時(shí)間[11]。而對某一最短時(shí)間流不存在最短時(shí)間增廣路時(shí),此過程得到的最大流即為最短時(shí)間最大流。

在構(gòu)造基于最小費(fèi)用流算法的增量網(wǎng)絡(luò)的基礎(chǔ)上,尋求增量網(wǎng)絡(luò)中時(shí)間最短的增廣路,在此之前需先計(jì)算各條增廣路的時(shí)間。

3.2增廣網(wǎng)絡(luò)中增廣路時(shí)間的確定方法

增廣網(wǎng)絡(luò)中增廣路時(shí)間的確定主要存在以下三種情況:

1) 原網(wǎng)絡(luò)中不存在含有反向弧的增廣鏈時(shí),該增廣路的時(shí)間是構(gòu)成該增廣路的各弧段的時(shí)間之和,即

(5)

2) 當(dāng)網(wǎng)路中含有反向弧增廣鏈時(shí),該增廣路的時(shí)間為該增廣路徑增加一個(gè)單位流量后形成的新流量分布中,時(shí)間最長的單位流時(shí)間。

在實(shí)施預(yù)估時(shí)間增量比較法時(shí),每次流量的增加應(yīng)以一個(gè)單位的流量的進(jìn)度迭代進(jìn)行[14]。根據(jù)以上分析,得到考慮路段時(shí)間的最短時(shí)間流算法如下:

Step1:設(shè)定初始流量f(0)=0;

Step2:構(gòu)造當(dāng)前流f(0)的增廣網(wǎng)絡(luò)N;

Step5:如此循環(huán),直到得到最短時(shí)間流,算法結(jié)束。

4　算例分析

圖1　構(gòu)造的初始零流狀態(tài)路網(wǎng)圖

依據(jù)考慮路段時(shí)間的最短時(shí)間流算法,迭代過程如表1所示。

表1　迭代過程

最終優(yōu)化結(jié)果如圖2所示。

圖2　動(dòng)態(tài)阻塞優(yōu)化結(jié)果

經(jīng)過考慮路段時(shí)間的最短時(shí)間流算法得到滿足最短時(shí)間的最大流分布圖,即在算例中流量為5個(gè)單位時(shí),在考慮動(dòng)態(tài)阻塞的情況下的最短時(shí)間為T=2+2+6=10,保證給定的流量順利流出。

若不考慮動(dòng)態(tài)阻塞情形,則上述算例的優(yōu)化最短時(shí)間最大流如圖3所示。

圖3　靜態(tài)阻塞優(yōu)化結(jié)果

考慮動(dòng)態(tài)阻塞和考慮靜態(tài)情形的優(yōu)化最短時(shí)間流曲線對比如圖4所示。

圖4　流量-最短時(shí)間圖

由上述案例分析可知,當(dāng)流量變化時(shí),由于考慮了動(dòng)態(tài)阻塞情況,造成時(shí)間延遲,當(dāng)流量越來越大時(shí)。阻塞越來越嚴(yán)重,故通行的時(shí)間會(huì)增加;當(dāng)不考慮阻塞程度對路段時(shí)間的影響時(shí),通行時(shí)間會(huì)小于網(wǎng)絡(luò)發(fā)生動(dòng)態(tài)阻塞時(shí)的時(shí)間。

5　結(jié)語

本文在目前交通系統(tǒng)的大背景下,考慮到如今日益嚴(yán)重的交通擁塞問題,對決策者在最短時(shí)間流如何制定的問題方面進(jìn)行了進(jìn)一步研究,在給出所建立的數(shù)學(xué)模型對應(yīng)算法的同時(shí),又對算法的復(fù)雜性進(jìn)行了分析和探導(dǎo),最后通過算例分析進(jìn)一步驗(yàn)證了該算法的有效性和合理性,從而為交通擁堵特殊情況下的交通合理規(guī)劃提供建設(shè)性參考。

[1] 寧宣熙.堵塞流理論及其應(yīng)用[M].北京:科學(xué)出版社,2005:1-100,162-176.

NING Xuanxi. Blocking flow theory and its application[M]. Beijing: Science Press,2005:1-100,162-176.

[2] 陳春妹,任福田,榮建.路網(wǎng)研究綜述[J].公路交通科技,2002,19(3):97-101.

CHEN Chunmei, REN Futian, RONG Jian. Review of research on road network[J]. Highway Traffic Science and Technology,2002,19(3):97-101.

[3] Hai Yang, Michael G. H. Bell, Qiang Meng. Modeling, The Capacity and Level of service ofUrban Transportation Networks[J]. Transportation Research PartB,2000(34):255-275.

[4] 周溪召.大城市中心區(qū)道路交通供求模型及其應(yīng)用[D].上海:同濟(jì)大學(xué),1995.

ZHOU Xizhao. The road center of big city traffic supply and demand model and its application[D]. Shanghai: Tongji University,1995.

[5] S. C. WONG, HAI YANG. On the Reserve Capacity of Priority Junctions and Roundabouts[J]. Transpn. Res.-B,1996,30(6):441-453.

[6] S. C. WONG, HAI YANG. Reserve Capacity of a Signal-controlled Road Network[J] . Transpn. Res.-B,1997,31(5):397-402.

[7] 楊濤.運(yùn)輸網(wǎng)絡(luò)極大流動(dòng)態(tài)診斷模型[J].中國公路學(xué)報(bào),1991,4(1):72-77.

YANG Tao. A dynamic diagnosis method of the maximum flow in transportation network[J]. Journal of Highway Chinese,1991,4(1):72-77.

[8] 楊濤.城市交通網(wǎng)絡(luò)總體性能評(píng)價(jià)與建模[D].南京:東南大學(xué),1995.

YANG Tao. The overall performance evaluation and modeling of city traffic network[D]. Nanjing: Southeast University,1995.

[9] 談曉潔,周晶,盛昭翰.城市交通擁擠特征及疏導(dǎo)決策分析[J].管理工程學(xué)報(bào),2003,17(1):56-59.

TAN Xiaojie, ZHOU Jing, SHENG Zhaohan. The crowded city traffic grooming feature and decision analysis[J]. Journal of Engineering Management,2003,17(1):56-59.

[10] 寧宣熙.有向網(wǎng)絡(luò)的最小流問題及其分支定界解法[J].系統(tǒng)工程,1996,14(5):61-66.

NING Xuanxi. A branch and bound method to its minimum flow problem of directed network[J]. Systems Engineering,1996,14(5):61-66.

[11] 寧宣熙.求解網(wǎng)絡(luò)最小流的雙向增流算法[J],系統(tǒng)工程,1997,15(1):50-57.

NING Xuanxi. The minimum flow for solving the network two-way flow increasing algorithm[J]. Systems Engineering,1997,15(1):50-57.

[12] 黃孝鵬.堵塞流理論在路網(wǎng)容量和最短時(shí)間流中的應(yīng)用研究[D].南京:南京航空航天大學(xué),2007.

HUANG Xiaopeng. Study on application of flow theory in network capacity and the minimum time flow blocking[D]. Nanjing: Nanjing University of Aeronautics & Astronautics,2007.

[13] Ning Xuanxi. The minimum flow problem of a transportation network and its approximate Solution[C]//Proceedings of ISIM’96, Nanjing: 488-492.

[14] 孫宇.運(yùn)輸網(wǎng)絡(luò)中的最小堵塞流問題及其算法研究[D].南京:南京航空航天大學(xué),1997.

SUN Yu. Study on the minimum blocking flow problem and its algorithm in the transportation network[D]. Nanjing: Nanjing University of Aeronautics & Astronautics,1997.

Shortest Time Flow Optimization Problem Considering Congestion

HUANG Yuda1LI Xuewei1ZHAO Hongzhuan2WANG Yiran3

(1. Information and Engineering Department, Zhoukou Vocational and Technical College, Zhoukou466000) (2. College of Automation, Chongqing University, Chongqing400044) (3. College of Computer Science and Technology, Zhoukou Normal University, Zhoukou466000)

Aiming at the time flow problem of traffic network system without considering the case of network congestion in the past, how the policy makers make the minimum time flow decision problem is studied and a static mathematical programming model is proposed, then the model algorithm is given, the complexity of the algorithm is discussed. Next, the network time flow problem has been further studied, the dynamic plugging circumstances of the time stream is analyzed, the traffic network congestion degree of influence through time is considered and the congestion coefficient is introduced, then a dynamic time function is presented, the shortest time congestion flow model in dynamic condition is established and the algorithm is given based on the model. Finally, the validity of the method by an example is verified.

road section congestion, minimum time flow, estimate time, block coefficient

2016年3月10日,

2016年4月22日

重慶市科技攻關(guān)計(jì)劃項(xiàng)目(編號(hào):CSTC2012gg-yyjsB30001);河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃項(xiàng)目(編號(hào):122300410397)資助。

黃宇達(dá),男,碩士,副教授,研究方向:知識(shí)工程,信息安全與控制,計(jì)算機(jī)網(wǎng)絡(luò)等。李學(xué)威,男,碩士,講師,研究方向:智能控制,計(jì)算機(jī)網(wǎng)絡(luò)。趙紅專,男,博士研究生,研究方向:嵌入式系統(tǒng),自動(dòng)化控制等。王迤冉,男,碩士,副教授,研究方向:計(jì)算機(jī)網(wǎng)絡(luò),人工智能等。

TN915.01DOI:10.3969/j.issn.1672-9722.2016.09.003