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

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

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

3、路段之间行驶时间的相关性。本文逻辑严谨，切入点独到，综合运用多种模型，结果可靠。关键词：最优路径；Dijkstra第法;图论模型；车流波动理论31. 问题的重述在复杂的交通环境下，如何寻找一条可靠、快速、平安的最优路径，已经成 为所有驾驶员的共识。传统的最优路径问题的研究大多数是基于“理想"的交通状况下分析的，B|J： 假设侮条路段上的行驶时间是确定的。在这种惜况下，最优路径就是行驶时间最 短的路径，可以用经典的最短路径算法来搜索（例如Dijkstra最短路径算法）。U 前的车辆路径导航系统也大都是基于这种理想的状况下的最优路径算法，寻找行 驶时间最短的路径。事实上，山于在现实生活中

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

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

6、时间相互独立；6. 假设同一路段上下游的期望时间和标准差时间相同。3. 变量说明州：第i条路径的第丿个属性的客观值；% :第k个出行者对第j个属性的可接受值；血厂第R个出行者对第j个属性的权重；(他，加)：在第丿个属性下，第R个出行者的主观偏好值術与第j条路径的客 观属性值的之间的偏差；丘：第i条路径的可靠度；Ti:第i条路径到达U的地的预留时间；“：第i条路径行程时间的均值；c :笫i条路径行程时间的标准差；“"：从d地到丿地的时间均值；6：从i地到丿地的时间标准差；/(")：赋权图中顶点"的均值；(“)：赋权图中顶点"的标准差；伦：均值邻接矩阵；Wd

7、 :标准差邻接矩阵；几：车辆在驶人流的行驶时间；抵：车辆在排队流中的排队等待时间；Th (/):在瓶颈段的行驶时间；几(/):车辆在瓶颈段下游行驶时间；(/):车辆在瓶颈段上游正常行驶长度；(/)：某时刻队列的排队长度；La (t):瓶颈段长度；：车辆在瓶颈段下游自由行驶的长度；(/):瓶颈段与道路入口间的距离；7；：时间/进入路段d的车辆在d上的行驶时间；匕：不同路段的交通流密度(n二1,2,3,4)；乞：不同路段的交通流密度(n二1,2,3,4)；vP v2:区域1,2车辆的平均速度；山：集结波面的移动速度。4.模型的建立与求解4. 1问题一的模型建立与求解 4.1.1模型的建立 4.1.

8、1.1 模型 I1最优路径评价指标综合考虑影响驾驶员路径的选择因素，本文选择行驶时间、行驶距离、拥挤 程度（路上车辆数、排队长度）、出行费用、行驶困难程度（道路宽度等）等作 为选择最优路径的评价指标叫 即决策变量。决彖戻图1.最优路径的评价指标(3)52最优路径确实定现实生活中，驾驶员依据自身偏好来选择路径时，对于不同的评价指标有着不同 要求，且对于评价指标值存在一个可接受范围而不是一个精确值。并且对于路径 而言，由于路径上行驶的速度和数量等方面是动态变化的，这就引起路径自身评 价属性值的波动。故本文以区间的形式来表达评价参数。设诂局分别表示第j条路径的第丿个属性的客观值吗的下限和上限，即 叫

9、=硏研，设第k个出行者对第丿个属性的可接受范围为由 于种种条件的制约，决策者的主观偏好与客观值之间往往存在着一定的差距。为 了使决策具有合理性，应使决策者的主观偏好与客观属性值的总偏差最小最终 建立如下评价模型定义为最优路径。“ m(1)工工(d(mj血/=| ；=1(1)其中，d(的，伽)=附-坎/田甘-时|表示在第丿个属性下，第R个出行者的 主观偏好值伽与第7条路径的客观属性值的之间的偏差；F(劲表示在所有属性 下第R个出行者的主观偏好值与客观属性值的总偏差；血,表示第R个出行者对第 丿个属性的权重。n m血为工(的血)0川(2)<=|冃4.1.1.2 模型 II我们定义可靠度尺来刻

10、画时间行驶时间的不确定性，ReO,l,表示在预留 时间7；之内到达口的地的概率。假设车辆在同一路段上的行程时间/服从正态分 布N(“,b2),那么第i条路径的可靠度可表示为：R. = P(0 <ti < Ti)=(匸上)-(匕竺).6 6(2)据此 为了尽可能准确的到达LI的地，可选取尺二95%.在满足P(0<a<L)>95%的条件下，min h对应道路i即为最优路径。4.1.2模型的求解与检验为了便于求解，我们选取模型II进行讨论。由公式(2)解得Ti ="(R + (一 )0-/ + “6其中，忆=0.95,7()表示标准正态分布的反函数。将图1所给

11、的数据：“匸33, 6二1；“2=30, 0-2=15带入公式(3)计算出：道路A预留时间7'i = 34.6 min,道路B预留时间72 = 58.8 min,即最优路径 为绕城快速路。结果与实际选择相符，间接验证了模型的正确性。4. 2问题二的模型建立与求解4. 2.1模型的建立对于一般交通网络，为了方便设计算法找到最优模型，我们根据附表中A-H 之间路段的时间均值和时间标准差，将其转化为图论模型。将11个地点AtH看成11个顶点，分别从1-11进行标号，构成一个顶点 集：V = VI, V2, V3, V4, V5,V6,V7,V & U9,0#11那么可将11个地点之间

12、的交通网络图看作一个无向赋权图(图2),每条路为图中的边。图2.赋权图根据问题一最优路径的定义，两点线路的均值“和标准差o假设使得 T(g 最小，即所选路线为最优路线。其中“为所有参与最优路段的时间均值 总和，而o不具有线性可加性，为所有参与最优路段的时间方差和的算术平方根。设0-1变量,边匕灯在最短路径中X，?=|0，边不在最短路径中那么从A到B的最优路径数学模型为:f=l j=lI也=bO其中冋表示从i地到j地的平均时间，6表示从7地到j地时间的标准差。4. 2. 2模型的求解4. 2. 2. 1求解方法此题的求解基于改良后的Dijkstra算法，Dijkstra算法是解决赋权图中 的最短

13、路问题，其赋权图顶点仅表示一个权重，而此题中每条线路的均值和方差 都对最短路径的选择都有影响，所以每个点上有两个权，分别为H“),/d(“)。此 外Dijkstra算法中每次迭代产生的永久标号表示起始点到该点最短路的权，此 题那么可以考虑基于均值和方差所求出的路径时间最小，以此作为该点权重的取 值依据，当所有的点都成为永久标号后，即可得到一颗以起点为根的最短路径树。4. 2. 2. 2求解步骤详细算法如下：Stepl：根据附表数据建立均值邻接矩阵仪，标准差邻接矩阵戚。(附件&2)Step2：把起点"。作为永久标记，起点的两个权值人伽)=0,/心()=0,其他点 的权值均为s。

14、Step3：对所有未被标记的点veS ,令TQe (v),/rf(v) = minT (/e(v), /rf(v), T (/< (v) + vtv(i/v),/(v,wv)(5)其中 T()为公式(3), f (v,HV)=>/(V)2 + wj(mv)2 .找到minT(v)(相对应的点，标记其为"的父顶点，同时把v作为永久标号。Step3：重复步骤2,直到所有的点成为永久标号。Stepd：根据每个顶点标记下的父顶点就可以推算出一点到起点的最优路径。4. 2. 2. 3求解结果基于此算法，利用mat lab编程(附录8.1)求的最优路径为从B-G-K-C f A,全程

15、时间的均值为10. 9946,标准差为0. 9110,在12. omin内能够到达的 概率为95%。4. 2.3算法的收敛性、复杂性分析对于该算法的复杂度，假设有n个顶点，那么除了起点被标记之外，其他点 均未被标记，那么由Step3中的条件可知Step3中的算法会执行n-1次，而为了 找到公式(7)中的最小值，会计算所有的点到卩的权重，这一步会执行n次，同 理寻找minT(”)也会执行n次，所以该算法的复杂度为O(/?-l)xnx/) = O(/7-l>2).随着算法迭代次数增加而产生新的永久标号点只 能够表示当前点的最短路情况，而并不能在一定程度上反响终点的最短路情况， 终点的最短路需

16、要到终点被标记后才能确定，所以该算法的收敛性一般。4. 3问题3的模型建立与求解4. 3. 1模型的建立针对问题3,本文利用车流波动理论研究不同路段时空的相关性。车流波动理论是英国学者莱特希尔和惠特汉在对密度很大的交通流研究 中提出的，是指当车流因道路或交通状况改变而引起密度改变时在车流中产生车 流波的传播。车流中两种不同密度局部的分界面经过每辆车，向车流后部传播的 现象称为车流波动。密度分界面沿道路移动的速度称为波速。当发生交通事件后, 事件发生点的通行能力降低，如果上游的交通需求超过瓶颈点的通行能力，产生 排队，排队尾端界面向上游蔓延，即出现一向后的返回波，称为“集结波"。假设一

17、条公路上有2个相邻的不同交通流密度区域用垂直线S分割这2种密度，称S为波阵面，设S的速度为皿，并规定交通流按照图中箭头正方向 运行(如图3所示)。*V11kJ A?V2图3.两种密度的车流运行情况图1中，力为A区车辆的区间平均速度;为3区车辆的区间平均速度。由交通流 量守恒可知在时间内通过界面S的车辆数N为：N = (v + Vw)kt =(V2 4- Vw)k2t由q = kv知：q=kiw, q2 =kivi代入式得:ki-k(7)根据车流波动理论，当上游交通需求大于瓶颈处通行能力时，在瓶颈处上游 形成排队队列。此时在瓶颈段上游有排队队列所处的排队等待路段，队列上游那 么是驶入流所处路段，

18、在瓶颈段下游那么是驶出流所处路段(如下图)。J(t)jt)f图4.有排队的路段行车区段因而，车辆在此路段上的行程时间主要山4个局部构成：车辆在驶人流的 行驶时间7；车辆在排队流中的排队等待时间Ta： (/);在瓶颈段的行驶时 间r；车辆在瓶颈段下游行驶时间Tti.设&，为车辆在瓶颈段上游正常行驶长度，(/)为某时刻队列的排队长 度，厶卫)为瓶颈段长度，纭为车辆在瓶颈段下游自由行驶的长度，厶为 瓶颈段与道路入口间的距离。各路段的车流量和车流密度分别用乞、匕表示(“ = 1,2,3,4 )定义7；为时间7进入路段d的车辆在d上的行驶时间，那么有：恥心)+处)+处)+町4 (0(8)M)=

19、3)+ M)(9)1) 驶入时间7；由上游驶入流的流率殆与密度匕，根据交通流的“流量-密度-速度"根本关13系式可以求出驶入流的车辆平均行驶速度为 那么驶入时间人为:k(10)S的大小受到集结波位置的影响。设路段损害发生在/O时刻，那么时刻集结 波移离事件发生地的距离：(0 =讪那么车辆驶入过程:(11)纭(/) = S (0 一 w打二益一（仏_山"5VIk(12)其中,2）排队等待时间：（/）(13)3）瓶颈段行驶时间7；短时间内很难恢复，所以瓶颈段的路段长度Q不发生变化。瓶颈路段行驶时间为：伙)=嘗(14)4）驶出时间7；驶出时间是车辆驶过瓶颈路段后，以自山流状态行驶

20、的一段时间，因为瓶颈 段限制了车辆的驶出数口，这个地段的交通流为高速低密度的自山流。因而瓶颈 地段不变，所以驶出路段的长度也是不变的。那么驶出时间为：(15)4. 3. 2模型的求解时间相关性：山公式（8）（13）,对于同一路段d而言，其车流量和密度是随 时间变化，因此其行程花费也是随时间变化的函数。可通过统计一天当中不同时 间/内各路段长度和车流量山和车流密度匕，计算出在路段d上的行程总时间 T。,作出巧-7图像，观察图形确定相关性。空间相关性：由公式7；卫）=（址芒/切Vh=7可知，对于某一时 K3 K2刻，皿路段的行驶时间不仅与自身路段的车流量G和密度$有关，还与其他路 段的一些因素有关

21、，比方路段破坏发生的位置厶5、和"3路段的车流量牛、 以及密度匕、也相关.可通过统计某一时间7,各个路段长度和车流量山和车流 密度匕5 = 123,4）。进而得到各个路段花费的时间，作出Tai-La5图像，观察 图形确定相关性的强弱。5 模型的优缺点5. 1模型的优点模型的建養具有较高的合理性。本文中建立的模型都是立足于题LI所给的相 关信息，同时在深入条件和数据的根底上建立起来的，而且，从模型的求解结果 及结果检验可以验证模型具有较高的合理性。本文中建立的模型具有较高的应用价值和推广价值，可以广泛应用于实际生 活中。5. 2模型的缺点评价指标考虑不全面所造成的误差：本文将模型的相关

22、指标理想化，但其实 很多客观因素都没有考虑完全，这就不可防止地使得评价的结果与实际存在一定 误差。6. 模型的改良与推广方向6.1模型的改良采用Dijkstra算法求解题二模型时，在算法的第二步时，在选择所有未被 标记的点"w f时可以做一定的筛选，即当"e f时，显然/e(")=s, /d(")=s , T(/(-(v),/4v)不可能是最小值，因此排除一定的"，可以在一定程度上加快迭代 的速度。6. 2模型的推广基于本模型的可信性和科学性，我们上述的模型可以进行科学、定量分析， 安排生产组织与安排，实现人力物力资源的优化配置，获得最正确的经

23、济效益。 因此，可以广泛应用于经济管理、交通运输、工农业生产等领域。7. 参考文献11王殿海.交通流理论M.北京：人民交通岀版社,2000： 69-76.2 徐泽水.不确泄多属性决策方法及应用M.北京：淸华大学岀版社,2004.3 韦增欣等.基于驾驶员偏好的最优路径选择J.交通运输系统工程与信息，2021年 12月第6期.4 霍东芳等.基于车流波动理论的车队路段行驶时间分析J.军事交通学院学报， 2021年第3期.8.附录8. 1问题2主程序clc,clear;NUM=xlsread(fC:UsersKingHDDesktop表.xls ,1,' B2：F15，);m=max(max(

24、NUM(1:14,1), max(NUM(1:14, 2);e=ones(m, m)*inf均值d=ones (m, m)*inf方差s_e=ones(l, ll)*inf;%顶点权s_d=ones(l, ll)*inf;s=zeros(l, 11);%标记点for i=l:14e(NUM(i, l),NVM(i,2)=NUM(i,4);%求出邻接矩阵e(NUM(i,2),NUM(i, D)二NUM(i,4);d(NUM(i, l)>NUM(i,2)=NUM(i,5);d(NUMG,2),NUM(i, D)二NUM(i,5);ends_e(l)=0;s_d 二0;s(l)=l;% 标记t

25、mp_e=100;tmp_d=50;f二1:11;%父顶点tmp=inf;tmp_e_j=O；while sum(s厂二 11for i=l:llif s(i)=0for j=l:llif minv(tmp_et tmp_d) >minv(e(i, j)+s_e(j), (d(i, j) *2+s_d(j)*2) *0. 5)tmp_e=s_e(j)+e(i, j);tmp_d= (d(i, j)"2+s_d(j)"2) *0. 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二i；tmp_f二