网络模型_地铁时刻表建模之事件活动网络模型

篇首语：本文由编程笔记#小编为大家整理，主要介绍了地铁时刻表建模之事件-活动网络模型相关的知识，希望对你有一定的参考价值。

事件-活动网络(Event-Activity Network)建模方法是由替代图(Alternative Graph, AG)法衍生而来的一种新型建模方法。该方法常被用于解决地铁运营受到扰动或中断后的时刻表调整问题[1-3]，使用该方法的研究机构主要来源于荷兰及意大利的高校，代表学者如Rob Goverde、Yongqiu Zhu、Lucas P. Veelenturf等，所发表的成果主要集中在交通及运筹优化领域顶级期刊(TS, TR-B, EJOR等)上。较之离散时间下的时空网络建模方法，该方法的优点是可以建立线性规划数学模型，大大减小求解的难度。

将每一个时空节点看做一个事件(Event)，而事件与事件之间的有效关系可看作为一个活动(Activity)。列车在时空网络上的路径实则是由连接每个事件的一系列活动组成。任意一张列车时刻表都可转换为相应的事件-活动网络，该转换示例见图1.1。

如图1.1所示，在列车运行时空图中，有两趟地铁列车从车站A运行至车站C。列车1从车站A出发到达车站B之后停站等待，再从车站B运行至车站C。列车2从车站A出发直接到达车站C，中途未在车站B停车。该列车时刻表可转换为事件-活动网络中的节点与弧的连接关系。针对于列车1，其事件-活动序列可表述为：列车1从车站A出发事件(Tr1, Dep, A)，通过列车运行活动（可表示为((Tr1, Dep, A),(Tr1, Arr, B))）到达车站B，执行列车1到达车站B事件(Tr1, Arr, B)；接着，列车1通过列车等待活动，执行列车1从车站B出发事件(Tr1, Dep, B)；最后，列车1通过列车运行活动，执行列车1到达车站C事件(Tr1, Arr, C)。至此，列车1的所有事件-活动序列结束。针对于列车2，其事件-活动序列可表述为：列车2从车站A出发事件(Tr2, Dep, A)，通过列车运行活动到达车站B，执行列车2通过车站B事件(Tr2, Pass, B)；接着，列车2通过列车运行活动到达车站C，执行列车2到达车站C事件(Tr2, Arr, C)。到达终点站C后，列车2的所有事件-活动序列结束。需要补充说明的是，在考虑客流加载时，换乘客流弧段的加入将使图中的事件-活动网络连接成连通图。

因此，可以采用事件-活动网络建模的方法将规划的列车运行时空图转化为一个新的事件-活动网络。在事件-活动网络中，事件的属性包括事件的执行者（该事件是由哪一趟列车发生）、该事件的类型（到达事件、出发事件或者是通过事件）、事件的位置（该事件发生在哪一个车站）和事件的时刻（该事件在哪一时刻发生）；活动的属性包括活动的类型（等待活动、运行活动、通过活动、或者车头时距活动）和活动持续时间（该活动持续了多长时间）。

一般地，采用事件-活动网络建模的方法构造任意一张简易时刻表，所考虑的约束条件通常分为三类：单一事件约束、同一车次事件约束和不同车次事件约束。单一事件约束即对于单个事件自身的约束，该约束保证单个事件的自身属性满足列车运行的条件；同一车次事件约束，该约束保证同一车次的列车事件之间的关系满足列车运行条件，如列车区间运行时间、车站等待时间等等；不同车次的事件约束，该约束诸如相邻车次的车头时距等。

地铁列车时刻表设计问题分为两类：一类是非周期性时刻表设计问题，另一类是周期性时刻表设计问题。非周期时刻表的设计只考虑在所研究时间段内的列车时刻表安排；而周期性时刻表需要首先制定一个周期之内的时刻表，接着延续之后周期的时刻表。本文首先介绍非周期性时刻表的建模。

非周期性时刻表是建立周期性时刻表的基础。在制定非周期性时刻表时，首先给定该时刻表铺画的周期时长以及列车数量，其次通过建立数学优化模型得到满足列车运行约束条件的最优时刻表。

2.1 目标函数

目标函数是评估地铁列车时刻表铺画质量的重要衡量指标。针对高峰时刻的客流需求，本文将铺画一条密集的列车时刻表，因此选择目标函数为最小化最晚列车到达最后车站的时间。

2.2 约束条件

在铺画一个周期内的地铁列车运行图时，单一事件约束要求在该周期内所有事件的发生时刻不超过该周期的时间边界。约束表达如下：

对于同一车次的事件，可分为三种：到达事件、出发事件、通过事件。同一车次的活动分为运行活动和等待活动。针对同一车次在某站停站或运行的时间限制，可对其事件得出如下约束：

对于不同车次的活动，只有一种活动，即列车的车头时距活动。

在进行简单的时刻表铺画时，只需决策每个事件的发生时刻。按照每列车的活动依次连接各个事件，便可得到每列车完整的列车运行图。

3.1 案例背景及参数设置

北京地铁2号线（Beijing Subway Line 2）于1984年9月20日开通运营，是中国第一条环形地铁线路，也是北京市最为繁忙的地铁线路之一。该线路全长23.1千米，设有18座车站和1座车辆段（ 太平湖车辆段），如图3.1所示。它由北京地铁运营有限公司三分公司运营，运行轨距1435毫米(标准轨距)，供电方式为直流750V第三轨供电。线路采用准B型6节编组，车型为DKZ16（T401-T450），最高时速为80千米[4]。据通知，为配合好在建19号线与既有线换乘施工改造工作，2021年4月10日至6月6日对积水潭站进行封闭改造。地铁列车在积水潭站不停车直接通过[5]。 

图3.1 北京市地铁2号线

区间的走行时间通过区间的长度与地铁的平均速度相除得到。区间长度可通过查阅北京市地铁官网得到[6]，地铁列车的平均速度限制在40-80之间。据此通过计算得到的区间最大和最小走行时间见表2。

表2 区间走行时间

为了简化模型，本文假设列车在每个车站的停站时间最大为3分钟，最小为1分钟。

3.2 结果分析

本文采用MATLAB R2014b调用ILOG CPLEX 12.6.3对所建立的线性规划模型进行求解，处理器配置为Intel(R) Core(TM)i5-4210U CPU@ 1.70HZ 2.40GHZ，求解时间为2.689秒。求解结果见图3.2。

图3.2 列车运行图

如图3.2所示，在一个小时之内铺画了7条地铁列车运行线，最后一趟列车到达车公庄站的时刻为55.83分。另外，经笔者调试，在一个小时内最多能够铺画8张完整的地铁列车运行线，且该铺画方案中第8条地铁列车到达车公庄站的时刻为59.83分。值得注意的是，本模型的最优解有无穷多个。可以看到，在第7趟列车运行线中，西直门站至鼓楼大街站为折线。事实上，在图中红色矩形框中，红色折线可用绿色直线代替，替换后并不改变模型的最优目标函数值。为了避免模型的无穷多解，就需要多考虑一些因素，使得模型的解更具唯一性。

本文用事件-活动网络模型建立了铺画简单列车时刻表的数学优化模型。在模型中只考虑了地铁列车及线路的运行条件，并未考虑客流的加载。事实上，时刻表的制定应充分考虑客流的需求，根据客流的需求制定列车时刻表更加符合实际运营的需求。因此，更加实用的地铁列车时刻表应当是在客流需求驱动下所设计的时刻表，而这也是我们后续文章中将要介绍的内容。

[1]Veelenturf, Lucas P., M. Kidd, Valentina Cacchiani, L. Kroon and P. Toth. A Railway Timetable Rescheduling Approach for Handling Large-Scale Disruptions[J]. Transportation Science. 50 (2016): 841-862.

[2] Zhu Y, Goverde R. Railway timetable rescheduling with flexible stopping and flexible short-turning during disruptions[J]. Transportation Research Part B: Methodological, 2019, 123(5):149-181.

[3]Ilse, Louwerse, Dennis . Adjusting a railway timetable in case of partial or complete blockades[J]. European Journal of Operational Research, 2014.

[4]https://baike.baidu.com/item/北京地铁2号线/4320943?fr=aladdin

[5]https://baijiahao.baidu.com/s?id=1699368874266244847&wfr=spider&for=pc

[6]https://www.bjsubway.com/station/zjgls/#