不确定性条件下优路径的选择

1、不确定性条件下最优路径的选 择作者:日期:#不确定性条件下最优路径的选择目前，交通拥挤和事故正越来越严重的困扰着城市交通。文章针对车辆的行驶时间存在的不确定性给出了最优路径的评价模型，帮助驾驶员寻找一条可靠、 快速、安全的最优路径。文章还分析不同路段之间的时空相关性对行程时间的影 响，为驾驶员路径的选择做了周全的考虑。针对问题一，我们建立了两种不同评价标准的最优路径评价模型.模型I基于对存在驾驶员偏好的最优路径选择问题的研究 ，提出了一种能够综合反映驾驶 员偏好的多属性决策方法，建立了驾驶员偏好与路径属性总偏差最小的最优评价 模型。模型n基于对不确定性条件下车辆准时到达终点的可靠性的分析，定义

2、可靠度来定量描述车辆行驶时间的不确定性，同时利用概率论知识给出了最优路径 数数学表达式和定义一在可靠度 R>95%勺条件下，预留时间T最短，则为最优 路径。利用MATLA踹程求解，将所建模型应用到例子中，得出的结论是：选择 道路A,验证了模型的正确性。针对问题二，在问题一定义的最优路径的基础上， 我们将AK这11个地点 之间的交通网络图看作一个无向赋权图，综合考虑均值、标准差这两个量作为权， 建立了图论模型.基于Dijkstra 最短路径算法，我们设计了一种能够涉及两个 权重的改进算法求解最短路问题.利用MATLA褊程，得出最优路径选择结果为： A- C- K- GH* B。针对问题三，

3、基于车流波动理论，建立行驶时间模型， 从时间和空间两个维 度描述交通路段之间行驶时间的相关性。本文逻辑严谨，切入点独到，综合运用多种模型，结果可靠。关键词：最优路径；Dijkstra 算法；图论模型；车流波动理论31.问题的重述在复杂的交通环境下，如何寻找一条可靠、快速、安全的最优路径，已经成 为所有驾驶员的共识。传统的最优路径问题的研究大多数是基于 理想”的交通状况下分析的，即： 假设每条路段上的行驶时间是确定的。 在这种情况下，最优路径就是行驶时间最 短的路径，可以用经典的最短路径算法来搜索 （例如Dijkstra最短路径算法）。目 前的车辆路径导航系统也大都是基于这种理想的状况下的最优路

4、径算法，寻找行驶时间最短的路径。事实上，由于在现实生活中，会受到很多不确定性因素的影 响，例如：交通事故、恶劣天气、突发事件等，车辆的行驶时间存在着不确定性。问题一：对于一般的交通网络，假设已知每条路段行驶时间的均值和标准 差，请建立数学模型，定量的分析车辆行驶时间的不确定性， 然后给出在不确定 性条件下车辆从起点到终点的最优路径的定义和数学表达式，将此模型应用到图1的例子中会选择哪条道路。问题二：根据第一问的定义，已知每条路段行驶时间的均值和标准差 （见图、 表,图表中A为起点B为终点），设计算法搜索最优路径，并将该算法应用到具体 的交通网络中，用计算结果验证算法的有效性。 如果可能的话，从

5、理论上分析算 法的收敛性、复杂性等性质。问题三：在现实的交通网络中，某个路段发生了交通拥堵，对上游或者下游 路段的交通状况有很大的影响，从而导致了交通路段之间的行驶时间有一定的相 关性，请建立数学模型描述这种交通路段之间行驶时间的相关性，并将这种相关性应用到第一问和第二问的最优路径搜索问题中， 并设计算法解决考虑相关性的 最优路径搜索问题，给出算例验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。2 .模型假设1 .假设车辆在每条路段上的行驶时间是随机变量；2 .假设车辆在同一路段上的行程时间t服从正态分布；3 .假设在同密度车流中各单个车辆的行驶状态与前车完全一致;4

6、.假设题目所给数据真实可靠；5 .假设各不同路段的期望时间和标准差时间相互独立；6 .假设同一路段上下游的期望时间和标准差时间相同。3 .变量说明aj:第i条路径的第j个属性的客观值； bj：第k个出行者对第j个属性的可接受值;kj:第k个出行者对第j个属性的权重;d (aj, bkj):在第j个属性下,第k个出行者的主观偏好值bkj与第i条路径的客观属性值aj之间的偏差；Ri：第i条路径的可靠度；Ti：第i条路径到达目的地的预留时间；i：第i条路径行程时间的均值；i：第i条路径行程时间的标准差；j：从i地到j地的时间均值;j：从i地到j地的时间标准差；le(u)：赋权图中顶点u的均值；1d(

7、u)：赋权图中顶点u的标准差；We：均值邻接矩阵；Wd：标准差邻接矩阵；Ta1(t)：车辆在驶人流的行驶时间；Ta2。)：车辆在排队流中的排队等待时间；Ta3(t)：在瓶颈段的行驶时间；Ta4 (t)：车辆在瓶颈段下游行驶时间；La)：车辆在瓶颈段上游正常行驶长度；La2。)：某时刻队列的排队长度；La,。)：瓶颈段长度；La4(t)：车辆在瓶颈段下游自由行驶的长度；La5(t)：瓶颈段与道路入口间的距离；Ta(t)：时间t进入路段a的车辆在a上的行驶时间;kn：不同路段的交通流密度(n=1,2,3,4 );qn ：不同路段的交通流密度(n=1,2,3,4 );M，V2 :区域1,2车辆的平均

8、速度；Vw :集结波面的移动速度4 .模型的建立与求解4.1 问题一的模型建立与求解4.1.1 模型的建立4.1.1.1 模型 I(1)最优路径评价指标综合考虑影响驾驶员路径的选择因素，本文选择行驶时间、行驶距离、 拥挤程度(路上车辆数、排队长度)、出行费用、行驶困难程度(道路宽度等) 等作为选择最优路径的评价指标2 ,即决策变量。图1.最优路径的评价指标(2)最优路径的确定现实生活中，驾驶员依据自身偏好来选择路径时， 对于不同的评价指标有着不同 要求，且对于评价指标值存在一个可接受范围而不是一个精确值。 并且对于路径 而言，由于路径上行驶的速度和数量等方面是动态变化的， 这就引起路径自身评

9、价属性值的波动。故本文以区间的形式来表达评价参数。设aj aj分别表示第i条路径的第j个属性的客观值aj的下限和上限，即ajaj，ajU,设第k个出行者对第j个属性的可接受范围为b. b；，bjU ,由于种种条件的制约，决策者的主观偏好与客观值之间往往存在着一定的差距。为 了使决策具有合理性，应使决策者的主观偏好与客观属性值的总偏差最小.最终建立如下评价模型定义为最优路径30n mmin(d(aj,bkj) kj)2( 1)i 1 j 1stkj 0kj 1Ij 1(D其中，d(aj,bkj) aijL bJ ajU bkjU表示在第j个属性下，第k个出行者的 主观偏好值bkj与第i条路径的客

10、观属性值aj之间的偏差；F()表示在所有属性 下第k个出行者的主观偏好值与客观属性值的总偏差；kj表示第k个出行者对第j个属性的权重。n mmin(d(aj,bkj) kj)2( 2)i 1 j 14.1.1.2 模型 H我们定义可靠度Ri来刻画时间行驶时间的不确定性，R 0,1,表示在预留 时间Ti之内到达目的地的概率。假设车辆在同一路段上的行程时间 t服从正态分 布N( , 2),则第i条路径的可靠度可表示为：Tii 0 iRi P(0 ti ()().(2)据此，为了尽可能准确的到达目的地，可选取R =95%在满足P(0 ti Ti) 95%的条件下，min Ti对应道路i即为最优路径。

11、4.1.2模型的求解与检验为了便于求解，我们选取模型n进行讨论。由公式(2)解得1iTi(Ri( 一) i i(3)5其中，Ri =0.95,表示标准正态分布的反函数。将图1所给的数据:出：道路A预留时间Ti1=33 ,1=1;2=30 ,2=15带入公式（3）计算 34.6min ,道路B预留时间T2 58.8min ,即最优路径为绕城快速路。结果与实际选择相符，间接验证了模型的正确性。4.2问题二的模型建立与求解4.2.1 模型的建立对于一般交通网络，为了方便设计算法找到最优模型，我们根据附表中A-H之间路段的时间均值和时间标准差，将其转化为图论模型。将11个地点A H看成11个顶点，分别

12、从1-11进行标号，构成一个顶点 集：V V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11则可将11个地点之间的交通网络图看作一个无向赋权图(图2),每条路为图中的边。图2.赋权图根据问题一最优路径的定义，两点线路的均值和标准差若使得T(,)最小，即所选路线为最优路线。其中为所有参与最优路段的时间均值总和，而不具有线性可加性，为所有参与最优路段的时间方差和的算术平方根。设0-1变量Xij1 ,边VV在最短路径中0 ,边V V不在最短路径中则从A到B的最优路径数学模型为:n n=ij Xiji 1 j 1(4)min T(,)Xij 1,0其中j表示从i地到j地的平均时间，j

13、表示从i地到j地时间的标准差。4.2.2 模型的求解4.2.2.1 求解方法本题的求解基于改进后的 Dijkstra 算法，Dijkstra 算法是解决赋权图中 的最短路问题，其赋权图顶点仅表示一个权重，而本题中每条线路的均值和方差 都对最短路径的选择都有影响，所以每个点上有两个权，分别为le(u),ld(u)。此外Dijkstra 算法中每次迭代产生的永久标号表示起始点到该点最短路的权，本 题则可以考虑基于均值和方差所求出的路径时间最小，以此作为该点权重的取值依据，当所有的点都成为永久标号后，即可得到一颗以起点为根的最短路径树。4.2.2.2 求解步骤详细算法如下：Step1:根据附表数据建

14、立均值邻接矩阵 we,标准差邻接矩阵wdo (附件8.2)Step2:把起点u0作为永久标记，起点的两个权值le(u0) 0,ld(u0) 0,其他点 的权值均为。Step3:对所有未被标记的点v S ,令T(le(v),ld(v) minT(le(v),ld(v),T(le(v) we(uv), f (v,uv)(5)其中 T ()为公式(3) , f (v,uv)=Jld(v)2wd(uv)2 .找到minT (v)相对应的点u ,标记其为v的父顶点，同时把v作为永久标号。Step3:重复步骤2,直到所有的点成为永久标号。Step4:根据每个顶点标记下的父顶点就可以推算出一点到起点的最优路

15、径。4.2.2.3求解结果基于此算法，利用 matlab编程(附录8.1 )求的最优路径为从B-G)今K- C 一A,全程时间的均值为10.9946,标准差为0.9110,在12.5min内能够到达的 概率为95%-4.2.3算法的收敛性、复杂性分析对于该算法的复杂度，若有n个顶点，则除了起点被标记之外，其他点均未 被标记，则由Step3中的条件可知Step3中的算法会执行n-1次，而为了找到公 式(7)中的最小值，会计算所有的点到v的权重，这一步会执行n次，同理寻找 minT(v)也会执行n次，所以该算法白复杂度为O(n 1) n n) O(n 1)n2). 随着算法迭代次数增加而产生新的永

16、久标号点只能够表示当前点的最短路情况， 而并不能在一定程度上反应终点的最短路情况，终点的最短路需要到终点被标记后才能确定，所以该算法的收敛性一般。4.3问题3的模型建立与求解 4.3.1模型的建立针对问题3,本文利用车流波动理论研究不同路段时空的相关性。车流波动理论1是英国学者莱特希尔和惠特汉在对密度很大的交通流研究 中提出的，是指当车流因道路或交通状况改变而引起密度改变时在车流中产生车 流波的传播。车流中两种不同密度部分的分界面经过每辆车，向车流后部传播的现象称为车流波动。密度分界面沿道路移动的速度称为波速。当发生交通事件后， 事件发生点的通行能力降低，如果上游的交通需求超过瓶颈点的通行能力

17、，产生排队，排队尾端界面向上游蔓延，即出现一向后的返回波，称为“集结波”。假设一条公路上有2个相邻的不同交通流密度区域k1,k2,用垂直线S分割这2种密度，称S为波阵面，设S的速度为vw,并规定交通流按照图中箭头正 方向运行(如图3所示)。vw -IV图3.两种密度的车流运行情况图1中，vi为A区车辆的区间平均速度；为B区车辆的区间平均速度。由交通流 量守恒可知在时间t内通过界面S的车辆数N为：N (vi vw) k1t (v2 vw)k 2t由 q kv 知：qk1v1 , q2k2V2 代入式(6)得:根据车流波动理论，当上游交通需求大于瓶颈处通行能力时，在瓶颈处 上游形成排队队列。此时在

18、瓶颈段上游有排队队列所处的排队等待路段， 队列上 游则是驶入流所处路段，在瓶颈段下游则是驶出流所处路段(如图所示)。易 QR53i I - 图4.有排队的路段行车区段因而，车辆在此路段上的行程时间主要由 4个部分构成：车辆在驶人流的 行驶时间Tai(t)；车辆在排队流中的排队等待时间 Ta2(t)；在瓶颈段的行驶时 问Ta3(t)；车辆在瓶颈段下游行驶时间Ta4.设L4 (t)为车辆在瓶颈段上游正常行驶长度，La2(t)为某时刻队列的排队长度，La3(t)为瓶颈段长度，La4(t)为车辆在瓶颈段下游自由行驶的长度，La5(t)为 瓶颈段与道路入口间的距离。各路段的车流量和车流密度分别用 、kn

19、表示(n 123,4)。定义Ta(t)为时间t进入路段a的车辆在a上的行驶时间，则有:Ta(t)n Ta2(t) Ta'(t) Ta4(t)(8)La5(t)Lai (t)La2(t)(9)1)驶入时间Ta1(t)由上游驶入流的流率qi与密度ki,根据交通流的“流量-密度-速度”基本关系式可以求出驶入流的车辆平均行驶速度为 vi,则驶入时间Ta1(t)4为：9(10)Ta1(t)8 YV1k1Lai(t)的大小受到集结波位置的影响。设路段损害发生在M时刻，则t时刻集结波移离事件发生地的距离:La2(t)Vwt那么车辆驶入过程:其中，VW ,吐3k3 k22)排队等待时间Ta2(t)3)

20、瓶颈段行驶时间Ta3(t)(11)La1(t)La5 (t) VwtTa, (t)Lai(L%(t) vwt )qik1(12)(13)短时间内很难恢复，所以瓶颈段的路段长度Ta2(t)平 k2La,不发生变化。瓶颈路段行驶11时间为:La3(t)q3上丁(14)4)驶出时间Ta4(t)因为瓶颈因而瓶颈驶出时间是车辆驶过瓶颈路段后，以自由流状态行驶的一段时间, 段限制了车辆的驶出数目，这个地段的交通流为高速低密度的自由流。地段不变，所以驶出路段的长度也是不变的。则驶出时间为:(15)Ta。La4(t)q4k44.3.2模型的求解时间相关性：由公式(8)(15),对于同一路段a而言，其车流量和密

21、度是随 时间变化，因此其行程花费也是随时间变化的函数。 可通过统计一天当中不同时 间t内各路段长度和车流量vn和车流密度kn,计算出在路段a上的行程总时间Ta,作出Ta- t图像，观察图形确定相关性。空间相关性：由公式Ta1(t) (La5vwt)q1、vw 空工可知，对于某一时k1k3 k2刻，a1路段的行驶时间不仅与自身路段的车流量 q1和密度k1有关，还与其他路段的一些因素有关，比如路段破坏发生的位置La5、a2和a3路段的车流量q2、q3 以及密度k2、k3相关.可通过统计某一时间t,各个路段长度和车流量vn和车流 密度kn (n 1,2,3,4)0进而得到各个路段花费的时间，作出 T

22、an-La5图像，观察 图形确定相关性的强弱。5 .模型的优缺点5.1 模型的优点模型的建立具有较高的合理性。本文中建立的模型都是立足于题目所给的相 关信息，同时在深入条件和数据的基础上建立起来的，而且，从模型的求解结果及结果检验可以验证模型具有较高的合理性。本文中建立的模型具有较高的应用价值和推广价值，可以广泛应用于实际生 活中。5.2 模型的缺点评价指标考虑不全面所造成的误差： 本文将模型的相关指标理想化，但其实 很多客观因素都没有考虑完全，这就不可避免地使得评价的结果与实际存在一定 误差。6 .模型的改进与推广方向6.1 模型的改进采用Dijkstra 算法求解题二模型时，在算法的第二步

23、时，在选择所有未被 标记的点v S时可以做一定的筛选，即当 u S时，显然le(u)= ,ld(u尸T(le(V),ld(V)不可能是最小值，因此排除一定的U,可以在一定程度上加快迭代的速度。6.2 模型的推广基于本模型的可信性和科学性，我们上述的模型可以进行科学、定量分析， 安排生产组织与安排，实现人力物力资源的优化配置，获得最佳的经济效益。因此，可以广泛应用于经济管理、交通运输、工农业生产等领域。7 .参考文献1王殿海.交通流理论M.北京：人民交通出版社，2000 : 69 76.2徐泽水.不确定多属性决策方法及应用M.北京：清华大学出版社，2004.3韦增欣等.基于驾驶员偏好的最优路径选

24、择J.交通运输系统工程与信息，2010年12月第6期.4霍东芳等.基于车流波动理论的车队路段行驶时间分析J.军事交通学院学报，2011年第3期.8 .附录8.1 问题2主程序clc,clear;表.xls',1,'B2:F15');m=max(max(NUM(1:14,1),max(NUM(1:14,2);e=ones(m,m)*inf;% 均值d=ones(m,m)*inf;% 方差s_e=ones(1,11)*inf;% 顶点权s_d=ones(1,11)*inf;s=zeros(1,11);% 标记点for i=1:14e(NUM(i,1),NUM(i,2)=NU

25、M(i,4);% 求出邻接矩阵 e(NUM(i,2),NUM(i,1)=NUM(i,4);d(NUM(i,1),NUM(i,2)=NUM(i,5);d(NUM(i,2),NUM(i,1)=NUM(i,5);ends_e(1)=0;s_d(1)=0;s(1)=1;% 标记 tmp_e=100;tmp_d=50;f=1:11;%父顶点 tmp=inf;whilesum(s)=11jfor i=1:11 if s(i)=0 for j=1:11 ifminv(tmp_e,tmp_d)>minv(e(i,j)+s_e(j),(d(i,j)A2+s_d(j)A2)A0.5)tmp_e=s_e(j)+e(i,j);tmp_d=(d(i,j)A2+s_dQ)A2)A0.5； tmp_e_j=j；endends_e(i)=tmp_e；s_d(i)=tmp_d；if tmp>minv(tmp_e,tmp_d)&&tmp_e=100tmp_i=