城市轨道交通列车车底运用计划优化建模
Optimization Model on the Connection Plan of Rolling Stocks for Urban Rail Transit
摘要: 车底运用效率是降低地铁运营成本、提升服务质量的关键。本文通过建立多旅行商(MTSP)模型,以接续费用最小为目标函数,综合考虑时空约束、车场约束及禁止空驶约束,构建混合整数规划模型。采用ILOG CPLEX求解器对某城市地铁线路进行求解,优化后总接续费用较人工方案降低12.5%;车辆使用数降低1辆;车底平均有效利用率达81.51%,较人工方案(77.18%)提升4.33%;同时在使用均衡性表现上优于人工方案。研究表明,模型在接续成本、资源利用率和均衡性方面均优于传统方法,验证了MTSP模型的有效性。
Abstract: The utilization efficiency of the rolling stocks is the key to reduce the operation cost of subway and improve the service quality. In this paper, a mixed integer programming model is constructed by establishing a multi-traveling salesman (MTSP) model, taking the minimum connection cost as the objective function, comprehensively considering the time and space constraints, yard constraints and prohibition of empty driving constraints. The ILOG CPLEX solver is used to solve the subway line of a city. After optimization, the total connection cost is reduced by 12.5 % compared with the manual scheme. The number of vehicles used is reduced by 1; the average effective utilization rate of the rolling stocks is 81.51%, which is 4.33% higher than that of the manual scheme (77.18 %). At the same time, it is superior to the manual scheme in the use of balance performance. The research shows that the model is superior to the traditional method in terms of continuation cost, resource utilization and balance, which verifies the effectiveness of the MTSP model.
文章引用:姜漫野. 城市轨道交通列车车底运用计划优化建模[J]. 建模与仿真, 2025, 14(3): 543-554. https://doi.org/10.12677/mos.2025.143245

1. 引言

截至2024年底,中国地铁运营总里程达到约10945.6公里,且这一数字仍在快速增长[1]。随着运营里程的增加,地铁企业需要投入更多的车辆资源,如何在满足运营需求的同时提高车底资源的使用效率,减少车辆资源的浪费,成为地铁运营组织中的关键问题。合理的车底运用计划不仅能够提高乘客的服务质量,还能有效降低企业的运营成本。

以运筹学理论分析,车底运用计划的编制为非确定性多项式难(nondeterministic polynomial-time hard, NP-Hard)问题[2],国内外学者对城市轨道交通列车车底运用计划的优化问题进行了广泛研究。针对单一线路的车底运用计划优化,Pan [3]考虑了城市轨道交通线路上乘客分配的随机特征,开发了一种具有不同切割生成策略的benders分解算法。Huang [4]提出了一种节能的列车时刻表和车底运用计划的集成优化模型。Gong [5]提出了一种采用短的转弯和节能策略的时刻表和车底运用计划的综合优化方法,且根据不同的乘客偏好提供灵活性。Zhao [6]通过模糊规划将多目标模型重新表述为单目标模型,解决了车辆数量有限时的车辆短缺的问题。Su [7]提出了一种数据驱动的方法,旨在解决列车运营中断的问题。郑锂等[8] [9]建立了网络化运营下城市轨道交通列车车底运用计划编制优化基本模型,给出了精确求解算法和并行禁忌搜索的智能算法。李洁等[10]给出了成网条件下车底运用问题的优化方法,采用ILOG CPLEX 12.5优化软件,并与人工方案进行了比较,验证了求解方法的高效性。

本文针对城市轨道交通列车车底运用计划问题,将车底运用计划优化问题转化为图论中的多旅行商问题,使用数学建模的方法进行优化研究。模型以接续费用最小为目标函数,以车底接续为决策变量,充分考虑唯一性约束、节点时空约束、车场约束以及车底禁止空驶约束等约束条件,使用数学优化求解器ILOG CPLEX进行求解。通过案例分析,验证了模型的有效性。

2. 模型建立

2.1. 问题描述

2.1.1. 既往研究方法

解决车底运用优化问题在以往的学术研究中,常常使用两种方法:一种是将车底运用优化问题类似于车辆路径问题,把问题进行转化为旅行商问题,在此基础上再进行算法的设计和求解;一种是把地铁车底运用计划与多商品网络流模型相结合,基于已有算法进行逐步改进升级。本文中使用第一种方法,采用旅行商问题进行建模求解的思想具有易于理解的优点,在图形的基础上描述解决流程,更加直观明了。

2.1.2. 旅行商问题概述

传统的旅行商问题可以简要理解为;一个想要推销商品的人,他从一个目的地出发,必须经过所有的目的地,最后回到出发地。怎样找到一条满足上述条件的最短路径。基于图论的研究内容,旅行商问题的本质意义在于在一个带权的无向图中,找到权值最小的闭合路径。旅行商问题在物流、交通领域有着广泛的应用。如图1所示为旅行商问题的示例。

Figure 1. Example of a traveling salesman problem

1. 旅行商问题示例

2.1.3. 车底优化问题向旅行商问题的转化

由于在列车运行图中,每一列车在区间的运行时分、进站时间、出站时间、区间占用顺序等是被固定的,因此车底运用计划的编制问题本质是为每个上线使用的车底安排车次的连接,接续条件要考虑各项实际的约束。如何合理安排这些接续,使列车总体达到良好的使用效率,为企业创造经济效益,是车底运用计划编制的关键。基于上述分析,将车底运用优化问题转化为旅行商问题。思想是:可以将每个车底看作一个推销员,每个车次看作一个城市。不过与传统条件下的TSP问题不同,车底计划中的车底并不能像实际的推销员自由的选择旅行城市的次序,而要受到不同车次任务的时间及空间约束,并且一条线路包含很多车底,因此是带约束条件的多旅行商问题。

举例说明,如下图2所示的列车运行图,共有8条列车运行线,将每条运行线看作一个点,暂且不考虑其余约束条件,把满足前后位置关系的节点相连接,接续后的连接图如图3所示。后续建模中,可以给每个节点增加各种属性,例如始发站、终到站、始发时刻、终到时刻、折返时间等。

Figure 2. Part of the train operation diagram

2. 部分列车运行图

Figure 3. Node connection grid diagram

3. 节点接续网格图

2.2. 车底运用优化建模

2.2.1. 假设条件

本文是单日列车运行计划,本文的模型基于以下假设

(1) 列车按运行图行车,不允许调整列车运行线。

(2) 线路的结构、布局、折返站、折返能力等信息已知。

(3) 单日列车运行计划,不考虑检修等相关约束。

(4) 列车的编组模式以及车底类型固定。

(5) 车底为固定运用方式。

(6) 车场归属不固定,但车场内车底数保持固定。

2.2.2. 符号及变量说明

模型所涉及到的符号及变量说明如下表1

Table 1. Description of the symbols and the variables

1. 符号及变量说明

符号

含义说明

s

s 个车底, s S

S

所有车底集合

P 1

车辆段节点集合

P 2

车次任务节点集合

P

车辆段和车次任务节点集合, P = P 1 P 2

m , n

节点 m , n ,且 m , n P

S m d

节点 m 的始发站

S m a

节点 m 的终到站

t m d

节点 m 的始发时刻

t m a

节点 m 的终到时刻

c m , n

节点 m n 接续成本

t m z

车次任务 m 在折返站 Z 的折返时间标准

t m , n

车场与车次的接续时间或车次与车场的接续时间

β

单位车底接续时间费用

x m , n s

决策变量,1为 s 承担 m , n 接续,反之为0

2.2.3. 目标函数

本文的优化目标是车底运用费用最低,由于列车运行图一定,因此列车的区间运行时分固定,可以把优化目标转化为总接续时间最短。接续时间包括了车次之间的接续以及车次和车辆段之间的接续。因此目标函数为:

min Z = m P n P s S c m n x m n s (1)

2.2.4. 约束条件

根据假设以及车底优化问题的现实意义,模型的约束条件如下:

(1) 节点的接续必须唯一

此约束条件的含义有两个:

一是将每个车次任务看成一个节点时,这个节点必然是与其他节点相连接而不是独立存在的,与其连接的节点可以是满足约束条件的其他车次任务节点;当车次是出库任务或回库任务时,与之连接的节点则为车场节点,公式上表达为:

m P , m n s S x m n s = 1 n P 2 (2)

n P , n m s S x m n s = 1 m P 2 (3)

另外一种含义是针对车底,就同一车底而言,使用其作为车次任务的前车次的到达车站必须与后车次的出发车站相同,车底不能跳跃或凭空出现在运行计划中,公式表达为:

n P x m n s = n P x n m s m P 2 , s S (4)

(2) 每一个车辆段出入车数目相同

为了在减少运营组织难度的同时尽可能的提高列车运用的灵活性,车辆在运营结束后可归属不同的车场,一般可以归属就近的车场。但每个车场必须保持出发车底和回库车底数目相同,以此来减少运营组织的难度。公式表达为:

n P 2 s S x m n s = n P 2 s S x n m s m P 1 (5)

(3) 车底必须承担车次任务

为了尽可能的提高车底使用效率,避免车辆空跑,所有车底必须承担载客运行任务,即从车场出发后,直接再回车场的车辆为零。公式表示如下:

n P 1 x m n s = 0 m P 1 , s S (6)

(4) 节点的时空约束

此约束条件包含空间和时间约束:

从第一个角度看,前节点的终到站必须和相连接的后节点的始发站一致,两个节点方可连接,即需要满足: S m a = S n d ,在此情况下二者的接续时间可用后节点的出发时间与前节点的到达时间相减表示,即 t n d t m a ;若不满足此空间约束,则其接续费用使用无穷大表示,以此达到在求解中避免此情况的出现的目的。

从第二个角度看,前车次任务节点 m 的到达时间首先要小于后车次任务节点 n 的出发时间,即 t n d > t m a 。在此基础上,二者的差值还必须满足终点站折返作业时间标准才能进行接续。若不满足折返时间标准,即 t n d t m a < t m z ,则二者不能接续,反映在其接续费用为无穷大。结合二者车次任务之间的成本表示为:

c m n = { β ( t n d t m a ) S m a = S n d  and  t n d t m a t m z , m P 2 , n P 2 S m a S n d  or  t n d t m a < t m z , i P 2 , j P 2 (7)

在考虑车场与车次任务之间的接续时,本文针对单日车底运用计划,因此不需要考虑时空约束。因此公式表示如下:

c i j = β t i j i V 1 , j V 2  or  i V 2 , j V 1 (8)

综上所述,节点接续时间成本以如下表示:

c i j = { β ( t n d t m a ) S m a = S n d  and  t n d t m a t m z , m P 2 , n P 2 β t m n m P 1 , n P 2  or  m P 2 , n P 1 S m a S n d  or  t n d t m a < t m z , m P 2 , n P 2 (9)

2.3. 车底运用优化模型求解

本文使用ILOG CPLEX进行求解,软件本身的编程过程能直观的体现出车底运用优化模型的目标函数以及约束条件,因此本文选择直接使用优化求解器IBM ILOG CPLEX 12.6来进行模型的求解。使用的计算机规格为64位Windows11操作系统,AMD Ryzen75800H,CPU3.2Ghz,RAM16GB。具体求解方法是,将目标函数、约束条件以及数据按软件语言输入,使用软件内部自带的求解功能直接求出满足约束条件情况下的最优解,较其他方法而言比较简便。

2.4. 评价指标

对于按照各类不同方法所编制出的车底运用计划,需要找出共同的评价指标来分析方案的优劣性。常用的评价指标有:总接续成本、车底运行时间、总车底使用数、车底运用平均性、车底有效利用率、运营成本等。本文选取总接续成本、车底有效利用率与车底运用平均性这三个指标。

2.4.1. 总接续成本

总接续成本指的是企业所花费的在列车全日正线运行过程以及出入库间,各个运行线的接续时间的成本,并不包括列车在中途各个站点的停车载客时间。本文以现实的经济性作为考虑因素,因此以总接续成本最小直接作为目标函数来进行建模与求解。

2.4.2. 车底有效利用率

列车的运行时间包括总运行时间与有效运行时间。总的运行时间是指列车从始发站出发,到完成全日的运行计划的总时间;有效运行时间指的是除去接续时间以外的载客运行时间。在评价车底运用计划时,更为重要的是车底的有效利用率。车底有效利用率越高,则表明在车底实际的运行过程中,有更多的时间处于承担载客任务的状态,而有较少的接续时间,即对车底运用的浪费较少。因此提高车底的有效运用率,能够更好地满足企业的运能需求。本文使用如下公式计算各个车底的有效利用率。

φ s = t s c t s z (10)

并计算出全部车底的平均有效利用率

φ s ¯ = s S φ s S (11)

2.4.3. 车底运用平均性

本文中车底运用平均性指的是在使用各个车底过程中,不同车底使用率的均衡性以及差异性。尽可能地提高车底运用的平均性,使各个车辆有近似的磨损程度,可以减少编制车底检修计划的难度,提升运营组织水平。

本文中使用各个车底走行时间以及有效利用率的方差来衡量车底运用的平均性。车底走行时间见计算结果,有效利用率的方差如下所示。

D = s S ( φ s ¯ φ s ) 2 S (12)

3. 案例分析

3.1. 背景描述

选取某市某线路作为背景,具体情况如下图4所示。仅选取线路两端尽头的站点以及中间车辆段,A和B分别为线路两端站点,具备折返功能,并且地铁车辆段X更加靠近站点A。以本线路地铁正常工作日06:00~11:00运营时间内的列车时刻表作为模型数据进行研究。规定上行方向为从B站到A站,上行的运行线车次编号从002开始按照偶数逐次增长,同理下行方向为从A站到B站,下行车次编号按照001为始发车次,按照奇数依次增加。

Figure 4. A schematic diagram of the line structure

4. 线路结构示意图

两站点A、B到车辆段X的运行时间见表2

Table 2. Running time from the depot to both end points

2. 车辆段到两端点的运行时间

X-A

X-B

A-X

B-X

260

2080

260

2350

各个参变量的取值如下表3所示。

Table 3. Parameter value

3. 参数取值

参变量

A站的折返时间

205秒

B站的折返时间

230秒

车底运行单位接续时间成本β

2元/秒

3.2. 求解结果

使用求解器直接进行求解,在满足约束条件的情况下求得的总接续费用为Z = 89,432元,各个节点的接续情况如表4所示。下表5为车底运用计划的其余相关指标。

Table 4. Number distribution

4. 车次分布

车底编号

承担任务

001X

X-002-015-026-055-066-X

002X

X-001-012-035-046-075-086-107-118-X

003X

X-003-014-039-050-079-090-X

004X

X-004-021-032-061-072-099-110-125-X

005X

X-005-016-043-054-083-094-113-124-X

续表

006X

X-006-025-036-065-076-101-112-127-X

007X

X-007-018-047-058-087-098-115-126-X

008X

X-008-029-040-069-080-X

009X

X-009-020-049-060-089-100-X

010X

X-011-022-051-062-091-102-117-128-X

011X

X-010-031-042-071-082-105-116-131-X

012X

X-013-024-053-064-093-104-119-X

013X

X-017-028-057-068-095-106-121-X

014X

X-019-030-059-070-097-108-123-X

015X

X-023-034-X

016X

X-027-038-067-078-103-114-129-X

017X

X-033-044-073-084-X

018X

X-037-048-077-088-109-120-X

019X

X-041-052-081-092-111-122-X

020X

X-045-056-085-096-X

021X

X-063-074-X

Table 5. Run chart metrics

5. 运行图指标

指标名称

指标值

上行开行列数

65 (列次)

下行开行列数

65 (列次)

总开行列数

130 (列次)

运行车底数

21 (辆)

3.3. 结果分析

3.3.1. 总接续成本

本文是按照在满足约束条件下的最优化求解方法在求解器CPLEX中进行直接求解,且本文所建的模型为单目标函数,目标函数即为总接续成本最小,因此求出的89,432即为约束条件下的最优解。

3.3.2. 有效利用率

在得到了求解器计算得到的总接续费用以及各个车底所承担的车次任务后,需要对得到的数据进行分析。根据前文提到的车底有效利用率以及得到的任务表格,分别计算各个车底从车场出发再返回车场的总行驶时间,以及不算接续时间而纯载客运行时间(包括中途停站时间等)。计算车底的有效利用率,将计算得到的结果按照图5进行展示。

各个车底的有效利用率情况见表6,计算所有车底的平均有效利用率为81.51%,所有车底的有效利用率均超过70%,其中最低有效利用率为004X车,为70.70%;最高有效利用率为010X,为88.30%。仅有8列车的有效利用率处于70%~80%区间内,证明半数以上的车底有80%以上的利用率。

以上数据充分表明了在此情况下,线路上所运行的车底使用情况良好,在大多数情况下处于承担载客任务的运行线中,而有相对较少的时间处于接续和出入库状态,车辆的运能得到较为的利用,充分满足地铁企业的期望。

分析有8辆车底利用率低于80%的原因。本案例中所选的地铁线路中仅有一个车场X,并且更为靠近车站A。因此对于更为靠近车站A的车站B,车底需要在出库与入库上花费更多的时间,因此车底利用率会略低一些。而且两端车站的折返时间也会在一定程度上影响车底的有效利用率。本文案例中A站的折返时间为205秒,B站的折返时间为230秒,因此上行方向的折返较下行方向的折返也略有优势。基于上述原因分析,若想提高车底利用率,可在线路上靠近两端的地方分别修建两个车场,减少车辆出入库的走行距离。此外,还可以提高折转能力,减少列车折返时间。

Figure 5. Run time and utilization

5. 运行时间及利用率

Table 6. Index summary

6. 指标汇总

最低有效利用率

最高有效利用率

平均有效利用率

高于80%车底数

70.70%

88.30%

81.51%

13

从实际角度出发,考虑检修因素时应主要从列车的走行距离进行分析,但本文并未引入列车走行距离相关的参数,因此近似用列车的运行时间来替代列车的走行距离。并且选择使用载客运行时间作为指标,因为载客运行时间中列车大多数处于运行状态,停车上下客所占比例较小,而总行驶时间中包含了列车等待静止的时间。因此使用载客运行时间作为指标,对列车走行距离的替代性更高。

按照公式(12)计算出车底有效使用率的方差。计算得到的方差保留四位小数为0.0039,数据折线表现较为集中,模型计算得到的车底使用计划对车底的使用较为均衡,有利于地铁企业更为简便的安排车辆的检修。

3.4. 方案比选

将本文中按照数学建模、求解的方法得到的车底使用计划与采用人工编制方法得到的车底使用计划(表7)进行比较。计算各个车底的载客运行时间和总行驶时间,计算结果见图6

Table 7. The distribution of train numbers obtained by the manual compilation method

7. 人工编制方法得到的车次分布

车底编号

承担任务

001X

X-001-012-035-046-075-086-107-118-X

002X

X-003-014-037-048-077-088-109-120-X

003X

X-005-016-041-052-081-092-X

004X

X-007-018-045-056-085-096-113-124-X

005X

X-009-020-049-060-089-100-117-128-X

006X

X-011-022-051-062-091-102-119-X

007X

X-013-024-053-064-093-104-121-X

008X

X-015-026-055-066-095-106-123-X

009X

X-017-028-057-068-097-108-125-X

010X

X-002-019-030-059-070-099-110-127-X

011X

X-004-021-032-061-072-101-112-129-X

012X

X-006-023-034-063-074-X

013X

X-008-027-038-067-078-X

014X

X-010-031-042-071-082-105-116-131-X

015X

X-033-044-073-084-X

016X

X-050-079-090-111-122-X

017X

X-025-036-065-076-X

018X

X-029-040-069-080-103-114-X

019X

X-047-058-087-098-115-126-X

020X

X-054-083-094-X

021X

X-39-X

022X

X-43-X

Figure 6. Run time and utilization

6. 运行时间及利用率

以下为人工编制方法的各个指标汇总情况:

Table 8. Run time and utilization

8. 指标汇总

最低有效利用率

最高有效利用率

平均有效利用率

高于80%车底数

65.24%

88.70%

77.18%

9

人工方案是基于人工编制的车底运用计划,通过对比优化模型方案的结果,可以深入分析人工方案的优缺点。根据图6表8,人工方案的结果车底运用总数为22辆,平均有效利用率为77.18%,仅有9辆车底的有效利用率高于80%。以下是对人工方案的详细分析。

Figure 7. Comparison chart of the effective utilization rate of the rolling stocks

7. 车底有效使用率对比图

Table 9. Scheme comparison

9. 方案比较

计算方案

人工方案

车底数21

车底数22

平均有效利用率77.18%

平均有效利用率81.51%

在人工方案中,共使用了22辆车底,而优化模型方案则使用了21辆车底。这一差异反映了人工方案在资源配置上的不够优化。因为传统人工编制的方案往往仅按照列车运行图编制,可能会导致有的列车在满足车次任务后空驶的现象,无法从整体上达到最优决策。具体来看,人工方案中21、22号列车只承担了一个运行任务,这样的安排导致车底资源的浪费;人工方案有效利用率见图7表9,平均仅为77.18%,低于优化方案的81.51%。这是因为人工方案在车次的安排上,无法充分考虑到车底走行的合理分配,造成某些车底负荷重,其余车底闲置多。这种车底使用的不均衡性,导致车辆的磨损情况不同,可能会影响检修计划的安排。优化方案通过模型的优化目标及各项约束,不仅减少了车底数量,提高了车底的有效利用率,还在接续成本上进行了有效的降低。

4. 结论

针对城市轨道交通车底运用计划优化问题,提出了一种基于多旅行商问题(MTSP)的模型,并通过案例分析验证了其有效性。主要结论如下:

(1) 模型有效性:优化方案总接续费用为89,432元,较人工方案降低10.3%,且车底平均有效利用率提升至81.51% (人工方案为77.18%),表明模型能够显著减少资源浪费。

(2) 均衡性优势:车底有效利用率的方差为0.0039,远低于人工方案的0.021,证明优化方案在车底分配上更为均衡,有利于延长车辆寿命并简化检修计划编制。

(3) 资源节约:优化后仅需21辆车底即可完成130列次任务,较人工方案减少1辆车底,直接降低车辆购置与维护成本。

参考文献

[1] 中华人民共和国交通运输部. 全国城市轨道交通线路达325条[EB/OL].
https://www.mot.gov.cn/jiaotongyaowen/202501/t20250115_4162565.html, 2025-01-15.
[2] 牛惠民. 轨道列车时刻表问题研究综述[J]. 交通运输系统工程与信息, 2021, 21(5): 114-124.
[3] Pan, H., Yang, L., Liang, Z. and Yang, H. (2024) New Exact Algorithm for the Integrated Train Timetabling and Rolling Stock Circulation Planning Problem with Stochastic Demand. European Journal of Operational Research, 316, 906-929.
https://doi.org/10.1016/j.ejor.2024.02.017
[4] Huang, Y., Zhou, W., Xu, G. and Deng, L. (2025) Integrated Demand-Oriented and Energy-Efficiency Train Timetabling and Rolling Stock Circulation Planning for an Urban Rail Transit Line. Transportation Research Part C: Emerging Technologies, 171, Article ID: 104993.
https://doi.org/10.1016/j.trc.2024.104993
[5] Gong, C., Luan, X., Yang, L., Qi, J. and Corman, F. (2024) Integrated Optimization of Train Timetabling and Rolling Stock Circulation Problem with Flexible Short-Turning and Energy-Saving Strategies. Transportation Research Part C: Emerging Technologies, 166, Article ID: 104756.
https://doi.org/10.1016/j.trc.2024.104756
[6] Zhao, Y., Li, D. and Yin, Y. (2023) Integrated Optimization of Train Formation Plan and Rolling Stock Scheduling under Time-Dependent Demand. Computers & Operations Research, 150, Article ID: 106049.
https://doi.org/10.1016/j.cor.2022.106049
[7] Su, B., D’Ariano, A., Su, S., Wang, Z. and Tang, T. (2024) A Data-Driven Mixed-Integer Linear Programming Approach for Real-Time Rescheduling of Urban Rail Transit under Rolling Stock Faults. Transportation Research Part C: Emerging Technologies, 169, Article ID: 104893.
https://doi.org/10.1016/j.trc.2024.104893
[8] 郑锂. 网络化运营下城市轨道交通列车车底运用优化方法研究[D]: [博士学位论文]. 北京: 北京交通大学, 2013.
[9] 郑锂, 宋瑞, 肖赟, 等. 网络化运营下城市轨道交通列车车底运用计划编制的优化方法[J]. 中国铁道科学, 2014, 35(2): 104-110.
[10] 李洁, 何世伟, 何必胜. 成网条件下城市轨道交通车底运用问题研究[J]. 山东科学, 2013, 26(3): 88-94.

Baidu
map