第36 卷第7 期
2006 年7 月
数学的实践与认识
MATHEMATICS IN PRACTICE AND THEORY
Vol136 　No17 　
July , 2006 　
高速公路网络上行车时间估计和最优路线的选取
洪　梅, 　王益柏, 　葛义军
(解放军理工大学气象学院海洋与空间环境系, 南京　211101)
摘要: 　首先建立交通流动力学模型求解问题Ⅰ. 在不考虑流量和考虑流量的两种情况下,该模型都能够
解出在任意给定的时刻t 位于第一个传感器的车辆到达第5 个感应器的行车时间. 我们还从四个方面给出
了判断交通堵塞的衡量标准,并且利用神经网络方法准确地对未来的车流状态进行了预测.
问题Ⅱ建立了交通网络的加权有向图模型,引入协方差矩阵描述网络中道路之间的相关性,并设计了查
找最优路径的动态Dijkstra 算法.
问题Ⅲ构建了统计多目标规划模型,利用车比雪夫不等式,成功找到了从端点3 到14 和14 到3 的最优
路径,并估算出了对应的行车时间.
关键词: 　交通流动力学; 统计多目标规划; 车比雪夫不等式
1 　交通流的流体理论模型
作者简介:洪梅(1982 —) ,女, 硕士研究生. 王益柏(1982 —) ,男, 硕士研究生. 葛义军(1983 —) ,男, 硕士研究生.
　　描述一维流体流动的主要物理量为流体的流量、密度、速度等,对交通流也有类似的
量,包括交通流量q ( x , t) ,交通流密度ρ( x , t) 和交通流速度u ( x , t) ,三者之间有如下的关
系:
q ( x , t) = ρ( x , t) v ( x , t) (1)
由此可见,这三个量中只有两个是独立的,已知其中两个量,第三个量可由上式确定.
111 　不考虑流量情况下的行车时间
由于问题一中,只有速度还没有考虑流量,这时候我们不用把问题考虑复杂,只要用简
单的力学公式来表示:
d x
d t
= v ( x , t) ,题目要求走完5 个监测器所花的时间,即t = t0 +∫x = x
5
x = 0
1
v ( x , t) d x , 但是根据题意, v ( x , t) 是离散的无法求出其解析式. 所以上式只能写成t = t0
+ Σ
x = x
5
x = 0
1
v ( x , t)Δx ,这样就可以通过分段求和的方法来求解.
根据以上思路,编写程序,只要任意给定的t ,都能够得到走完5 个监测器所需花的时
间.
1. 例如选取的t 就是资料最开始的起始时间点,即下午的3 点40 分07 秒,带入到我们
的程序中,可以求出走完5 个站点所需要用的时间114119 秒.
2. 我们以每个测量时间(间隔两分钟) 为一次发车时间,算出每一次所对应的走完全程
所需要的时间,将其统计在一起,绘制成图1 如下:
对于问题Ⅰ中提出的不用2 分钟的最后20 秒来代替2 分钟,而是每20 秒就测量一次,
也就是观测的时间间隔更短,点更密集了,由于没有这方面的资料,我们可以利用2 分钟的
图1 　车辆出发时刻一走完全程时间对应图
时间间隔的资料进行三次多项式插值来得到合理的20 秒时间间隔的资料.
113 　考虑流量情况下的行车时间
考虑了车流量的情况下,这时候求车流量的速度还是最关键的一步. 这就要用到我们
前面所介绍交通流流体模型理论了. 其中宏观稳态交通流模型并不是很精确也不太符合实
际,下面我们就要引入更加完善的速度动态模型来求解.
速度v ( x , t) 不可能瞬时地根据ρ( x , t) 面变化,根据q = ρv 关系, q ( x , t) 也是如此.
所以,在动态交通条件下使用稳态q (ρ) 关系不能准确地表示q、v 的动态过程,正是前述模
型的不足之处,事实上,驾驶员调整车速总是根据前方交通的密度;而且由于驾驶员有一个
反应过程,车辆动力、传动装置有一个调整时间,故车速的变化总比前方Δx 处密度变化滞
后一个时间τ,即:
V ( x , t + τ) = v[ρ( x +Δx , t) ] (2)
应当指出, (2) 式比前面所讨论的模型有改进.
把(2) 式左侧对τ、右侧对Δx 展开Taylor 级数,略去高阶项,得到:
v ( x , t) + τd v ( x , t)
d t
= v[ρ( x , t) ] +
5 v[ρ( x , t) ]
5ρ
5ρ
5 x
Δx (3)
通过对微观交通的研究与观察发现,取Δx 为车头距离的一半为宜,即Δx =
1
2ρ;再把
5 v
5ρ
近似的看作一个常数,引入一个常参量(其值大于0) ,即:
γ = - 015
5 v
5ρ (4)
同时把全导数:
d v
d t
=
5 v
5 x
v +
5 v
5 t
(5)
代入式(3) ,得到:
5 v
5 t
= - v
5 v
5 x
+
1τ
v (ρ) - v -
γ
ρ
5ρ
5 x
(6)
7期 洪 　梅 ,等:高速公路网络上行车时间估计和最优路线的选取 23
此即连续形式的速度动态模型.
对(6) 式作空间离散化处理,即划分高速公路为若干路段,设路段i 内交通均一,表示为
vi ( t) 、ρi ( t) ,则有:
vi =
1τ
[ v (ρi ) - vi ] +
vi
Δi
( vi - 1 - vi ) -
γ
τΔi
ρi
+1 - ρi
ρi
+ λ (7)
其中Δi 为路段i 的长度. 动态情况下,Δi 宜选的尽量短一些,才能近似认为其内部交通均
匀,一般取为数百米至1km. 式(7) 中末项引入一个新的常参数λ,是考虑到当ρi 很小的情
况下,该项不应该呈现很大的、不切实际的数据.
以采样周期T 实行时间离散化处理,得到:
vi ( k + 1) = vi ( k) + Tτ
[ v (ρi ( k) ) - vi ( k) ] + Tξ
Δi
vi ( k) [ vi - 1 ( k) - vi ( k) ]
-
γT
τΔi
ρi
+1 ( k) - ρi ( k)
ρi
( k) + λ , 　i = 1 ,2 , ⋯; k = 0 ,1 ,2 ⋯ (8)
(8) 式右端第三项引入一个修正参数ξ,以便于调整该项权重,使模型更容易适合于实际交
通. 第二、四两项的权重,可通过适当地估计τ、γ数值来加以调整.
对于考虑流量情况下的行车时间的情况下的问题求解,由于基本方法与前面不考虑的
时候相同,考虑到版面问题,这里就不具体介绍了.
114 　判断交通堵塞或顺畅
可以通过行车的时空图、车流密度ρ的变化情况、v - ρ曲线和q - ρ曲线、在交通流中
引入波的概念等方法来判断堵塞或顺畅,考虑版面问题,这里就不详述了.
115 　用RBF 神经网络预测———模型的补充
RBF 神经网络简介、网络模型设计与预测、输入输出因子设计由于版面的问题,这里就
不详述了,这里只是把网络的训练和仿真检验和预测的结果表述一下:
将前面70 个作为训练样本,后30 组用来进行检验. 以第一个监测器为例,其在t 时刻的
交通状态( q , v) ,其输入因子为t 时刻前的交通状态,设某时刻交通状态的输入因子是其前
面的三个时次的资料, 设置网络参数为: 误差指标(error goal) eg = 010 , 展开常量(spread
constant) sc = 1. 图2 (a) ,2 (b) 给出了经过样本训练后的仿真曲线.
(a) 速度仿真散点图　　　　　(b) 流量仿真散点图
图2 　RBF 神经网络辩识交通状态仿真散点图(O 表示RBF 预测点, + 表示实际监测点)
24 数 　学 　的 　实 　践 　与 　认 　识 36卷
由于RBF 神经网络每训练一步,就增加一个隐层节点,直至达到预定的精度指标. 从上
图可以看出,利用检验样本对网络进行验证的结果表明,网络的预测值和交通流流量的实际
检测值相对误差很小,结果令人满意. 以上结果表明神经网络模型能够对复杂的短时交通
流特性进行描述. 另外RBF 网络能对短时交通流进行准确的预测.
作为一个试验,不妨取最后十个时次的数据作为训练样本输入,通过RBF 预测出未来
三个时次的交通流量和速度,如表1 所示.
表1 　预测流速和流量的表
v (m/ s) q(n/ s) v (m/ s) q(n/ s) v (m/ s) q(n/ s) v (m/ s) q(n/ s) v q
t1 　7 :00 :07 281834 0119917 30125 0125433 261942 01287 141328 0129575 271374 0127167
t2 　7 :02 :07 281468 0130462 291491 012583 261573 0131571 810704 0138683 261297 0124555
t3 　7 :04 :07 271351 0156621 281326 0126227 261205 013673 0149581 0149718 241861 0121382
表2 　预测走完的时间
发车时刻走完的时间(s)
7 :00 :07 72147
7 :02 :07 831492
7 :04 :07 831984
用这预测出来的三组数据就可以求出题目中一点资料
没有的7 :00 :07 , 7 :02 :07 ,7 :04 :07时刻走完全程的时间,其
结果分别如表2 所示:
2 　交通网络的加权有向图模型
对这一问,考虑版面,我们主要是介绍动态Dijkstra 算法. 由于每条道路的行驶时间是
随时间变化的,因此模型中权重W也是变化的. 而Dijkstra 算法是一种静态最优路径算法,
计算过程中权重是固定的. 为了改进这个问题,我们通过改进Dijkstra 算法得到一种动态
Dijkstra 算法. 由于我们不能得到每条道路行程时间的连续关系式,为此,我们对时间作离散
处理,将系统工作时间分为若干个工作时段,求得各个时段内的每条道路行程时间. 而且为
了求得最佳动态路径必须知道车辆行驶到某一路段时对应的工作时段.
211 　车辆通过路段m 的行程时间的确定
以t0 表示系统工作起始时刻,一个工作时段为ΔT ,对各个时段进行编号(i 、ii 、iii 、iv、v、
vi ⋯) ,对涉及路段进行编号( Ⅰ、Ⅱ、Ⅲ、Ⅳ⋯) . 以下Tij 表示第j 个时段的通过路段i 的行程
时间. 可以列出一个路网中路段动态时间表(表略) .
车辆在从起点到目的地的过程,可能要经过若干条段路段,以[ tm , t′
m ] 表示车辆经过第
m 路段的时间范围,令Tm = tm - t′
m . 显然t′
m- 1 = t′
m .
车辆通过路段m 可能会跨越多个时段,各时段分别记为Tm1 、T′
m2 、T′
m3 、T′
m4 ⋯. 以Xm 表
示车辆到达第m 时段的起点的时刻所处的系统工作时段序号,则
Xm = int
tm - t0
Δt
+ 1 (9)
Tm′= Tm( x
m
+ i - 1)
当Tmi′≤ΔT 时,表示车辆在一个时段内能驶过的路段m , 则Tm = Tm1′.
当Tm1′> ΔT 时,表示车辆需要一个以上时段才能通过路段m ,设共需要h 个时段,设
路段m 的长度为g ,则有:
7期 洪 　梅 ,等:高速公路网络上行车时间估计和最优路线的选取 25
Σ
h- 1
i = 1
g
Tmi′·ΔT h- 1
i = 1
g
Tmi′·ΔT (10)
化简为:
Σ
h- 1
i = 1
g
T′mi
1
ΔT
≤ Σ
h- 1
i = 1
g
T′
mi
(11)
根据式(11) 可以确定h 的值
由于h - 1 个时段完全占用,故
Tm = ( h - 1)ΔT + g - Σ
h- 1
i = i
g
Tmi′
ΔT /
g
Tmn′
= ( h - 1)ΔT + 1 - Σ
h- 1
i = 1
ΔT
Tmi′
(12)
综合可得:
Tm =
Tm1′, Tm1 ≤ΔT
( h - 1)ΔT + 1 - Σ
h- 1
i = 1
ΔT
Tmi′·Tmn′, Tm1 > ΔT
(13)
212 　动态Dijkstra 算法的流程
按照上面的估计,可以动态更新网络中弧段的权值. 这样我们在Dijkstra 算法的基础上
进行一些改进,得到动态Dijkstra 算法. 它的具体步骤如下:
Step 1 : 置l
3 ( i) = 0 ,当j ≠ i 且i ∈V 时, 令tm = 0 , k = i ,执行第三步中的(1) , (2)
步,如果( i , j) ∈ E 令l ( j) = W( i , j) ; 如果( i , j) | E 则令l ( j) = ∞; 对j 赋以标记[ i ,
l ( j) ] .
Step 2 : 在所有临时标记l ( j) 中,取l ( k) = min l ( j) ,将l ( k) 标记改为l
3 ( k) . 若无剩
余的临时标记则停止.
Step 3 : 对( k , j) ∈ E 的所有临时节点j ,
1) 令t0 = 0 , tm = l
3 ( k) ,由(29) 式得到Xm ,进一步确定Tm1′;
2) 由(13) 式求得Tm ,令l ( k , j) = Tm ;
3) 令l ( j) = min[ l ( j) , l
3 ( j) + l ( k , j) ] ,将节点j 的临时标记改变为[ k , l ( j) ] ,
Step 4 : 返回第2 步.
3 　统计多目标规划模型
这里我们要根据题意作出两个规定:
1. 观察题目中所给的交通网络图,在有些道路的某段是存在堵塞的(图中Congested 和
Heavily congested 颜色标注的地方) ,考虑到所用时间要尽量短,那么这时候这条道路就不列
为我们所考虑的路径.
2. 我们按照美国交通的规定:行驶靠右边,我们通过图可以看出一共有5 条路有堵塞,
分别为4 →7 ,5 →6 ,8 →5 ,1 →4 ,11 →7.
311 　用统计多目标规划方法寻找最优路径的算法:
1. 目标:
通过某种算法找出图中从节点3 到节点14 ,和节点14 到节点3 的用时最短的路线.
26 数 　学 　的 　实 　践 　与 　认 　识 36卷
2. 已知条件:
行驶路线由若干路段相连接而成,而各路段的平均路段行驶时间正比于该路段的长度,
用概率的观点来看就是存在关系: E( Ti ) = αli ,其中Ti 是第i 路段上车流驶过的平均时间
(数学期望) , li 为路段的长度,α是比例系数,可视为常值;另外,各路段行驶时间的方差反
比于因子: l2/ 3
i ,同时正比于该路段的两个端点所连结的路段数目(图论上将该数称为节点的
“度数”) 的乘积,于是有:var ( Ti ) = β2 ai ·bi
l2/ 3 ≡σ2
i ,其中, ai , bi 分别是两端点的度数,β是比
例常数,σ是标准方差.
3. 算法步骤:
以从节点3 到节点14 为例.
Step 1 : 按前面的方法,先找出所有可能的由节点3 到14 的路线集合. 对集合中的每一
条路线,进行如下处理,假设取第j 条路线;
图3 　针对第j 条路线路段示意图
Step 2 : 如图3 所示,针对第j 条路线,该路线的第i 个路段上满足:
E( Ti ) = αli , 　i = 1 ,2 , ⋯,N. (14)
var ( Ti ) = β2 ai ·bi
l2/ 3 = σ2
i (15)
　　其中N 为该线路上的分路段数目.
利用车比雪夫不等式,对任意的正数δ,变量Ti 落在区间( E( Ti ) - δσi , E( Ti ) +δσi ) 的
概率不小于1 -
1
δ2 ,即: P(| Ti - E( Ti ) | ≤δσ) ≥1 -
1
δ2 ,为方便用Pi 代替P( | Ti -
E( Ti ) | ≤δσ) .
Step 3 : 由第二步,易得到整条路线上行驶时间的平均期望值为T = Σ
N
i = 1
E( Ti ) , T 落在
区间Σ
N
i = 1
E( Ti ) - Σ
N
i = 1
δσi , Σ
N
i = 1
E( Ti ) + Σ
N
i = 1
δσi (以下不妨称之为“置信区间”) 中的概率
为:
P ≡ P1 ·P2 ·⋯PN ≥ 1 -
1
δ2
N
(16)
Step 4 : 固定常数δ的值,计算整条路线上的行驶时间及置信区间,及概率.
其中:
T = Σ
N
i = 1
E( Ti ) = Σ
N
i = 1
α·li = αΣ
N
i = 1
li = α·L (17)
Σ
N
i = 1
δσi = δβΣ
N
i = 1
ai ·bi
l1/ 3
i
≡δ·σ (18)
7期 洪 　梅 ,等:高速公路网络上行车时间估计和最优路线的选取 27
则置信区间可写为: (α·L - δ·σ,α·L + δ·σ)
Step 5 : 由上述计算结果对N 条线路进行比较,同时考虑到最优的路径不仅要满足时间
期望T 要小,而且T 落在置信区间内的概率最大,或者说置信区间的范围(用M = δ·σ来
标记) 要小. 所以可以确定一个能同时反映这两点的目标函数,对每条路线, 根据该目标函
数的大小来比较确定哪条路线是最优的. 这类似于多目标规划问题. 经分析选定的目标量
为:
S = Tj + Mj = αL + δβΣ
N
i = 1
ai ·bi
l1/ 3
i
(19)
其中α,β是要我们确定的,这就相当于多目标问题中的确定权重.
按照该量的大小对各条路线进行从小到大的排序,则排在第一位的( S 值最小的) 对应
的路线即为最优路线. 同时可以用前面算出的该段行驶时间的期望值和方差来估计该路线
的行驶时间(因为随机,是一个时间段) . 理论上在目标量中应该考虑概率Pj ,但通过计算结
果发现, Pj 在各条路线上的值相差不大,影响很小,故将它从目标量中剔除.
312 　模型的求解
由于版面限制,在这里就具体介绍从3 节点到14 节点的情况,从14 节点到3 节点的情况
与此类似.
我们给定δ = 25 ,此时我们可以求出18 条路线分别对应的L 和δΣ
N
i = 1
ai ·bi
l1/ 3
i
以及概率
P ,如表3 所示:
表3 　3 →14 的所有路径的参数表
路
径
参数L δΣ
N
i = 1
ai ·bi
l1/ 3
i
P
路径1 35125 160119 0198623
路径2 46135 192185 0198349
路径3 3916 259194 0198077
路径4 3316 228122 0198349
路径5 40135 269145 0198077
路径6 34135 237173 0198349
路径7 30145 166181 0198623
路径8 41155 199147 0198349
路径9 3418 266155 0198077
路径10 2818 234184 0198349
路径11 35155 276106 0198077
路径12 29155 244135 0198349
路径13 3211 263123 0198077
路径14 32185 272174 0198077
路径15 26185 241103 0198349
路径16 3313 245175 0198077
路径17 2713 214103 0198349
路径18 2611 231152 0198349
这里需要说明两点:
1) 我们认为当概率P〉98 %时,此时基本上每次的行车总时间都能够落在置信区间内,
28 数 　学 　的 　实 　践 　与 　认 　识 36卷
即使落不到,我们也认为是小概率事件.
2) 由于置信区间是αL - βδΣ
N
i = 1
ai ·bi
l1/ 3
i
, αL + βδΣ
N
i = 1
ai ·bi
l1/ 3
i
,因为走完全程的时
间必须大于0 ,所以αL - βδΣ
N
i = 1
ai ·bi
l1/ 3
i
> 0 , 这样就可以确定出权重α与β之间的关系了.
在这里可以求得α > 12β.
由目标函数公式S = Tj + Mj = αL +δβΣ
N
i = 1
ai ·bi
l1/ 3
i
, 将上面求得每条路径的L 和δΣ
N
i = 1
ai ·bi
l1/ 3
i
带入进去,就可以求得18 条路径分别的目标函数值. 进行由小到大的排序,得到结
果:
1) 当我们设定12β 即3 →6 →5 →4 →10 →14.
假如此时令α = 15β, 我们就可以求的最短路径所花的平均时间是456175 , 落在
(237127 ,676123) 置信区间内的概率是大于99123 %.
2) 当我们设定α > 20β时,可以得到此时的目标函数最小的最优路径是路径18 , 即3 →
6 →9 →8 →7 →11 →14.
可以看出当α比β大的越多时,也就是T 上的权重要越来越大于M ,那么T 最小的那条
路径就渐渐的变成了最优路径了,这与实际情况也是符合的.
假如此时令α = 25β,我们就可以求的最短路径所花的平均时间是65215 ,落在(347187 ,
957113) 置信区间内的概率是大于991203 %.
4 　模型的结论
模型一的结论有四点: ①无论在考虑流量还是不考虑流量的情况下,只要任意给定一
个出发时刻t ,都能够得到走完全程(即5 个传感器) 所需的时间. ②对于资料的间隔偏大
(2min) 可以通过插值很好的解决这类问题. ③从行车时空图、交通密度变化、v - ρ图和v -
q 图、交通流中的波速等四个方面充分的给出了判断交通是否堵塞的依据. ④RBF 神经网
络能够合理和比较精确的利用现有的资料预测出未来时刻车流状态(速度和流量) .
模型二的结论主要是将问题转化为G( V , E ,W) 中最优路径选择的问题. 为了描述各
条道路的行驶时间的相关程度,我们引入了协方差矩阵COVd×d ,并且利用COVd×d 对道路行
驶时间的预测进行改进. 我们通过改进Dijkstra 算法设计了一种动态Dijkstra 算法.
模型三的结论如果是从3 节点到14 节点,那么只要①12β 3 →6 →5 →4 →10 →14. ②α > 20β时,最优路径是3 →6 →9 →8 →7 →11 →14.
如果是从14 节点到3 节点,那么只要①12β 13 →9 →6 →3. ②α > 68β,最优路径是14 →11 →12 →8 →9 →6 →3.
参考文献:
[1 ] 　EBF 网络在交通流模型辨识中的应用[J ] . 清华大学学报, 2001 , 41 (9) : 74 —82.
7期 洪 　梅 ,等:高速公路网络上行车时间估计和最优路线的选取 29
[2 ] 　郭耀煌等编著. 运筹学与工程系统分析[M] . 北京: 中国建筑工业出版社, 1986.
[3 ] 　肖位枢主编. 图论及其算法[M] . 北京: 航空工业出版社, 1993.
[4 ] 　张　琦. 动态OD 估计的交通检测器优化布置研究[C] . 硕士毕业论文,吉林大学,2005.
[5 ] 　盛　骤, 谢式千, 潘承毅编. 概率论与数理统计[M] . 北京: 高等教育出版社, 2002.
The Estimation of The Travel Time on Freeway Net
And The Choice of the best way
HONGMei , 　WANG Yi2bai , 　GE Yi2jun
( Institute of Meteorology PLA University of Science and Technology , Nanjing 211101 , China)
Abstract : 　First , we set up a traffic kinetic model to solve the question Ⅰ. Not only taking no account of
the flow but also considering the flow we all can get the answer of question Ⅰ. We can get the standard of
estimating the traffic jamor not. And we also use the nerve net to forecast the intending freight flow well and
truly.
Then we set up the directional traffic map model to solve the question Ⅱ. We introduce the coefficient
matrix to describe the relativity of the roads in the net and design the dynamic Dijkstra arithmetic.
Finally we set up statistical several aiming design model to solve the question Ⅲ. Using the Chebyshev′
s Inequality , we can find the best way from 3 to 14 and 14 to 3 and can also get the travel time.
Keywords : 　traffic kinetic model ; statistical several aiming design model ; the Chebyshev′s Inequality
30 数 　学 　的 　实 　践 　与 　认 　识 36卷