基于博弈思想的编组站阶段计划自动调整系统研究

张 明

（中国铁路南昌局集团有限公司， 南昌 330002）

编组站作为铁路货物列车的“制造工厂”[1]，是铁路枢纽及干线畅通的关键环节，它对加速全路车辆周转、提高运输能力起着举足轻重的作用，其作业效率和质量直接影响着铁路运输的效率和效益[2-3]。随着铁路信息化建设的不断推进，我国铁路编组站调度指挥完成了由手工作业到计算机辅助作业的过渡。目前在逐步向智能化调度作业发展。编组站阶段计划编制理论经过几十年的发展，已经积累了丰富的理论基础，但真正与实际现场结合却有许多困难。早期国外相关研究对编组站调度计划编制理论的研究较少，且注重从数学、运筹学的视角出发，如 Gulbodsen[4]、Grainic[5]等、Assad[6]和 Keaton[7-8]等人的研究。我国学者对阶段计划编制的优化模型以及计算机实现等方面的研究已较为深入，如刘军[9]、牛惠民[10]、何世伟[11]、王莹[12]等的研究。本文在上述研究的基础上，根据南昌铁路局向塘西编组站的编组站综合自动化（SAM）系统的应用情况，利用博弈思想，设计了一种协调优化编组站调机运用和配流问题的模型，并用于阶段计划自动编制和调整系统。

1 编组站阶段计划编制与调整

每个工作日开始前，铁路局调度所会下发本日计划任务给编组站。编组站通过制定和实施班计划、阶段计划和调车作业计划来保证日计划的顺利完成。为了完成班计划任务，编组站调度员要利用编组站技术作业表，记录编组站运输工作的实际完成情况，并以每3 h为一个阶段，在表上安排下一阶段的接发列车和调车工作，指挥全站的运输生产。

1.1 编组站阶段计划编制

编组站阶段计划的编制方法如图1所示。其中，基础资料收集内容包括班计划规定的各项任务、时间要求和本阶段重点工作；各到达列车的到达时刻及编组内容（实绩）；各车场现车情况；调机作业进度（实绩）；机车整备、扣修、站内施工等资料。而后根据场内存车和解编车流推算下一阶段的车流。跟据推算车流和基础资料内容铺画到、发列车运行线，填写到达列车编组内容，确定到达列车的解体顺序，确定出发列车的编组时机，确定取送内容和时机。并编制到发线运用计划和调机运用计划。

图1 阶段计划编制方法

1.2 编组站阶段计划调整规则

编组站的作业和车流随着时间不断变化，阶段计划的调整必须具有实时性和有效性。所以本文采用循环调整和分层规划调整两个调整规则，对阶段计划进行调整。

1.2.1 循环调整规则

编组站阶段计划根据现有作业进度等基础数据在设定的计算时域进行滚动迭代。可以随机制定开始调整的时间点和迭代时域。阶段计划循环调整依据上一阶段的阶段计划，根据实际作业情况和作业进度进行滚动调整。不断地根据现有基础数据更新约束条件，并将新的约束条件带入到后续调整计算中去。如此调整的阶段计划更能符合现场实际作业情况，提高阶段计划的兑现率和编组站的工作效率，满足实时性的调整原则。

1.2.2 分层规划调整规则

编组站有大量的调车作业，作业复杂。各项作业之间需要相互配合协调，很难建立统一的、整体的优化模型。因此需要建立分层规划调整模型。本文利用分层规划，将阶段计划调整问题分为车流分配和调机运用协同调整、到发线应用优化两个问题。既保证了调整决策的整体优化，又大大降低了问题的复杂程度。其中到发线应用优化问题的相关研究已经比较成熟，本文重点研究车流分配和调机运用协同调整问题。该规则满足有效性的调整原则。

2 基于博弈思想的调机运用与配流协同优化

2.1 演化博弈理论

与古典博弈理论不同，演化博弈理论的基本假设是参与人的理性度是有限的。在这一问题中，参与人的各项决策均处于连续的动态变化过程中，为了实现最终的均衡目标，必须历经一个复杂的演化发展过程。这里存在一种可能性，即这一问题永远无法实现最终的均衡目标，而是始终处于无限接近均衡的状态。如果问题存在多种均衡模式，那么最终处于哪一种均衡模式就取决于演化博弈的初始条件以及演化的具体过程和动态更新路径。演化博弈理论在问题分析中更加适用于实际情况，更加具有灵活性和实用性。

2.2 模型假设

为适应南昌铁路局向塘西编组站调车作业和站场结构复杂的情况。根据演化博弈理论思想，将车流的集结过程和出发计划类比为生产车间的一个加工任务。为了保证先交货的加工任务无间断加工（车流集结为无间断连续集结），加工完成后进行第2个加工任务的加工（集结完毕后进行后续出发列车的车流集结）。因此，一般先确定车流的编组顺序，然后根据编组顺序确定最优解体顺序。可以将牵出线和担当编组任务的调车机看作生产线上第1个加工机器，将驼峰和担当推峰解体任务的调车机看作生产线上第2个加工机器，将编组列车的编组完成时刻看作加工任务的模糊交货期。因此，编组站解编顺序调整问题可进行简化，并类比为一个带模糊交货期的无等待流水车间调度问题 ，其甘特图如图2所示。

此问题的目标为：在满足每个客户的最小满意度阈值的条件下，使得所有客户满意度的加权和最大。

2.3 模型建立

本文建立的博弈模型包括多个有博弈关系的局中人（车流的集结过程和出发计划）、每个局中人的策略集合（解体和编组方案中各列车的解编顺序）、每个局中人采取各自策略后得到的收益函数（编组列车的编组完成时刻）。

图2 无等待流水车间调度问题甘特图

依照演化博弈理论的思想，每个车流的集结过程和出发计划都想通过竞争最佳解编顺序来获得该车流最早的编组完成时刻，若某车流的集结过程和出发计划的编组完成时刻不能达到期望值，该车流的集结过程和出发计划就会寻求更好的解编顺序位置。

2.3.1 参变量定义

R：足够大正数；

AR={ar1, ar2, …, arm}：数量为m的本阶段内到达解体列车的集合（包含已经集结在编组场内的现车）；

SE={se1, se2,…, sej,…, sen}：数量为n的本阶段内编组出发列车的集合（不包含已整编的待发列车）；

GO={1, 2,…, B} ：编组去向集合；

Tj

编组：编组开始时刻；

t解体：待解列车在站进行解体作业的标准时间；

arib：到达列车ari中拥有到达编组站的编组去向号b(1≤b≤B)的车辆数；

sejb：待发列车sej中拥有出发编组站的编组去向号b(1≤b≤B)的车辆数；

seijb：从 ari(i=1, 2,…, m)中配入 sej(j=1, 2,…, n)中的去向号为b(1≤b≤B)的车辆数；

nj： sej满轴车辆数 ；

Pj：配流方案；

ωij：0-1变量，若sej能够接续ari，则ωij取1，否则取0；

σj：0-1变量，若 Pj≥ 0，σj取 1，否则取 0；

AM={1, 2,…, m}：调机集合；

ari(i=1, 2,…, m)：到达解体列车；

Ti到达：到达时刻；

t到达：到达列车在站内进行技检作业的时间标准；

t解体：待解列车进行解体作业的时间标准；

Xa：调机a固定作业的总数量；

αia：0-1变量，若调机a(1≤a≤A)负责进行到达列车ari(i=1, 2,…, m)的解体作业，αia取1，否则取0；

βja：0-1变量，若调机a(1≤a≤A)负责进行出发列车 sej(j=1, 2,…, n)的编组作业，βja取1，否则取 0；

Tj出发：出发列车sej(j=1, 2,…, n)的出发时刻；t编组：编组列车的技术作业时间标准；t出发：出发列车的技术作业时间标准。

2.3.2 配流约束

同去向配流约束：

基本去向组车辆数约束：

车流的接续时间约束：

列车编成车辆数约束：

2.3.3 解体约束

列车解体占用调机的时域约束：

到达列车解体作业可行性约束：

解体调机作业的时域约束：

双推单溜约束：

作业交叉约束：

2.3.4 编组约束

编组调机约束（同一出发列车只可使用一台编组调机）：

出发列车正点发车约束（开始编组时刻须早于满足出发列车技术作业时间要求的最晚开始编组时刻）：

调机作业时域约束（不同出发列车不可同时使用同一台调机进行编组作业）：

牵出线时域约束（不同调机进行编组作业时不可同时占用同一牵出线）：

作业交叉约束（编组作业不可与调机的固定作业相互冲突）：

2.3.5 目标函数

以出发列车的正点满轴出发列车数最多，定义目标函数为：

相关参数区间如下：

3 编组站阶段计划自动调整系统设计

本文利用UML对编组站阶段计划自动调整系统进行设计。

3.1 系统功能设计

编组站阶段计划自动调整系统的功能模块有：数据自动分类汇总模块、阶段计划自动调整及人工干预功能模块、图表及调整结果显示模块、日志及文档管理模块、用户管理模块。其中阶段计划自动调整及人工干预模块利用数据自动分类汇总模块提供的基础信息，根据本文第2节中建立的优化模型对调机运用和配流进行优化，并通过图表及调整结果显示模块进行输出。

图3 系统功能结构图

系统功能结构如图3所示。

3.2 系统动态模型设计

系统动态模型设计主要包括调机运用与配流协同调整模块设计、数据管理模块设计、网络消息处理模块设计和规则检查模块设计4个部分，详细模型如图4所示。当需要对阶段计划进行调整时，调机运用与配流协同调整模块首先从数据管理模块获取当前可用资源，包括调机状态、到发线状态、现车信息、驼峰状态、牵出线状态等。而后通过套用调机运用与配流协同调整模型，根据规则检查模块提供的规则约束，计算出调整后的阶段计划。网络消息处理模块主要负责模块间的消息通信。

4 软件仿真实现

根据南昌铁路局向塘西编组站SAM系统应用情况，选择将向塘西站现场数据导入SAM系统仿真环境，并布置系统，对向塘西站进行1：1仿真模拟。阶段计划自动调整效果如图5所示。在点击调整计划后，系统自动生成了两台推峰调机的推峰计划，并且根据作业先后顺序排序。如按照调整后的作业计划，能够最高效率的满足始发车流的集结和出发。点击应用调整方案后，该计划会下达至值班员的操作终端。由值班员具体安排作业。

5 结束语

阶段计划自动编制的研究成果很多，但在结合现场实际使用时却困难重重。本文利用博弈思想对编组站阶段计划自动编制和调整进行数学建模和系统建模，在南昌铁路局向塘西编组站SAM系统仿真环境的支撑下验证了系统的正确性和有效性，具有一定的理论和技术意义。下一步的研究目标是充分结合现场作业，研究局、站一体化情况下的阶段计划自动编制和调整问题。

图4 系统动态模型图

图5 阶段计划调整自动调整界面