交通分配软件设计.doc

本科学生毕业设计 交通分配软件设计 黑黑 龙龙 江江 工工 程程 学学 院院 二 一二年六月 The Graduation Design for Bachelor s Degree Design of Traffic Distribution Software 摘 要 随着我国城市化进程和经济发展 机动车拥有量和出行量迅速提高 随之而来的 是日益严峻的交通拥堵问题 而解决复杂的城市交通问题离不开交通规划理论的指导 做好不同层次的交通规划 尤其是加强区域交通规划 城市综合交通规划和交通管理 规划的制定和实施 对于建立可持续发展的交通环境和综合交通体系具有重要意义 如何利用现有的公路运输资源 尽可能地提高运输效率来缓解这一矛盾 已经成为人 们关注的问题 而交通分配是交通规划理论中重要的一部分 合理的交通分配可以作 为解决这个问题的一个方法 因此 研究交通分配理论及交通分配软件具有重要的现 实意义 本设计运用 AoutCAD 软件绘制虚拟路网图 并结合 Access 软件建立虚拟路网基 本数据库 用 VB 语言对交通分配算法进行编程 从而实现交通量分配 主要是对全 有全无分配法 改进的多路径 Logit 模型和 Dail 算法 单路径 增量加载分配法进行 编程 并结合案例对交通分配方法进行性能比较 本设计可以实现输入路网阻抗 流 量等数据后 方便的查询各点之间的最短路径 各路段之间的流量分配 从而可以方 便进行交通量分配 提高交通量分配的精度 为交通规划参考提供参考依据 关键词 Access 数据库 VB 全有全无分配法 Logit 模型 Dail 算法 增量加载分 配法 黑龙江工程学院本科生毕业设计 II ABSTRACT With China s urbanization process and economic development and motor vehicle ownership and travel quantity increased rapidly and with it the increasingly serious problem of traffic congestion And solve complex urban transportation problem without transport planning theory guidance Do the different levels of transportation planning especially the regional transportation planning strengthen comprehensive urban transportation planning and traffic management planning and implementation to build the sustainable development of the traffic environment and integrated transportation system has important significance How to use the existing road transport resources as far as possible to improve transport efficiency to ease this contradiction has become a concern of the people And the traffic distribution transport planning theory is an important part of the the reasonable traffic assignment can be as one solution to this problem Therefore the traffic distribution theory and traffic distribution software has the important practical significance This design uses AoutCAD software rendering virtual network diagram and combined with Access software based on the virtual network basic database VB language to traffic assignment algorithm programming so as to realize the traffic distribution Is mainly to the all or nothing assignment improved many path Logit model and Dail algorithm single path incremental load distribution method on programming and combination of case of traffic distribution method for performance comparison This design can realize the input impedance and flow rate on the network data convenient inquires between each point of the shortest path between sections each of the flow distribution thus can be convenient for traffic distribution improve the precision of the traffic flow distribution traffic planning for reference to provide the reference 黑龙江工程学院本科生毕业设计 III Key words the Access database VB all or nothing assignment Logit model Dail algorithm Incremental load distribution method 目 录 摘 要 I ABSTRACT II 第 1 章 绪 论 1 1 1 课题研究目的及意义 1 1 1 1 课题研究目的 1 1 1 2 课题研究意义 1 1 2 国内外研究现状 2 1 2 1 国内研究现状 2 1 2 2 国外研究现状 3 1 3 课题研究主要内容及技术路线 4 1 3 1 研究主要内容 4 1 3 2 技术路线 4 第 2 章 交通分配理论及方法 6 2 1 交通分配概述 6 2 2 基本概念 6 2 2 1 路径与最短路径 6 2 2 2 交通阻抗 6 2 2 3 交通网络的表示 7 2 3 交通分配的基本原理 8 2 3 1 交通均衡问题 8 2 3 2 非均衡模型 9 黑龙江工程学院本科生毕业设计 2 4 交通分配的方法 9 2 4 1 全有全无分配法 9 2 4 2 阻抗可变单路径分配方法 11 2 4 3 阻抗为常数的多路径分配方法 12 2 4 4 阻抗可变的多路径分配方法 16 2 5 本章小结 17 第 3 章 数据库的建立与调用 18 3 1 ACCESS数据库介绍 18 3 1 1 概括 18 3 1 2 Access 的六种对象 18 3 2 选择 ACCESS的理由 19 3 3 数据库的建立和调用 19 3 3 1 数据结构 19 3 3 2 数据库的建立 20 3 3 3 数据库的导入 21 3 4 本章小结 23 第 4 章 程序设计 24 4 1 模块设计的总体思路及流程 24 4 1 1 设计总体思路 24 4 1 2 程序操作流程的基本步骤 24 4 2 虚拟路网建立模块 26 4 2 1 绘制虚拟路网 26 4 2 2 虚拟路网的链接 26 4 3 各部分模块具体设计 27 4 3 1 登录模块 27 4 3 2 虚拟路网模块 27 4 3 3 数据输入模块 28 4 3 4 模型选择模块 28 4 4 本章小结 29 黑龙江工程学院本科生毕业设计 结 论 30 参考文献 31 致 谢 33 附 录 34 黑龙江工程学院本科生毕业设计 1 第 1 章 绪 论 1 1 课题研究目的及意义 随着我国城市化进程和经济发展 机动车拥有量和出行量迅速提高 随之而来的 是日益严峻的交通拥堵问题 而解决复杂的城市交通问题离不开交通规划理论的指导 做好不同层次的交通规划 尤其是加强区域交通规划 城市综合交通规划和交通管理 规划的制定和实施 对于建立可持续发展的交通环境和综合交通体系具有重要意义 而交通分配是交通规划理论中重要的一部分 因此 研究交通分配理论及交通分配软 件具有重要的现实意义 1 1 1 课题研究目的 传统的交通规划都是采用四阶段法 即交通量的生成 分布 出行方式的选择和 交通量的分配四个阶段来确定路段交通量 首先划分不同的交通小区 预测出未来年 各个交通小区的交通发生量和吸引量 再用重力模型或增长系数法推断各个交通小区 之间的交通出行 再根据交通组成 计算出各个小区之间利用公路出行的交通量 最 后通过不同的交通分配方法 将这些公路出行交通量分配到各种出行路径上 再把所 有交通小区间的交通量进行叠加 即得到设计道路上的路段交通量 这一方法的核心 就是交通量的分配模型 交通分配 就是将预测得出的 OD 交通量 根据已知的道路网描述 按照一定的 规则符合实际地分配到路网中的各条道路上去 进而求出路网中各路段的交通流量 并据此对城市交通网络的使用状况做出分析和评价 交通分配的理论的基础 实际上 就出行者的路径选择行为 它是根据出行者的选择行为将交通分布矩阵合理地分配到 路段上 路段交通量是分配到的小区出行的叠加 交通分配可以将现状 OD 量在现状交通网络上分配 以分析目前交通网络的运行 状况 还可以将这些观测值与在相应路段的分配结果进行比较 以检验 4 步骤预测模 型的精度 也可以是规划年 OD 分布预测值在现状交通网络上的分配 以发现对规划 年的交通需求 现状交通网络的缺陷 为后面交通网络的规划设计提供依据 还可以 是规划年 OD 分布预测值在规划交通网络上的分配 以评价交通网络规划方案的优劣 黑龙江工程学院本科生毕业设计 2 1 1 2 课题研究意义 在传统交通规划中交通分配曾是四阶段交通预测的最后一步 在现代交通规划中 它是方案设计的理论基础 它可以用来分析交通路网的合理性 交通分配模型是用来 预测未来规划方案的路网流量 估算路段的出行时间和相关的属性 是估算路网规划 相关项目经济效益的基础 交通分配模型还用于有关路网性能的估算 为很多模型中 方式选择和出行分布等阶段的模型提供依据 研究交通分配软件可以方便进行交通量分配 用计算机对交通最短路及交通量计 算 从而减少计算量 并减少工作的失误 提高交通量分配的精度 1 2 国内外研究现状 在道路规划和设计过程中 交通量的预测一般都采用四阶段法 在众多研究者的 共同努力下 交通量的分配是研究最为成熟的一个阶段 人们根据不同的交通行为的 假设 选择不同的交通抗阻和离散选择模型 推出了不同的交通分配模型 例如全有 全无分配模型 按比例分配模型 均衡分配模型等 其中全有全无模型是其他模型的 基础 对于交通分配 国内外均进行过较多的研究 数学规划方法 图论方法及计算机 技术的发展 为合理的交通分配模型的研制及应用提供了坚实的基础 常见的交通分 配模型有平衡模型与非平衡模型两大类 均以 Wardrop 第一 第二原理作为划分依据 根据分配手段的不同交通分配模型可分为静态与动态两类 就路径的选择又可分为单 路径型与多路径型两类 1 1 2 1 国内研究现状 国内外出现了许多关于交通分配的方法 其中 Logit 模型以其直观易懂 算法简 洁 有较强的可解释性等优点得到广泛应用 而 Dail 算法较好地实现了 Logit 模型的 求解 但是该算法在实际应用中仍存在一定的缺陷 河海大学交通学院的陈扶皂 吴中在原有Logit模型与国内外学者研究基础上 对Logit模型进行了改进 修改了Dail算法中关于有效路径的定义条件 并结合算例给 出了具体改进Dail算法的分配过程 说明改进的方法分配速度快且比较符合实际情况 2 中山大学工学院李军 聂佩林 余志在全路径Logit交通分配模型的求解方法中分 析了求解Logit模型的现有算法的不足 根据路网的连通特征提出了一种新的求解全 路径Logit分配模型的迭代算法 给出了Dail算法和Logit模型的等价性证明 并和经典 的Dail算法进行了比较 3 华南理工大学的温惠英 王晓 曹更永 黄永刚提出了一 个基于Logit方法的动态交通随机分配模型 该模型通过最短路算法和随机分配来解 黑龙江工程学院本科生毕业设计 3 决动态均衡交通分配中的出行选择问题 避免了以往动态交通均衡分配中解凸规划或 非线性规划问题 同时不需要路径枚举 而使本模型更适合于大型路网的动态交通分 配 4 对于交通分配的研究多注重交通分配本身以及交通分配和交通控制一体化的算法 研究及成果较多 而对于交通分配中路网模型的研究则较少 作为路线优化的基础 必须对其进行深人的研究 昆明理工大学交通工程学院的刘小兰 成卫在对路线选择 进行较为深入的理论研究和应用分析的基础上 考虑到路线优化问题的特殊性和基本 特点 提出了改进的路网表示法 5 刘小艳 金宝辉 黄新建通过运用决策理论的思 想对现有的两类静态多路径交通分配方法进行对比分析 提出决策系数的概念 将出 行者个人行为引入交通分配模型 建立了一种新的静态多路径交通分配模型 可使交 通需求预测的结果更加精确 具有一定的实际意义 6 静态多路径交通分配法由于效 果较好 算法清晰 易于在计算机上实现等特点 因而在实际交通分配中得到了普遍 的采用 但该方法在计算中 存在输入输出数据量大 结果不易保存等问题 潘鲁萍 潘山 李乐荣针在VB编程实现静态多路径交通分配中对此问题 采用VB软件编程 通过算法和设计新颖的输入输出界面 有效解决了该问题 7 陈斌研究了多路径 容 量限制交通分配方法的计算模型 编制了准确快速实用的程序 8 邓应军 李明顺讨 论了多路径交通分配的计算模型与方法 提出基于广义费用最小的Logit模型 并对 其计算方法详细阐述 9 秦鸣 姜培根据有效路径的不同定义 进行相应的交通流分 配确定了合理的有效路径 10 黄文 刘润有 练象平 程海波在前人研究的基础上 对不同的交通分配模型进行分析 根据它们不同的机理 阐明了不同分配模型的应用 条件 11 1 2 2 国外研究现状 近半个世纪以来 国内外学者对交通分配问题进行了大量的研究 提出了不少交 通流分配模型与软件 总体来看这些模型可以分为两大类 平衡分配模型和非平衡分 配模型 然而以往的研究成果无论是平衡模型还是非平衡模型基本上都属于静态模型 的范畴 不能反映交通流的时变特性动态交通分配 12 为解决这个问题 国内外在 动态交通流分配领域进行了很多研究 动态交通分配理论模型自1978年提出后至今的三十多年里 国外学者对动态交通 分配理论模型进行了较多的研究 主要有数学规划方法 计算机模拟方法 最优控制 理论方法和变分不等式 VI 方法等 这些方法的发展 为动态交通分配模型的研究 提供了坚实的理论基础 13 在数学规划方法上 Ziliaskopoulos引入了一个单一终点的 基于单元传播的SO DTA 系统最优动态分配 线性规划模型 该模型可以用于交通 黑龙江工程学院本科生毕业设计 4 流传播模型 14 在计算机模拟方法方面 VanAerde与Yagar对基于计算机模拟的动态 网络交通流分配模型的算法进行了改进 15 目前国内外在交通分配方面的研究主要表现为 静态交通流领域己经有了成熟的 理论和方法 并有相关的中外学术专著问世 但在动态交通分配方面的学术专著还没 有成熟 国内外在动态交通流分配领域的研究都在积极的进行当中 表现为国外在理 论 方法和应用的研究较之国内要超前 国内还处于初级阶段 同时无论国内外在理 论方面的研究居多 而在实际应用上还有待进一步发展 16 能够进行交通分配的软件多为交通规划软件 交通规划软件于20世纪60年代末首 先在美国开始尝试 经历了从大型计算机时代的诞生期 伴随个人电脑普及而来的发 展期 以及Windows系统与地理信息系统和交通模型成功结合带来的成熟期 推广日 渐广阔 功能日趋完善 操作更为便捷 从20世纪80年代中期 国内大专院校和交通 规划单位开始引进交通规划软件 国内也出现一些自己开发的软件 如东南大学的 Tran2Star 建设部交通中心的TranSolution等 随着计算机技术的应用 有很多交通 软件可以进行交通分配 目前国内使用的交通分配软件有 TRANSCAD EMME2 TRANSTAR CUBE TRIPS VISUM等 1 3 课题研究主要内容及技术路线 1 3 1 研究主要内容 本课题主要研究交通分配的理论及方法 运用 Access 建立虚拟路网基本数据库 并用 VB 语言对交通分配算法进行编程 从而实现对交通量的分配 本课题的主要内容如下 1 论证并建立比较通用的数据库结构 完成对数据库的调用 2 实现全有全无算法 多路径分配方法 改进的 Dail 方法和 Logit 模型 单 路径 增量加载分配法的 VB 编程 3 实现交通分配软件的设计 并结合案例对算法进行性能比较 1 3 2 技术路线 技术路线如图1 1所示 黑龙江工程学院本科生毕业设计 5 黑龙江工程学院本科生毕业设计 6 资料查询 文献总结 确定交通分配方法 全有全无分配方法多路径分配方法 Dail 方法和 Logit 模型 增量加载分配法 建立虚拟路网 进行交通量分配 建立路网数据库 并与 VB 连接 确定最短路径 输出交通量分配结果 用 VB 对分配方法进行编程 结合实际案例 对各分配算法进行性能比较 完成交通分配软件设计 图 1 1 设计技术路线图 黑龙江工程学院本科生毕业设计 7 第 2 章 交通分配理论及方法 2 1 交通分配概述 交通分配是指将各分区之间出行分布量分配到交通网络的各条边上去的工作过程 具体包括以下内容 1 可以是将现状 OD 量在现状交通网络上的分配 以分析目前交通网络的运 行状况 如果有某些路段的交通量观测值 还可以将这些观测值与在相应路段的分配 结果进行比较 以检验四阶段预测模型的精度 2 也可以是规划年 OD 分布预测值在现状交通网络上的分配 以发现对规划 年的交通需求来说 现状交通网络的缺陷 为后面交通网络的规划设计提供依据 3 还可以是规划年 OD 分布预测值在规划交通网络上的分配 以评价交通网 络规划方案的优劣 就交通分配的工作特点来说 可以分做两类 交通工具的运行线路固定类型和运 行线路不固定类型 前者有 城市公共交通网 城市轨道交通网 这些是集体旅客运 输 后者有 城市道路网 公路网 高速公路网 这一般是指个体旅客运输或货物运 输 这类网络中 车辆是自由选择运行路径的 2 2 基本概念 2 2 1 路径与最短路径 1 路段 交通网络上相邻两个节点之间的交通线路称作 路段 2 路径 交通网络上任意一对 OD 点之间 从产生点到吸引点一串连通的路 段的有序排列叫作这对 OD 点之间的路径 一对 OD 点之间可以有多条路径 3 最短路径 一对 OD 点之间的路径中总阻抗最小的路径叫 最短路径 一 对 OD 点之间的最短路径也可能不止一条 用 M r s 表示点对 r s 间的最小阻抗 最 短路径和最小阻抗的求法是这个交通分配的基本问题 它们的求法将在后面专门讨论 2 2 2 交通阻抗 交通阻抗是指交通网络上路段或路径之间的运行距离 时间 费用 舒适度 或 这些因素的综合 具体到不同交通网络其含义随人们的关注点不同而有所偏重 或为 黑龙江工程学院本科生毕业设计 8 了简单起见 干脆单指其中某个因素 如对城市道路网 一般指出行时间 公路网较 多地指距离 交通阻抗有两部分组成 路段上的阻抗 节点处的阻抗 2 2 3 交通网络的表示 为了方便对交通网络的数学处理 首先必须把交通网络抽象化 一般地 用图论 中的 图 表示交通网络比较方便 此时 把交通网络中的出行生成点 线路交叉点看 作是图的节点 把任意两个节点之间的交通线路看作是图的边 一般地 将一些次要 的路段和交叉点忽略掉 以简化交通网络图 如果某条交通线路是单向的 则用一条 带箭头的有向边表示它 而无箭头的边则表示双向的交通线路 关于交通网络的数学 描述方法很多 这里介绍常用的三种 1 邻接矩阵 邻接矩阵 L 是一个 n 阶方阵 n 是节点的数目 其中的元素 lij表示交通网络中 节点的邻接关系 定义为 图中存在边 图中不存在边 ji ji lij 1 0 2 1 2 邻接目录表 邻接矩阵中有绝大部分的元素为 0 是个稀疏矩阵 对一个实际的交通网络 如 含 100 个节点的城市道路网 只有约 400 个元素为 1 其它 10000 400 个元素为 0 占 96 要浪费大量的计算机内存空间 邻接目录表就可以克服这个缺点 所谓邻接目录表也是一个矩阵 V 是 n k 阶的 此处 k 表示图中街道最多邻接的 节点数 如对一个没有四支以上的城市道路网 可取 k 4 元素表示第 i 个节点的 ij v 第 j 个邻接的节点 不足的用虚拟节点 0 表示 3 阻抗矩阵 邻接矩阵和邻接目录表都只能表达节点之间是否相邻 而没能表达相邻节点之间 交通线路的阻抗 阻抗矩阵则可以弥补这个缺陷 在交通网络图上 标上各边的阻抗 值 就得带阻抗的交通网络图 针对带阻抗的交通网络图可定义阻抗矩阵 其中 矩阵中的元素 ij n n Dd 点不相邻 点相邻点与驶时间 车辆在路段上的平均行 时 ji ji ji dij 0 黑龙江工程学院本科生毕业设计 9 2 2 2 3 交通分配的基本原理 2 3 1 交通均衡问题 如果两点之间有很多条路线可供出行者选择 那每个出行者自然都选择最短路径 但随着这两点之间交通量的增大 其最短路径上的交通流量也会随之增加 增加至一 定程度之后 这条最短路径的走行时间就会因为拥挤或堵塞而变长 以至长过次短路 径的走行时间 于是就有一部分道路利用者会选择次短的道路 随着两点之间的交通 量继续增加 两点之间的所有道路都有可能被利用 如果所有的道路利用者都准确知道各条道路所需的行走时间 并选择走行时间最 短的道路 最终两点之间被利用的各条道路的走行时间会相等 没有被利用的道路的 走行时间会更长 这种状态被称之为道路网的均衡状态 1952 年 Wardrop 给这种均 衡状态下了准确定义 实际道路网中一般有很多对 OD 点 每对 OD 点之间的各条路径都是由很多独立 的路段组成 由这些独立的路段又可以组合成许多条不同的路径 因此实际道路网的 每对 OD 点都有很多条路径 另外 各对 OD 点的路径也互相重叠 因此 实际道路 网的均衡状态是非常复杂的 由于这种复杂性 从 1952 年 Wardrop 提出道路网均衡 的概念和定义之后 如何数学描述和求解这个均衡问题成了一个难题 1956 年 Bechmann 等提出了描述这个均衡问题的一个数学规划模型 经过 20 年之后即 1975 年才由 LeBlanc 等学者设计出了求解 Bechmann 模型的算法 从而形成了现在的实用 解法 Wardrop 原理 Bechmann 模型 Leblanc 算法这三点突破是交通分配问题 研究的三个里程碑 也是现在交通分配理论的基础 Wardrop 的道路网交通均衡的准确定义是 在道路网的利用者都知道网络的状态并试图选择最短路径时 网络会达到这样一 种均衡状态 每对 OD 点之间各条被利用的路径的走行时间都相等而且是最小的走行 时间 而没有被利用的的路径的走行时间都大于或等于这个最小的走行时间 这条定 义通常称为 Wardrop 的第一原理 Wardrop 的第二原理 在系统平衡的条件下 考虑拥挤对走行时间影响的网络中 网络中的交通量应按 某种方式分配 以使网络中的交通量的总走行时间最小 在交通规划中 把使用 Wardrop 原理的模型称为 均衡模型 不使用 Wardrop 黑龙江工程学院本科生毕业设计 10 原理的模型叫 非均衡模型 2 3 2 非均衡模型 目前已提出许多非均衡模型及其解法 这些模型都不用数学表达式描述 根据分 配手法可分为容量限制与容量不限制两类 就路径选择可分为单路径与多路径两类 综合起来 可以分以下四类 见表 2 1 表 2 1 非均衡交通分配模型 分类容量不限制分配方法容量限制分配方法 单路径最短路 全有全无 分配容量限制单路径分配 多路径多路径分配容量限制多路径分配 2 4 交通分配的方法 2 4 1 全有全无分配法 设路段的阻抗为常数 即假定走行时间不受路段上流量的影响 一次将一个 OD 点对的出行分布量全部分配到它们这间的最短路径上去的方法叫做 全有全无分配 法 该法又叫 最短路径分配法 和 0 1 分配法 这是一种最简单的分配方法 是其它分配方法的基础 在进行全有全无分配之前 首先要介绍最短路径算法 最短路径算法是交通分配的最基本的算法 几乎所有交通分配方法都要以它作为 一个基本子过程反复调用 最短路径算法的设计问题是图论 运筹学 交通规划等领 域的学者们广为关注的问题 因此已设计出了多种算法 其实 这个问题包含两个子 问题 两点间的最小阻抗 和两点间的阻抗最小的路径 最短路径 前一个子问题是 解决后一个子问题的前提 许多方法都是将这两个子问题分开考虑 设计出来的算法 是分别单独求出最小阻抗或最短路径 我们这里介绍 Floyd 和 Warshall 于 1962 年设 计的算法 当时他们是各自独立设计出来的 Floyd Warshall 方法同时能求出最小阻 抗和最短路径 首先把交通网络中的节点分成 OD 点和交叉点两类 OD 点产生或吸引交通量 而交叉点不会 现定义两个矩阵 最小阻抗矩阵 其中 表示节点对 i j 间的最小阻抗 ij n n Cc ij c 倒数第二个节点矩阵 其中 表示节点 i 到节点 j 的最短路径 ij n n Vv ij v 上倒数第二个节点 根据最后求得的矩阵 V 可以找出任意两点之间的最短路径 如 则节 ij vk 黑龙江工程学院本科生毕业设计 11 点 i 到节点 j 的最短路径上倒数第二个节点是 k 若 则节点 i 到节点 j 的最短 ik vl 路径上倒数第三个节点是 l 依次类推 可以从 j 点逐步上溯 一直到 i 点为止 找 出最短路径上的各个节点 因此 剩下的问题就是求出矩阵 C 和 V Floyd Warshall 算法 步 1 初始化 令 C 为阻抗矩阵 对所有的节点 i 和 j 令 vi ij 步 2 对所有的交叉点 k 作 对所有的节点 包括交叉点和 OD 点 i i k 作 对所有的节点 j j i k 作 若 则 ccc ikkjij cccvv ijikkjijkj 算法结束 可以发现 Floyd Warshall 算法非常简练 设网络中交叉点数为 m 总节点数 为 n 则该算法的计算量为次判断和赋值运算 2 m n 广泛使用的寻找最短路的基本算法还有两个 一个是 Moore 算法 另一个是 Dijkstra 算法 我们将讨论更方便的节点标注法 网路中 AB 之间的路段长度表示为 d 路径或道路定义为一系列联结的节点 比如 A C D H 而路径的长度是路径中相应路 段长度的代数和 令 d 表示从出发点 S 到节点或质点 A 的最短距离 P 是 A 的 前 点 那么路段 P A 就是从 S 到 A 的最短路中的一部分 构造一个从 S 到网络中任何其他节点的最短路树的过程可以描述如下 初始化 令所有 d 在计算机上设置一个合适最大值 d 0 建立表 L 来容纳已开始被算法计算但并没有作为其他节点的前点的点 这是构 造树的技巧 使其分枝可以到达所有节点 设所有 L 中的节点 L 为 0 所有 P 设一个 合适的缺省值 过程 起点 S 作为 当前 节点的 A 1 逐个检验路径 A B 如果 d d B d 那么令 2 将 A 从 L 中除去 若 L 为空表 那么停止计算 否则转向步骤 3 3 选择表 L 中的另外一个节点作为 A 回到步骤 在这个过程中有两点需要说明 第一 Moore 算法和 Dijkstra 算法的区别在于从 L 中选择节点 Moore 选择最前面的节点 也就是表中 最老 节点 Dijkstra 选择 与起点最近的节点 也就是选择 d 值最小的节点 L 这种方法需要额外的计算 但可 以保证每个路段只被检验一次 所以可以认为 Dijkstra 算法优于 Moore 算法 特别是 黑龙江工程学院本科生毕业设计 12 在大的网络中 全有全无分配法的基本步骤 1 确定各 OD 点对之间的最短路径 2 将各 OD 点对的出行量全部分配到相应的最短路径上 3 累加各路段上的出行分配量 得最后分配结果 2 4 2 阻抗可变单路径分配方法 全有全无分配方法认为出行时间与流量没有关系 即交通流量对阻抗没有影响 对于一些交通网络 由于路段上容量 通行能力 是有限的 路段上行驶的车辆越多 拥挤程度加大 车辆速度降低 从而行驶时间就会增加 这样一来 流量越大 阻抗 也越大 本小节我们来研究交通流量对阻抗存在影响时的交通分配问题 这类问题称 为 阻抗可变分配 问题 有两种分配方法 增量加载分配法 迭代加权法 1 增量加载分配法 将 OD 分布矩阵分成若干份 N 份 各份比重由大到小 具体比重值可以人为 任意确定 从大份开始 每次取一份进行全有全无分配 每次分配前根据前一次的分 配结果用走行时间公式修正各路段的阻抗值 算法如下 在本章中 要借用一个数学 符号 它表示 任意的 意思 步 1 初始化 将 OD 分布矩阵分解成若干份 N 份 令 k 1 路段 axa 0 0 步 2 计算各路段阻抗 axtt k aa k a 1 步 3 按全有全无分配法将各 OD 点对 i j 的第 k 份出行分布量分配到它们之 间的最短路径上 并累加各路段从该步分配新得到的交通量 设为 awk a 步 4 令 awxx k a k a k a 1 步 5 判定 k N 若是 停止计算 否则令 k k 1 返回到第 2 步 算法结束 从以上算法可以看出 全有全无分配法是增量分配法的基础 当 N 1 时 增量 分配法蜕化全有全无他配法 2 迭代加权法 每次都将全 OD 分布量按全有全无法分配到路网上去 得到的各路段上的分配量 叫 附加量 这一次分配所得附加量与原路段上的交通量的加权平均值作为新的路 段上的交通量 再由这个量计算出各路段的交通阻抗 作为下一次分配的依据 当前 黑龙江工程学院本科生毕业设计 13 后两次分配的结果近似相等时 停止迭代 具体算法如下 步 1 初始化 按照各路段的自由走行时间进行第一次全有全无分配 得各路段 的交通量 令 k 0 axa路段 0 0 步 2 令 k k 1 按当前路段上的交通量计算路段上的走行时间 axtt k aa k a 1 步 3 按新的走行时间再将全 OD 分布量用全有全无法作一次分配 得各路段的 附加交通量 af k a 步 4 加权平均计算各路段新的交通量 af k x k x k a k a k a 1 1 1 1 步 5 若 是预先确定的精度临界值 则停止计算 即为最 1k a k a xx axk a 终求得交通网络上个路段的分配量 否则返回到第 2 步 2 4 3 阻抗为常数的多路径分配方法 全有全无分配法假定出行者对这个交通网络的结构和各条路段的阻抗非常清楚 因此在假定阻抗为常数的前提下 每对 OD 点之间的出行者都同时选择该点对之间的 最短路径 但实际上 由于交通网络的复杂性和路段上交通状况的多变性 以及各个 出行者主观判断的多样性 某 OD 点对之间不同出行者所感知的最短路径将是不同的 随机的 因此这些出行者所选择的 最短路径 不一定是同一条 从而出现多路径选 择的现象 关于它的交通分配叫做 多路径分配 或 随机加载 首先 本小节研 究阻抗为常数的多路径分配方法 1 Logit 方法 设某 OD 点对 r s 之间每个出行者总是选择他认为阻抗最小的路径 k 称出行者 主观判断的阻抗值为 感知阻抗 Pr klCCP rs l rs k rs k 2 3 根据关于 效用 的定义 可以用路径的感知阻抗的负值来表示选择的效用 k rs k rs kk cCU 2 4 式中 Uk 路径 k 作为选择 的效用 阻抗越大 效用值越小 被选择的概率越 小 黑龙江工程学院本科生毕业设计 14 Ckrs 路径 k 的感知阻抗 ckrs 路径 k 的实际阻抗 k 随机变量 那么这就是一个多项选择中挑选效用最大的选择枝的问题了 当假定 k是独立服从 相同的 Gumbel 分布 此时可以用一个 表示所有的 k 时 选择概率 l rs l rs krs k bc bc P exp exp 2 5 式中 b 参数 与 的方差有关 可以证明 6 2 D b 称模型 2 5 为 Logit 模型 用这个模型求路径选择概率需要把点对 r s 间所以的路 径都找出来 这其实是个非常困难的工作 例如对一个含有 100 个节点的交通网络来 说 当 r 与 s 离的较远的时 就存在上千条路径 因此直接根据它设计算法是不切实 际的 1971 年 Dail 发明了一个算法 其特点有二 一是 假定出行者不是在起点 r 就决定选择哪条路径 而是在出行过程的每个节点都做一次关于下步选择哪条路段的 选择 即真正选择的不是 路径 而是 路段 二是 出行者在一个节点处选择路段 时 并不是以该节点为起点的每条路段都是被选择的对象 只有那些所谓的 有效路 段 才可能被选择到 有效路段的定义是 当路段 i j 的上游端点 i 比下游端点 j 离起 点 r 近 而且 i 比 j 离终点 s 远 则称该路段为有效路段 由有效路段组成的路径叫 有效路径 所幸的是 后人证明 Dail 算法计算出的结果正好与模型所描述的路径 选择概率完全相同 2 Dail 算法 Dail 算法的步骤如下 步 1 初始化 找有效路段和有效路径 1 计算从起点 r 到所有节点的最小阻抗 记之为 r i 计算从所有节点到讫点 s 的最小阻抗 记之为 s i 2 设 Oi为离开节点 i 的路段另一个端点的集合 I 为进入点 i 的路段的另一 个端点的集合 对每条路段 i j 计算 路段似然值 否则 且 若 0 exp jsisjrirjitirjrb jiL 黑龙江工程学院本科生毕业设计 15 2 6 式中 t i j 为路段 i j 的实际阻抗 r i s j 表示 i 比下游端点 j 离起 点 r 近 而且 i 比 j 离终点 s 远 其中 L i j 0 的 i j 是非有效路段 有效路径不 应该包含它们 L i j 0 的 i j 是有效路段 而所包含的所有路段的 L i j 1 的路径必 是最短路径 步 2 向前计算路段的权重 假定参数 b 1 0 从 r 点开始 按 r i 的上升顺序依次考虑每个节点 计算离开它的所有路段的权重 对节点 i 路段 i j 的权重为 i Im Oj imWjiL rijiL jiW i 否则 若 2 7 当 i s 时 停止计算 步 3 向后计算路段流量 从 s 点开始 按 s j 的上升顺序依次考虑每个节点 j 计算进入它的所有路段的流量 对路段 i j 它的流量为 j Im Om Im rs Ii jmW jiW mjx sj jmW jiW q jix j j j 否则 若 2 8 当 j r 时 停止计算 可以证明 以上算法产生的流量与 Logit 模型 2 5 的配流的结果完全一致 即 Dail 算法与 Logit 模型是等价的 3 改进的模型和算法 将 Logit 模型改为 王炜 1992 m i LiLb LkLb ksrP 1 exp exp 2 9 在改进的模型中 参数 b 无量纲 与感知阻抗无关 仅与可供选择的路径数有关 通 过模拟发现 它的变化范围相当稳定 在 3 00 4 00 之间 对于一般的城市道路网 黑龙江工程学院本科生毕业设计 16 b 在 3 00 3 50 之间 一般我们建议取 b 3 3 为了减少 Dail 算法的计算量 可以降低有效路段的评定标准 仍设 从起点 r 到任意节点 i 的最小阻抗为 r i 从任意节点 j 到讫点的最小阻抗为 s i 有效路段重 新定义为 如果 s i s j 即只要路段 i j 使出行者更靠近终点 至少不更远离终点 路段 i j 就定义为有效路段 上面新的有效路段的定义不包含从起点 r 到任意节点 i 的最小阻抗 r i 这就节 省了计算时间 算法算法 步 1 初始化 找出有效路段和有效路径 1 计算各节点到终点 s 的最小阻抗 2 从起点出发 判别各个节点下游的有效路段 并计算经该路段的最小阻抗 否则 若 0 jsisjsjid sjiL 2 10 式中 s i s j 是有效路段的判别式 计算大于 0 的 L i j s 设共有 J 个 的平均值 0 1 sjiL sjiL J siL 2 11 3 计算各有效路段的似然值 取 b 3 3 否则 若 0 exp jsissiLsjibL jiL 2 12 步 2 向前计算路段的权重 从 r 点开始 按 s i 的下降顺序依次考虑每个节点 计算离开它的所有路段的权 重 对节点 i 它的权重为 i Im Oj imWjiL rijiL jiW i 否则 若 2 13 当 i s 时 停止计算 黑龙江工程学院本科生毕业设计 17 步 3 向前计算路段流量 从 r 点开始 按 s i 的下降顺序依次考虑每个节点 i 计算进入它的所有路段的流 量 对路段 i j 进入它的流量为 i Om Il Om rs Oj miW jiW ilx ri miW jiW q jix i i i 否则 若 2 14 当 i s 时 停止计算 算法结束 用此改进的算法算得的交通网络上各个路段的流量与原有算法相比 路段上的流 量有较大的差别 关键是新算法扩展了有效路径 在所有的条路径上都安排了流量 改进的算法的优点是节省计算时间 尤其对大型交通网络 到目前为止 尚未发现任 何理由和经验证据 说明原有的 Dail 算法的配流结果就一定优于上面改进的算法的 配流结果 因此建议用改进的 Dail 算法 2 4 4 阻抗可变的多路径分配方法 前面所研究的无容量限制多路径分配方法是假设路段实际阻抗为一个常数 没有 考虑路段阻抗与流量的关系 现在我们研究在考虑路段上的流量对路段实际阻抗存在 影响的情况下的多路径分配方法 即阻抗可变的多路径分配方法 这将会使分配结果 更加接近实际情况 与阻抗可变单路径分配方法一样 增量加载和迭代加权两种方法 它们都是建立 在阻抗不变的多路径分配方法的基础上的 这里只介绍多路径 迭代加权方法 步 1 初始化 基于零流量的初始阻抗 执行一次 阻抗不变 随 0 0 aa tta 机加载 产生路段流量 并令 k 1 1 a xa 步 2 更新各路段的阻抗 令 kk aaa ttxa 步 3 在新的阻抗的基础上 调用算法执行一次流量随机加载 得到新的路段流 量 k a ya 步 4 令 1 11 1 kkk aaa xxya kk 步 5 判别收敛条件 如果 黑龙江工程学院本科生毕业设计 18 12 kk aa a k a a xx x 是预先确定的精度临界值 则停止 为之所求 否则 令 k k 1 返回第二步 1 k a xa 算法结束 说明 在第 4 步中 k l l a k a k a k a k a k a k a k a k a k a y k yy k x k k y k y k x k k k k y k x k x 1 11 111 112 1 1 1 1 211 1 1 可见 是前面产生的 k 个的平均值 故又称此分配方法为 相继平均算法 1 k a x l a y 2 5 本章小结 本章主要介绍了交通分配的基本概念及理论方法 重点介绍了全有全无分配法 阻抗为常数的多路径分配方法 Logit 模型和 Dail 算法 阻抗可变的单路径增量加载分 配方法 为以后的编程打下基础 黑龙江工程学院本科生毕业设计 19 黑龙江工程学院本科生毕业设计 20 第 3 章 数据库的建立与调用 3 1 Access 数据库介绍 3 1 1 概括 在办公软件 Office 套件中 最为广大用户熟悉的是 Word 和 Excel 因为它们功 能强大且方便易用 更因为它们不仅可用于办公 还可用于个人写作和家庭记帐理财 等 同为 Office 套件中一部分的 Access 虽然有着同样强大的功能 但使用的人却 相对少些 不像 Word 和 Excel 那样广泛 事实上 真正用过 Access 的用户 对其强 大功能和灵活应用均称赞 数据库是有结构的数据集合 它与一般的数据文件不同 其中的数据是无结构 的 是一串文字或数字流 数据库中的数据可以是文字 图象 声音等 Microsoft Access 是一种关系式数据库 关系式数据库由一系列表组成 表又由 一系列行和列组成 每一行是一个记录 每一列是一个字段 每个字段有一个字段名 字段名在一个表中不能重复 表与表之间可以建立关系 或称关联 连接 以便查 询相关联的信息 Access 数据库以文件形式保存 文件的扩展名是 DB 3 1 2 Access 的六种对象 Access 数据库由六种对象组成 它们是表 查询 窗体 报表 宏和模块 1 表 Table 表是数据库的基本对象 是创建其他 5 种对象的基础 表由记 录组成 记录由字段组成 表用来存贮数据库的数据 故又称数据表 2 查询 Query 查询可以按索引快速查找到需要的记录 按要求筛选记录并 能连接若干个表的字段组成新表 3 窗体 Form 窗体提供了一种方便的浏览 输入及更改数据的窗口 还可 以创建子窗体显示相关联的表的内容 窗体也称表单 4 报表 Report 报表的功能是将数据库中的数据分类汇总 然后打印出来 以便分析 5 宏 Macro 宏相当于 DOS 中的批处理 用来自动执行一系列操作 Access 列出了一些常用的操作供用户选择 使用起来十分方便 6 模块 Module 模块的功能与宏类似 但它定义的操作比宏更精细和复杂 用户可以根据自己的需要编写程序 模块使用 Visual Basic 编程 黑龙江工程学院本科生毕业设计 21 3 2 选择 Access 的理由 Access 是桌面型关系数据库 只适合数据量少的应用 在处理少量数据和单机访 问的数据库时是很好的 效率也很高 但是它的同时访问客户端