城市路网的一种最优路径搜索算法

贾新春,彭登永,李雷,张敏敏

(1.山西大学 自动化系,山西 太原 030013;2.山西大学 数学科学学院,山西 太原 030006)

0 引言

随着经济的发展和人们生活水平的提高,车辆人均拥有量也逐渐上升,然而城市道路等基础设施建设并没有随之增加。这直接导致了城市交通拥堵现象的发生。为了缓解交通拥堵带来的影响,已经发展了两类方法:一是宏观调控;二是微观诱导。前者根据城市路网中的实时交通状况调节各交叉口信号灯配时方案,进而调控引导交通流,增大城市道路资源利用率,减少交通拥堵现象发生。后者根据实时交通状况及车辆起点与终点信息,再结合实时交通状况,为车辆寻找最优路径,以降低交通拥堵对个体车辆的影响。本文方法属于后者。

针对城市路网的最优路径算法有多种,下面列举一些其中有代表性的算法。杨娟等[1]应用不等式约束方法建立了同时兼顾时间和距离要素的最优路径模型,并应用罚函数、零权和无限权的思想给出模型的算法。徐达等[2]将城市路网构建成加权有向图模型,并改进了Floyd算法用于求解该模型,提高了计算效率。杨庆芳等[3]提出一种基于云计算的并行遗传算法来求解城市路网最短路径问题,充分利用了计算资源,提高了算法计算速度。类似的基于大数据技术的方法[4],充分利用现有的大量交通数据,其目标不是保证最优性,而是在可接受的计算时间内提供高质量的解决方案。孙威等[5]采用快速收敛牛顿算法获得城市路网最短路径,该算法拥有较高的精度和较快的收敛速度。赵峰等[6]提出了一种基于局部信息获取策略的动态改进型蚁群算法,与传统蚁群算法相比,提高了路径规划的收敛速度,拥有一定的动态路径规划能力。宋青等[7]提出了一种新的分层路径计算算法,该算法利用层次图模型的优点,采用区域剪枝策略,在不影响搜索精度的前提下,显著地减少了搜索空间。一些学者考察更具体因素如车道变换和转弯限制[8-10],以求所得结果更符合实际情况。此外,自从Nordbeck[11]于1969年提出椭圆限制搜索区域的最短路径算法,随后出现了多种限制区域最短路径算法[12-15],这些算法减小了搜索区域,进而降低了计算量。

本文首先将起点与终点所在连线为对角线的矩形区域作为限制搜索区域,综合考虑了行车环境中影响道路阻抗的两大主要因素:时变的交通流及定常的空间距离,同时考虑了交叉口信号灯调控的影响,建立了针对城市路网的限制搜索区域时变权重有向图模型,给出了相应的最优路径搜索算法。此外,该算法在每次选择最优路段时考虑了方向问题,进而减小了搜索范围,降低了计算量与存储量。最后在MATLAB平台对所提算法进行了仿真验证,证明了其可行性、有效性、自适应性和实时性。本文创新点为:在建立针对城市路网的时变权重有向图模型过程中,既考虑了主要时变因素——车流密度,也考虑了搜索方向因素。

1 基本原理及方法

1.1 城市路网模型

城市道路网络中包含双向道路和单向道路,因此城市道路网络可抽象为一个双向有向图模型,如图1所示,其中道路交叉口作为顶点,交叉口间的路段作为有向边。同时,城市道路中不同的路段在不同的时间点道路的拥堵程度以及不同路段的长度等因素使得车辆通过城市道路所花费的时间是动态变化的,为此引入时变路阻函数作为有向图中边的权函数。

图1 城市路网模型示意图Fig.1 Schematic map of urban road network model

为了缩小搜索范围,减少计算量,这里只考虑以起点和终点连线为对角线的矩形区域。假设该区域内有n个交叉口,则可以用n阶的邻接矩阵表示该区域的路网模型,如式(1)所示。该矩阵中的第i行第j列的元素表示第i个顶点到第j个顶点的权值。矩阵主对角线上的元素均为0。如果从一个顶点不能直接到达另一个顶点,则其对应的邻接矩阵中的元素为无穷大,如此对于单行道的路段也可以包含在该模型中。邻接矩阵中的元素,即路阻函数的确定在接下来进行。

(1)

1.2 时变路阻(权)函数

与城市道路网络模型密切相关的是交通流理论,表征交通流特性的基本参数是交通流量、行车速度和车流密度。交通流量qij(t)(单位:辆/小时)是指t时刻在x点(x点在第i个交叉口到第j个交叉口方向的路段上)处单位时间内通过的车辆数。行车速度vij(t)(单位:km/h)是指在t时刻在x点附近车辆速度的平均值。车流密度ρij(t)(单位:辆/千

米)是指t时刻在x点处每车道单位长度道路上拥有的车辆数。根据上述定义,交通流的3个参数之间符合式(2)。

q=ρv

(2)

当道路上的车辆增多、车流密度增大时,车辆间距将缩小,出于安全考虑,驾驶员将降低车速;当车流密度变小时,驾驶员则会提高车速。因此,车速随着车流密度的增加呈单调下降趋势。格林希尔兹(Green Shields)于1934年提出了v-ρ线性关系模型[16],即

(3)

(4)

(5)

(6)

(7)

路阻也称路权,由路段阻抗和节点(交叉口)阻抗组成。对于传统的路径规划算法,道路权重选取的是路段的长度,这是大部分路径规划的首选指标,因为它容易获得,相对比较简单。但此类指标只适应于道路畅通、路况较为一致的道路,并没有充分考虑由于长度以外的路阻所带来的延误。由于大多数路阻最终都会导致时间延误,或者与时间延误相关,因此构造路阻函数为

(8)

结合(6)、(7)和(8)式,可得

(9)

1.3 针对城市路网的最优路径求解

针对城市路网的带权双向有向图模型已经建立起来,接下来需要求解从起点到终点的最优路径。为此,首先需要作一些必要的假设。

1.3.1 模型假设

由于所建立的模型涉及多个参数,为了保证模型的严谨性及其求解算法的严密性,需要对其中一些参数作必要的假设与限定。

2) 如果能直接测算得到车流密度ρij(t),则假设可以较准确地预测未来时间段Δt内的城市路网各路段的车流密度值。

3) 如果不能直接测算得到车流密度ρij(t),则必须能测算交通流量qij(t)和交通流平均速度vij(t),并且假设能较准确地预测未来时间段Δt(一般不超过15 min)内的城市路网各路段的交通流量值与交通流平均速度值。

4) 假设车流密度ρij(t)在短时间段Δt内变化幅度较小,如此在将未来短时间段Δt内车流密度的均值作为权重函数输入变量时可以减小误差。

5) 假设城市路网中各交叉口的位置及信号灯配时方案均是已知的。

6) 为了计算方便,假设起点和终点都在有向网的顶点。如果起点或终点不在顶点,则确定邻近顶点作为代起点或代终点。邻近顶点的确定方法为:起点的邻近顶点选择起点所在有限弧的终止端;终点的邻近顶点选取终点所在有向弧的起始端。

7) 假设车辆在城市路网中除了在交叉口等待绿灯外,其余时间都不停车,直到到达终点。如此可以保证算法所选各路段的局部最优性。

1.3.2 针对城市路网的最优路径算法

根据前文所述,如果将未来短时间段Δt内车流密度的均值作为输入变量,则可利用类似于微积分理念将具有时变特性的模型分解成若干静态模型。根据这一思路,可利用如下针对城市路网的最优路径算法步骤求解上述模型。

2) 初始化,以某一时刻为算法初始时刻t0;计算时间段[t0,t0+Δt)内的符合θ取值范围的以当前所在顶点为起始端的有向弧的车流密度均值,并将其作为输入变量;记录当前所在顶点的编号。

3) 判断当前所在顶点是否是终点(或代终点),若是,则停止算法,输出所经过的顶点序列,即为所求最优路径,输出对应的行程时间;否则继续执行下一步。

4) 更新参数,k=k+1;tk=t;计算时间段[tk,tk+Δt)(k=0,1,2,…)内的符合θ取值范围的以当前所在顶点为起始端的有向弧的车流密度均值,并将其作为输入变量。

5) 根据前文公式(9)计算符合θ取值范围的以当前所在顶点为起始端的有向弧的权重,选取其中权重最小的有向弧作为接下来行驶的路段,沿该有向弧到达下一顶点。

1.3.3 算法分析

前文对针对城市路网的最优路径搜索算法进行了详细描述,包括模型基本假设及具体的算法步骤,这里按照前文所述算法步骤,可绘制流程图如图2,下面分析和讨论本算法。

图2 算法流程图Fig.2 Flow chart of algorithm

确定以起点与终点连线为对角线的矩形区域为搜索区域,可减少不必要的搜索范围,且可以保证起点到最优路径中任一顶点的距离不大于起点到终点的距离。在平面上,当前所在顶点到终点的向量与起点到终点的向量间的夹角θ最大取值范围为[0, 180°]。本文算法取θ∈[0, 90°),如此可避免所走路径连接成环,从而令所选路径方向尽可能接近起点到终点的方向;同时可以减少不必要的搜索范围,降低算法计算量。

由于限定了整体的矩形搜索区域,且避免了所走路径连接成环,使得整个最优路径各路段的空间距离之和不大于所限定的矩形搜索区域的两条直角边之和。这一点保证了本文算法比传统的仅将空间距离作为权重的算法更优秀,因为本算法考虑了动态变化的行车环境,能够自适应选取最优路径,而仅将空间距离作为权重的算法所选取的路径是固定不变的,不能适应动态变化的环境。

城市路网中各处的行车环境时刻在变化,这对最优路径的搜索造成较大的影响。本文算法利用短时预测得到的未来短时间段Δt内车流密度的均值作为输入变量,选取下一步要走的路段。当通过所选取的路段到达下一顶点后,重新预测未来短时间段Δt内车流密度。重复这一过程,直到到达终点为止。在这一过程中,每次循环所选取的路段均是综合考虑当时行车环境的最优路段,这保证了所选整体路径在当时所处行车环境下的最优性。

2 仿真实验及结果

根据上节描述的算法,利用MATLAB软件进行了仿真实验。在实验过程中,采用图1所示的简化城市路网图。为了尽可能接近实际的城市道路网络系统,将图1 中的各路段分成了三级:主干路、次干路、支路,并按照《城市交通运行状况评价规范》[18]中的标准给出各路段设置了基本参数。

对应于图1中各编号交叉口的坐标如表1所示。主干路包括1-2-3-4-5和24-25-26-27-28-29-30;次干路包括1-6-17-24、2-8-14-21-26、3-9-15-22-27、4-10-16-23-28、5-12-19-30;其余路段均为支路。这三级道路的自由流速度依次设为50、40、30(单位:km/h),阻塞密度依次设为125、115、105(单位:辆/千米)。两条主干路上各交叉口信号周期时长设为0.04 h,第18交叉口信号周期时长设为0.02 h,其余交叉口信号周期时长设为0.03 h。此外,支路中还有两条单向路段17→20和16→18,其余各路段均为双向路段。作为输入变量的车流密度和交叉口时间延误是在合理范围内随机生成的。

根据上述所设参数,将上一节描述的算法在MATLAB平台上进行编程实现,选取第1个交叉口为起点、第30个交叉口为终点,得到结果如图3所示(实线为本文算法所求最优路径,上三角标记起点,下三角标记终点),验证了所提算法的可行性与有效性。如果是传统的最短路径搜索算法,只考虑空间距离这类定常因素,则所搜索的路径将是固定不变的,不适用于实际情况中城市道路网络多变复杂的行车环境。从这一角度也证明了本文模型算法的自适应特性。

表1 各编号交叉口的坐标

图3 不同行车环境中的最优路径图Fig.3 Optimal path diagram in different driving environments

此外,本文进行了对比仿真实验,从图1所示的地图中任意选取两个交叉口作为起点和终点,分别利用本文算法和传统的Floyd算法搜索最优路径[2]。结果发现在软件平台MATLAB(R2014a)及硬件平台3.2 GHz处理器(CPU)安装内存(RAM)4 GB基础上,在行车环境动态变化的情况下,本文算法对于图1中的任意两个交叉口都能搜索到最优路径。在相同条件下,Floyd算法(道路权重仅考虑空间距离)则由于时间复杂度(O(n3))较大,导致只能实现部分交叉口之间的最优路径搜索,多数最优路径搜索过程需要花费时间超过30 min,例如以第1交叉口为起点,分别以第10、11、13、16、18、19、29、30交叉口为终点的最优路径搜索仿真实验消耗时间均在30 min以上。通过这一对比仿真实验,可凸显本文算法的实时性。

3 结论

本文综合考虑了城市路网中影响道路阻抗的时变因素与定常因素,结合限制搜索区域方法,同时引入搜索方向因素,建立了针对城市路网的限制搜索区域的时变权重有向图模型,并给出了相应的最优路径搜索算法。该模型算法更符合城市路网中的实际交通状况,能够在不断变化的交通流影响下,自适应地选取最优路径,保证了车辆在当时所处环境下所选路径是最优的。仿真实验验证了该模型算法的有效性、自适应性和实时性。

虽然考虑了城市路网中影响最优路径搜索的交通流的主要时变因素,但同样还存在其他时变因素未能考虑,如天气等。此外,本文模型算法是建立在多个基本假设基础之上的,尤其是需要较准确地预测未来短时间内车流密度,可能使得算法存在一定局限性。因此,我们下一步工作是从以上两方面来改进模型算法。