高速公路网络上行车时间估计和最优路线的选取

第 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 xd t = v ( x , t) ,题目要求走完 5个监测器所花的时间 ,即 t = t0 +∫ x = x5 x = 0 1 v ( x , t) d x , 但是根据题意 , v ( x , t) 是离散的无法求出其解析式. 所以上式只能写成 t = t0 + ∑ x = x5 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 = 12ρ;再把 5 v5ρ 近似的看作一个常数 ,引入一个常参量 (其值大于 0) ,即 : γ = - 015 5 v5ρ (4) 同时把全导数 : d v d t = 5 v5 xv + 5 v5 t (5) 代入式 (3) ,得到 : 5 v5 t = - v 5 v5 x + 1τ v (ρ) - v - γρ 5ρ5 x (6) 327 期 洪 　梅 ,等 :高速公路网络上行车时间估计和最优路线的选取 此即连续形式的速度动态模型. 对 (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预测点 , + 表示实际监测点) 42 数 　学 　的 　实 　践 　与 　认 　识 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 ,则有 : 527 期 洪 　梅 ,等 :高速公路网络上行车时间估计和最优路线的选取 ∑ h - 1 i = 1 g Tmi′·ΔT < g ≤ ∑ 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 的用时最短的路线. 62 数 　学 　的 　实 　践 　与 　认 　识 36 卷 2. 已知条件 : 行驶路线由若干路段相连接而成 ,而各路段的平均路段行驶时间正比于该路段的长度 , 用概率的观点来看就是存在关系 : E ( Ti ) = αli ,其中 Ti 是第 i 路段上车流驶过的平均时间 (数学期望) , li 为路段的长度 ,α是比例系数 ,可视为常值 ;另外 ,各路段行驶时间的方差反 比于因子 : l2/ 3i ,同时正比于该路段的两个端点所连结的路段数目 (图论上将该数称为节点的 “度数”) 的乘积 ,于是有 :var ( Ti ) = β2 ai ·bil2/ 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 ·bil2/ 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 l i = α·L (17) ∑ N i = 1 δσi = δβ∑ N i = 1 ai ·bi l1/ 3i ≡δ·σ (18) 727 期 洪 　梅 ,等 :高速公路网络上行车时间估计和最优路线的选取 则置信区间可写为 : (α·L - δ·σ,α·L +δ·σ) Step 5 : 由上述计算结果对 N 条线路进行比较 ,同时考虑到最优的路径不仅要满足时间 期望 T 要小 ,而且 T 落在置信区间内的概率最大 ,或者说置信区间的范围 (用 M = δ·σ来 标记) 要小. 所以可以确定一个能同时反映这两点的目标数 ,对每条路线 , 根据该目标函 数的大小来比较确定哪条路线是最优的. 这类似于多目标规划问题. 经分析选定的目标量 为 : S = Tj + Mj = αL + δβ∑ N i = 1 ai ·bi l1/ 3i (19) 其中α,β是要我们确定的 ,这就相当于多目标问题中的确定权重. 按照该量的大小对各条路线进行从小到大的排序 ,则排在第一位的 ( S 值最小的) 对应 的路线即为最优路线. 同时可以用前面算出的该段行驶时间的期望值和方差来估计该路线 的行驶时间 (因为随机 ,是一个时间段) . 理论上在目标量中应该考虑概率 Pj ,但通过计算结 果发现 , Pj 在各条路线上的值相差不大 ,影响很小 ,故将它从目标量中剔除. 312 　模型的求解 由于版面限制 ,在这里就具体介绍从3节点到14节点的情况 ,从14节点到3节点的情况 与此类似. 我们给定δ = 25 ,此时我们可以求出 18条路线分别对应的 L 和δ∑ N i = 1 ai ·bi l1/ 3i 以及概率 P ,如表 3 所示 : 表 3 　3 →14 的所有路径的参数表 路 径 参 数 L δ∑ N i = 1 ai ·bi l1/ 3i 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 % 时 ,此时基本上每次的行车总时间都能够落在置信区间内 , 82 数 　学 　的 　实 　践 　与 　认 　识 36 卷 即使落不到 ,我们也认为是小概率事件. 2) 由于置信区间是 αL - βδ∑ N i = 1 ai ·bi l1/ 3i , αL +βδ∑ N i = 1 ai ·bi l1/ 3i ,因为走完全程的时 间必须大于 0 ,所以αL - βδ∑ N i = 1 ai ·bi l1/ 3i > 0 , 这样就可以确定出权重α与β之间的关系了. 在这里可以求得α > 12β. 由目标函数公式 S = Tj + Mj = αL +δβ∑ N i = 1 ai ·bi l1/ 3i , 将上面求得每条路径的 L 和δ∑ N i = 1 ai ·bi l1/ 3i 带入进去 ,就可以求得18条路径分别的目标函数值. 进行由小到大的排序 ,得到结 果 : 1) 当我们设定 12β < α < 20β时 ,可以得到此时的目标函数最小的最优路径是路径 7 , 即 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β < α < 20β时 , 最优路径是 3 →6 →5 →4 →10 →14. ②α > 20β时 ,最优路径是 3 →6 →9 →8 →7 →11 →14. 如果是从 14 节点到 3 节点 ,那么只要 ①12β < α < 68β,最优路径是 14 →11 →12 → 13 →9 →6 →3. ②α > 68β,最优路径是 14 →11 →12 →8 →9 →6 →3. 参考文献 : [1 ] 　EBF 网络在交通流模型辨识中的应用[J ] . 清华大学学报 , 2001 , 41 (9) : 74 —82. 927 期 洪 　梅 ,等 :高速公路网络上行车时间估计和最优路线的选取 [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 HONG Mei , 　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 jam or 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 03 数 　学 　的 　实 　践 　与 　认 　识 36 卷