考虑客流时变特性的列车时刻表优化方法.pdf

第 卷第 期运 筹 与 管 理 ，年 月 收稿日期：作者简介：张矢宇（），女，湖北武汉人，副教授，博士，研究方向：交通运输规划与管理。考虑客流时变特性的列车时刻表优化方法张矢宇，杨云超，杨宇昊（武汉理工大学 交通学院，湖北 武汉 ；河南省交通规划设计研究院股份有限公司，河南 郑州 ）摘要：针对列车时刻表优化问题，考虑客流的时变特性，提出了一个列车运行优化方法。以列车出发时间为变量，以车站容量、列车容量、出发间隔、首末班车出发时间和备用车辆的数量为约束条件，以乘客和运营单位的最小总成本为优化目标，构建了城市轨道交通列车时刻表的优化模型。根据模型的特点，设计了基于仿真的两步遗传算法。以武汉地铁一号线为例，对列车的运行时刻表进行优化，验证了模型和算法的有效性。研究结果表明，设计的算法收敛性强，求解效率高；“小而高密度”列车运行计划可以平衡乘客和运营单位的利益，较小的平台容量严重限制了城市轨道交通的服务水平，导致运营成本增加，车站容量越小，运营成本和乘客等候的成本越高。关键词：城市交通；遗传算法；时刻表；客流；时变特性中图分类号：文章标识码：文章编号：（）：，（，；，）：，；，（，），“”，（，），：；引言近年来，城市轨道交通凭借其容量大、速度快、消耗低和绿色环保的特点迅速成为解决大城市拥堵问题的优先考虑对象。客流是交通运输能力和运输系统合理配置、制定运营计划的重要因素。城市轨道交通中的乘客流量明显存在时间和空间不平衡，沿线各车站的入站和出站车站的乘客流量差异很大。目前国内外城市轨道交通的出发间隔一般根据每小时的 客流量或每小时最大客流量确定，运行方式为均衡运行方式。同等间隔的平衡列车模式易于管理，广泛用于控制国有和城际列车的运行，但对于城市地铁，这种调度模式可在高峰时段使用，队列中的等待时间太长，非高峰容量被浪费，并且每列的载客率不平衡，将不可避免地导致运营成本增加或服务水平下降，阻碍了城市轨道交通服务水平的提高。研究表明利用实际动态客流信息、科学建模方法和优化算法来解决城市轨道交通中的时间表优化问题是十分关键的。国内外对于轨道交通时间表优化的研究成果较为丰富，研究成果较多。随着动态客流信息可获取性越来越强，使用动态客流信息进行时刻表优化，能为乘客提供更好的旅行服务 。曹亮 构建了基于客流需求的旅客列车时刻表优化模型；许得杰等 构建了考虑客流时变需求的大小交路列车时刻表优化模型；等 构建了考虑乘客出发时间的时刻表优化模型；祁奇 构建了基于动态客流的城轨列车时刻表优化模型。对现有单线时间表优化的研究考虑了动态客流特征，主要是通过优化时间表来减少乘客等待时间 ，缺乏对更灵活的停车模式的研究。综上所述，对时间表的优化研究不单单要考虑客流的时间不平衡，同时也要考虑其空间不平衡，即考虑客流的时空不平衡性。基于以上成果，本文分析了城市轨道交通客运需求的时变特征，给出了一种基于客运效率计算客运成本的方法；建立了城市轨道交通列车时刻表的优化模型，并设计了一种基于仿真的两阶段遗传算法求解该模型；以武汉地铁一号线为例进行实证分析，验证了模型和算法的有效性。考虑客流时空特性的列车时刻表优化模型 问题描述（）研究对象如图 所示，城市轨道线路共有 个站点，列车出发方向记为 ，返回方向记 。所有列车从出发站出发，到终点站后返回，休整后进入等待下一次出发的空闲车道。图 城市轨道交通线路示意图（）研究时段为了更好地解释乘客的乘车过程，将为不同的车站分配不同的研究时段，具体见图 。每个站的第 期张矢宇，等：考虑客流时变特性的列车时刻表优化方法研究时段如下：车站：（），（）：，：车站：（），（）：，：车站：（），（）：，：车站：（），（）：，：整个研究时段为 ，表示开始时间，即图中的 ，表示结束时间，即图 中的 。为了便于建模，将 ，离散化为一系列相等长度的时间段，可以表示为一组离散节点的集合，（），。这里，表示时间间隔，表示研究时段的开始时间，表示研究时段结束时间。为了简化说明，在后面的时间的说明中省略了时间间隔 ，即 ，（），。图 运行图示例 基本假设及变量定义（）基本假设根据研究经验做出假设，具体如下：沿地铁运输路线的车站的旅行需求和乘客到达分布是已知，且相对稳定的。所有列车在相同路段的运行过程和时间都是固定且相同的。所有列车为同一款列车，容量是已知，且在列车运行期间，不允许乘客数量超过列车上的最大人数。车站的设计容量是已知的，并且车站的最大容量不应超过车站的设计容量。根据研究，在车站聚集的人数与在平台上等待的人数和下车的乘客数量密切相关。由于每列列车的乘客人数众多，预测下车人数较为困难。为简化计算，本文仅预测在研究期间可以沿着线路下车的最大人数，并且将车站容量安全约束转换为在车站等待的人数。可以使用以下公式计算在车站等待的最大人数：（）在等式中，：车站 的最大乘客数，：站台设计容量，：站中可存在的最大人数。（）变量定义模型中变量具体定义如下：车站，；：车站站台，；：当 时，站 的上行方向上的站台，当 时，站 的下行方向上的站台；：运行线路的长度；：列车编号，；：开行列车编号；：最大列车编号；：时刻到达车站的乘客数量；：车站 的乘客前往车站 的概率；：研究时段到达的乘客总数；：列车在车站 停车的时间；，：列车在时间段 ，的运行时间；：在出发站 修整列车的时间；：在 站折回列车的时间；：离散时间段长度；：每单位时间购买列车车厢的成本；：列车车厢的行驶距离转换费；：乘客等待值；：最大发车间隔；：最小发车间隔；：列车容量；：列车数量；：最大载客率；：乘客到达阀值，如果在车站等候的乘客数量小于，乘客可以进入车站 ，否则乘客将等待下一站机会，需要在车站外排队；，：变量，如果站 允许乘客在时间 进入车站，则 ，否则 ，；：时刻列车中的乘客数；：时刻车站外等待乘客人数；：时刻在车站等候的乘客数量；：时刻在车站下车的乘客数量；：列车 离开车站的时间；：列车 到达车站时间；：车站 上第 名乘客到达后，第一趟与该乘客运行方向一致的列车的到达时间；：列车 重新进入空闲车底的时间；：第 名乘客到达车站的时间；：第 名乘客在车站 进站的时间；：第 名乘客在车站 的上车时间；运 筹 与 管 理 年第 卷：可用车辆的总数；：时刻站 的具有空闲车底数，；，：变量，当车站 处于拥挤状态时，即当不允许乘客进入车站时，否则，；：决策变量，如果在时间 有列车离开站，则 ，否则 ；：决策变量向量，。优化模型（）目标函数运行单位总是希望满足乘客的出行需求的条件下尽可能地降低运营成本；乘客总是希望尽可能高效地出行。因此，城市轨道交通业务的决策部门需要从整个系统的角度全面考虑双方的利益，优化列车时刻表。运营单位地铁运输运营成本一直是相关运营单位在优化城市轨道交通列车时刻表方面的重点。本文的运营成本主要包括调查期间购买列车的成本和行驶距离的成本。研究时段的列车购买成本可以通过以下公式计算：（，）（）研究时段列车行驶公里的转换成本可以通过以下公式计算：（）乘客作为城市轨道交通的服务，乘客总是希望提高效率。然而，一旦地铁线路和车站完工，将很难改善乘客的步行和乘车时间。因此，本文重点关注减少乘客等待时间，通过减少乘客的等待时间来提高乘客的出行效率。每个乘客的移动过程简单描述如下：到站 进站 候车 上车 下车 出站。乘客等待过程可分为以下站内等待和站外等待两种。基于上述分析，乘客上车和到达的时间差就是实际等待时间，具体如下：，（）（）然而，由于等待环境的影响，乘客对车站外的等待时间敏感，而等待列车的等待时间由于列车满载而使得感知的等待时间长于实际等待时间。因此，在本文中，通过引入惩罚系数 和 （，），此参数表明了乘客站内外等待时间的感知误差。另外此处引入了时间价值因子，将乘客的等待时间转换为乘客的广义等待时间成本。乘客的总等待时间如下：，（）（）（）（）（）列车时刻表优化模型基于以上分析，建立如下的优化模型：（）（），（），（），（），（），或 ，（），（），（），（）目标函数（）表示运营单位和乘客的最小总成本。不等式（）是一种安全条件，也就是说，任何两列车的发车间隔应大于最小发车间隔。不等式（）是服务水平约束，换句话说，城市地铁的出发间隔不应大于某一确定值。不等式（）和（）是容量限制，以确保车内乘客和站内总数不超过设计容量。本文将约束条件（）简化为 ，。等式（）表示车站 不拥挤（，），或车站等候的最小人数，乘客才可以进入车站。公式（）为最后一列地铁列车的出发时间。公式（）保证每次出发都有足够的空闲车底数。公式（）保证研究时段的运行供应将满足总乘客需求。基于仿真的优化模型求解方法遗传算法是模拟生物进化机制的全局随机搜索和优化算法，被广泛用于解决运输行业优化问题 。基于以上分析，提出了一种基于仿真的遗传算法求解该模型。仿真过程列车仿真过程模拟包括列车出发和列车到达两个事件。具体仿真模拟过程如下：当根据列车的时间表确定每个列车出发站的出发时间并且将模拟时间提前到列车的出发时间时，即是否满足列车的出发需求。如果空闲车底存在（），列车将准时离开出发站，相反，如果没有空车的底部（），列车将按计划出发。第 期张矢宇，等：考虑客流时变特性的列车时刻表优化方法当列车开始运行时，根据行程和停止时间，按顺序计算列车沿车站的到达和离开时间。当列车返回出发站并且修理工作的时间结束时，列车使用的车底进入空闲车底行列，此时，。另外，列车下车最大人数直接影响每个车站最大乘客人数的计算结果、乘客的等候时间和每列车的乘客人数。然而，由于在模拟之前难以准确地计算来自每个站的列车的最大数量，因此在本文中，在模拟期间添加反馈处理，并且不断更新每个站的最大列车数量，确保其小于车站的安全容量。基于仿真的两阶段遗传算法由于决策变量 是与二进制编码形式相似的 变量，直接将其作为遗传算法的染色体。根据解向量 的结构，可以看出，可以表示任何一种开行方案，即在研究时段从始发站发送的列车的数量可以从 变化。然而，如果两列地铁列车之间的距离太长或太短，由于约束（）和（）难以满足，大多数开行方案将不可行。如果仍然使用传统的遗传算法求解方法，则需要大量的计算时间来随机生成具有特定可行性的指定数量的初始解决方案组。为提高效率，提出了一种基于仿真的两步遗传算法。具体过程如下：（）阶段 ：产生初始解候选集合为提高效率，在优化之前提前部分生成初始解候选合集。生成均衡方案合集。该方案为等间隔发车，解决方案相对简单，枚举法即可以快速找到部分可行解。故采用枚举法，将每个均衡运行计划依次输入到仿真模型中，选择所有可行的均衡运行计划。丰富最初解决方案。基于均衡方案生成的初始备选解决方案，通过变异操作生成部分不平衡方案，将方案代入模型，若结果可行，将方案加入候选初始解，否则则舍弃该方案。此过程中具体变异过程如下：从初始候选组中随机选择亲本染色体，随机产生实数 ，如果 ，则使用突变规则 突变父染色体（见图 ）。否则，使用变体染色体 突变亲本染色体（见图 ）。图 变异规则 ：基因片段内部重组图 突变规则 ：单点变异（）阶段 ：遗传算法优化该优化过程包括 个步骤：步骤 生成种群进化代数最大值 。步骤 从 之 前 生 成 的 方 案 中 随 机 选 择 个染色体作为初始种群。步骤 将每条染色体的驱动方法输入模型中，运行获得参数值，并代入自适应函数以获得每条染色体的自适应函数值。在本文中，选择目标函数（）作为遗传算法的适应度函数：（）（），（）在该等式中，（）表示对应于染色体 的适应度函数值。步骤 使用轮盘赌方法，从亲代染色体群体中选择 个染色体以形成子染色体群体。具体程序如下：步骤 找出最大的适应度函数值 ：（）（）步骤 令 ，计算累积选择概率：（）（），（）步骤 随机生成实数 （，并将其与累积选择概率（，）进行比较以选择第 个染色体（）加入子染色体群体。步骤 结束条件判断。如果选择 个染色体，则终止选择操作并输出子染色体群，否则过程进入步骤 。步骤 两个选择的亲本染色体交叉操作产生新的染色体。具体程序为：确定染色体交叉概率，随机选择两条染色体，同时随机生成实数 ，如果，则遵循单点交叉规则（图 ）染色体相交。步骤 随机选择染色体突变，程序如下：步骤 确定染色体交叉概率，随机选择染色体，同 时 随 机 生 成 随 机 数 ，如 果，则进行步骤 以突变染色体；否则，父代染色体不改变。运 筹 与 管 理 年第 卷步骤 随机生成实数 ，如果 ，改变父染色体，此时改变规则遵循突变规则 ；否则遵循突变规则 。步骤 将新生成的染色体代入模型进行模拟验证，若方案可行，则将新染色体加入到子染色体群。步骤 当算法达到最大进化代数时，算法结束并输出最佳染色体；否则进化代数增加 ，进入步骤 。图 交叉规则：单点交叉 武汉地铁一号线时刻表优化分析 参数设置武汉地铁 号线由 个站组成，站间的行程时间设置为 分钟，每个站点的停止时间为 秒，返回站点的周转时间和出发站点的翻新时间均为 秒。每个站台的设计容 量 为 ，安 全 阈值 。优化目标是在出发站 处制定每列地铁列车的特定出发时间，假设每个站的乘客的到达分布规律满足下面的分布：（），在公式中，和 是每个站的乘客数量的基本参数，基本值如表 所示。显然，当确定优化时间间隔 时，可以通过以下等式计算各站 （，）的乘客需求。槡 （）（）例如，假设 ，将发送站 的基本参数代入等式（），并且在第一时间间隔 ，内到达的乘客数量是 。以 至 站为例，表 显示了前往每个站的乘客的概率 。研究表明：站的 乘客可以通过地铁转移到 站。算例参数取值和遗传算法参数取值情况分别见表 和表 。表 各站客流需求的基本参数取值车站东吴大道 五环大道 额头湾 舵落口 古田一路 古田二路 古田三路 古田四路 汉西一路 宗关 太平洋 口路 崇仁路 利济北路 友谊路 循礼门 大智路 三阳路 黄浦路 头道街 二七路 徐州新村 丹水池 新荣 堤角 竹叶海 表 车站 的乘客前往车站 的概率到达车站 起点车站 表 算例参数取值参数单位取值列 人 辆 节 列 元 （辆 ）元 （辆 ）元 第 期张矢宇，等：考虑客流时变特性的列车时刻表优化方法表 遗传算法参数取值参数含义取值 种群规模 最大进化代数 变异概率 交叉概率 模型优化结果分析作为优化结果和优化率的重要因素之一，优化时间间隔 的调整对于整个结果有显著影响，基于此本文 选择 了 三个不 同的 时 间 间 隔（，和 ）来优化模型，收敛过程如图 所示，优化结果如表 所示。图 收敛过程表 优化结果 根据上述优化结果，可以得出以下结论：从图 可以看出，优化结果在 代后开始收敛。根据表 ，在 的情况下，模型的最优解优化为 元，比 时的最优解优化了 元，比 时的最优解优化了 元。在此，给出 时求得到的最优开行方案。结论（）对于所建模型基于仿真的两步遗传算法，收敛性强，求解效率高。（）选择三个不同的时间间隔（，和 ）优化模型，优化结果在 代后开始收敛。在时间间隔为 的情况下，模型的最优解优化为 元，比时间间隔为 时的最优解优化了 元，比时间间隔为 时的最优解优化了 元，故时间间隔为 时求得到的最优开行方案。（）通过对列车数量、车站人数和乘客等待时间进行敏感性分析，发现“小而高密度”列车运行计划可以平衡乘客和运营单位的利益；同时，较小的平台容量严重限制了城市轨道交通的服务水平，增加了城市轨道交通的运营成本；而且越小的平台容量就会导致越高的成本，包括运营成本和乘客等候的成本。（）有关部门根据所得最优方案可对列车开行方案进行优化，确定更加合理的列车开行方案（包括运营时间及交路和用车计划等），将会有效提高乘客出行效率，减少出发站每列列车的运营费用，提高了城市轨道交通服务水平，对城市轨道交通高质量发展起到推动作用。参考文献：，：，：曹亮 基于客流需求的旅客列车时刻表优化研究 北京：北京交通大学，许得杰，巩亮，曾俊伟 考虑客流时变需求的大小交路列车时刻表优化模型 交通运输系统工程与信息，（）：，（）：祁奇 基于 动 态 客 流 的 城 市 轨 道 列 车 时 刻 表 北京：北京交通大学，：牛丰，戚建国，秦进 基于不确定客流的高速铁路列车停站方案优化方法 铁道学报，（）：，：，：，：胡金成 考虑运行能效的公交区域时刻表优化 交通运输系统工程与信息，（）：许潇月 基于时空网络客流分析的城市轨道交通列车时刻表优化 成都：西南交通大学，运 筹 与 管 理 年第 卷