交通网络有效路径的一种搜索算法

《交通网络有效路径的一种搜索算法》由会员分享，可在线阅读，更多相关《交通网络有效路径的一种搜索算法（6页珍藏版）》请在金锄头文库上搜索。

1、交通网络有效路径的一种搜索算法摘 要：基于图论中 Dijkstra 算法的思想，建立了一种搜索交通网络 OD 对间所有有效路径的方法。当不考 虑有效路径的限制时，该方法可按路径长度递增的顺序依次搜索出有向图中的所有通路。针对具有 24 个节 点、77 条路段的某交通网络，我们进行了大量仿真，结果表明该算法是十分有效的。本文提出的方法可用 于简化交通网络 OD 估计中监测点定位的算法。关键词：0D矩阵；路径搜索；仿真A Search Algorithm for Effective Paths in Traffic NetworksLIN Yong, CAI YuanLi, HUANG YongX

2、uan( School of Electronic and Information Engineering, Xian Jiaotong University, Xian 710049,China )Abstract: Based on the Dijkstra methodology in graph theory, an algorithm to search all the effective paths between OD pairs in traffic networks is proposed. This algorithm is also generalized to dete

3、rmine all the paths in a directional graph in the ascending order of paths length. A lot of simulations have been conducted on a traffic network with 24 nodes and 77 links. It is shown that the search algorithm is effective and efficient. The algorithm can be applied to simplify the surveillance poi

4、nts positioning in the OD matrix estimate of traffic networks.Keywords: OD matrix; path search; simulation1引言OD矩阵，或称0D表，是交通网络中 所有起点(Origin)与终点(Destination)之 间出行交换数量的表格，其中的每个元素反 映了特定 OD 对间在一定时间段内的出行 量。它是交通网络规划和交通管理的重要依 据。历史上， OD 矩阵是作大量的交通调查 得到的，代价十分高昂。1978 年， Vdnzuylon 和 Wllumsen 通过交通网络中一定数量的路 段流量观测值

5、来估计OD矩阵，使OD估计 的研究有了一个突破口1。之后，经过国内 外学者的不断努力，建立了各种OD估计模 型2。然而，几乎所有的 OD 估计模型均未 讨论如何设置交通量观测点，使得任意 OD 对间的出行量均能被某个观测点检测到。文 献35对此进行了专门研究，提出观测点设 置应当满足的 4 个规则，并建立0-1整数规 划模型进行求解。但上述方法需已知各 OD 对间的有效出行路径。文献6为避免列举这 些有效路径，根据检测点应当满足的规则， 建立了关于其分布的非线性规划模型。在已 知极点间转移概率的前提下，将检测点的分 布问题描述成一个平均报酬 Markov 决策过 程，并通过转化为一个等价的整数

6、线性规划 问题求解。为此，本文运用仿真的思想来搜 索 OD 对间的所有有效路径，以简化上述的 OD 量观测点定位算法。2 有效路径的搜索算法2.1 有效路段与有效路径7有效路段 (i, j) 定义为路段终点 j 比路 段起点i更靠近出行目的地s的路段，即沿 该路段前进能更接近出行终点。因此，有效 路段的判别条件为：对于路段(i, j)，若 L (j,s) L (i,s) ， 则为有效路段。 mi nmi nL .(a, b)为节点a至b的最短路权，可采 min用Dijkstra算法得到。有效路段是相对于OD 对(r, s)而言的，某一路段在某一 OD对下 为有效路段，而在另一 OD对下可能为非

7、有 效路段。有效路径必须由一系列的有效路段 组成，每个OD对的出行量只在它相应的有 效路径上进行分配。对于通常的城市交通网络，交叉口相交 道路数多数为 4 条，各节点的有效路段及有 效路径一般为 13 条。在区域公路网中，一 般交通节点与城市交通节点相同，但对于交 通枢纽(城市)，连接道路可多达810 条， 有效路段可达 5 条左右。2.2 算法的基本思想在具有非负权值的图中， D.jkstra 算法 是求取两点间最短路问题的有效方法之一。 其基本思想是8：从起点 s 沿一切可能的弧 派遣使者，这些使者均以相同的速度匀速前 进，看谁首先到达一个新的顶点；当一个使 者到达第一个新顶点时，则给他作

8、记号，以 表示他是从顶点 s 来的，同时记录下历经的 路径长度；而后又毫无延迟地再派遣使者， 沿一切可能的弧以原速匀速前进，重复 前面的过程，一直到达要求的终点为止。把 从s到t最快的使者历经的路径，作为 s t 的最短路径。上述思想稍加整理，即 可得到 D.jkstra 算法。对 D.jkstra 算法的思想稍加变通，即只 对满足有效路段约束条件的下游弧派遣使 者，便可按路径长度递增的顺序搜索交通网 络中特定的 OD 对间的全部有效路径。不加 约束条件，算法按路径长度递增的顺序可依 次得到从起点s到其它各点的所有通路。对 于大规模的交通网络，这或许会导致“组合 爆炸”；但在计算能力容许的前提

9、下，至少 可按路径长度递增的顺序，一次找出某起点 s到其它节点间的所有长度小于L的通路。 和常用的通路搜索算法相比，如邻接矩阵乘 方逐步回溯法9，转化为最短路、次短路、 次次短路、的搜索方法10，该方法的思 路直观简洁、易于实现；而且，仿真中可根 据需要设定搜索条件，如上文所述的有效路 径搜索，极大地减少了计算量。将上述思想用仿真的方法实现，即可得 到期望的结果。2.3 仿真流程仿真系统中，交通网络的各路段信息存 放在数据库中。各路段的属性为：上游节点、 下游节点、路段长度等；各使者的属性有： 指向其父使者的指针，历经的路径上的各节 点顺序表，所在路段的下游节点，当前时间， 到达下游节点的时间

10、。所有使者的信息存放 在一条使者链表中，链表中的每个节点存放 一个使者的信息。各使者的速度假定均为 lm/s,故通过一条路段所需时间数值上与该 路段长度相等。仿真流程如下1) 仿真数据初始化。包括生成交通网络(有向图)邻接矩阵，设置OD对起点、 终点号，仿真钟置0等；调用Dijkstra 算法计算各节点到终点的最短距离并 存于缓冲区中，为后续仿真步中判断可 行路段提供依据。2) 从起点往下游各可行路段派遣使者，每 个使者记录下其将历经的路段的下游 节点号，存放在节点顺序表中。3) 调度最先到达下游节点的使者作为当 前使者。4) 若仿真钟大于预设的仿真时间段长度 或所有使者均已到达目标节点，则输

11、出 统计结果，仿真结束；否则，仿真钟置 为该使者到达下游节点的时刻，并将该 使者作为父使者。如果父使者所处的当 前节点不是终点，则生成子使者并向下 游各可行路段派遣，同时在使者链表中 增加一个新的节点以存储与该使者相 关的信息；否则，输出父使者所历经路 径的节点顺序表。5) 注销父使者。记录下父使者的节点顺序表后，从使者链表中删除对应节点，并 释放其占有的内存空间。6) 各子使者将父使者节点顺序表中的各 节点号，以及该子使者即将通过的路段 的下游节点号添加到其对应的节点顺序表中；判断各子使者的节点顺序表中是否存在相同的两节点，如是，表明有回环存在，注销该使者（即从链表中删 除对应节点，并释放占

12、有的内存空间）。7）转 3，进入下一次仿真循环。图1仿真流程图图 1 给出了该仿真算法的流程图。3 实例分析将文献6中的交通网络作为本文仿真 研究的实例。如图 2 所示，网络中共有 24 个节点，77 条路段（有向弧），各路段的权 值均为1。算法用Visual C+ 6.0软件开发 工具实现，计算机的 CPU 为 1.2G 的赛扬处 理器，内存为128M的SDRAM。仿真15 步，花费机器时间不超过 10 毫秒，求出了 节点 1 到节点 20 的有效路径共3 条，分别 为：1-2-6-8-16-18-20， 1-2-6-8-7-18-20， 1-3-12-13-24-21-20。将算法稍作修改

13、，即当 前使者向下游所有路段派遣子使者，便可按 路径长度递增的顺序搜索网络中从某节点 出发的所有通路。在同样的硬件平台上，仿 真 17525 步，花费机器时间 12.1 秒，按路径 长度递增的顺序依次枚举出了节点1到节点 20间的所有通路共计3165条，最短长度为 6，最大长度为 23；同时，也得到了节点 1 到其它各节点的长度小于23，且路径长度递 增的若干通路（可以肯定，所有长度小于等 于 23 的通路均已完全枚举出）。其中，最短 路之一为：1-2-6-8-16-18-20；最长路之一为：1- 2-6-5-9-8-7-18-16-10-17-19-15-14-11-4-3-12- 13-2

14、4-23-22-21-20。4 结束语根据图论中 Dijkstra 算法的基本思想， 本文提出了按路径长度递增的顺序求取交 通网络OD对间所有有效路径的一种计算方 法。在不考虑有效路径的约束下，该方法可 按路径长度递增的顺序依次搜索有向图中 的所有通路。大量仿真结果证实了该算法是 有效和可行的。本文提出的方法可用于简化 交通网络OD估计中监测点定位的算法，并 可用于有向图中的通路搜索。图2交通网络图参考文献1 尹娟、郭国会，人工神经网络在交通网 络 OD 矩阵推算中的应用，浙江大学学 报，2000，34（4）：423-427。2 丁以中，交通运输网络中OD流矩阵的 估算方法，系统工程理论方法应

15、用， 1996， 5（2）：35-41。3 陈森发、邓学钧、王炜，估计OD矩阵 的监测路段选择的优化，自动化学报， 1997， 23（6）：831-834。4 周晶、盛昭瀚、何建敏等，交通检测点 分布规则及其数学模型，东南大学学报， 1998， 28（6）：59-63。5 杨琪、王炜、卢林等，用于 OD 反推的 路段交通量观测点设置研究，中国公路 学报， 1999，第12卷增刊：81-87。6 周晶、盛昭瀚、何建敏等，适于估计 OD 矩阵的交通检测点的最优分布，自动化 学报， 2000， 26（3）：303-309。7 王炜，多路径交通分配模型的改进及节 点分配算法，东南大学学报， 1994， 24 （6）：21-26。8 陈森发，网络模型及其优化，南京：东 南大学出版社， 1992， 302。9 卢开澄、卢华明，图论及其应用 M ， 北京：清华大学出版社， 1992， 4-10。10 杨东援，交通规划决策支持系统 M ， 上海：同济大学出版社， 1997， 35-73。