不确定性条件下最优路径的选择
摘要
目前，交通拥挤和事故正越来越严重的困扰着城市交通。文章针对车辆的行驶时间存在的不确定性给出了最优路径的评价模型，帮助驾驶员寻找一条可靠、快速、安全的最优路径。文章还分析不同路段之间的时空相关性对行程时间的影响，为驾驶员路径的选择做了周全的考虑。
针对问题一，我们建立了两种不同评价标准的最优路径评价模型.模型Ⅰ基于对存在驾驶员偏好的最优路径选择问题的研究,提出了一种能够综合反映驾驶员偏好的多属性决策方法,建立了驾驶员偏好与路径属性总偏差最小的最优评价模型。模型Ⅱ基于对不确定性条件下车辆准时到达终点的可靠性的分析，定义可靠度来定量描述车辆行驶时间的不确定性，同时利用概率论知识给出了最优路径的数学表达式和定义—在可靠度R≥95%的条件下，预留时间T最短，则为最优路径。利用MATLAB编程求解，将所建模型应用到例子中，得出的结论是：选择道路A，验证了模型的正确性。
针对问题二，在问题一定义的最优路径的基础上，我们将A～K这11个地点之间的交通网络图看作一个无向赋权图，综合考虑均值、标准差这两个量作为权，建立了图论模型.基于Dijkstra最短路径算法，我们设计了一种能够涉及两个权重的改进算法求解最短路问题.利用MATLAB编程，得出最优路径选择结果为：A→C→K→G→B。
针对问题三，基于车流波动理论，建立行驶时间模型，从时间和空间两个维度描述交通路段之间行驶时间的相关性。
本文逻辑严谨，切入点独到，综合运用多种模型，结果可靠。
关键词：最优路径；Dijkstra算法；图论模型；车流波动理论
1．问题的重述
在复杂的交通环境下，如何寻找一条可靠、快速、安全的最优路径，已经成为所有驾驶员的共识。
传统的最优路径问题的研究大多数是基于“理想”的交通状况下分析的，即：假设每条路段上的行驶时间是确定的。在这种情况下，最优路径就是行驶时间最短的路径，可以用经典的最短路径算法来搜索(例如Dijkstra 最短路径算法)。目前的车辆路径导航系统也大都是基于这种理想的状况下的最优路径算法，寻找行驶时间最短的路径。事实上，由于在现实生活中，会受到很多不确定性因素的影响，例如：交通事故、恶劣天气、突发事件等，车辆的行驶时间存在着不确定性。
问题一：对于一般的交通网络，假设已知每条路段行驶时间的均值和标准差，请建立数学模型，定量的分析车辆行驶时间的不确定性，然后给出在不确定性条件下车辆从起点到终点的最优路径的定义和数学表达式，将此模型应用到图1的例子中会选择哪条道路。
问题二：根据第一问的定义，已知每条路段行驶时间的均值和标准差(见图、表,图表中A为起点B为终点)，设计算法搜索最优路径，并将该算法应用到具体的交通网络中，用计算结果验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。
问题三：在现实的交通网络中，某个路段发生了交通拥堵，对上游或者下游路段的交通状况有很大的影响，从而导致了交通路段之间的行驶时间有一定的相关性，请建立数学模型描述这种交通路段之间行驶时间的相关性，并将这种相关性应用到第一问和第二问的最优路径搜索问题中，并设计算法解决考虑相关性的最优路径搜索问题，给出算例验证算法的有效性。如果可能的话，从理论上分析算法的收敛性、复杂性等性质。
2．模型假设
1.假设车辆在每条路段上的行驶时间是随机变量；
2.假设车辆在同一路段上的行程时间t服从正态分布；
3.假设在同密度车流中各单个车辆的行驶状态与前车完全一致；
4.假设题目所给数据真实可靠；
5.假设各不同路段的期望时间和标准差时间相互独立；
6.假设同一路段上下游的期望时间和标准差时间相同。
3．变量说明
a:第i条路径的第j个属性的客观值；
ij
b:第k个出行者对第j个属性的可接受值；
kj
:第k个出行者对第j个属性的权重；
kj
(,)
ij kj
d a b：在第j个属性下,第k个出行者的主观偏好值kj b与第i条路径的客观属性值ij a之间的偏差；
i
R: 第i条路径的可靠度；
i
T: 第i条路径到达目的地的预留时间；
i
μ: 第i条路径行程时间的均值；
i
σ: 第i条路径行程时间的标准差；
ij
μ: 从i地到j地的时间均值；
ij
σ: 从i地到j地的时间标准差；
()
e l u:赋权图中顶点u的均值；
()
d l u:赋权图中顶点u的标准差；
e
w:均值邻接矩阵；
d
w:标准差邻接矩阵；
1()
a
T t:车辆在驶人流的行驶时间；
2()
a
T t:车辆在排队流中的排队等待时间；
3()
a
T t:在瓶颈段的行驶时间；
4()
a
T t:车辆在瓶颈段下游行驶时间；
1()
a
L t:车辆在瓶颈段上游正常行驶长度；
2()
a
L t:某时刻队列的排队长度；
3()
a
L t:瓶颈段长度；
4()
a
L t:车辆在瓶颈段下游自由行驶的长度；
5()
a
L t:瓶颈段与道路入口间的距离；
()
a
T t:时间t进入路段a的车辆在a上的行驶时间；n
k:不同路段的交通流密度（n=1,2,3,4）；
n
q:不同路段的交通流密度（n=1,2,3,4）；
12
v v，：区域1,2车辆的平均速度；
w v :集结波面的移动速度。
4． 模型的建立与求解
4.1问题一的模型建立与求解
4.1.1 模型的建立
4.1.1.1 模型Ⅰ
（1）最优路径评价指标
综合考虑影响驾驶员路径的选择因素，本文选择行驶时间、行驶距离、拥挤程度（路上车辆数、排队长度）、出行费用、行驶困难程度（道路宽度等）等作为选择最优路径的评价指标[2]，即决策变量。
图1.最优路径的评价指标
（2）最优路径的确定
现实生活中，驾驶员依据自身偏好来选择路径时，对于不同的评价指标有着不同要求，且对于评价指标值存在一个可接受范围而不是一个精确值。并且对于路径而言，由于路径上行驶的速度和数量等方面是动态变化的，这就引起路径自身评价属性值的波动。故本文以区间的形式来表达评价参数。
设L U ij ij a a ，分别表示第i 条路径的第j 个属性的客观值ij a 的下限和上限，即[]U ij ij ij a a a =L ，，设第k 个出行者对第j 个属性的可接受范围为[]U kj kj kj b b b =L ，，由于种种条件的制约,决策者的主观偏好与客观值之间往往存在着一定的差距。为了使决策具有合理性,应使决策者的主观偏好与客观属性值的总偏差最小.最终建立如下评价模型定义为最优路径[3]。
min 211((,))n m
ij kj kj i j d a b ω==∑∑
( 1)
..s t 0kj ω≥
11m kj j ω
==∑
（1）
其中，(,)L L U U ij kj ij kj ij kj d a b a b a b =-+-表示在第j 个属性下,第k 个出行者的主观偏好值kj b 与第i 条路径的客观属性值ij a 之间的偏差；()F ω表示在所有属性下第k 个出行者的主观偏好值与客观属性值的总偏差；kj ω表示第k 个出行者对第j 个属性的权重。
min 211((,))n m ij kj kj i j d a b ω==∑∑
( 2)
4.1.1.2 模型Ⅱ
我们定义可靠度i R 来刻画时间行驶时间的不确定性，[0,1]i R ∈，表示在预留时间i T 之内到达目的地的概率。假设车辆在同一路段上的行程时间t 服从正态分布N 2(,)μσ，则第i 条路径的可靠度可表示为：
0(0)(
)()i i i i i i i i
T R P t T μμσσ--=≤≤=Φ-Φ. （2）
据此，为了尽可能准确的到达目的地，可选取i R =95%.在满足(0)95%i i P t T ≤≤≥的条件下，min {i T }对应道路i 即为最优路径。
4.1.2 模型的求解与检验
为了便于求解，我们选取模型Ⅱ进行讨论。
由公式（2）解得
1(())i i i i i i
T R μσμσ-=Φ+Φ-
+ （3）
其中，i R =0.95，()1-Φ表示标准正态分布的反函数。
将图1所给的数据： 1=33μ，1=1σ； 2=30μ，2=15σ带入公式（3）计算
出：道路A 预留时间134.6min T =，道路B 预留时间258.8min T =，即最优路径为绕城快速路。结果与实际选择相符，间接验证了模型的正确性。
4.2问题二的模型建立与求解
4.2.1 模型的建立
对于一般交通网络，为了方便设计算法找到最优模型，我们根据附表中A-H 之间路段的时间均值和时间标准差，将其转化为图论模型。
将11个地点A →H 看成11个顶点，分别从1-11进行标号，构成一个顶点集：
{}1,2,3,4,5,6,7,8,9,10,11V V V V V V V V V V V V =
则可将11个地点之间的交通网络图看作一个无向赋权图（图2），每条路为
图中的边。
图2. 赋权图
根据问题一最优路径的定义，两点线路的均值μ和标准差σ若使得(,)
T μσ最小，即所选路线为最优路线。其中μ为所有参与最优路段的时间均值总和，而σ不具有线性可加性，为所有参与最优路段的时间方差和的算术平方根。
设0-1变量
10ij x ?=??
，边V i V j 在最短路径中 ，边V i V j 不在最短路径中
则从A 到B 的最优路径数学模型为：
min (,)T μσ
11=n n
ij ij i j x μμ==∑∑
..s t σ10
ij x =，
（4） 其中ij μ表示从i 地到j 地的平均时间，ij σ表示从i 地到j 地时间的标准差。
4.2.2 模型的求解
4.2.2.1求解方法
本题的求解基于改进后的Dijkstra 算法， Dijkstra 算法是解决赋权图中的最短路问题，其赋权图顶点仅表示一个权重，而本题中每条线路的均值和方差都对最短路径的选择都有影响，所以每个点上有两个权，分别为(),()e d l u l u 。此外Dijkstra 算法中每次迭代产生的永久标号表示起始点到该点最短路的权，本题则可以考虑基于均值和方差所求出的路径时间最小，以此作为该点权重的取值依据，当所有的点都成为永久标号后，即可得到一颗以起点为根的最短路径树。
4.2.2.2求解步骤
详细算法如下：
Step1:根据附表数据建立均值邻接矩阵e w ，标准差邻接矩阵d w 。（附件8.2） Step2:把起点0u 作为永久标记，起点的两个权值00()0,()0e d l u l u ==，其他点的权值均为∞。
Step3:对所有未被标记的点v S ∈，令
((),())min{((),()),(()(),(,))}e d e d e e T l v l v T l v l v T l v w uv f v uv =+
（5）
其中( )T 为公式(3)，(,f v uv 找到min{()}T v 相对应的点u ，标记其为v 的父顶点，同时把v 作为永久标号。 Step3:重复步骤2，直到所有的点成为永久标号。
Step4:根据每个顶点标记下的父顶点就可以推算出一点到起点的最优路径。
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 次，同理寻找min{()}T v 也会执行n 次，所以该算法的复杂度为2((1))((1))O n n n O n n -??=-.随着算法迭代次数增加而产生新的永久标号点只能够表示当前点的最短路情况，而并不能在一定程度上反应终点的最短路情况，终点的最短路需要到终点被标记后才能确定，所以该算法的收敛性一般。
4.3问题3的模型建立与求解
4.3.1模型的建立
针对问题3，本文利用车流波动理论研究不同路段时空的相关性。
车流波动理论[1]是英国学者莱特希尔和惠特汉在对密度很大的交通流研究
中提出的，是指当车流因道路或交通状况改变而引起密度改变时在车流中产生车流波的传播。车流中两种不同密度部分的分界面经过每辆车，向车流后部传播的现象称为车流波动。密度分界面沿道路移动的速度称为波速。当发生交通事件后，事件发生点的通行能力降低，如果上游的交通需求超过瓶颈点的通行能力，产生排队，排队尾端界面向上游蔓延，即出现一向后的返回波，称为“集结波”。
假设一条公路上有2个相邻的不同交通流密度区域12,k k ,用垂直线S 分割这2种密度，称S 为波阵面，设S 的速度为w v ,并规定交通流按照图中箭头正方向运行（如图3所示）。
图3. 两种密度的车流运行情况
图1中, 1v 为A 区车辆的区间平均速度;为B 区车辆的区间平均速度。由交通流量守恒可知在时间t 内通过界面S 的车辆数N 为：
1122()()w w N v v k t v v k t =+=+
(6)
由q kv =知:111q k v =，222q k v = 代入式(6)得：
1221
w q q v k k -=
- (7) 根据车流波动理论，当上游交通需求大于瓶颈处通行能力时，在瓶颈处上游形成排队队列。此时在瓶颈段上游有排队队列所处的排队等待路段，队列上游则是驶入流所处路段，在瓶颈段下游则是驶出流所处路段（如图所示）。
图4. 有排队的路段行车区段
因而，车辆在此路段上的行程时间主要由4个部分构成：①车辆在驶人流的行驶时间1()a T t ;②车辆在排队流中的排队等待时间2()a T t ;③在瓶颈段的行驶时
间3()a T t ;④车辆在瓶颈段下游行驶时间4()a T t .
设1()a L t 为车辆在瓶颈段上游正常行驶长度，2()a L t 为某时刻队列的排队长
度，3()a L t 为瓶颈段长度，4()a L t 为车辆在瓶颈段下游自由行驶的长度，5()a L t 为
瓶颈段与道路入口间的距离。 各路段的车流量和车流密度分别用n q 、n k 表示（1,2,3,4n =）。
定义()a T t 为时间t 进入路段a 的车辆在a 上的行驶时间，则有：
1234()()()()()a a a a a T t T t T t T t T t =+++
(8)
512()()()a a a L t L t L t =+
(9)
1) 驶入时间1()a T t
由上游驶入流的流率1q 与密度1k ，根据交通流的“流量-密度-速度”基本关系式可以求出驶入流的车辆平均行驶速度为1v ，则驶入时间1()a T t [4]为：
111111()()a a a L L t q T t v k =
=
(10) 1()a L t 的大小受到集结波位置的影响。设路段损害发生在0t 时刻，则t 时刻集结波移离事件发生地的距离：
2()w a L t v t =
(11)
那么车辆驶入过程：
15()()w a a L t L t v t =- 51
1111(())()w a a a L t v t q L T t v k -=
=
(12) 其中，2332w q q v k k -=- 2)排队等待时间2()a T t 222()w a v tq T t k =
(13)
3)瓶颈段行驶时间3()a T t
短时间内很难恢复，所以瓶颈段的路段长度3a L 不发生变化。瓶颈路段行驶
时间为： 3333()()a a L t q T t k =
(14)
4)驶出时间4()a T t
驶出时间是车辆驶过瓶颈路段后，以自由流状态行驶的一段时间，因为瓶颈段限制了车辆的驶出数目，这个地段的交通流为高速低密度的自由流。因而瓶颈
地段不变，所
以驶出路段的长度也是不变的。则驶出时间为： 4444()()a a L t q T t k =
(15)
4.3.2 模型的求解
时间相关性：由公式(8)～(15),对于同一路段a 而言，其车流量和密度是随时间变化，因此其行程花费也是随时间变化的函数。可通过统计一天当中不同时间t 内各路段长度和车流量n v 和车流密度n k ，计算出在路段a 上的行程总时间a T ，作出a T -t 图像，观察图形确定相关性。 空间相关性：由公式1511(())()w a a L t v t q T t k -=、2332
w q q v k k -=-可知，对于某一时刻，1a 路段的行驶时间不仅与自身路段的车流量1q 和密度1k 有关，还与其他路段的一些因素有关，比如路段破坏发生的位置5a L 、23a a 和路段的车流量2q 、3q 以及密度2k 、3k 相关.可通过统计某一时间t ，各个路段长度和车流量n v 和车流密度n k （1,2,3,4n =）。进而得到各个路段花费的时间，作出an T -5a L 图像，观察图形确定相关性的强弱。
5．模型的优缺点
5.1模型的优点
模型的建立具有较高的合理性。本文中建立的模型都是立足于题目所给的相关信息，同时在深入条件和数据的基础上建立起来的，而且，从模型的求解结果及结果检验可以验证模型具有较高的合理性。
本文中建立的模型具有较高的应用价值和推广价值，可以广泛应用于实际生活中。
5.2模型的缺点
评价指标考虑不全面所造成的误差：本文将模型的相关指标理想化，但其实很多客观因素都没有考虑完全，这就不可避免地使得评价的结果与实际存在一定误差。
6．模型的改进与推广方向
6.1模型的改进
采用Dijkstra 算法求解题二模型时，在算法的第二步时，在选择所有未被标记的点v S ∈时可以做一定的筛选，即当u S ∈时，显然()=,()=e d l u l u ∞∞，
((),())
T l v l v不可能是最小值，因此排除一定的u，可以在一定程度上加快迭代
e d
的速度。
6.2模型的推广
基于本模型的可信性和科学性，我们上述的模型可以进行科学、定量分析，安排生产组织与安排，实现人力物力资源的优化配置，获得最佳的经济效益。因此，可以广泛应用于经济管理、交通运输、工农业生产等领域。
7．参考文献
[1] 王殿海.交通流理论[M].北京：人民交通出版社,2000： 69—76.
[2] 徐泽水.不确定多属性决策方法及应用[M].北京：清华大学出版社,2004.
[3] 韦增欣等.基于驾驶员偏好的最优路径选择[J].交通运输系统工程与信息，2010年12月第6期.
[4] 霍东芳等.基于车流波动理论的车队路段行驶时间分析[J]. 军事交通学院学报，2011年第 3期.
8．附录
8.1问题2主程序
clc,clear;
NUM=xlsread('C:\Users\KingHD\Desktop\表.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(NUM(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);
end
s_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
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(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;
end
end
s_e(i)=tmp_e;
s_d(i)=tmp_d;
if tmp>minv(tmp_e,tmp_d)&&tmp_e~=100
tmp_i=i;
tmp_f=tmp_e_j;
tmp=minv(tmp_e,tmp_d);
end
tmp_e=100;
tmp_d=50;
end
end
s(tmp_i)=1;
f(tmp_i)=tmp_f;
s_e(tmp_i)=tmp;
tmp=inf;
end
i=2;
fprintf('路径从B→');
while f(i)~=1
fprintf('%c→',f(i)+64);
i=f(i);
end
fprintf('A\n');
8.2问题二邻接矩阵