考虑实时路况的出行路线选择模型

考虑实时路况的出行路线选择模型

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

(中国传媒大学 理工学部，北京100024)

摘要：为了缓解交通拥堵问题，本文在现有的导航仪基础上，考虑到道路的实时情况，设计新的导航仪，帮助居民选择出用时最短且能尽量避免拥堵的路线。研究主要包括两方面：首先，在存在不拥堵路线的情况下，利用最大流模型计算出道路流量，结合实际流量，在尽量避免拥堵(实际流量不超过最大流量)的情况下，求出最短路程，给出建议。然后，考虑拥堵问题难以避免，加强了与实际道路状况的联系，对道路出行选择模型进行了优化，先将道路分为非常拥堵、存在拥堵、畅通三种情况，然后再根据道路实时流量，利用G-LN的模型计算出车道的速度，结合路程，找出用时最短的路线。

关键词：道路流量；出行选择模型；最大流模型；居民出行路线；最短路模型

中图分类号：O224文献标识码：A

收稿日期：2014-09-20

基金项目：国家自然科学基金(71172040)；中国传媒大学理科

作者简介：李倩(1993-)，女(汉族)，河南内乡人，中国传媒大学统计学专业.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引言

交通拥堵是一定时间道路交通的需求量超过道路的容量，超过部分的交通流量滞留在道路上的现象。近几年高速路交通拥堵问题日益严重，路况实际能承受的最大流量模糊不清，严重影响了居民的出行选择。

现有的导航仪，只是按照最短路线制定出行方案，给出的路线大部分会出现拥堵情况，这时，最短路线就不一定是最省时的，而且单条道路车流量长期过大，会加速道路的损伤。考虑到这种情况，我们根据实时的路况，结合道路长度、容量、流量，制定出更加合理的路线，使导航出来的路线既能减少拥堵情况的产生，又最省时。设计思路如下：

图1　设计的基本思路

2研究现状综述

针对道路拥堵和出行选择的问题，近几年国内外学者从不同方面进行了研究。美国学者JeffreyL.Alder[1]等人提出了一种基于分布式多智能体的改善交通诱导系统与交通管理系统的集成方法；加拿大滑铁卢大学学者LiPingfu[2]提出了一种基于实时信息的自适应路径优化算法，来解决交通诱导路径优化过程中存在着一些最短路优化的问题。美国德克萨斯州大学的学者Ng.ManWo[3]等人针对传统的动态交通分配理论，假定路径选择仅依赖于时间，建立了一种平衡路径选择模型。这表明，基于实时路况信息的路径诱导在交通管理系统中起着非常重要的作用，这也是本文研究的重点部分。国内研究主要涉及动态路径选择、动态网络最短路法、基于计算机技术的终端实现等方面。高峰等(2009)[4]基于决策场理论，建立面向过程的车辆动态路径选择模型，主要研究行程时间、距离和拥堵路况对驾驶者的决策产生的影响，表明了不完全的交通信息不能对驾驶人进行有效的引导。这表明实时路况的实现会提高驾驶者的决策质量，并对交通疏导起到了积极的作用。考虑到实时路况的重要性，本文的模型最终实现也是基于一个动态的交通网络。孙晓梅等(2011)[5]也研究了动态路径的选择模型，同样地从微观上优化出行者的路线，促进宏观路网交通流量的均衡分配。秦颖(2008)[6]对最大流的研究主要是道路网络优化。通过分析交通拥堵区域的路网结构，通过实施道路升级等措施，使道路之间流量均衡，路网通行能力最大，但是并没有结合居民出行和路况实时变化，研究得不够全面。雷东升(2008)[7]对导航仪的路径规划算法进行了改进，在传统迪杰斯特拉算法和A*算法的基础上，实现了动态的导航，但主要改进转弯限制和单行道路等方面，并没有从宏观上考虑整个道路网的拥堵情况。本文的研究弥补了以上论文的不足，一方面将道路最大流模型与居民的出行选择模型结合，另一方面也考虑了道路的实时路况，紧密结合道路实时流量的情况，选择最优的出行线路，更具有科学性和全面性。

3基于流量的道路通行能力和出行路线选择模型

本节研究的是从一点出发到达另一点间的道路网络，将在考虑道路容量、流量、路程的基础上选择一条最佳的路线，使得所走的路程最短，同时又尽量避免拥堵。

3.1　出行路线选择模型设计

假设一个道路网中每条道路的容量、流量、长度都是已知的，然后通过容量对道路网计算最大流，再在实际流量不超过最大流量的前提下，运用最短路模型，找出路程最短的出行线路。 步骤如下：

第一步，使用求最大流的标号法算出道路网络的最大流。

第二步，根据路程，利用最短路模型，选择出一条路程最短的路线。

第三步，在考虑到实际流量不超过最大流量的前提下，利用最短路模型，对第二步中选定的路线进行修改，找出一条不拥堵的最短路线。

3.2　算例分析

假设如图2所示的道路网，居民要从V1处驾车行驶到V7处，已知每条道路上标注的数字为容量和初始流量，初始流量设为0。我们按照以上步骤寻找最佳出行路线。

第一步，利用容量和初始流量计算道路网络的最大流量，道路模型如图2(第一个数字为道路容量，第二个数字为初始流量设为0)。

运用标号法，解得每条线路的最大流如图3所示，其中每条边上第一个数字代表道路容量，第二个数字代表该条道路的最大流量。

第二步，利用最短路模型找出道路网络中从V1到V7路程最短的路径。

假设每条道路的距离和实际流量已经给出，再根据图2的数据结合标号法算出每条路的最大流量，得出图4，这时每条路上第一个数字表示该条路的距离，第二个数字为依据最大流计算得出的每条路可承载的最大流量，第三个数字为实际流量。

图2　道路网的容量和初始流量

图3　每条线路的容量和最大流量

图4　每条路的最大流量、实际流量和长度

我们利用最短路的Dijkstra算法求最佳出行路线，根据图4得出距离矩阵为：

运行结果如表1所示：

表1　只考虑路程最短的 Dijkstra运行结果

L(v)是表示从v1出发到其他各个地点的最短路程。Z(v)是表示最短途径下，到达此点必须经过的前一点。由表1知，在只考虑路程最短不考虑道路是否拥堵的前提下，所选择的最短路径为v1→v2→v5→v7。

第三步，在考虑流量不超过利用最大流的情况下，利用最短路模型，选择出一条不拥堵的最短路程。

最大流量矩阵为L，实际流量矩阵为L′

此时需要对上一步中的距离进行修改，那些实际流量等于最大流量的道路会出现拥堵，就假设这些道路的路程为无穷大，这样就能保证只有在没有其他道路选择的时候，才会选择拥堵路段。

根据以上原理修改后的距离矩阵为：

考虑流量后的运行结果如表2所示：

表2　考虑流量后的计算结果

L(v)是表示从v1出发到其他各个地点的最短路程(去掉了那些实际流量和最大流量相等的路线)。Z(v)是表示在到达某一地点时所用距离最短的前一地点(去掉了那些实际流量和最大流量相等的路线)。在考虑流量和路程的前提下，选择的最佳路线为v1→v3→v4→v7(如表2所示)。

从以上分析可以看出，在不考虑流量的情况下，从v1出发到v7所选择的最短路径为v1→v2→v5→v7，总路程为15(这一般是现有的导航仪所显示出来的路线)。在考虑流量的情况下，即考虑最大流模型的情况下，我们在保证实时道路流量不超过道路的最大路流量的前提下，选择出的合理的路线为v1→v3→v4→v7，总路程为19，虽然路程可能会有所增加，但是提高了整个道路网络的通行能力，避免了拥堵状况，也是一种路线的优化。

4基于实时路况路线选择模型

上一节只是简单的选用实际流量不超过最大流量的路线，对于路段也只划分了拥堵和不拥堵两种情况，在实际生活中，道路情况要更为复杂。所以本节对于拥堵路线，根据实际情况划分为非常拥堵、一般拥堵、不拥堵，然后以距离最短和用时最短为目标建立优化模型，对拥堵情况下的出行路线进行选择。

首先运用模型把流量转化成速度，计算实时路况下每条道路需要的时间，然后再根据路程、时间建立最短路模型求出距离最短和用时最短的出行路线，并进行对比。

4.1　速度流量模型

利用G-LN模型[8]来建立速度和流量间的关系，根据容易得到的流量数据来计算各个不同路段的平均速度，进而计算出通过不同路段的时间。根据实际的数据模拟出图5，推断出速度和流量之间的关系比较符合指数模型。

G-LN速度和流量关系分段模型如下：

Q=aV2+bV+cV≥Vm

(1)

Q=D×lnV+EV≥Vm

(2)

(1)式是在速度较高，实际流量较小情况下的反应流量和速度之间关系的二次函数的模型。

(2)式则是在速度较低，实际流量较高情况下的反应流量和速度之间关系的对数函数模型。

图5　速度与流量的关系图

图6　模拟的道路

假设有一个道路网络如上图6所示，居民要从起点处U1驾车行驶到终点U6处，我们将结合流量、路程和速度三方面因素，根据计算出的平均速度，得到每条道路需要行驶的时间。其中图6中的粗线路段指的是畅通路段，较粗线段指的是一般拥堵的路段，较细线段指的是不拥堵的路段。

利用G-LN模型算出每条道路在各自的拥堵状态下可以行驶的平均速度和所需的时间。各个路段的数据如下表所示：

表3　不同路段的数据信息

其中各个路段的拥堵程度，路程和流量都是已知的。我们从中选取了作者根据实际数据，利用G-LN分段模型，《城市干道交通流速—流量关系模型研究》[8]模拟出的道路参数情况作为我们所需参数的一部分。从而根据已知的流量数据，计算出不同路段的平均速度和时间，如表3所示。

4.2　距离最短和用时最短的最佳出行路线

在选择出行路线时首先不考虑拥堵情况，只仅仅根据距离最短的原则，用最短路算法计算从U1出发到各点的距离最短的出行路线。然后再根据实时路况，考虑拥堵，找出一条用时最短的出行路线，并进行比较。

图6的距离矩阵为：

首先不考虑拥堵，按距离最短计算，结果如表4所示：

表4　按距离最短计算的结果

L(v)是表示从U1出发到其他各个地点的最短路程。Z(v)是表示在到达某一地点时所用距离最短的前一地点。由表4可以得知，在只考虑路程的前提下，从U1到U6的距离最短的线路U1→U6。

下面在考虑拥堵路段的情况下计算用时最短的出行路线，根据图6写出时间矩阵。

按用时最短计算的结果如表5所示：

表5　按时间最短计算的结果

L(v)是表示从U1出发到其他各个地点的最少时间。Z(v)是表示在到达某一地点时所用时间最少的前一地点。由表5我们可以得知，在只考虑时间的前提下，从U1到U6时间最短的出行路线为：U1→U2→U6。

对按路程最短计算的结果和按时间最短计算的结果进行比较容易得出：距离最短的路线，不一定所用时间最短。

5结论及展望

本文从微观层面上，对居民的出行问题进行了研究，优化了居民出行线路的选择，一定程度上也对交通管理系统起到了积极的作用。研究方法基于最大流模型和最短路模型，根据出行两个地点之间不同路线的道路的容量及流量需求数据，计算出通行能力约束条件下每条路线的最大通行量，以及在不超过最大通行量的条件下各出行路线所用的时间，找出时间最短路线，为居民出行提供合理化的建议。

在实际道路交通网络中，道路的拥堵情况和线路的拥堵路段也是随着车流量实时变化的，因此本文的研究主要基于一个动态的道路网络，居民所获得的道路交通信息也是确定的全面的，这样加强了本文研究方法的实用性和先进性。在根据道路实时流量计算通过道路所用时间时，本文主要采用了速度流量模型，在以后的研究中，可以选取道路车流密度等因素来更加准确地计算出在已知路况数据下的车行速度，降低选取路线的理论需求时间与实际需求时间之间的误差。实时路况信息采集方面，需要进一步提升现有的车用导航仪性能。在史军勇[9]《基于GPRS的实时路况车载导航终端研究与实现》一文中，也对实时路况的实现进行了研究，实验证明是可以实现的。相信在不久的将来，随着GPRS技术的提升和终端硬件的推广，我们的研究将会有更广阔的应用空间。

参考文献：

[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]高峰，王明哲. 面向决策过程的动态路径选择模型[J]. 系统工程理论与方法，2009，9(5)：128-131.

[5]孙晓梅.多源交通信息下的动态路径选择模型和方法研究[D].吉林：吉林大学，2011.

[6]秦颖. 北京市典型区域交通流量空间分布特征的初步研究[D].北京：北京交通大学，2008.

[7]雷东升.一种基于实时路况信息的动态路径规划算法[J].计算机科学，2008，35(4)：28-30.

[8]高超，李鸣，杨孝宽，纪英. 城市干道交通流速—流量关系模型研究[J].山东交通学院学报，2005，05(3)：16-20.

[9]史勇军，张晓煜. 基于GPRS的实时路况车载导航终端研究与实现[J].计算机技术与发展，2011，21(9)：156-160.

[10]苏镇洪，赵文秀，龙科军. 道路网络容量的多端最大流算法[J].交通科学与工程，2012，28(1)：84-89.

[11]周培德.道路交通网中任意两点之间最短路径的快速算法[J].计算机工程与科学，2002，24(4)：35-37.

(责任编辑：宋金宝)