基于四维消耗的公交线网优化模型及蚁群算法.pdf

第 38卷第 2期 2008年 3月 东 南 大学 学 报 自 然 科 学 版 J OURNAL O F SOUTHEAST UN I V ERSI TY Natural Science Edition Vol 38 No 2 M ar 2008 基于四维消耗的公交线网优化模型及蚁群算法 胡启洲 1 邓 卫 1 田新现 2 1 东南大学交通学院 南京 210096 2 平顶山教育学院 平顶山 467000 摘要 针对城市公交线网的优化问题 应用四维消耗概念进行了综合研究 给出了公交线网优化 的多目标线性规划模型及蚁群算法 在定义时间 空间 环境 能源等四维消耗概念的基础上 从 点 线 面 3个方面对公交线网优化问题进行研究 在考虑效益最大化 成本最小化 发展可持续 化的情况下 利用效用函数建立了公交线网优化的多目标线性规划模型 并用蚁群算法对多目标 线性规划模型求解 得到最佳的公交线路网络布局结构和公交线网运营效率 实例表明 利用蚁 群算法优化后公交线网利用率增大 可达性良好 乘客出行时间减少 优化结果符合城市交通的 实际情况 该方法合理可行 关键词 交通工程 线网优化 蚁群算法 四维消耗 中图分类号 U491 13 文献标识码 A 文章编号 1001 0505 2008 02 0304 05 Opti mization model of public traffic network and ant algorithm with four di mensions consumption Hu Q izhou1 Deng W ei 1 T iam X inxian2 1Schoo l of Transportation SoutheastUniversity N anjing 210096 China 2Pingding shan Education Co llege Pingdingshan 467000 China Abstract A i m ed at the opti m ization problem for public traffic line net w ork a new method and al gorith m of public traffic line network opti m ization ispresented using the concept of four di m ensions consumption Based on the definition of four di mensions consumption concep tincluding ti me space environment and energy constraint conditions and objective function are analyzed on three facets po ints lines and range Taking the benefitsm ax i m ization and costsm ini m ization and sus tainable developm ent as the objectives a network opti m izationmodel isdeveloped A multi objective linear programm ing m odel of public transportation opti m ization is established Ant algorithm is used to plan the public transport network The best layout structure of public traffic line net w ork and the best operational efficiency of public traffic system can then be achieved The application results show that the multi objective linear programm ing m odel not only m eets the transport demands but also i mple m ents the environment protection objective and i mproves the utilization ratio of urban public traffic line network The opti m ization results accord w ith the real situation The method is feasible Key words public traffic line net w ork opti m ization ant algorithm four di mensions consumption 收稿日期 2007 07 10 作者简介 胡启洲 1975 男 博士生 邓卫 联系人 男 博士 教授 博士生导师 dengwei seu edu cn 基金项目 十一五 国家科技支撑计划资助项目 2006BA J18B03 引文格式 胡启洲 邓卫 田新现 基于四维消耗的公交线网优化模型及蚁群算法 J 东南大学学报 自然科学版 2008 38 2 304 308 对于城市公交线网优化问题的研究主要分成 两类 一类是单纯的理论研究 即以单纯的定量模 型解决公交线网优化问题 1 3 另一类是以定性为 主兼顾定量 在线网优化过程中一部分由定量模型 决定 4 7 由于城市公交系统是一个复杂的 多因素 多目标和多功能的随机动态大系统 所以公交线网 优化模型是整个线网优化的基础 模型的好坏直接 影响优化的效果 作为一个好的优化模型应清晰 简洁 易于实施 对于规模较大 布局复杂多样的公 交线网优化问题 可行方案数较多 传统的优化算 法不易得到满意的近似解 1 7 本文根据目前城市 交通发展特点 在定义公交线网优化的三大要素 点 线 面的基础上 考虑公交线网优化的时间 空 间 环境 能源四维消耗情况下 建立了公交线网优 化模型 并用蚁群算法对优化模型进行了求解研 究 1 公交线网优化的要素分析 1 1 公交线网优化的原则 公交线网是城市公交客流的主要承担者 合理 的公交线网布局 可以充分发挥公共交通的优势 提高运营效率 改善服务水平 缓解公交紧张状况 方便居民出行 减轻城市道路系统的交通压力 发 挥有限城市用地的最大效能 所以公交线网优化应 该遵循如下原则 最小交通需求 通过科学的城 市布局和线网规划 使得维持城市与社会的运作和 发展所需的交通量最小 8 最佳服务水平 城市 公交系统能够使各种交通需求得到最大限度的满 足 整个公交系统以安全 准点 运量大 运效高的 方式运行 最小能源占用 城市单位产值的交通 能耗最低 城市公交系统的建设 维护 使用和管理 对占土地 人力资源等占用最低 8 最小环境影 响 城市公交对人的生存环境和活动的影响和干扰 最小 8 1 2 公交线网优化的三大要素 随着城市化进程的推进 城市规模进一步扩 大 为了促进城市功能的正常发挥 提高城市活动 运转效率 促进城市之间结构的合理调整 必须加 强公交系统连通这些城市功能分区 使城市各个重 要节点之间的空间距离从时间上加以缩短 各个重 要节点建立便捷的联系 9 在对城市结构空间认 识分析的基础上 提出了公交线网优化的三大要素 点 线 面 并给出相应的检验指标 定义 1 公交线网优化的点是指城市空间结 构布局中的重要节点 要求公交线路必须经过 是 城市中所有重要活动实现的 场所 如居民小区 车站等 点 要满足居民出行要求 在一定的服务 水平要求下 客运量大的区域 要求布置的公交线 网客运能力较大 检验指标 线网日均满载率 即 f1 qo i i 1 k为第 k条线路的节点 i至 i 1路段车 容量 Li i 1 k为第 k条线路的节点 i至 i 1路段客 流量间距离 N为公交线路数 n为通行公交车辆的 道路网结点数 定义 2 公交线网优化的线是指城市交通系 统中的公交线路 在满足乘客需要和城市发展的基 础上 线 是主要客流走最短路径到达目的地 走 廊 对公交线网而言 线 要与主要客流方向一 致 组织客流直达运输 使得客流直达率高 道路网 是公共交通网络的基础 但并非所有的道路都适合 公交车辆行驶 所以要考虑道路几何线形 路面条 件和容量限制等因素 1 检验指标 乘客直达率 即 f2 Dij 为交通小区 i至交通小区 j间的O D量 n为通行公 交车辆的道路网结点数 m 为交通小区总数 定义 3 公交线网优化的面是指整个城市公 交线路网络系统 在考虑城市交通发展的情况下 面 与城市交通总体规划相匹配 引导城市交通 空间向合理方向发展 在有效利用公交资源 优化 城市结构 提高城市土地利用效率的情况下 应该 特别考虑线网 面 效益因素 检验指标 线网效 率 即 f3 i j k 为经过节点 i至节点 j的客运需求量在路线 k上的 分配的比例 lk为线路 k的长度 1 3 公交线网优化的四维消耗 公交线网优化目标可归结为公交效率最大化 而公交效率则是在一定的公交投入与该投入产生 的对公交需求满足程度之间的对比关系 能够影响 公交投入和需求满足程度的相关因素很多 本文从 乘客利益 企业效益以及社会环境的角度出发 运 用系统科学的思想 提出公交线网优化的四维消耗 概念 公交线网优化的四维消耗是指基于时间 空 间 环境 能源四维下的公交系统消耗 具体如下 定义 4 公交线网优化的时间消耗是指乘客 总的出行时间消耗 是公交线网优化中社会整体效 305第 2期胡启洲 等 基于四维消耗的公交线网优化模型及蚁群算法 益最显著的目标 反映出合理公交线网应尽量节约 乘客出行时间 保证较低的换乘率 尽量提高公交 出行的直达率 检验指标 乘客总出行时间 即 f4 T1 T2 T3 T4 T5 4 式中 T1为每位乘客从出行点到相应车站的平均 步行时间且 T1 Lo V Lo为乘客从出行点到相应 车站的最短距离 V 为乘客步行的平均速度 T2为 从出行点到相应车站后的平均候车时间且 T2 0 5 0 5为修正值 为平均发车间隔时 间 为平均留站率 可取经验常数 建议 5 m in 5 T3为中转换乘的平均时间且 T3 0 5 T0 T0为从下车站到上车站的中转时 间 T4为车辆行使的平均时间且T4 Lij VL VL为 车辆平均旅行速度 Lij为第 i区形心节点到第 j区 形心节点公交线的长度 T5为下车后乘客步行到 达目的地的平均时间且 T5 Ld V Ld为乘客从车 站下车后步行目的地的最短距离 定义 6 公交线网优化的空间消耗是指公交 系统在空间的物质消耗 即公交系统总投入 包括 公交运营费用和公交建设费用 作为公交部门 一 方面是社会服务 另一方面也是为了寻求企业的经 济利益 就是在给定的出行量下 使得运输成本最 小 检验指标 公交系统总投入 即 f5 Nk为 第 k条线路的发车数 Mk为第 k条线路的车公里成 本 Ck为第 k条线路的单位建设费用 Lk为第 k条 线路的长度 定义 6 公交线网优化的环境消耗是指城市 公交对环境的影响 主要指城市公交产生的污染 物 公交污染物排放量反映了公交系统的环境负效 应 在满足一定的公共交通需求的前提下 污染物 排放量越少 公交效率越高 4 检验指标 污染物 排放量 即 f6 li i 1 k为第 k条线路的节点 i 至 i 1路段的长度 vjk 为第k条线路上的车速 vk行使情况下第 j种 污染物的实际排放质量浓度 o vjk 为第 k条线 路上的车速 vk行使情况下第 j种污染物的排放标 准质量浓度 定义 7 公交线网优化的能源消耗是指城市 公交对能源的消耗情况 能源消耗量反映的公交的 能源投入 在满足一定的交通需求前提下 能源消 耗量越少 公交效率越高 4 检验指标 公交能源 消耗 即 f7 q i k为公交 路网中第 k条线路上第 i 种公交车型的交通流量 v i k为公交路网中第 k条线路上第 i种公交车型的行 驶速度 i v i k 为公交路网中第 k条线路上第 i种 公交车型以 v i k速度行驶时的能源消耗因子 z为整 个城市行驶公交车的车型数 2 数学模型与算法 2 1 优化模型的建立 为了突出公交线网优化模型的合理性和可实 现性 在建立线网优化模型时 应结合城市的用地 规模 用地布局 人口规模 经济发展状况以及当地 的风土人情 选取适当的约束条件和目标函数 本 文将点 线 面的 3个检验指标作为约束条件 时 间 空间 环境 能源四维下的城市公交系统消耗作 为目标函数 运用系统科学的思想 建立公交线网 优化的数学模型 由式 1 3 可知点 线 面的 3个检验指 标的函数值越大越符合需求 由式 4 7 可知 时间 空间 环境 能源四维下的城市公交系统消耗 越小越能满足目标函数要求 所以为了消除不同指 标量纲的差异 利用经济转化系数 将目标函数都 转化为同一单位考察 则 1 基于时间 空间 环境 能源四维消耗最小 的数学模型为 m in F1 m in 1f4 2f5 3f6 4f7 8 式中 1 2 3 4为经济转化系数 采用层次分 析法或五级权重法来确定 2 基于点 线 面的检验指标最大的数学模型 为 m axF2 m ax 1f1 2f2 3f3 9 式中 1 2 3为经济转化系数 采用层次分析法 或五级权重法来确定 为了使公交线网优化问题简单化 并利于用蚁 群算法进行求解计算 将多目标规划问题转化为单 目标规划问题来处理 处理后的公交线网优化模型 为 m in 1f4 2f5 3f6 4f7 1f1 2f2 3f3 306东南大学学报 自然科学版 第 38卷 10 2 2 蚁群算法 2 2 1 蚁群算法原理 依照 逐条布线 优化成网 的布线原则 结 合蚁群算法的基本原理 在每个现有公交起 终 点上放置一个人工蚂蚁 根据 味道 和 信息素 确定出蚂蚁从该公交站点到其相邻公交站点的转 移概率 并取转移概率最大值运动到下一个公交 站点 依次类推 直至所有蚂蚁因线路长度或退化 而不再向前运动为止 10 11 2 2 2 公交线网优化的算法步骤 公交线网优化的算法如下 1 定义解的适应度函数 F A F1 F2 式中 A 为一个正数 可以保证个体适应值为正 F1 为目标函数 为约束条件 F2的惩罚函数 初值为 1 在算法演化中 若约束条件被违反 则逐步增大 惩罚函数 以保证约束条件得到满足 2 编码及初始化 对可行线路集中的每条线路用 0或 1随机选取 可构成一个初始公交线网 随机产生m 个初始解 计算这m 个初始解的适应度 由这m 个初始解得到 各个分量值的候选组 并根据候选组中的值按其所 在解的适应度计算其信息量 3 迭代过程 W hile not结束条件 do for i 1 to n do 对 n个分量循环 Fork 1 tom do 对m 个蚂蚁循环 根据概率 p k ij 在第 i个分量候选组里选择第 k 个蚂蚁在该分量的初值 end fork 对所选择的第 i个分量的m 个初值 实行交 叉 变异操作 生成第 i个分量的新一代的m 个值 并加入候选组 end w hile 根据所选择的分量构成 m 个新一代解 并计算新一代解的适应度值 修改各分量候选组中各候选值的信息量 选取第 i个分量的候选组中第 j个值的概率 p k ij ij t Fk为第 k 只蚂蚁所对应的解的 适应度 按式 12 和 13 相应地更新各个分量的候 选组中的信息量 ij t 取各分量的候选组中信息量较高的m 个值 作为新的候选组 end w hile 4 停止准则 循环执行适应值实行交叉 变异操作 直到满 足某个停止准则 停止准则一般为找到一个能接受 的解或已迭代了预置的代数 在线网优化中一般设 置最大迭代次数 5 线网输出 对优化线网输出 通过评价检验其合理性与正 确性 3 应用分析 到 2005年 6月 银川市已开通线路 48条 线 路总长度 545 7 k m 年客运量 7 000万人次 占公 共汽车客运量的 66 7 主要承担中心城区的公 共交通客运任务 拥有公交车辆 931辆 折合 737 标台 万人拥有公交车辆 9 2标台 城市公交已经 形成一定的规模 成为基本覆盖全市的公交线 网 12 以银川市的现状公交网络为例 利用基于四 维消耗的优化模型对其进行优化调整 依据公交客流分布情况 现有公交网络的特点 以及市区的城市结构 在考虑城市发展的基础上 选取合适的优化控制参数 建立公交线网优化模型 m in 0 25f4 0 25f5 0 25f6 0 25f7 0 33f1 0 33f2 0 33f3 14 取 n 500 得到公交线路网络优化调整的最 优解 见表 1 表 1 优化目标考察值 优化函数f1 f2 f3 f4 m inf5 万元f6 f7 调整前58 776 362 338650 333 463 8 调整后67 381 367 532582 921 358 7 307第 2期胡启洲 等 基于四维消耗的公交线网优化模型及蚁群算法 由表 1可以看出 从社会效益来看 不仅乘 客的总出行时间减少了 6m in 步行时间也减少了 而且乘客直达率提高了 5 0 在市区公交线路总 长度不变的情况下 将路线重复过多的部分取消 用之补开居民乘行急需的空白路段 使线网分布合 理化 线网效率提高 5 2 从而较大程度方便居 民出行 从经济利益看 由于线网调整后补开了 服务区内道路网的空白区段 在限制交通需求的基 础上 减少了乘客出行时间 所以调整后 线网日均 满载率提高 8 6 公交企业投入减少 67 4万元 从可持续发展和环境保护角度看 线网调整后 污染物的排放了减少 12 1 能源消耗减少 5 1 所以在节约能源 减少污染 保护环境的基础上 充 分发挥公交系统自身运能 促进城市交通的可持续 发展 4 结论 1 公交系统是一个复杂的 多因素多目标和 多功能的随机动态系统 优化目标函数多 约束条 件也多 因此很难有一种较好的通用优化方法 本 文从点 线 面三个角度出发 考虑乘客利益 公交 企业效益 能源消耗以及环境影响等因素的情况 下 建立了公交线网优化的数学模型 该模型利用 经济转化系数 将多目标非线性优化问题转化为线 性优化问题 易于求解计算 具有广泛的代表性和 较高的实用价值 2 通过蚁群算法 对模型进行求解的基础上 对模型进行了实际应用分析 结果表明通过点 线 面的限制 不但提高了算法的可靠性和计算精度 而且使可行线网数量减少 在优化阶段消除了不必 要的计算 得到的公交线网更加合理科学 参考文献 References 1 王炜 杨新苗 陈学武 城市公共交通系统规划方法与 管理技术 M 北京 科学出版社 2002 2 W angW e i W ang Fu m in Scheme design technique for urban traffic manage ment planning J Journa l of Southeast University English Edition 2005 21 3 353 358 3 JinW enlong A dynam ical system m odel of the traffic assignm ent proble m J Transportation Research Part B 2007 41 1 32 48 4 吴世江 史其信 陆化普 基于交通效率的城市公共交 通路网布局模型 J 土木工程学报 2005 38 1 117 120 W u Shijiang Sh