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

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

2、论知识给出了最优路径的数学表达式和定义在可靠度R95%的条件下，预留时间T最短，则为最优路径。利用MATLAB编程求解，将所建模型应用到例子中，得出的结论是：选择道路A，验证了模型的正确性。针对问题二，在问题一定义的最优路径的基础上，我们将AK这11个地点之间的交通网络图看作一个无向赋权图，综合考虑均值、标准差这两个量作为权，建立了图论模型.基于Dijkstra 最短路径算法，我们设计了一种能够涉及两个权重的改进算法求解最短路问题.利用MATLAB编程，得出最优路径选择结果为：ACKGB。针对问题三，基于车流波动理论，建立行驶时间模型，从时间和空间两个维度描述交通路段之间行驶时间的相关性。本文

3、逻辑严谨，切入点独到，综合运用多种模型，结果可靠。关键词：最优路径；Dijkstra算法；图论模型；车流波动理论 1问题的重述在复杂的交通环境下，如何寻找一条可靠、快速、安全的最优路径，已经成为所有驾驶员的共识。传统的最优路径问题的研究大多数是基于“理想”的交通状况下分析的，即：假设每条路段上的行驶时间是确定的。在这种情况下，最优路径就是行驶时间最短的路径，可以用经典的最短路径算法来搜索(例如Dijkstra 最短路径算法)。目前的车辆路径导航系统也大都是基于这种理想的状况下的最优路径算法，寻找行驶时间最短的路径。事实上，由于在现实生活中，会受到很多不确定性因素的影响，例如：交通事故、恶劣天气

4、、突发事件等，车辆的行驶时间存在着不确定性。问题一：对于一般的交通网络，假设已知每条路段行驶时间的均值和标准差，请建立数学模型，定量的分析车辆行驶时间的不确定性，然后给出在不确定性条件下车辆从起点到终点的最优路径的定义和数学表达式，将此模型应用到图1的例子中会选择哪条道路。问题二：根据第一问的定义，已知每条路段行驶时间的均值和标准差(见图、表,图表中A为起点B为终点)，设计算法搜索最优路径，并将该算法应用到具体的交通网络中，用计算结果验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。问题三：在现实的交通网络中，某个路段发生了交通拥堵，对上游或者下游路段的交通状况有很大的影

5、响，从而导致了交通路段之间的行驶时间有一定的相关性，请建立数学模型描述这种交通路段之间行驶时间的相关性，并将这种相关性应用到第一问和第二问的最优路径搜索问题中，并设计算法解决考虑相关性的最优路径搜索问题，给出算例验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。2模型假设1.假设车辆在每条路段上的行驶时间是随机变量；2.假设车辆在同一路段上的行程时间服从正态分布；3.假设在同密度车流中各单个车辆的行驶状态与前车完全一致；4.假设题目所给数据真实可靠；5.假设各不同路段的期望时间和标准差时间相互独立；6.假设同一路段上下游的期望时间和标准差时间相同。3变量说明:第条路径的第

6、个属性的客观值；:第k个出行者对第个属性的可接受值；:第个出行者对第个属性的权重；：在第个属性下,第个出行者的主观偏好值与第条路径的客观属性值之间的偏差；:第条路径的可靠度；:第条路径到达目的地的预留时间；:第条路径行程时间的均值；:第条路径行程时间的标准差；:从地到地的时间均值；:从地到地的时间标准差；:赋权图中顶点的均值；:赋权图中顶点的标准差；:均值邻接矩阵；:标准差邻接矩阵；:车辆在驶人流的行驶时间；:车辆在排队流中的排队等待时间；:在瓶颈段的行驶时间；:车辆在瓶颈段下游行驶时间；:车辆在瓶颈段上游正常行驶长度；:某时刻队列的排队长度；:瓶颈段长度；:车辆在瓶颈段下游自由行驶的长度；:

7、瓶颈段与道路入口间的距离；:时间进入路段的车辆在上的行驶时间；:不同路段的交通流密度（n=1,2,3,4）；:不同路段的交通流密度（n=1,2,3,4）；：区域1,2车辆的平均速度；:集结波面的移动速度。4 模型的建立与求解4.1问题一的模型建立与求解4.1.1 模型的建立4.1.1.1 模型（1）最优路径评价指标综合考虑影响驾驶员路径的选择因素，本文选择行驶时间、行驶距离、拥挤程度（路上车辆数、排队长度）、出行费用、行驶困难程度（道路宽度等）等作为选择最优路径的评价指标2，即决策变量。图1.最优路径的评价指标（2）最优路径的确定现实生活中，驾驶员依据自身偏好来选择路径时，对于不同的评价指标有

8、着不同要求，且对于评价指标值存在一个可接受范围而不是一个精确值。并且对于路径而言，由于路径上行驶的速度和数量等方面是动态变化的，这就引起路径自身评价属性值的波动。故本文以区间的形式来表达评价参数。设分别表示第条路径的第个属性的客观值的下限和上限，即，设第k个出行者对第个属性的可接受范围为，由于种种条件的制约,决策者的主观偏好与客观值之间往往存在着一定的差距。为了使决策具有合理性,应使决策者的主观偏好与客观属性值的总偏差最小.最终建立如下评价模型定义为最优路径3。 ( 1) （1）其中，表示在第个属性下,第个出行者的主观偏好值与第条路径的客观属性值之间的偏差；表示在所有属性下第个出行者的主观偏好

9、值与客观属性值的总偏差；表示第个出行者对第个属性的权重。 ( 2)4.1.1.2 模型我们定义可靠度来刻画时间行驶时间的不确定性，表示在预留时间之内到达目的地的概率。假设车辆在同一路段上的行程时间服从正态分布N，则第条路径的可靠度可表示为： . （2）据此，为了尽可能准确的到达目的地，可选取=95%.在满足的条件下，min 对应道路即为最优路径。 4.1.2 模型的求解与检验为了便于求解，我们选取模型进行讨论。由公式（2）解得 （3）其中，=0.95，表示标准正态分布的反函数。将图1所给的数据： ，； ，带入公式（3）计算出：道路A预留时间，道路B预留时间，即最优路径为绕城快速路。结果与实际选

10、择相符，间接验证了模型的正确性。4.2问题二的模型建立与求解4.2.1 模型的建立对于一般交通网络，为了方便设计算法找到最优模型，我们根据附表中A-H之间路段的时间均值和时间标准差，将其转化为图论模型。将11个地点AH看成11个顶点，分别从1-11进行标号，构成一个顶点集：则可将11个地点之间的交通网络图看作一个无向赋权图（图2），每条路为图中的边。 图2. 赋权图根据问题一最优路径的定义，两点线路的均值和标准差若使得最小，即所选路线为最优路线。其中为所有参与最优路段的时间均值总和，而不具有线性可加性，为所有参与最优路段的时间方差和的算术平方根。设0-1变量，边ViVj在最短路径中，边ViVj

11、不在最短路径中则从A到B的最优路径数学模型为： （4）其中表示从地到地的平均时间，表示从地到地时间的标准差。4.2.2 模型的求解4.2.2.1求解方法本题的求解基于改进后的Dijkstra算法， Dijkstra算法是解决赋权图中的最短路问题，其赋权图顶点仅表示一个权重，而本题中每条线路的均值和方差都对最短路径的选择都有影响，所以每个点上有两个权，分别为。此外Dijkstra算法中每次迭代产生的永久标号表示起始点到该点最短路的权，本题则可以考虑基于均值和方差所求出的路径时间最小，以此作为该点权重的取值依据，当所有的点都成为永久标号后，即可得到一颗以起点为根的最短路径树。4.2.2.2求解步骤

12、详细算法如下：Step1:根据附表数据建立均值邻接矩阵，标准差邻接矩阵。（附件8.2）Step2:把起点作为永久标记，起点的两个权值，其他点的权值均为。Step3:对所有未被标记的点，令 （5）其中为公式(3)，.找到相对应的点，标记其为的父顶点，同时把作为永久标号。Step3:重复步骤2，直到所有的点成为永久标号。Step4:根据每个顶点标记下的父顶点就可以推算出一点到起点的最优路径。4.2.2.3求解结果基于此算法，利用matlab编程（附录8.1）求的最优路径为从BGKCA，全程时间的均值为10.9946，标准差为0.9110，在12.5min内能够到达的概率为95%。4.2.3算法的收

13、敛性、复杂性分析对于该算法的复杂度，若有n个顶点，则除了起点被标记之外，其他点均未被标记，则由Step3中的条件可知Step3中的算法会执行n-1次，而为了找到公式(7)中的最小值，会计算所有的点到的权重，这一步会执行n次，同理寻找也会执行n次，所以该算法的复杂度为.随着算法迭代次数增加而产生新的永久标号点只能够表示当前点的最短路情况，而并不能在一定程度上反应终点的最短路情况，终点的最短路需要到终点被标记后才能确定，所以该算法的收敛性一般。4.3问题3的模型建立与求解4.3.1模型的建立针对问题3，本文利用车流波动理论研究不同路段时空的相关性。车流波动理论1是英国学者莱特希尔和惠特汉在对密度很

14、大的交通流研究中提出的，是指当车流因道路或交通状况改变而引起密度改变时在车流中产生车流波的传播。车流中两种不同密度部分的分界面经过每辆车，向车流后部传播的现象称为车流波动。密度分界面沿道路移动的速度称为波速。当发生交通事件后，事件发生点的通行能力降低，如果上游的交通需求超过瓶颈点的通行能力，产生排队，排队尾端界面向上游蔓延，即出现一向后的返回波，称为“集结波”。假设一条公路上有2个相邻的不同交通流密度区域,用垂直线分割这2种密度，称为波阵面，设的速度为,并规定交通流按照图中箭头正方向运行（如图3所示）。图3. 两种密度的车流运行情况图1中, 为区车辆的区间平均速度;为区车辆的区间平均速度。由交

15、通流量守恒可知在时间内通过界面的车辆数为： (6)由知:， 代入式(6)得： (7)根据车流波动理论，当上游交通需求大于瓶颈处通行能力时，在瓶颈处上游形成排队队列。此时在瓶颈段上游有排队队列所处的排队等待路段，队列上游则是驶入流所处路段，在瓶颈段下游则是驶出流所处路段（如图所示）。图4. 有排队的路段行车区段因而，车辆在此路段上的行程时间主要由4个部分构成：车辆在驶人流的行驶时间;车辆在排队流中的排队等待时间;在瓶颈段的行驶时间;车辆在瓶颈段下游行驶时间.设为车辆在瓶颈段上游正常行驶长度，为某时刻队列的排队长度， 为瓶颈段长度，为车辆在瓶颈段下游自由行驶的长度，为瓶颈段与道路入口间的距离。 各

16、路段的车流量和车流密度分别用、表示（）。定义为时间进入路段的车辆在上的行驶时间，则有： (8) (9)1) 驶入时间由上游驶入流的流率与密度，根据交通流的“流量-密度-速度”基本关系式可以求出驶入流的车辆平均行驶速度为，则驶入时间4为： (10)的大小受到集结波位置的影响。设路段损害发生在时刻，则时刻集结波移离事件发生地的距离： (11)那么车辆驶入过程： (12)其中，2)排队等待时间 (13)3)瓶颈段行驶时间短时间内很难恢复，所以瓶颈段的路段长度不发生变化。瓶颈路段行驶时间为： (14)4)驶出时间驶出时间是车辆驶过瓶颈路段后，以自由流状态行驶的一段时间，因为瓶颈段限制了车辆的驶出数目，

17、这个地段的交通流为高速低密度的自由流。因而瓶颈地段不变，所以驶出路段的长度也是不变的。则驶出时间为： (15)4.3.2 模型的求解时间相关性：由公式(8)(15),对于同一路段而言，其车流量和密度是随时间变化，因此其行程花费也是随时间变化的函数。可通过统计一天当中不同时间内各路段长度和车流量和车流密度，计算出在路段上的行程总时间，作出-图像，观察图形确定相关性。空间相关性：由公式、可知，对于某一时刻，路段的行驶时间不仅与自身路段的车流量和密度有关，还与其他路段的一些因素有关，比如路段破坏发生的位置、路段的车流量、以及密度、相关.可通过统计某一时间，各个路段长度和车流量和车流密度（）。进而得到

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

19、未被标记的点时可以做一定的筛选，即当时，显然，不可能是最小值，因此排除一定的，可以在一定程度上加快迭代的速度。6.2模型的推广基于本模型的可信性和科学性，我们上述的模型可以进行科学、定量分析，安排生产组织与安排，实现人力物力资源的优化配置，获得最佳的经济效益。因此，可以广泛应用于经济管理、交通运输、工农业生产等领域。7参考文献1 王殿海.交通流理论M.北京：人民交通出版社,2000： 6976.2 徐泽水.不确定多属性决策方法及应用M.北京：清华大学出版社,2004. 3 韦增欣等.基于驾驶员偏好的最优路径选择J.交通运输系统工程与信息，2010年12月第6期.4 霍东芳等.基于车流波动理论的

20、车队路段行驶时间分析J. 军事交通学院学报，2011年第 3期.8附录8.1问题2主程序clc,clear;NUM=xlsread('C:UsersKingHDDesktop表.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:14    e(N

21、UM(i,1),NUM(i,2)=NUM(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;tmp_e_j=0;while sum(s)=11 

22、60;  for i=1:11        if s(i)=0           for j=1:11           if minv(tmp_e,tmp_d)>minv(e(i,j)+s_e(j),(d(i,j)2+s_d(

23、j)2)0.5)                   tmp_e=s_e(j)+e(i,j);                   tmp_d=(d(i,j)2+s_d(j)2)0.5;   

24、;                tmp_e_j=j;               end           end     &

25、#160;     s_e(i)=tmp_e;           s_d(i)=tmp_d;           if tmp>minv(tmp_e,tmp_d)&&tmp_e=100         &#

26、160;     tmp_i=i;               tmp_f=tmp_e_j;               tmp=minv(tmp_e,tmp_d);