考慮實(shí)時(shí)路況的出行路線選擇模型

李倩，趙思雨，李安娜，李波

(中國傳媒大學(xué) 理工學(xué)部，北京100024)

摘要：為了緩解交通擁堵問題，本文在現(xiàn)有的導(dǎo)航儀基礎(chǔ)上，考慮到道路的實(shí)時(shí)情況，設(shè)計(jì)新的導(dǎo)航儀，幫助居民選擇出用時(shí)最短且能盡量避免擁堵的路線。研究主要包括兩方面：首先，在存在不擁堵路線的情況下，利用最大流模型計(jì)算出道路流量，結(jié)合實(shí)際流量，在盡量避免擁堵(實(shí)際流量不超過最大流量)的情況下，求出最短路程，給出建議。然后，考慮擁堵問題難以避免，加強(qiáng)了與實(shí)際道路狀況的聯(lián)系，對(duì)道路出行選擇模型進(jìn)行了優(yōu)化，先將道路分為非常擁堵、存在擁堵、暢通三種情況，然后再根據(jù)道路實(shí)時(shí)流量，利用G-LN的模型計(jì)算出車道的速度，結(jié)合路程，找出用時(shí)最短的路線。

關(guān)鍵詞：道路流量；出行選擇模型；最大流模型；居民出行路線；最短路模型

中圖分類號(hào)：O224文獻(xiàn)標(biāo)識(shí)碼：A

收稿日期：2014-09-20

基金項(xiàng)目：國家自然科學(xué)基金(71172040)；中國傳媒大學(xué)理科

作者簡(jiǎn)介：李倩(1993-)，女(漢族)，河南內(nèi)鄉(xiāng)人，中國傳媒大學(xué)統(tǒng)計(jì)學(xué)專業(yè).E-mail：lq18216129@163.com

TheModelaboutTravelRouteinConsideration

oftheReal-timeTraffic

LIQian，ZHAOSi-yu，LIAn-na，LIBo

(FacultyofScienceandTechnology，CommunicationUniversityofChina，Beijing100024)

Abstract：In order to relieve the increasingly serious traffic congestion，the authors put forward a new method on the basis of existing navigation. In view of the real-time road condition，this new method could help residents choose a route with the shortest time and less congestion. This paper mainly includes two aspects：firstly，the authors established a travel route model based on traffic flow，which was suitable for the situation of no congestion. Taking the demand of real flow into consideration，the authors used the Maximal Flow Model to calculate the traffic flow. Then，the authors figured up the shortest route with less congestion which meant the real flow did not exceed the maximum flow .Finally，some suggestions about the choice of travel routes were given. Secondly，the authors found it is difficult to avoid the congestion in many cases，therefore the authors strengthened the connection with the actual road condition and optimized the first study .To begin with，the condition of roads could be divided into three kinds：serious congestion，slight congestion and no congestion. Then，according to the real-time traffic flow，the authors used the G-LN speed-flow model to calculate the average speed of lane and combined it with distance to find a route with the shortest time.

Keywords：road flow；travel route model；the maximal flow model；residents ’travel route；the shortest distance model

1引言

交通擁堵是一定時(shí)間道路交通的需求量超過道路的容量，超過部分的交通流量滯留在道路上的現(xiàn)象。近幾年高速路交通擁堵問題日益嚴(yán)重，路況實(shí)際能承受的最大流量模糊不清，嚴(yán)重影響了居民的出行選擇。

現(xiàn)有的導(dǎo)航儀，只是按照最短路線制定出行方案，給出的路線大部分會(huì)出現(xiàn)擁堵情況，這時(shí)，最短路線就不一定是最省時(shí)的，而且單條道路車流量長期過大，會(huì)加速道路的損傷?？紤]到這種情況，我們根據(jù)實(shí)時(shí)的路況，結(jié)合道路長度、容量、流量，制定出更加合理的路線，使導(dǎo)航出來的路線既能減少擁堵情況的產(chǎn)生，又最省時(shí)。設(shè)計(jì)思路如下：

圖1　設(shè)計(jì)的基本思路

2研究現(xiàn)狀綜述

針對(duì)道路擁堵和出行選擇的問題，近幾年國內(nèi)外學(xué)者從不同方面進(jìn)行了研究。美國學(xué)者JeffreyL.Alder[1]等人提出了一種基于分布式多智能體的改善交通誘導(dǎo)系統(tǒng)與交通管理系統(tǒng)的集成方法；加拿大滑鐵盧大學(xué)學(xué)者LiPingfu[2]提出了一種基于實(shí)時(shí)信息的自適應(yīng)路徑優(yōu)化算法，來解決交通誘導(dǎo)路徑優(yōu)化過程中存在著一些最短路優(yōu)化的問題。美國德克薩斯州大學(xué)的學(xué)者Ng.ManWo[3]等人針對(duì)傳統(tǒng)的動(dòng)態(tài)交通分配理論，假定路徑選擇僅依賴于時(shí)間，建立了一種平衡路徑選擇模型。這表明，基于實(shí)時(shí)路況信息的路徑誘導(dǎo)在交通管理系統(tǒng)中起著非常重要的作用，這也是本文研究的重點(diǎn)部分。國內(nèi)研究主要涉及動(dòng)態(tài)路徑選擇、動(dòng)態(tài)網(wǎng)絡(luò)最短路法、基于計(jì)算機(jī)技術(shù)的終端實(shí)現(xiàn)等方面。高峰等(2009)[4]基于決策場(chǎng)理論，建立面向過程的車輛動(dòng)態(tài)路徑選擇模型，主要研究行程時(shí)間、距離和擁堵路況對(duì)駕駛者的決策產(chǎn)生的影響，表明了不完全的交通信息不能對(duì)駕駛?cè)诉M(jìn)行有效的引導(dǎo)。這表明實(shí)時(shí)路況的實(shí)現(xiàn)會(huì)提高駕駛者的決策質(zhì)量，并對(duì)交通疏導(dǎo)起到了積極的作用?？紤]到實(shí)時(shí)路況的重要性，本文的模型最終實(shí)現(xiàn)也是基于一個(gè)動(dòng)態(tài)的交通網(wǎng)絡(luò)。孫曉梅等(2011)[5]也研究了動(dòng)態(tài)路徑的選擇模型，同樣地從微觀上優(yōu)化出行者的路線，促進(jìn)宏觀路網(wǎng)交通流量的均衡分配。秦穎(2008)[6]對(duì)最大流的研究主要是道路網(wǎng)絡(luò)優(yōu)化。通過分析交通擁堵區(qū)域的路網(wǎng)結(jié)構(gòu)，通過實(shí)施道路升級(jí)等措施，使道路之間流量均衡，路網(wǎng)通行能力最大，但是并沒有結(jié)合居民出行和路況實(shí)時(shí)變化，研究得不夠全面。雷東升(2008)[7]對(duì)導(dǎo)航儀的路徑規(guī)劃算法進(jìn)行了改進(jìn)，在傳統(tǒng)迪杰斯特拉算法和A*算法的基礎(chǔ)上，實(shí)現(xiàn)了動(dòng)態(tài)的導(dǎo)航，但主要改進(jìn)轉(zhuǎn)彎限制和單行道路等方面，并沒有從宏觀上考慮整個(gè)道路網(wǎng)的擁堵情況。本文的研究彌補(bǔ)了以上論文的不足，一方面將道路最大流模型與居民的出行選擇模型結(jié)合，另一方面也考慮了道路的實(shí)時(shí)路況，緊密結(jié)合道路實(shí)時(shí)流量的情況，選擇最優(yōu)的出行線路，更具有科學(xué)性和全面性。

3基于流量的道路通行能力和出行路線選擇模型

本節(jié)研究的是從一點(diǎn)出發(fā)到達(dá)另一點(diǎn)間的道路網(wǎng)絡(luò)，將在考慮道路容量、流量、路程的基礎(chǔ)上選擇一條最佳的路線，使得所走的路程最短，同時(shí)又盡量避免擁堵。

3.1　出行路線選擇模型設(shè)計(jì)

假設(shè)一個(gè)道路網(wǎng)中每條道路的容量、流量、長度都是已知的，然后通過容量對(duì)道路網(wǎng)計(jì)算最大流，再在實(shí)際流量不超過最大流量的前提下，運(yùn)用最短路模型，找出路程最短的出行線路。 步驟如下：

第一步，使用求最大流的標(biāo)號(hào)法算出道路網(wǎng)絡(luò)的最大流。

第二步，根據(jù)路程，利用最短路模型，選擇出一條路程最短的路線。

第三步，在考慮到實(shí)際流量不超過最大流量的前提下，利用最短路模型，對(duì)第二步中選定的路線進(jìn)行修改，找出一條不擁堵的最短路線。

3.2　算例分析

假設(shè)如圖2所示的道路網(wǎng)，居民要從V1處駕車行駛到V7處，已知每條道路上標(biāo)注的數(shù)字為容量和初始流量，初始流量設(shè)為0。我們按照以上步驟尋找最佳出行路線。

第一步，利用容量和初始流量計(jì)算道路網(wǎng)絡(luò)的最大流量，道路模型如圖2(第一個(gè)數(shù)字為道路容量，第二個(gè)數(shù)字為初始流量設(shè)為0)。

運(yùn)用標(biāo)號(hào)法，解得每條線路的最大流如圖3所示，其中每條邊上第一個(gè)數(shù)字代表道路容量，第二個(gè)數(shù)字代表該條道路的最大流量。

第二步，利用最短路模型找出道路網(wǎng)絡(luò)中從V1到V7路程最短的路徑。

假設(shè)每條道路的距離和實(shí)際流量已經(jīng)給出，再根據(jù)圖2的數(shù)據(jù)結(jié)合標(biāo)號(hào)法算出每條路的最大流量，得出圖4，這時(shí)每條路上第一個(gè)數(shù)字表示該條路的距離，第二個(gè)數(shù)字為依據(jù)最大流計(jì)算得出的每條路可承載的最大流量，第三個(gè)數(shù)字為實(shí)際流量。

圖2　道路網(wǎng)的容量和初始流量

圖3　每條線路的容量和最大流量

圖4　每條路的最大流量、實(shí)際流量和長度

我們利用最短路的Dijkstra算法求最佳出行路線，根據(jù)圖4得出距離矩陣為：

運(yùn)行結(jié)果如表1所示：

表1　只考慮路程最短的 Dijkstra運(yùn)行結(jié)果

L(v)是表示從v1出發(fā)到其他各個(gè)地點(diǎn)的最短路程。Z(v)是表示最短途徑下，到達(dá)此點(diǎn)必須經(jīng)過的前一點(diǎn)。由表1知，在只考慮路程最短不考慮道路是否擁堵的前提下，所選擇的最短路徑為v1→v2→v5→v7。

第三步，在考慮流量不超過利用最大流的情況下，利用最短路模型，選擇出一條不擁堵的最短路程。

最大流量矩陣為L，實(shí)際流量矩陣為L′

此時(shí)需要對(duì)上一步中的距離進(jìn)行修改，那些實(shí)際流量等于最大流量的道路會(huì)出現(xiàn)擁堵，就假設(shè)這些道路的路程為無窮大，這樣就能保證只有在沒有其他道路選擇的時(shí)候，才會(huì)選擇擁堵路段。

根據(jù)以上原理修改后的距離矩陣為：

考慮流量后的運(yùn)行結(jié)果如表2所示：

表2　考慮流量后的計(jì)算結(jié)果

L(v)是表示從v1出發(fā)到其他各個(gè)地點(diǎn)的最短路程(去掉了那些實(shí)際流量和最大流量相等的路線)。Z(v)是表示在到達(dá)某一地點(diǎn)時(shí)所用距離最短的前一地點(diǎn)(去掉了那些實(shí)際流量和最大流量相等的路線)。在考慮流量和路程的前提下，選擇的最佳路線為v1→v3→v4→v7(如表2所示)。

從以上分析可以看出，在不考慮流量的情況下，從v1出發(fā)到v7所選擇的最短路徑為v1→v2→v5→v7，總路程為15(這一般是現(xiàn)有的導(dǎo)航儀所顯示出來的路線)。在考慮流量的情況下，即考慮最大流模型的情況下，我們?cè)诒ＷC實(shí)時(shí)道路流量不超過道路的最大路流量的前提下，選擇出的合理的路線為v1→v3→v4→v7，總路程為19，雖然路程可能會(huì)有所增加，但是提高了整個(gè)道路網(wǎng)絡(luò)的通行能力，避免了擁堵狀況，也是一種路線的優(yōu)化。

4基于實(shí)時(shí)路況路線選擇模型

上一節(jié)只是簡(jiǎn)單的選用實(shí)際流量不超過最大流量的路線，對(duì)于路段也只劃分了擁堵和不擁堵兩種情況，在實(shí)際生活中，道路情況要更為復(fù)雜。所以本節(jié)對(duì)于擁堵路線，根據(jù)實(shí)際情況劃分為非常擁堵、一般擁堵、不擁堵，然后以距離最短和用時(shí)最短為目標(biāo)建立優(yōu)化模型，對(duì)擁堵情況下的出行路線進(jìn)行選擇。

首先運(yùn)用模型把流量轉(zhuǎn)化成速度，計(jì)算實(shí)時(shí)路況下每條道路需要的時(shí)間，然后再根據(jù)路程、時(shí)間建立最短路模型求出距離最短和用時(shí)最短的出行路線，并進(jìn)行對(duì)比。

4.1　速度流量模型

利用G-LN模型[8]來建立速度和流量間的關(guān)系，根據(jù)容易得到的流量數(shù)據(jù)來計(jì)算各個(gè)不同路段的平均速度，進(jìn)而計(jì)算出通過不同路段的時(shí)間。根據(jù)實(shí)際的數(shù)據(jù)模擬出圖5，推斷出速度和流量之間的關(guān)系比較符合指數(shù)模型。

G-LN速度和流量關(guān)系分段模型如下：

Q=aV2+bV+cV≥Vm

(1)

Q=D×lnV+EV≥Vm

(2)

(1)式是在速度較高，實(shí)際流量較小情況下的反應(yīng)流量和速度之間關(guān)系的二次函數(shù)的模型。

(2)式則是在速度較低，實(shí)際流量較高情況下的反應(yīng)流量和速度之間關(guān)系的對(duì)數(shù)函數(shù)模型。

圖5　速度與流量的關(guān)系圖

圖6　模擬的道路

假設(shè)有一個(gè)道路網(wǎng)絡(luò)如上圖6所示，居民要從起點(diǎn)處U1駕車行駛到終點(diǎn)U6處，我們將結(jié)合流量、路程和速度三方面因素，根據(jù)計(jì)算出的平均速度，得到每條道路需要行駛的時(shí)間。其中圖6中的粗線路段指的是暢通路段，較粗線段指的是一般擁堵的路段，較細(xì)線段指的是不擁堵的路段。

利用G-LN模型算出每條道路在各自的擁堵狀態(tài)下可以行駛的平均速度和所需的時(shí)間。各個(gè)路段的數(shù)據(jù)如下表所示：

表3　不同路段的數(shù)據(jù)信息

其中各個(gè)路段的擁堵程度，路程和流量都是已知的。我們從中選取了作者根據(jù)實(shí)際數(shù)據(jù)，利用G-LN分段模型，《城市干道交通流速—流量關(guān)系模型研究》[8]模擬出的道路參數(shù)情況作為我們所需參數(shù)的一部分。從而根據(jù)已知的流量數(shù)據(jù)，計(jì)算出不同路段的平均速度和時(shí)間，如表3所示。

4.2　距離最短和用時(shí)最短的最佳出行路線

在選擇出行路線時(shí)首先不考慮擁堵情況，只僅僅根據(jù)距離最短的原則，用最短路算法計(jì)算從U1出發(fā)到各點(diǎn)的距離最短的出行路線。然后再根據(jù)實(shí)時(shí)路況，考慮擁堵，找出一條用時(shí)最短的出行路線，并進(jìn)行比較。

圖6的距離矩陣為：

首先不考慮擁堵，按距離最短計(jì)算，結(jié)果如表4所示：

表4　按距離最短計(jì)算的結(jié)果

L(v)是表示從U1出發(fā)到其他各個(gè)地點(diǎn)的最短路程。Z(v)是表示在到達(dá)某一地點(diǎn)時(shí)所用距離最短的前一地點(diǎn)。由表4可以得知，在只考慮路程的前提下，從U1到U6的距離最短的線路U1→U6。

下面在考慮擁堵路段的情況下計(jì)算用時(shí)最短的出行路線，根據(jù)圖6寫出時(shí)間矩陣。

按用時(shí)最短計(jì)算的結(jié)果如表5所示：

表5　按時(shí)間最短計(jì)算的結(jié)果

L(v)是表示從U1出發(fā)到其他各個(gè)地點(diǎn)的最少時(shí)間。Z(v)是表示在到達(dá)某一地點(diǎn)時(shí)所用時(shí)間最少的前一地點(diǎn)。由表5我們可以得知，在只考慮時(shí)間的前提下，從U1到U6時(shí)間最短的出行路線為：U1→U2→U6。

對(duì)按路程最短計(jì)算的結(jié)果和按時(shí)間最短計(jì)算的結(jié)果進(jìn)行比較容易得出：距離最短的路線，不一定所用時(shí)間最短。

5結(jié)論及展望

本文從微觀層面上，對(duì)居民的出行問題進(jìn)行了研究，優(yōu)化了居民出行線路的選擇，一定程度上也對(duì)交通管理系統(tǒng)起到了積極的作用。研究方法基于最大流模型和最短路模型，根據(jù)出行兩個(gè)地點(diǎn)之間不同路線的道路的容量及流量需求數(shù)據(jù)，計(jì)算出通行能力約束條件下每條路線的最大通行量，以及在不超過最大通行量的條件下各出行路線所用的時(shí)間，找出時(shí)間最短路線，為居民出行提供合理化的建議。

在實(shí)際道路交通網(wǎng)絡(luò)中，道路的擁堵情況和線路的擁堵路段也是隨著車流量實(shí)時(shí)變化的，因此本文的研究主要基于一個(gè)動(dòng)態(tài)的道路網(wǎng)絡(luò)，居民所獲得的道路交通信息也是確定的全面的，這樣加強(qiáng)了本文研究方法的實(shí)用性和先進(jìn)性。在根據(jù)道路實(shí)時(shí)流量計(jì)算通過道路所用時(shí)間時(shí)，本文主要采用了速度流量模型，在以后的研究中，可以選取道路車流密度等因素來更加準(zhǔn)確地計(jì)算出在已知路況數(shù)據(jù)下的車行速度，降低選取路線的理論需求時(shí)間與實(shí)際需求時(shí)間之間的誤差。實(shí)時(shí)路況信息采集方面，需要進(jìn)一步提升現(xiàn)有的車用導(dǎo)航儀性能。在史軍勇[9]《基于GPRS的實(shí)時(shí)路況車載導(dǎo)航終端研究與實(shí)現(xiàn)》一文中，也對(duì)實(shí)時(shí)路況的實(shí)現(xiàn)進(jìn)行了研究，實(shí)驗(yàn)證明是可以實(shí)現(xiàn)的。相信在不久的將來，隨著GPRS技術(shù)的提升和終端硬件的推廣，我們的研究將會(huì)有更廣闊的應(yīng)用空間。

參考文獻(xiàn)：

[1]JLAlder，GSatapathy，VManikonda，BBowles，VJBlue.AMulti-agentapproachtocooperativetrafficmanagementandrouteguidance[J].TransportationResearchPartB，39(2005)：297-318.

[2]LipingFu.Aadaptiveroutingalgorithmforin-vehiclerouteguidancesystemswithreal-timeinformation[J].TransportationResearchPartC，11(2003)：375-388.

[3]NgManWo，WallerS.Dynamicroutechoicemodelinfaceofuncertaincapacities[C].WashingtonDC：TransportationResearchBoard88thAnnualMeeting，2009.

[4]高峰，王明哲. 面向決策過程的動(dòng)態(tài)路徑選擇模型[J]. 系統(tǒng)工程理論與方法，2009，9(5)：128-131.

[5]孫曉梅.多源交通信息下的動(dòng)態(tài)路徑選擇模型和方法研究[D].吉林：吉林大學(xué)，2011.

[6]秦穎. 北京市典型區(qū)域交通流量空間分布特征的初步研究[D].北京：北京交通大學(xué)，2008.

[7]雷東升.一種基于實(shí)時(shí)路況信息的動(dòng)態(tài)路徑規(guī)劃算法[J].計(jì)算機(jī)科學(xué)，2008，35(4)：28-30.

[8]高超，李鳴，楊孝寬，紀(jì)英. 城市干道交通流速—流量關(guān)系模型研究[J].山東交通學(xué)院學(xué)報(bào)，2005，05(3)：16-20.

[9]史勇軍，張曉煜. 基于GPRS的實(shí)時(shí)路況車載導(dǎo)航終端研究與實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，21(9)：156-160.

[10]蘇鎮(zhèn)洪，趙文秀，龍科軍. 道路網(wǎng)絡(luò)容量的多端最大流算法[J].交通科學(xué)與工程，2012，28(1)：84-89.

[11]周培德.道路交通網(wǎng)中任意兩點(diǎn)之間最短路徑的快速算法[J].計(jì)算機(jī)工程與科學(xué)，2002，24(4)：35-37.

(責(zé)任編輯：宋金寶)