一种地铁网络列车时刻表快速编制方法

摘要

本发明属于城市轨道交通控制技术领域，涉及一种地铁网络列车时刻表快速编制方法，包括：S1：设置目标地铁网络的基础参数；S2：设置各线路区间的运行时间、停站时间、发车间隔和旅行时间的范围；采集现实数据，设置各换乘车站站台间的换乘走行时间；S3：采集地铁网络的客流信息；S4：采用广义Benders分解算法进行编制；S5：获得大型地铁网络的协同优化列车时刻表和线路间列车接续情况。本发明采用广义Benders分解算法将原问题分解为更易求解的子问题和主问题，具有较好的求解效率，且能够最大程度减少乘客等待时间，提高地铁系统的换乘效率和服务水平。

说明书

技术领域

本发明属于城市轨道交通控制技术领域，涉及一种地铁网络列车 时刻表快速编制方法，尤其涉及一种地铁网络下基于广义Benders分 解算法的地铁网络列车时刻表快速编制计算方法。

背景技术

随着全世界城市化和机动化进程的加剧，城市中交通拥堵、意外 事故和尾气排放所引起的交通污染等问题越来越严重。为缓解城市交 通拥堵，倡导低碳环保出行，优先发展城市公共交通已成为国内外广 泛采用的重要举措。作为公共交通的重要组成部分，城市轨道交通具 有运量大、速度快、节能环保和准时可靠等特点，而受到各大城市的 青睐。随着居民出行的急剧增加和出行需求的多样化，在城市轨道交 通网络中的乘客为完成出行，往往从起始点到目的地，有时需要完成 一次(或多次)不同线路之间的接驳转运，即换乘。对城市轨道交通 换乘站来说，换乘客流比例较高，而换乘效率直接影响乘客出行时间 和乘客对地铁系统服务水平的满意度。高质量的换乘可以减少出行时 间，增强地铁的吸引力，而不合理的换乘则对出行的便捷性、舒适性 和出行需求产生不利影响。随着北京和上海等城市轨道交通网络的快 速扩大，网络运营提高了地铁的可达性和覆盖范围，同时也存在大量 的换乘客流需求。如果线路间列车运行计划不相互协调，会给乘客换 乘带来不便，从而产生较长的等待时间，降低换乘的衔接性和流畅性。 因此，研究地铁网络中列车衔接和时刻表优化问题，对地铁运营管理 具有重要的指导作用和现实意义。

列车时刻表优化是轨道交通网络运营管理的重要组成部分，通过 调整线路上列车的到发时间等，使不同线路上的列车同步到达换乘 站，或换乘乘客下车后走行至换乘站台赶上接续列车。通过优化后的 时刻表，乘客可以体验无缝换乘衔接和良好的地铁系统服务水平，从 而实现换乘乘客和进站乘客等待时间的最小化。

面对具有大量线路、车站和列车的大规模地铁网络，往往需要较 长的求解时间来编制时刻表。而在城市轨道交通运营中，由于工作日、 节假日、大型活动和疫情爆发期间的客流特性不同，需根据历史或预 测的客流特征来编制新时刻表，这给地铁运营公司带来了巨大的计算 负担。因此，针对大规模地铁网络的列车时刻表编制问题提出一种计 算效率高的优化算法是很有必要的。

本发明提供一种地铁网络列车时刻表快速编制计算方法，以期最 大程度减少换乘乘客和进站乘客的总等待时间，并提高线路间换乘效 率和客运服务水平。

发明内容

面对大规模地铁网络问题时计算负荷大的情况，本发明公开了一 种新的基于广义Benders分解算法的时刻表快速编制计算方法，通过 在合理范围内调整两列接续列车的到发时间，从而达到快速计算得到 协同优化的时刻表，最大程度减少进站乘客和换乘乘客等待时间的目 标。

为了解决上述问题，本发明提出一种基于广义Benders分解算法 的地铁网络列车时刻表快速编制方法，具体技术方案如下：

一种地铁网络列车时刻表快速编制方法，包括以下步骤：

S1：设置目标地铁网络的基础参数；

所述基础参数包括：线路数量、每条线路的车站数和目标地铁网 络中不同线路间换乘车站情况等；

S2：设置各线路区间的运行时间、停站时间、发车间隔和旅行时 间的范围；

采集现实数据，设置各换乘车站站台间的换乘走行时间；

S3：采集地铁网络的客流信息；

所述地铁网络的客流信息包括：换乘车站的换乘乘客人数和进站 的乘客人数；

S4：为了快速编制大规模地铁网络列车时刻表，采用广义Benders 分解算法进行编制，具体包括以下步骤：

S41：给定计划列车数量和时域；

S42：根据目标大型地铁网络(即大规模地铁网络)相关参数和 客流信息等，建立时刻表协同优化模型；

S43：利用广义Benders分解算法，将步骤S42构建的时刻表协 同优化模型，分解为容易求解的子问题和主问题，并迭代求解子问题 和主问题，直至收敛至最优解；

S5：由步骤S4得到最优解，获得大型地铁网络的协同优化列车 时刻表和线路间列车接续情况。

在上述技术方案的基础上，步骤S42的具体步骤如下：

S421、构建时刻表线性约束：

利用公式(1)得到各线路上每列车到达各车站的时间，利用公 式(2)得到各线路上每列车离开各车站的时间，

其中：i是列车标号；s是车站标号；m是线路标号；M表示： 目标大型地铁网络中所有线路标号的集合；S

为满足运营需求，同一车站内两列相邻列车间的发车间隔时间需 要满足如式(3)所述约束，

其中，

为保证列车i从离开起始站到到达终点站的时间在合理的总旅行 时间内，列车i的总旅行时间需要满足如式(4)所述约束，

其中，

考虑到运营安全和服务水平，线路m上列车i在车站s的停站时 间

其中：

为保证所有列车在计划周期H内完成行程，

S422、计算换乘等待时间线性约束：

线路m和线路m'交汇于s站，若在换乘站s实现线路m至线路m' 的换乘，则需要满足乘客乘坐线路m'上列车i'到达后，换乘走行至线 路m的换乘站台时，列车还未驶离换乘站s；

为准确表示列车在换乘站的接续，引入0-1变量

其中，M是足够大的正数，

基于对

其中，基于所有乘客都将登上第一列接续列车的假设，

根据上述约束，如果线路m上的列车i是线路m'上列车i'的第一 列接续列车，则

换乘站s内在两列车间换乘乘客的等待时间计算如约束式(11) 所示，如果线路m'上的列车i'成功接续线路m上列车i，则换乘等待 时间为

S423、最小化乘客等待时间的目标函数：

为了最小化乘客的等待时间，所述等待时间包括：换乘乘客和从 地铁网络外进入车站乘客的等待时间，构建目标函数如式(12)所示，

其中，

S424、建立时刻表协同优化模型：

结合上述目标函数和约束，构建时刻表协同优化模型如式(13) 所示，

上述时刻表协同优化模型是一个混合整数非线性规划问题，称 为：时刻表编制问题，其约束是线性的，而目标函数是非线性的。

在上述技术方案的基础上，包含大量0-1变量的混合整数非线性 规划问题较复杂，难以在较短时间内求解包含大量线路、车站的大规 模地铁网络问题。为减轻大规模问题的计算负担，提出：以广义 Benders分解算法来代替传统的集中式求解方法。

基于广义Benders分解算法将步骤S42构建的时刻表编制问题分 为两部分：子问题(SP)和主问题(MP)；将一些复杂变量特别是整 数变量暂时固定为给定值，剩余部分称为子问题较容易解决；如果子 问题不可行，则需要引入松弛变量，使得子问题可行；然后将子问题 求解出的其他决策变量值和对偶变量值构建Benders割，而迭代增加 的Benders割和时刻表编制问题中仅涉及复杂变量的约束构成主问 题，优化求解复杂变量；最后，将主问题求出的复杂变量值代入子问 题再次求解，重复以上过程直至收敛至最优解；

所述Benders割包括：可行割和最优割；

Benders割函数包括：可行割函数和最优割函数。

在上述技术方案的基础上，所述步骤S43具体包括以下步骤：

S431、推导与求解子问题：

根据广义Benders分解算法，在时刻表协同优化模型，即式(13) 中，定义两列车是否可以衔接的0-1决策变量

首先，将

其中，如果

然后，结合子问题求出的最优值

因整数变量固定后，子问题是原问题的限制问题，故其目标函数 的最优值是原问题的上限。最后，将第k次迭代的子问题的目标函数 值写作Z

UB

S432、构建Benders割函数和主问题：

一些整数变量的给定值可能对耦合约束(8)不可行，从而使得 子问题不可行，因此需基于实际情况，向主问题加入防止问题不可行 且不改变最优解的可行割。给定Z

将所有的Benders割一起构成主问题，主问题的目的在于：通过 求解

其中，K

应注意，主问题是原问题的松弛问题，它从下接近原问题的目标 函数。因此，对第k次迭代，式(19)的目标函数值是原问题目标函 数的下界，如式(20)所示，

LB

S433、基于广义Benders分解算法求解，具体步骤如下：

第一步：初始化，设置迭代计数k＝1和容差值ε，将整数变量

第二步：求解子问题：

如果固定

第三步：生成Benders割：利用子问题的解，如果子问题不可行， 按公式(17)生成可行割

第四步：求解主问题；

求解式(19)，得到μ

第五步：检查收敛：

计算上界UB

在上述技术方案的基础上，在所述广义Benders分解算法中，当 一些复杂决策变量固定时，有下列三种情况：

①子问题可行且有界，只有一个最优解，将最优割加至主问题；

②子问题可行但无界，因原问题也无界，故算法停止(Geoffrion, 1972)；

③子问题不可行，将可行割加至主问题。

在上述技术方案的基础上，如果子问题不可行是指：式(14)中 的人工变量

本发明的有益技术效果如下：

本发明通过历史或预测的客流信息，针对具有较多线路和车站的 大规模地铁网络，提出了一种地铁网络列车时刻表快速编制方法，通 过调整列车的到发时间来优化列车间衔接情况，采用广义Benders分 解算法将原问题分解为更易求解的子问题和主问题，具有较好的求解 效率，且能够最大程度减少乘客等待时间，提高地铁系统的换乘效率 和服务水平。

附图说明

本发明有如下附图：

图1示出本发明提供的城市地铁线路示意图。

具体实施方式

为了更清楚地说明本发明，下面结合优选实例和附图对本发明做 进一步的说明。附图中相似的部件以相同的附图标记进行表示。本领 域技术人员应当理解，下面所具体描述的内容是说明性的，而非限制 性的，不应以此限制本发明的保护范围。

为证明所提出的模型和求解方法的实用性，我们对实际大型地铁 网络进行试验。图1中的网络是北京地铁网络的一部分，包括15条 运营线和51个换乘站，其运行方向在图中用箭头标记。

试验考虑的规划周期是早上8点至10点，共150列车从线路首 站发出，每条线10列车。每条线的发车间隔时间的上下限列在了表 1中，每个车站的列车停站时间是[10,60]s。相邻车站间的列车运行时 间是[120,300]s。另外，根据北京地铁网络实际运营数据设置相交线 路m和m'在换乘站s的换乘走行时间

表1试验的北京地铁网络中每条线的发车间隔的上下限列表

首先，我们尝试用CPLEX求解器直接求解，但没有得到一个可 接受的解。而运用Benders分解算法的情况下，目标函数值为4.82×10

表2列车时刻表优化前后的结果对比表

特别地，表3展示了地铁网络中所有换乘车站的换乘等待时间和 相应的改进之处。计算优化前后每个换乘车站上10列车的总换乘等 待时间的偏差作为每个换乘节点的改进之处。譬如，从1号线至2号 线的建国门站换乘节点在优化前后的换乘等待时间分别为23650s和 10240s，故其提升了13410s。而少量换乘节点上换乘等待时间的增加， 可以减少整个地铁网络上总的乘客换乘等待时间。因为每条线上每列 车在首站发车时间的限制，共有8个换乘节点在规划周期内不能接续 成功，一些线路上在前几列车里的乘客可能会等待较长时间。

综上，本发明公开的基于广义Benders分解算法的城市轨道交通 列车时刻表快速编制方法，构建了一种考虑列车衔接的时刻表协同优 化模型，并运用Benders分解算法将原模型分解为容易求解的子问题 和主问题两部分，从而能够快速求解得到协调优化后的列车时刻表， 最大程度减少换乘乘客和进站乘客的等待时间，大大提高运营服务水 平和乘客出行满意度。

显然，本发明的上述实施例仅仅是为清楚地说明本发明所做的举 例，而并非是对本发明的实施方式的限定，对于所属领域的普通技术 人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变 动，这里无法对所有的实施方式予以穷举，凡是属于本发明的技术方 案所引申出的显而易见的变化或变动仍处于本发明的保护范围之列。

本说明书中未做详细描述的内容属于本领域专业技术人员公知 的现有技术。