车辆导航系统的动态最优路径搜索方法研究

　2000 年 7 月　　　　　　　　系　统　工　程　　　　　　第 18 卷第 4 期 (总第 100 期) 车辆导航系统的动态最优路径搜索 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 研究3 α 苏永云　晏克非　黄　翔　朱培康 【提　要】　对车辆导航系统中线路引导信息的供给与需求进行了综合分析, 提出了 一种新的具有真实最短路径意义的实时动态最优路径, 并 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 了搜索该 路径的改进D ijk stra 算法与改进A 3 算法, 前者适用于多车导航, 后者适 用于单车导航。 【关键词】　车辆导航系统, 动态最优路径, 改进D ijk stra 算法, 改进A 3 算法 　　车辆导航系统利用计算机和通讯技术, 向行驶在道路的的车辆提供信息, 引导车辆避开拥 挤路段, 沿最佳的线路到达目的地, 它是智能化交通系统 ( IT S) 中效益显著、见效快的项目, 是 欧、美、日等国竟相研究与开的重点[1 ] [2 ]。车辆导航系统同交通管理与控制系统融合, 可以在大 范围内进行交通流诱导, 从而缓解道路交通拥挤状况; 此外, 还可以向火警车辆、救护车辆与紧 急救援车辆提供最短路径引导服务。 最短路径计算方式分为集中式与自主式两类, 前者由中心计算机集中计算出最短路径并 将信息发给车辆, 后者由车载计算机根据从通信网络接收到的实时交通信息计算出最短路径。 按服务对象类型, 分为多车导航和单车导航, 前者向众多请求线路引导服务的车辆服务, 后者 为单个车辆服务。 1　最优路径划分方法 车辆导航系统向有路径选择权的车辆提供路线引导服务。影响驾驶员选择路径的因素很 多, 可以从路径特性与驾驶员特性两个方面进行分解, 前者包括行程时间、行驶距离、拥挤程 度、路线所经过交叉口的数量及控制方式等, 后者包括驾驶员的驾驶经验、个人偏好、出行目的 等。研究 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明, 驾驶员选择路线的准则呈现多样性, 不同驾驶员有各自的偏好, 但是限于可计量 性和数据可获得性, 系统提供的可选准则是有限的[2 ] [3 ] [5 ] [6 ]。对用户信息需求多样性与系统提 供信息能力有限性作折衷处理, 可以提供以行程时间、行驶距离、拥挤程度、道路属性和综合费 用为准则的最优路径, 供具有不同偏好的出行者选择或参考。其中行程时间是多数驾驶员选择 或关注的准则, 对此作重点剖析。 由于路段上交通状态是动态变化的, 路段行程时间也是动态变化的。但是受交通参数检测 技术和预测分析技术的限制, 难以得到准确的、可用的行程时间随时间变化的关系式, 为此, 对 时间作离散化处理, 将系统工作时间划分为若干时段, 认为单个时段内交通状态稳定、行程时 23 α 收稿日期: 2000- 06- 06。作者单位: 同济大学道路与交通工程系, 苏永云系博士研究生; 晏克非系博士生导师; 黄翔、 朱培康系硕士研究生。上海·2000923 国家自然科学基金资助项目 (59978035) ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 间固定, 但不同时段的行程时间可能不相同。 当时段划分得较长时, 车辆可能在一个时段内就能完成出行, 这实际忽略掉了行程时间的 变化, 会造成在一长段时间内给同一起讫点的所有车辆推荐同一路线, 称这种路径为静态路 径。若时段划分适当, 车辆一次出行可能跨越几个时段。若仅根据某一时段各路段的行程时间 计算最短路径, 则只有当车辆行驶过程中各路段的行程时间是固定不变的, 所求出的路径才为 真实最短路径, 称这种根据固定不变的行程时间计算的最优路径为静态最优路径。但是, 实际 上行程时间是动态变化的, 需要以车辆经过各路段花费的实际行程时间作为路阻, 才能计算出 真实最短路径, 称这种根据动态行程时间计算的最优路径为动态最优路径。 由交通流变化特性可知, 路段流量日变、时变具有一定规律性, 过去的最优路径对搜索当 前最优路径有一定参考意义。称根据前日或前几日检测到的交通数据计算出的路径为历史路 径, 称根据实时检测到的数据计算出的路径为实时路径。综上所述, 将各种类型最优路径及其 特征列入下表: 最优路径类型及其特征 表 1 路阻类型 最优路径类型 计算依据 参数获取方法 计算特点 行 程 时 间 将时间 离散为 短时段 历 史 静态最优路径 过去某一时段各路段行程时间 实测 事前计算、计算量小 动态最优路径 各路段过去各时段行程时间 实测 事前计算、计算量较大 实 时 静态最优路径 当前或未来某一时段各路段行程时间 实测或预测 实时计算、计算量大 动态最优路径 各路段当前与未来各时段行程时间 基于实测的预测 实时预测与计算、计算量很 大 长时段 静态路径 当前或预测一长段时间内各路段行程时间 实测或预测 实时 (预测)计算、计算量大 几何距离 物理最短路径 各路段几何长度 调查 事前计算、计算量小、路径固定 道路质量 路况最优路径 路段长度、车道数、路面类 型、坡度、车道功能划分和侧 向净空 调查 事前计算、计算量小、路径固定 拥挤程度 拥挤程度最低路径 [T (k) - T 0 ]öT 03 实测、预测 实时计算、计算量大 综合路阻 综合最优路径 以上四类参数的组合 调查、实测与预测 实时预测与计算、计算量很大3 : T —— (k) 路段 k 的行程时间; T 0—— 车辆以自由行驶车速通过路段 k 所需的时间。 拥挤程度最低路径中所有路段的[T (k ) - T 0 ]öT 0 值都较小, 但未考虑总行程时间和行驶 路程。路况最优路径中按照理想程度将路段长度、车道数、路面类型、坡度、车道功能划分和侧 向净空 6 个指标划分为几个等级, 采用评分法给各等级赋值, 路段的综合质量为各指标的加权 和, 各指标的权重可采用专家咨询法结合层次分析法进行确定。 以几何距离、道路质量为路阻计算的最短路径和静态路径都属于静态型最优路径, 目前车 辆导航系统动态交通分配研究中多采用该类路径, 计算结果与真实最短路存在较大差 异[1 ] [2 ] [7 ]。实时动态最优路径是真实的最短路径, 并且, 若想提高导航信息的准确度, 拥挤程度 最低、综合最优路径的计算都应以动态行程时间为依据, 可见, 车辆导航系统应以动态行程时 间作为计算最优路径的基础, 并提供实时动态最优路径作为必备服务。 33 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 2　动态最优路径的搜索方法 对静态型最优路径, 开始搜索时已知各路段的路阻, 对此已有成熟的算法[4 ] [8 ]。而动态最 优路径则不然, 由于路段行程时间与车辆经过路段的时刻有关, 而搜索开始时车辆到达某路段 的时刻是未知的, 需要在搜索过程中才能确定车辆到达路段的时刻与经过路段所需的行程时 间。 2. 1　动态行程时间的表示 以 t0 表示导航系统工作开始时刻, 将系统工作时间划分为若干时段, 以 ∃T 表示一个时段 的长度。系统开始工作时刻属于第一个时段, 对各时段进行编号 ( i、ii、iii、iv、v、vi、vii、viii、 ⋯⋯) , 称此编号序列为系统工作时段序列; 对涉及的路段进行编号。以 T ij 表示路段 i 第 j 个时 段的行程时间, 将各路段各时段的行程时间表示为表 2。 路网中路段动态行程时间表 表 2 路 段 时 段 i ii iii iv ⋯ j ⋯ I T Ii T Iii T Iiii T Iiv ⋯ T Ij ⋯ II T IIi T IIii T IIiii T IIiv ⋯ T IIj ⋯ III T IIIi T IIIii T IIIiii T IIIiv ⋯ T IIIj ⋯ IV T IV i T IV ii T IV iii T IV iv ⋯ T IV j ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ i T ii T iii T iiii T iiv ⋯ T ij ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ 车辆可能在某时刻呼叫服务, 某车辆从起点到目的地可能需经过若干条路段, 对其所经过 的路段按序编号 (1, 2, 3, ⋯k - 1, k , k + 1, ⋯) , 以[ tk , t′k ] 表示车辆经过第 k 路段的时间范围, 车辆通过路段k 的行程时间记为T k , 则 t′k = tk + T k。路段k 为路段k - 1的后续路段, 可知 t′k- 1 = tk。 2. 2　车辆通过路段 k 行程时间的确定方法 车辆通过路段 k 可能跨越若干时段, 各时段对应的行程时间表示为 T ′k1、T ′k2、T ′k3、T ′k4、 ⋯, 以 x k 表示车辆通过路段 k 起点时刻所属时段在系统工作时段序列中的次序, 则 x k = in t [ ( tk - t0)∃ t ] + 1 (1) in t: 取整函数。 且 T ′k i = T k (x k+ i- 1)。 当 ∃T、路段长度 (L ) 与行程速度有不同取值或不同组合时, 可能出现 T ′k1 比 ∃T 大、T ′k1 比 ∃T 小、T ′k1 与 ∃T 相等三种情况。 当 T ′k1 ≤ ∃T 时, 表示车辆在一个时段内就能通过路段 k , 则 T k = T ′k1。 当 T ′k1 > T 时, 表示车辆需要一个以上时段 (设为 f ) 才能通过该路段, 则根据运动学原 理, 下式成立: 43 ZQL 铅笔工具 ZQL 铅笔工具 ZQL 铅笔工具 ∑ f i= 1 ( L T ′k i õ ∃T ) ≤L < (∑f + 1i= 1 LT ′k i′õ ∃T ) ) 化简化: ∑ f i= 1 1 T ′k i ≤ 1∃T < ∑f + 1i= 1 1T ′k i (2) 可采用试算法确定 f 值。 由 f 值, 根据运动学原理可计算呼叫服务的车辆通过路段 k 的行程时间 (T k ) : T k = (f - 1) ∃T + [L - ∑f - 1 i= 1 ( L T ′K i∃T ) ]ö( LT ′kf ) = (f - 1) ∃T + (1 - ∑f - 1i= 1 ∃TT ′K i) õ T ′kf 由此, 得到路段 k 行程时间 计算公式 六西格玛计算公式下载结构力学静力计算公式下载重复性计算公式下载六西格玛计算公式下载年假计算公式 为: T k = T ′k1　　　　　　　　　　　　　　　 (T k1 ≤ ∃T ) (f - 1) ∃T + (1 - ∑f - 1 i= 1 ∃T T ′K i) õ T ′kf 　 (T k1 > ∃T ) (3) 式中: f ∑ f i= 1 1 T ′k i ≤ 1∃T < ∑f + 1i= 1 1T ′k i 的 T ′k i = T k (x k+ i- 1)。 2. 3　动态最优路径算法 多车导航会有起讫点不同的车辆呼叫服务, 需要同时搜索出连接若干不同起点与目的地 的最优路径; 而单车导航仅需为某辆车搜索出从其起点到目的地的最优路径。这两者的计算量 差异极大, 需要采用不同的算法。 2. 3. 1　适用于多车导航的实时动态最优路径的改进D ijk stra 算法 D ijk stra 算法又称 P T 标号法, 是经典的最短路径算法[4 ]。它能同时求出从原节点到其他 各节点的最优路径, 适用于多车导航系统。 D ijk stra 算法用P、T 分别表示某个节点的P 标号、T 标号; S 表示具有P 标号点的集合; 用Κ表示某节点的后向指针指向的节点, 若 Κ= 0, 表示该节点为原节点, Κ= M , 表示不含从原节 点到该节点的路径。由于动态路径的特点, 需要在搜索过程中临时计算出到达某路段起点时刻 对应时段在系统工作时段序列中的次序和通过路段的行程时间, 为此, 对D ijk stra 算法进行改 进, 计算步骤为: [ 1 ] 设边始的S 仅包含原节点, 原节点为当前节点 (m ) , 令其P = 0, Κ= 0, 无T 标号, 其他 各节点的 T 值为∞, Κ值为M 。 [ 2 ] 如果S 中包含全部节点, 算法终止, 这时, 对每个属于S 的节点, 其 P 值即为从原节点 沿最短路径到该节点的距离; 否则转入[ 3 ]。 [ 3 ] 根据当前节点m 后面连接的路段生成当前节点的后继节点, 对每一个后继节点 n, 进 行下列过程: ①根据式 (1) 计算车辆到达当前节点m 时对应的 x k; 根据式 (3) 计算当前节点m 与节点 n 间的行程时间; ② 如果 T (n) > P (m ) + 从m 到 n 的行程时间, 则将 T (n) 改为 P (m ) + 从m 到 n 的行 程时间, 将节点 n 的后向指针指向m ; 否则转入[ 4 ]。 53 [ 4 ] 在所有具有 T 标号的点中, 搜索 T 值最小的点, 如果该 T 值小于∞, 则令该节点为当 前节点 (m ) , 去掉其T 标号, 变为P 标号, 将m 移入S 中, 转入[ 2 ]; 否则终止, 这时, 对每个属于 S 的节点, 其 P 值即为从原节点沿最段路径到该节点的距离。 [ 5 ]从S 中各个节点开始回溯, 根据各节点的后向指针, 一直到原节点遍历节点; 最后报告 解路径。 若以 z 表示道路网中的节点数, s 表示道路网中路段数, 则该算法的运行时间是O (z 2 + s) + O (z 2)。 2. 3. 2　适用于单车导航的实时动态最优路径改进A 3 算法 对单车导航时, 没有必要在道路网中求从原点到其他各节点的最优路径。A 3 算法是发展 人工智能而产生的计算最短路最有效的启发式搜索方法, 算法到达目标节点即停止搜索[1 ]。 A 3 算法中应用了启发式估价函数, 用于评价每个生成节点的优先值, 该函数使得算法首先搜 索最有希望的路径。对于以动态行程时间为路阻的动态最优路径, 构造节点 n 的启发式估价函 数为: t′(n) = T (n) + h′(n) = ∑ n i= 1 T i (n) + d′(n) v′ t′(n) 为路径行程时间, T (n) 为从原节点到 i 节点所经过的所有路段的动态行程时间总 和, T i (n) 为路段 i 的动态行程时间, 估计项 h′(n) 是当前节点 n 和目标节点之间欧氏距离除以 估计的最高车速 v′。根据动态路径的特点, 将车辆到达某路段起点时刻对应时段在系统工作时 段序列中的次序和通过路段的行程时间纳入最优路径搜索过程, 对A 3 算法进行改进, 计算步 骤为: [ 1 ] 设初始的O PEN 表仅包含原节点, 其费用值为 0, 即 T 值为 0。令CLO SED 为空表, 设 其他节点的费用为∞。 [ 2 ] 若O PEN 表为空, 则宣告失败; 否则, 选取O PEN 表中具有最小 t′值的节点, 并叫做最 佳节点BEST , 把BEST 从O PEN 表移至CLO SED 表, 判断此BEST 是否是目标节点。若BEST 为目标节点, 转步骤[ 3 ], 若BEST 不是目标节点, 则根据本节点后面续接的路段生成BEST 的 后继节点, 对于每一个后继节 n, 进行下列过程: ①计算节点 n 的费用: 根据式 (1) 计算到达BEST 时对应的 x k; 根据 (3) 计算BEST 到节点 n 的行程时间; T (n) = BEST + 从BEST 到 n 的行程时间。 ②如果 n 与O PEN 表上的任一节点相同, 判断 n 是否具有最低的 T 值, 若是最低的 T 值, 用 n 的费用代替O PEN 表中相同的节点费用, 且将匹配节点的后向指针指向BEST。 ③如果 n 在CLO SED 表中与一节点相匹配, 检查节点 n 是否具有最小的 T 值, 如果节点 n 具有最小的T 值, 则用n 的费用代替匹配节点的费用, 并把匹配节点的后向指针指向BEST , 并 把该匹配节点移到O PEN 表。 ④如果 n 不在O PEN 表上, 也不在CLO SED 表上, 则把 n 的后向指针指向BEST , 并把 n 放入O PEN 中, 计算节点 n 的估价函数: t′(n) = T (n) + h′(n) 重复第[ 2 ] 步。 63 ZQL 铅笔工具 [ 3 ] 从BEST 节点回溯, 即从BEST 的后向指针一直到原节点遍历节点; 最后报告告解路 径。 若以b表示每一节点后继节点数的平均值, d 表示从原节点到目标节点最短路径的搜索深 度, 则算法的运行时间为O (bd )。该算法比D ijk stra 算法大大减少需要的时间与空间。 3　结　束　语 搜索最优路径是车辆导航系统的关键部分之一, 静态型最优路径与真实最优路径存在较 大差异, 基于动态行程时间的实时动态最优路径是具有真实意义的最优路径。文中设计的改进 D ijk stra 算法与改进A 3 算法, 将计算车辆到达路段起点时刻所属时段在系统工作时段序列中 的次序和路段行程时间融入搜索过程。前者适用于多车导航能系统, 能同时搜索出若干起讫点 间的最优路径, 后者适用于单车导航系统, 到达目的地即停止搜索, 后者比前者大大减少需要 的时间与空间。 预测路网上各路段未来各时段的行程时间是搜索动态最优路径的基础, 尚需深入研究提 高路段行程时间预测精度的预测策略、方法与技术; 交通参数采集周期和引导信息更新周期对 预测结果与引导效果有重要影响, 需要进一步研究合适的周期。 参 考 文 献 1　赵亦林著, 谭国真译. 车辆定位与导航系统. 北京: 电子工业出版社, 1999 2　杨兆升著. 城市交通流诱导系统理论与模型. 北京: 人民交通出版社, 2000 3　上海交通工程学会主编. 畅达新世纪的城市交通- 99’上海国际交通学术研讨会论文选. 上海: 同济大学出版社, 1999 4　钱颂迪等编. 运筹学. 北京: 清华大学出版社, 1990 5　Hom epage of ADVAN CE P ro ject: h ttp: ööais. its2p rogram. am. govö 6　T. D uncan, T he veh icle Rou ting p rob lem ; h ttp: ööwww. aiai. ed. ac. ukö2t im edöveh iclesövrp. h tm l, 1996 7　J. W erner, IT S on line, h ttp: ööww. itson line. com ö, 1996 8　D. J. Bertsim as and D. Sim ch i2L evi, A new generation of veh icle Rou ting research: Robust A lgo rithm s, A ddressing U ncertain ty, Operations Res. ,M aröA p r. 1996. V o l. 44, N o. 2. 286- 304 Study of The M ethod to Search D ynam ic Optim um Route for Veh icle Nav iga tion System Su Yongyun　Yan Kefei　H uang X iang　Zhu Peikang 【Abstract】　 T h is paper analysis the supp lies and dem ands of the rou te gu idance info rm at ion in veh icle navigat ion system , then a new real t im e dynam ic op t im um rou te has been p resen ted w h ich app roach the true op t im um rou te and pu t fo rw ard imp roved D ijk st ra a lgo rithm and imp roved A 3 algo rithm to calcu la te th is rou te, the fo rm er su it m u lt i2veh icles navigat ion and the la t ter su it so lo2veh icle navigat ion. 【Keywords】　V eh icle navigat ion system , D ynam ic op t im um rou te, Imp roved D ijk st ra a lgo rithm , Imp roved A 3 algo rithm 73 ZQL 铅笔工具