城市道路网络设计的数学模型及其解法.pdf

第 18 卷 第 1 期 1997 年 3 月 大 连 铁 道 学 院 学 报 JOURNAL OF DALIAN RAILWAY INST ITU TE Vol 18 No 1 Mar 1997 城市道路网络设计的数学模型及其解法 王志栋 机车车辆系 摘 要 讨论了城市路网优化设计的通用模型 以及在离散变量和连续变量两种特殊情况下的 路网设计模型 并分析了模型的解法 关键词 市区交通 交通网络 数学模型 中图分类号 U121 收稿日期 1995 10 09 铁道部科技发展计划项目 王志栋 男 1967 年生 讲师 硕士 大连 大连铁道学院机车车辆系 116028 为解决城市交通紧张问题 国内许多大城市自 80 年代已开始着手制定城市交通总体规 划 道路网络设计在城市交通总体规划中占有重要地位 但是我国在这一领域的研究尚未 形成较成熟完整的理论 许多城市在进行网络规划时 往往是根据交通需求及交通流量在 路网上分布情况的预测 结合城市实际情况 制定路网设计方案 在这一过程中 缺少对 路网优化设计进行定量分析的数学模型 本文参考国外的研究成果 探讨一般情况下网络 设计的数学描述模型和在离散 连续设计变量两种特殊情况下 路网设计的数学模型及其 解法 1 路网设计的通用模型 城市道路网络优化设计的目的就是寻求在能够满足交通需求的前提下 用最少的投资 指修建或改造道路所需投入的费用 以下称设计费用 最大程度地降低交通费用的最佳 网络设计方案 设城市路网可用一个有向图 N A 表示 N 表示节点集 A 为弧集 X 为路网上各 种交通类型的集合 交通类型指车 行人 货物等 Rk为第 k 类交通类型从它的起点 O 点 到终点 D 点 的需求 f k a为第k 类型交通体在弧 a i j 上的流量 ya为弧 a 的 容量比 kaya为弧a 的交通容量 ya的取值将决定是否需要新建或改造该路段 称 ya为设 计变量 其取值范围用Ya表示 用 y ya f f a 分别表示设计变量和流量变量集 则一般网络设计可用如下模型来描述 min U f y 1 1 s t 2 j Nf k ij 2 L Nf k Li Rk 如 i O k Rk 如 i D k 0 其它 1 2 1 f a 2 k Xf k a ka Ya a i j A 1 3 f y S 1 4 f k a 0 ya Ya a A k X 1 5 1 式 1 1 为目标函数 式 1 2 为流量约束 它表明整个路网的流量守恒 即当节点为起点时 流出量为需求量 Rk 流入量为 O 当节点为终点时 流入量为需求量 流出量为 O 当节 点为中间节点时 流入量等于流出量 式 1 3 为路段 弧 a i j 容量约束 表明 该路段的流量不能超过其交通容量 式 1 4 流量和设计变量的一些其它限制 如资金 资源等方面的限制 称为 边缘约束 2 离散设计变量的路网设计模型 在有些情况下 如决定是否新建道路时 设计变量 ya只能取固定值 0 或 1 即 ya 0 1 当ya 0 时表明不需要新建道路 当 ya 1时表明需要新建道路 此时上述路网设 计的通用模型转变成离散设计变量的路网设计模型 对式 1 1 中的目标函数U f y 可 以看成由两部分组成 第一部分为交通费用 它是流量 f 和设计变量 y 的函数 用 c f y 表示 第二部分为新建或改造道路所需的费用 即设计费用 它仅是路段容量的函数 用 F y 表示 则目标函数可写成 U f y c f y F y 2 若交通费用 c f y 为流量的线性函数 设计费用为设计变量的线性函数 则目标函 数为如下的线性函数 U f y 2 k X 2 a AC k af k a 2 a AFaya 3 式中 C k a为第 k 类交通体单位流量通过弧 a 的费用 Fa为路段构造费用 将式 3 所示的目标函数和设计变量的离散约束 ya 0 1 代入路网设计通用模型 即式 1 得到离散设计变量路网设计的线性模型 min 2 k X 2 a AC k af k a 2 a AFay a 4 1 s t 2 j Nf k ij 2 L Nf k Li Rk 如 i O k Rk 如 i D k 0 其它 4 2 f k a kaYa a i j A k X 4 3 f k a 0 a i j A k X 4 4 ya 0 1 a i j A 4 5 f y S 4 式 4 为混合整数规划问题 可以采用分枝定界法求解 下面仅讨论当无容量限制约 束 即路段交通容量为无穷大 而且路段设计费用为 0 时 采和分枝定界法确定目标函数 65 第 1 期王志栋 城市道路网络设计的数学模型及其解法 下界的方法 由于目标函数中设计费用为0 且无容量限制 对于任意的路网状况 最优解为每一OD 点对的最短路 此时目标函数完全由路网形状决定 当设计变量ya在约束 0 1 中确定 后 路网形状即确定下来 目标函数也随之确定 用A P 表示在弧集 A 中尚未确定是否需要 构造的那部分弧 现在就是要确定在满足约束条件下 构造哪些弧使目标函数达到最优 假 设 A P 中的所有弧全部构造 由于没有设计费用 此时最小费用为最大程度的最短路费用 即为 U yP yP为所有 A P 中的弧全部构造时的一个解 此时目标函数的下界为 U y U y P 5 但是由于受约束条件的限制 不可能构造所有的弧 必须从A P 中消去一些弧 此时最短路 费用增加 则分枝定界的下界为 U y U y P 2 a APy PI a y P 6 式中 y a 1 y a I a y P 记为当弧a i j 从 y P 定义的路网中去掉时 从节点 i 到节 点 j 最短路费用的增长 分枝定界法实际上是一种枚举法 就是根据枚举定界的所有可行解中搜索最优解 从 上面可以看出 对于大型路网的设计问题 离散设计变量模型求解的计算量非常大 难以 求解 采用分枝定界法只能求解小型路网设计问题 3 连续设计变量的路网设计模型 上面讨论的是离散设计变量的路网设计模型 在许多情况下 设计变量不是离散的 而 是在某一区间内连续变化的 如道路改良 交通控制及公交路网优化等 这些问题归结为 连续设计变量的网络设计问题 设目标函数 U f y 取式 2 的形式 设计变量的变化 区间Ya取 0 则路网设计模型可写成 min 2 a ACa f a ya 2 a AF a ya a i j A 7 1 s t 2 j Nf k ij 2 L Nf k Li Rk i O k Rk i D k 0 其它 7 2 fa 2 k Xf k a 7 3 f k a 0 7 4 ya Ya 0 a i j A 7 5 7 采用Steenbeink 提出的近似解法 可将上面模型改写成 min f F 2 a A min Ca f a ya Fa ya a i j A 8 式中 f fa 是弧流量 F 是所有满足约束的可行流量 f 的集合 令 Ha fa min yn Yn Ca f a ya Fa ya 9 则路网设计模型为 66 大 连 铁 道 学 院 学 报第 18卷 min 2 a AH a fa 10 1 s t 2 j Nf k ij 2 L Nf k Li Rk i O k Rk i D k 0 其它 10 2 fa 2 k Xf k a a i j A 10 3 f k a 0 a i j A 10 4 10 或写成 min f F 2 a AH a fa a i j A 11 式 10 11 实际上是一个多种交通类型下的交通流问题 对每条弧选取最佳流量 fa 使 目标函数最小 然后根据流量求解最优设计变量 ya 然而对于一个固定的路网 交通流量在路段中的分配不一定能使整个系统的费用 即 上述模型中的目标函数 最小 假设交通流分配满足平衡分配模型 则目标函数中的交通 费用C f y 应满足如下约束 Ca fa ya f a 0 Ca x ya dx fa ya 0 0 fa 0 fa 0 fa 0 1 将交通分配的平衡模型与上述路网设计模型结合 可得到求解路网设计模型的启发式 算法 其步骤为 第一步 给出一个满足可行条件的初始流量 f f a a i j A 第二步 将初始可行流量代入路网设计模型 求解在该流量下的最优设计变量 f f a 第三步 取设计变量为 y 按平衡模型进行交通流量分配 得到各弧 路段 上的一组 新的流量 记为 f y 用 f y 代替初始可行流量 f 返回第二步 直到第 n 次迭代得 到的流量 fn y 与第n 1 次迭代得到的流量fn 1 y 的差 f n y f n 1 y E 停 止迭代 E为迭代精度 4 结 论 1 城市路网优化设计可以归结为一个数学规划问题 2 离散设计变量的路网设计模型 可转换成一个混合整数规划问题 对于大型路网设 计 由于维数较高 模型难以求解 求解大型路网设计问题的有效算法 尚需进一步研究 3 连续设计变量的路网设计模型可与交通分配平衡模型结合 采用启发式算法求其近 似解 4 城市路网规划设计还涉及到城市的许多实际情况 因此在实际应用中应采用理论分 析与实际情况相结合的方法 制定合理的城市路网优化设计方案 67 第 1 期王志栋 城市道路网络设计的数学模型及其解法 参考文献 1 Fwkushima M A modified Frank Wolfe algorithm for solving the traffic assingment problem Transpn Res B 1984 18B 2 2 Benchman M On the dual approach to the traffic assingment problem Transpn Res B 1984 18B 3 3 任福田等 交通工程学导论 北京 人民交通出版社 1987 4 王炜 徐启谦 城市交通规划理论与方法 北京 人民交通出版社 1992 The Maths Model of Urban Road Network Design and the Solution Wang Zhidong Dept ofLocomotive and Railway Car Abstract Discusses the general model of optimum design about city road network and the design model of road network in the two extra cases discrete variable and continuous variable and analyses the solution