基于多智能体博弈的路网旅客列车运行图协调优化研究*

宋嫣然，倪少权，陈钉均，张燕，耿敬春

（1西南交通大学交通运输与物流学院硕士研究生，四川 成都 610031；2、3西南交通大学教授，四川 成都 610031；4西南交通大学讲师，四川 成都 610031；5中国铁路经济规划研究院有限公司教授级高级工程师，北京 100038）

0 引言

随着高速铁路的相继开通，我国已形成纵横交错的大规模复杂客运路网[1-2]，在日益复杂的客流结构影响下，跨线列车开行数量逐渐增多。在铺画列车运行图时，大量上线运行的跨线列车与本线列车的运行线间产生了诸多冲突，目前我国仍采用人工调整的方式完成跨线列车与本线列车运行线冲突消解，由于运行线间相互约束关系复杂，人工协调冲突时难以直观权衡跨线列车和本线列车的开行效益，存在“短视性”。随着跨线列车开行数量的上升，跨线列车和本线列车间的冲突越来越严重，由于消解冲突时需要牺牲部分运行线的开行效益，如何科学合理地制定运行线冲突消解策略，保证运行图中的全部运行线总体效益损失最小，实现跨线列车与本线列车运行线协调编制，已经成为旅客列车运行图协调优化的关键问题，决定着运行图的编制质量和综合效益。因此，有必要对该问题进行研究，实现路网旅客列车运行图协调优化，提高列车运行图编制质量及自动化水平。

对于旅客列车运行图的优化问题，国内外学者进行了大量且有意义的研究。大部分学者在进行运行图优化时未考虑跨线列车上线运行的情况：周文梁等[3-4]建立开行方案与运行图优化双层规划模型，设计模拟退火综合优化算法求解模型；黄鉴等[5]构建客运专线列车运行图优化模型，提出循环布线的模拟退火方法；赵宏涛等[6]提出列车运行图鲁棒性优化方法，构建运行图编制优化模型，设计改进的粒子群优化算法求解模型；刘敏[7]提出适用于单条线路以及不跨线运行成网线路的高速铁路列车运行图协调优化模型及求解方法；Zhang等[8]建立基于时空网络的双线铁路周期化列车运行图整数规划模型并求解；Yan等[9]建立了周期列车运行图多目标混合整数规划模型，设计Pareto边界算法求解模型；Meng等[10]建立以运行图利润最大化以及旅客需求满足度最高为目标的列车运行图综合优化模型并求解。部分研究考虑了跨线列车上线运行的情况，但将跨线列车运行线固定，视为优化调整本线列车运行线时的约束条件：江峰等[11]构建基于时空网络的列车运行图编制优化模型及求解方法，研究基于拉格朗日松弛的运行图局部调整方法；刘敏[12]提出客运专线列车运行图调整优化方法，构建本线列车增开模型和本线列车优化模型。

综上，目前关于旅客列车运行图优化问题的研究，绝大多数采用不考虑跨线列车开行或固定跨线列车运行线的方法进行列车运行线调整优化，这种方法虽然降低了求解难度，但忽略了跨线列车运行线与本线列车运行线的相互作用关系以及跨线列车开行对运行图编制优化的干扰，缺少适用性。因此，本文在已有研究的基础上，以多智能体技术为基础，运用博弈论的相关理论及方法，提出一种基于多智能体博弈的路网旅客列车运行图协调优化方法，确定消解冲突的运行线调整策略，协调跨线列车和本线列车的开行效益，并结合京沪高铁实例进行验证。

1 协调优化模型

1.1 问题分析与模型假设

本文将铁路客运路网视为一个系统，通过智能体间的合作与相互协调来解决跨线列车与本线列车运行线协调编制问题，进而实现路网旅客列车运行图协调优化。路网系统由多个区域组成，一个区域由多个车站以及连接这些车站的线路组成。系统内主要有两类智能体：区域智能体和车站智能体。每个区域及车站都有其对应的区域智能体和车站智能体，一个区域智能体内包含若干车站智能体。

列车运行图协调优化问题可以描述为：根据已确定的列车开行方案、理想始发时刻、跨线列车理想接入/交出时刻，寻找代价最小的运行线冲突消解策略，使各运行线在车站智能体达成良好协作，实现跨线列车与本线列车开行效益的协调优化，确保列车运行图整体效益的最大化。由于各运行线间相互作用、相互影响，任何一个智能体在进行决策时必然会受到其他智能体的影响，因此本文运用合作博弈论相关理论及方法，建立基于多智能体博弈的路网旅客运行图协调优化模型。

基于以上分析，本文在建立模型时做出以下假设：

1）线路区间均为复线区间，且上下行线路固定使用，列车在区间追踪运行，追踪间隔时间取相邻两站的出发间隔时间与到达间隔时间的最大值。

2）列车开行方案已知，开行方案中确定的各列车停靠车站不可取消，可以适当增加停站和改变停站时间。

3）给定一个各列车理想始发时刻以及跨线列车的理想接入/交出时刻，并可以在一定范围内调整。

4）忽略车站的进路冲突，如果车站能力允许，则列车可以在该站出发、到达及通过。

1.2 符号说明

本文模型中涉及的符号及参数定义如表1所示。

1.3 模型建立

在协调优化时，由于各智能体间的决策相互影响，因此各智能体间需要相互通信，确保每个智能体完全了解其他智能体的策略空间、效用函数等信息，即各智能体间的协调是基于完全信息的博弈过程[13]。

将一次博弈协调定义为：

每个智能体根据其掌握的信息I，在S中选择适当的策略，通过不断地协调，使各智能体的总体效用水平U达到最优，其中U为本模型的目标函数。

协调过程分为上、中、下3 个层次，上层协调是区域智能体间的协调，中层协调是车站智能体与区域智能体间的协调，下层协调是车站智能体间的协调，如图1所示。

图1 协调层次图

1.3.1 协调策略

当跨线列车与本线列车产生运行线冲突时，协调策略无非是调整跨线列车或者调整本线列车，即S={S1：跨线列车调整；S2：本线列车调整}。消解运行线冲突的方法主要有平移运行线、变更停站方案、变更运行线顺序三种。

列车在区间的运行时间由列车运行区段及列车种类决定，因此不管采用何种方法协调冲突，协调结果均为列车在某一或某几个车站的出发时刻发生改变，因此跨线列车的协调策略集为S1={S跨1：出发时刻不变；S跨2：出发时刻提前；S跨3：出发时刻延后}，本线列车的协调策略集为S2={S本1：出发时刻不变；S本2：出发时刻提前；S本3：出发时刻延后}。

1.3.2 目标函数

由于跨线列车和本线列车均按照其理想时刻及停站方案开行时会产生运行线冲突，在协调优化时，调整一些运行线在某几个途经车站的出发时刻，使其实际始发时刻、实际停站方案、实际接入/交出时刻与理想始发时刻、理想停站方案、理想接入/交出时刻产生一定偏离，这种偏离就是消解冲突带来的不利影响，引起偏离的根本原因是列车在途经车站的出发时刻发生了改变，即列车在途经车站出发时刻的改变间接影响了运行线效益。列车车站出发时刻的调整幅度影响着列车始发时刻、停站时间以及跨线列车接入/交出时刻的偏离程度，也决定了运行线的总体调整情况。因此，本文用列车车站出发时刻的调整值反映运行线调整情况，衡量协调优化时运行线冲突消解造成效益损失。

为达到运行图整体效益的最大化，需要选择使各方运行线总体效益损失最小的协调策略，实现跨线列车与本线列车在开行效益方面的相互协调。鉴于运行线间存在复杂的约束关系，某一运行线调整对其他运行线产生的影响和效益损失难以直接观测，本文运用合作博弈论整体效益最大的思想，从全局角度着手，以跨线列车开行效益U1和本线列车开行效益U2加权总和最大化构建目标函数，引入跨线列车影响权重ρ1和本线列车影响权重ρ2，分别代表跨线列车和本线列车在运行图中的相对重要程度。目标函数构建如下：

其中，ρ1+ρ2=1。

为了量化在协调优化过程中消解冲突对跨线列车与本线列车运行线效益造成的影响，赋予各运行线一个初始效益πl，代表该列车运行线以其理想始发时刻从始发站出发，按理想接入/交出时刻接入本线或从本线交出，在各停靠车站以最小理想停站时间铺画时的效益。为消解冲突调整运行线的部分运行线段车站出发时刻，引起始发时刻、接入/交出时刻的变动以及停站时间的延长（停站的增加或在站停时的延长），初始效益受到相应的影响发生变动。以调整跨线列车运行线l为例，该运行线的运行线段dlk的初始效益变动值∆qlk可由该运行线段的车站出发时刻变化值∆ulk及车站出发时刻改变对运行线效益的影响程度λl确定，如式(2)所示，其中λl表示改变车站出发时间对运行线l效益的影响程度，可根据编图的实际需求确定。根据各运行线段的初始效益变动值∆qlk，可以求得跨线列车运行线l的调整后总效益ql，如式(3)所示。

则所有跨线列车运行线的开行效益U1为：

同理，可得所有本线列车运行线的开行效益U2为：

将式(4)、式(5)带入式(1)中，则目标函数可表示为：

1.3.3 约束条件

为保证列车安全运行以及列车运行图协调优化过程中不产生新的运行冲突，调整后的所有列车运行线均需满足以下约束条件。

1.3.3.1车站能力限制约束

车站能力限制约束为任意时刻t车站c办理的列车数量不大于该站的最大列车办理数量，即

1.3.3.2行车间隔时间约束

行车间隔时间分为出发间隔时间和到达间隔时间，分别如图2(a)和图2(b)所示。

图2 行车间隔时间示意图

出发间隔时间约束为对任意车站的任意两相邻列车出发时间差不小于车站规定的发车间隔时间标准pk，即

到达间隔时间约束为对任意车站的任意两相邻列车到达时间差不小于车站规定的到达间隔时间标准qk+1，即

1.3.3.3区间不越行约束

任意两列车占用同一区间的时间段不能重合，在运行图中任意两条运行线不得在区间相交，如图3所示。

图3 区间越行示意图

则区间不越行约束可以表示为对于∀l，l′∈L，若ulk

1.3.3.4停站时间约束

列车停站时间如图4所示，任意列车在车站k的停车时间不小于规定的该列车在车站k最小停站时间tlk，即

图4 停站时间示意图

1.3.3.5运行线接续性约束

为保证运行线的接续性，列车从车站出发的时刻必须晚于列车到达车站的时刻，即

2 协调优化算法

2.1 运行线冲突消解次序确定

各运行线间的冲突可分为车站冲突和区间冲突两种，车站冲突又可以分为出发间隔冲突和到达间隔冲突，分别如式(13)、(14)所示。

区间冲突为两列车占用同一区间的时间重合，在区间发生越行，如式(15)所示。

消解冲突时会改变某些运行线的初始运行及停站情况，消解任何一个运行线冲突都会带动运行图状态变更，但由于各冲突的消解难度难以量化评价，本文在确定运行线冲突消解次序时采用出发时刻调整值最小原则，即优先选择消解时出发时刻调整值最小的冲突进行消解。设bk(l1,l2)是运行线l1、l2在车站k或区间(k,k+1)发生的冲突，是车站k消解冲突bk(l1,l2)时所需的最小出发时刻调整值，其计算公式如式(16)-(20)所示。

当冲突为车站冲突中的出发间隔冲突时，

当冲突为车站冲突中的到达间隔冲突时，

当冲突为区间冲突时，

根据各冲突的最小出发时刻调整值，每次选择调整值最小的冲突进行消解。若存在两个及以上冲突的调整值相同，则按照时间顺序依次消解。

2.2 多智能体博弈算法

2.2.1算法原理

由于运行线“牵一发而动全身”，冲突消解产生的不利影响也具有一定“传播性”，随着运行线调整范围及幅度的增加，冲突消解的不利影响从冲突发生点逐渐向周围运行线和车站传播。列车运行图协调优化的原则为降低消解冲突产生的不利影响，减少各运行线的纵向调整范围和横向调整幅度，克制不利影响的“传播性”。其中，纵向调整范围为消解冲突时需要调整运行线出发时刻的车站数量，横向调整幅度为运行线出发时刻调整值。基此，设计层层递进的多智能体博弈算法，采用逐步扩大纵向调整范围的方式寻找最优冲突消解运行线调整策略。

多智能体博弈算法的原理为：控制纵向调整范围，改变横向调整幅度，即在较小的纵向调整范围内尝试通过改变横向调整幅度消解冲突，若可以得出冲突消解策略，则无需继续扩大纵向调整范围；若无法得出冲突消解策略，则扩大纵向调整范围。首先进行车站智能体间的下层博弈协调，若通过下层博弈协调可以得到冲突消解策略，则无需进行中层博弈协调和上层博弈协调，因为下层博弈协调得到的冲突消解策略中涉及需要协调和调整运行线出发时刻的车站数量、需要调整的运行线数量和对运行图总体效益不利影响的波及范围必然小于中层及上层博弈协调。当下层博弈协调无法得出冲突消解策略时，则需进一步扩大纵向调整范围，增加协调车站的数量，进行车站智能体与区域智能体间的中层博弈协调。同理，若中层博弈协调可以得出冲突消解策略，则无需进行上层博弈协调。当中层博弈协调无法得出可行的冲突消解策略时，则需再次扩大纵向调整范围，进行区域智能体间的上层博弈协调。随着博弈协调层级的上升，协调车站范围逐步扩大，受到影响的车站和运行线增多，消解冲突带来的不利影响及其波及范围增大。

2.2.2多智能体博弈协调机制

本文中的多智能体博弈协调是一个基于反馈的马尔科夫决策过程，可由一个元祖表示。其中，N为进行博弈协调的智能体数量，Si={}si1,si2,...,sij,... 为智能体i策略空间，Oi为智能体i观测空间，U为运行图加权总效益，P为运行图环境状态空间。本文的多智能体博弈属于完全观测多智能体博弈，运行图状态可以被每个智能体完全观测，各智能体可以获得运行图现阶段的状态信息，并通过与其他智能体进行信息交互，形成自己的观测空间Oi。多智能体博弈协调过程主要包括多智能体间的博弈以及多智能体与运行图环境状态的反馈。其中多智能体间博弈确定运行线冲突消解的联合策略Se，其中联合策略Se由所有响应协调请求的智能体i决策动作Sij组成，单一智能体的决策动作Sij包括各运行线调整策略及具体调整数值。各智能体的联合策略生成方式为首先由发生冲突的车站智能体确定采取何种决策动作，在策略集S1、S2中选择具体策略，此时有以下四种调整策略：

1）调整冲突跨线列车运行线，使其从冲突车站智能体的出发时刻提前；

2）调整冲突跨线列车运行线，使其从冲突车站智能体的出发时刻延后；

3）调整冲突本线列车运行线，使其从冲突车站智能体的出发时刻提前；

4）调整冲突本线列车运行线，使其从冲突车站智能体的出发时刻延后。

为了得到使跨线列车和本线列车的总体效益最大的协调策略，发生冲突的车站智能体进行决策时需要遍历以上四种调整策略，寻找各种调整策略下的多智能体可行联合策略。

以调整策略1）为例，发生冲突的车站智能体调动途经该站的运行线进行协作，以调整最小值为调整初始值△，基于调整初始值根据式(13)-(15)判定途经该车站的其他运行线出发时刻是否需要调整，并根据式(16)-(20)计算相应的调整数值。此时，冲突车站生成初始决策动作完毕，将该决策动作传递给相邻车站智能体，相邻车站智能体根据接收到的信息以及式(7)-(12)判断是否有可行决策动作。若在冲突发生车站智能体采取初始决策动作时，其相邻车站智能体有可行决策动作，则各车站智能体的决策动作共同构成了调整策略1）下的联合策略；若其相邻车站智能体没有可行决策动作，此时相邻车站智能体将信息反馈给冲突发生车站智能体，冲突发生车站智能体在冲突运行线调整初始值的基础上，以1 min 为步长增加调整值，并重复上述动作进行循环，退出循环至少需要满足以下两个条件之一：

（1）找到联合策略；

（2）未找到联合策略，但冲突车站智能体决策动作中有运行线的始发时刻、总停站时间、列车接入/交出时刻调整值大于设定范围。

若找到调整策略1）下的联合策略，则计算各运行线调整引起的跨线列车、本线列车以及运行图加权总效益变动数值；若未找到，则证明调整策略1）下无联合策略。调整策略2）、调整策略3）、调整策略4）下的联合策略确定方法与调整策略1）相同，此处不再赘述。若调整策略1）、调整策略2）、调整策略3）及调整策略4）均无联合策略，则证明仅通过下层博弈无法得出可行的冲突消解策略，需调动更多车站智能体进行博弈，即进行车站智能体和区域智能体间的中层博弈。中层博弈过程与下层博弈相似，只是参加博弈的车站智能体数量增多，运行图调整范围及计算难度增大。当中层博弈无法得出可行的冲突消解策略，需进行区域智能体间的上层博弈，此时区域智能体类似于下层博弈协调中的车站智能体，各区域智能体确定本区域内所有车站的联合策略，然后通过信息传递和反馈完成区域间的联合策略确定。

经过多智能体间的博弈后，得出的联合策略Se数量若为1，那么该策略就是最终的运行线冲突消解策略；若大于1，则以调整后运行图加权总效益U最大的联合策略为最优冲突消解策略。执行联合策略后，运行图环境状态P会发生转移变更，多智能体与运行图环境状态的反馈则是在各智能体根据最优策略调整相应运行线后，运行图环境将状态转移信息反馈给各智能体的过程，各智能体接收反馈信息后更新观测空间Oi，为下次多智能体博弈做准备。

2.2.3算法流程

算法流程如图5所示。

图5 算法流程图

3 实例验证

京沪高速铁路是我国“八纵八横”高速铁路网络规划的南北走向主通道之一，与津秦高铁、胶济客专、徐兰高铁、宁杭高铁等7 条高速铁路衔接，开行了大量的跨线列车，且跨线列车比例呈逐年上升趋势，其路网结构如图6所示。

图6 京沪高铁及其衔接线路网络结构图

本文以京沪高铁为算例，协调优化其6:00—12:00时段的运行图。根据线路管辖情况及跨线车流接口站分布，选取北京南、济南西、徐州东、南京南、无锡东5个车站作为区域划分起始节点，将路网划分为5个区域，验证提出方法的有效性。

3.1 数据准备

3.1.1列车初始运行及停站数据

根据2021 年第三季度京沪高铁列车开行数据，京沪高铁6:00—12:00 时段上行方向开行本线列车26 列，跨线列车96 列，共122 列车，下行方向开行本线列车22 列，跨线列车108 列，共130 列车。基于2021 年第三季度各线路的列车开行方案，确定各列车的初始理想运行及停站数据。

3.1.2运行线初始效益πl及调整影响系数λl

设各运行线的初始效益为1 000，根据列车速度标尺、本线运营里程，将本线列车、跨线列车分别划分为3、4 个等级，各等级列车的影响系数取值如表2、3所示。

表2 本线列车分类及影响系数

表3 跨线列车分类及影响系数

3.1.3其他参数

设各车站的出发间隔时间和到达间隔时间分别为3 min 和2 min，时速300 km 及以上的列车起停车附加时分分别为2 min 和3 min，其余列车起停车附加时分均为2 min。列车既有及新增停靠车站的最短停站时间均为2 min。本线列车始发时刻以及跨线列车接入/交出时刻的可调整度均为10 min，各列车的总停站时间可延长度为60 min。

由1.3.2 节可知，算法的计算结果与跨线列车和本线列车影响权重ρ1、ρ2有关，ρ1、ρ2界定了跨线列车和本线列车在运行图中的重要程度，可通过调整参数ρ1、ρ2计算各列车不同重要程度下的运行图协调优化结果。

3.2 求解结果

本文运用MATLAB 软件实现基于多智能体博弈的路网旅客列车运行图协调优化，将列车初始理想运行及停站数据作为输入信息，调整参数ρ1、ρ2的取值，运行MATLAB 程序得到了不同的列车运行图协调优化结果。

3.2.1跨线列车与本线列车重要程度相同

跨线列车与本线列车重要程度相同时，参数ρ1、ρ2的取值为ρ1=ρ2=0.5。在这种情况下，跨线列车与本线列车运行线协调优化结果如表4 所示，各类列车出发时刻调整值及效益变动情况如表5所示。

表4 跨线列车与本线列车运行线协调优化结果

表5 各类列车出发时刻调整值及效益变动情况

3.2.2跨线列车比本线列车重要程度高

跨线列车比本线列车重要程度高时，设置两组参数取值，分别为ρ1=0.8、ρ2=0.2 和ρ1=0.6、ρ2=0.4。跨线列车与本线列车运行线协调优化结果如表6、7所示，各类列车出发时刻调整值及效益变动情况如表8所示。

表6 跨线列车与本线列车运行线协调优化结果（ρ1=0.8、ρ2=0.2）

表7 跨线列车与本线列车运行线协调优化结果（ρ1=0.6、ρ2=0.4）

表8 各类列车出发时刻调整值及效益变动情况

3.2.3本线列车比跨线列车重要程度高

本线列车比跨线列车重要程度高时，设置两组参数取值，分别为ρ1=0.2、ρ2=0.8和ρ1=0.4、ρ2=0.6。跨线列车与本线列车运行线协调优化结果如表9、10所示，各类列车出发时刻调整值及效益变动情况如表11所示。

表9 跨线列车与本线列车运行线协调优化结果（ρ1=0.2、ρ2=0.8）

表10 跨线列车与本线列车运行线协调优化结果（ρ1=0.4、ρ2=0.6）

表11 各类列车出发时刻调整值及效益变动情况

3.3 结果分析

实验结果显示，本文提出的方法可以通过智能体间的博弈协调将初始松弛运行图中的跨线列车与本线列车运行线冲突完全消解，得出各运行线的调整方案，并保证运行图中的全部运行线总体效益最大，实现跨线列车与本线列车在开行效益方面的协调。不同参数取值下的跨线列车、本线列车效益损失分布如图7所示，图中组别1、2、3、4、5的参数取值分别为ρ1=ρ2=0.5，ρ1=0.8、ρ2=0.2，ρ1=0.6、ρ2=0.4，ρ1=0.2、ρ2=0.8，ρ1=0.4、ρ2=0.6。由图7 可知，算法求解结果受参数ρ1、ρ2取值的影响，参数取值不同则跨线列车与本线列车效益变动值不同，各类列车的出发时刻调整情况不同，由于消解冲突造成的全图总体列车开行效益损失为5 259.6～8 508（视参数取值而定）。算法的参数敏感性如图8所示，从图中可以看出，本文所提算法对参数较为敏感，实际运用时需要根据运行图铺画需求合理标定参数ρ1、ρ2。

图7 跨线列车、本线列车效益损失分布

图8 参数敏感性示意图

综合以上分析，本文提出的基于多智能体博弈的路网旅客列车运行图协调优化方法具有有效性和可行性。

4 结束语

针对目前大量跨线列车上线运行造成的跨线列车与本线列车运行线诸多冲突，本文提出基于多智能体博弈的路网旅客列车运行图协调优化方法，制定消解冲突的运行线调整策略，协调跨线列车与本线列车开行效益使得运行图总体效益实现最大化。通过实例验证，该方法可以有效消解运行线冲突，实现跨线列车与本线列车开行效益协调优化，使运行图总体效益最大化，具有可行性。

为简化计算，本文在建立模型和设计算法时未考虑车站进路约束。下一步将考虑车站进路约束，研究列车运行图与车站到发线作业计划协同优化智能方法。