基于技术作业时间协调的铁路客运站技术作业计划编制算法研究

何 洁，陈 韬，王永成，彭 岳

HE Jie1, CHEN Tao2, WANG Yong-cheng3, PENG Yue4

（1.中铁集装箱有限责任公司国内物流部，北京100055；2.西南交通大学交通运输与物流学院，四川成都610031；3.北京铁路局运输处，北京100860；4.西安铁路局西安站，陕西西安710000）

(1.Domestic Logistic Department, China Railway Container Transport Co., Ltd., Beijing 100055； 2.School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, Sichuan, China； 3.Transport Department, Beijing Railway Administration, Beijing 100860, China； 4.Xi’an Station, Xi’an Railway Administration, Xi’an 710000, Shaanxi, China)

基于技术作业时间协调的铁路客运站技术作业计划编制算法研究

何 洁1，陈 韬2，王永成3，彭 岳4

HE Jie1, CHEN Tao2, WANG Yong-cheng3, PENG Yue4

（1.中铁集装箱有限责任公司国内物流部，北京100055；2.西南交通大学交通运输与物流学院，四川成都610031；3.北京铁路局运输处，北京100860；4.西安铁路局西安站，陕西西安710000）

(1.Domestic Logistic Department, China Railway Container Transport Co., Ltd., Beijing 100055； 2.School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, Sichuan, China； 3.Transport Department, Beijing Railway Administration, Beijing 100860, China； 4.Xi’an Station, Xi’an Railway Administration, Xi’an 710000, Shaanxi, China)

通过分析客运站各类技术作业的特点，阐述到发线、调车机车、客技线、咽喉进路等设备上技术作业的同质性与共性，在此基础上确定技术作业富余时间，以最大限度固定使用和均衡使用设备为目标建立客运站技术作业计划编制模型，并给出模型求解思路及算法，最后通过算例验证模型及算法的有效性。

客运站；技术作业计划；作业时间协调；算法

1　概述

客运站技术作业计划编制是指在固定的列车运行图和车站设备资源条件下,在保证安全前提下为列车/车底在站各项技术作业安排相应设备和时间的过程,该问题属于 NP 难题,一般的方法是将其按作业流程和设备种类分解为到发线运用、调车机车运用、客车整备线运用等问题进行模型优化和求解[1-7]。吕红霞[4]分别确定到发线、牵出线、客技线、咽喉进路对调车机车作业的约束条件,然后对调车机车作业时间窗划分时间片段来确定作业起止时间,从而协调各项技术作业；陈彦[5]构造列车过站径路与调车机车整体优化模型,在时间窗范围内随机生成车底出入库时间方案,运用模拟退火算法进行求解；雷定猷等[6-7]利用排序理论建立车底停留线运用模型、车底取送模型,并引入满意度隶属函数协调车底出入库时间,提出基于分派规则和解改进优化策略的启发式算法进行求解。上述方法可以降低求解的规模和难度。但是,子模型间的协调复杂度较大,特别对一些大型客运站,存在复杂和特殊的作业流程,如动车组与普通列车混合安排、移位式客车准备作业等,如果按照作业环节分解成子问题,则子模型的数量和协调难度都会显著上升。

虽然客运站的股道、调车机车等各种设备特点不同,但就列车/车底在这些设备上的作业计划安排而言,都需要考虑以下因素：①确定每项技术作业占用的设备；②确定每项技术作业的起止时间；③保证每项技术作业满足相应的作业时间标准；④保证每项技术作业在时间和空间上的惟一性；⑤保证每项技术作业起止时间的接续性。因此,无论是到发线、调车机车、客技线、咽喉进路还是其他特殊设备 (如场间联络线等) 的技术作业安排,在优化目标及约束条件上都具有同质化的可能性。为了不依赖设备种类,提高算法的通用性和适应性,将客运站各项技术作业抽象为基于列车/车底的一组同质性的作业任务进行建模和求解。作业同质化的具体做法为：将每个列车/车底的每项作业赋予“作业起止时间、作业静动态性质、作业可用设备集合、是否安排进路”等属性,并按时间进行排序。

其中,作业可用设备集合、是否安排进路根据车站技术作业规则确定；作业静动态性质是指列车/车底在作业时处于静止状态还是运动状态,一般情况下,到发线、客车整备线、检修库线等设备上的作业称为静态作业,走行线、调车机车、牵出线等设备上的作业称为动态作业,静态作业和动态作业在时间安排和调整上有不同的约束规则,通过这项属性可以反映不同种类设备作业安排上的特点；作业起止时间中,只有列车到达、出发时间是确定的,其余各项作业时间都存在一个可调整的时间窗,需要算法确定。在上面的几个属性中,技术作业起止时间的确定是进行作业同质化的基础环节,也是客运站各项技术作业相互协调的关键,车站技术作业时间的协调具有多方案性,因而属于柔性调整。

2　数学模型

2.1 变量定义

根据客运站的技术作业要求,为每个列车/车底Ji确定一个按时间顺序排列的技术作业任务集合其中 Si表示列车/车底 Ji在车站需要安排的技术作业项数,定义每项技术作业 Rij的七元组变量为分别表示作业开始时间、作业结束时间、作业性质、技术设备编号(股道、调车机车、走行线等)、是否安排进路、进路安排开始时间、进路安排结束时间。其中：μij为 0-1 变量,如果是静态作业则取值 1,如果是动态作业则取值 0；θij为 0-1 变量,如果列车/车底 Ji的第 j 项作业需要安排进路则取值 1,否则取值 0。

列车/车底 Ji在每项作业上的技术作业时间标准为；进路占用时间标准为。

2.2模型建立

2.2.1技术作业富余时间的确定

大多数研究者[4-7]是在客运站定位式作业背景下探讨车底各项技术作业时间,只要确定了车底入库、出库时间,就可以确定各项技术作业起止时间,时间的调整也主要是在入库、出库时间窗内进行。对于作业流程复杂的车站,除了入库、出库时间需要确定,还可能存在多次转场或转线作业,这些转场或转线作业也存在时间窗。因此,复杂作业流程下的列车/车底技术作业时间的确定和协调较为复杂。

由于每个列车/车底在车站的到达时刻、出发时刻、技术作业内容和技术作业时间标准是确定的,因而每个列车/车底在站停留总时间与在站技术作业需要的最少总作业时间存在一个确定的差值这个时间差就是列车/车底的技术作业富余时间。列车/车底技术作业安排方案示意图如图1 所示,作业占用时间有实线和虚线 2 种表示,实线表示该作业规定的时间标准,虚线表示技术作业富余时间。

技术作业富余时间具有以下特点：①技术作业富余时间是常量,而且只能产生在静态作业上；②调车机车、走行线等动态作业的调整导致技术作业富余时间在各种静态作业上分布的变化。图1 中的2 个方案都可行,但 a 方案的技术作业富余时间分布在客车整备线上,客车整备线被占用的时间长,则后续车底可利用的客车整备线空闲能力就少；b方案将技术作业富余时间分布在到发线上,到发线被占用的时间长,则后续车底可利用的到发线空闲能力就少。因此,根据设备资源的紧缺程度,尽量将技术作业富余时间分布在非紧缺设备上,可以给后续列车/车底技术作业计划提供更好的编制条件,有利于更快形成优化方案。

2.2.2目标函数

第一优化目标是使各项技术作业最大可能地按照固定使用方案选择设备,第二优化目标是在第一目标基础上最大可能地实现设备均衡使用,即

式中：wi表示列车/车底 Ji的权值,列车等级越高权值越小,高等级列车应尽量优先安排；cijk表示列车/车底 i 的第 j 项作业安排在设备 k 上的费用系数,当符合固定设备使用方案时,cijk取值为 1,当该设备可用时取值为 10,当该设备不可用时取值为一个极大值 F；xijk为 0-1 变量,当列车/车底 i 的第 j 项作业安排在设备 k 上时 xijk= 1,否则 xijk= 0。

⑴ 式表示尽量按照设备固定使用方案安排作业；⑵ 式是列车/车底占用设备作业时间的方差值,该值越小表示设备使用均衡性越好。

将 2 个目标函数进行归一化处理,则

式中：α1和 α2是无量纲系数,可以根据用户对目标函数的偏好确定取值。

图1　列车/车底技术作业安排方案示意图

2.2.3约束条件

⑸ 式是设备占用惟一性约束,保证每个列车/车底每项技术作业只占用 1 个设备；⑹ 式表示每个列车/车底占用每项设备的作业时间要大于作业时间标准；⑺ 式表示每个设备上的任何 2 个列车的占用时间不能相互冲突；⑻ 式表示每个列车/车底只能占用 1 条接发车进路,其中分别为进路开始、结束占用 0-1 变量,表示列车/车底 i 的第 j 项作业安排在进路 k 上时,则取值为 1,否则取值为 0；⑼ 式表示列车/车底占用进路时间要大于进路占用时间标准；⑽ 式表示每条进路上任何 2 个列车的占用时间都不能相互冲突；⑾ 式为各项技术作业 Rij起止时间的取值,其中第 1 和 4 分项分别是列车占用到发线的到达作业起止时间和出发作业起止时间,第 2 分项是按顺序的其他静态作业起止时间,第 3 分项是按顺序的动态作业起止时间。

3　求解思路及算法

作业时间调整策略是指通过调整和改变技术作业当前起止时间的方法,从时间维度上来化解作业冲突、优化作业安排。调整规则为：①判断作业Rij是静态还是动态作业,如果是动态作业则可以直接调整时间,如果是静态作业则通过调整其紧邻的动态作业时间来达到调整静态作业时间的目的；②动态作业采用起止时间同时偏移法进行调整,不能改变动态作业时间长度；③每项作业Rij可调整的时间范围为Δtdik是作业 Rij前每项静态作业的等待时间；④以需要调整的动态作业当前时间为原点,以 Δtij为最大限度,向其前后搜寻能够安排该项动态作业的合理设备上的时间空档,如果找到合适时间空档则判断其是否满足化解冲突或优化作业的时间偏移需求,如果满足则将动态作业时间偏移至该空挡,否则终止调整算法；⑤时间调整后对紧前作业和紧后作业时间进行修正(时间修正的计算见 ⑾ 式),对修正后的作业进行冲突检测,如果存在冲突,则运用作业设备调整策略对冲突进行调整,如果调整无效,则终止调整算法,否则统计目标值,记录修改后的作业方案。

4　算例分析

以某站技术作业计划编制为例进行算例分析。该站有 2 条正线,9 条客车到发线,5 个站台,3 条到发场至客技场的联络线,17 条客车整备线,2 台调车机车 (1 台负责到发场与联络线间车底取送,1台负责客整场与联络线间车底取送),选取该站某天的列车时刻表,包含到发列车 96 对,其中有 22个车底 (含 2 个动车组)入库。其车站技术作业时间标准为：始发作业 40 min,到达作业 30 min,进出站咽喉占用 7 min,调车机车取送 10 min,客车整备 360 min,联络线作业 10 min。按照上述算法流程并用计算机编程开发的系统计算[8],得到车站出入库车底技术作业计划编制方案如表1 所示。

表1　车站出入库车底技术作业计划编制方案

方案给出了 22 个出入库车底及动车组的计划,由于动车组无需调车机车作业,因而只给出了其在联络线上的作业起止时间。与固定使用方案相比,系统给出的方案中,固定设备使用兑现率超过 90%,同时设备使用过程中的均衡性也较好,达到了客运站技术作业计划编制要求,证明算法可行、有效,能够大大减轻人工编制客运站技术作业计划的工作强度。

5　结束语

客运站技术作业计划的时间协调具有多方案性,属于柔性调整,运用基于时间协调的技术作业任务同质化求解算法寻求有效解,并以某车站为实例进行验证,表明该算法在降低客运站技术作业编制复杂度和规模性上的有效性,为编制复杂作业流程客运站技术作业计划提供了解决途径。为继续提升算法效率,还需要对作业设备调整策略和作业时间调整策略算法做进一步的研究。

[1] 史 峰,陈 彦,秦 进,等. 铁路客运站到发线运用和接发车进路排列方案综合优化[J]. 中国铁道科学,2009, 30(6) ：108-113. SHI Feng,CHEN Yan,QIN Jin,et al. Comprehensive Optimization of Arrival-Departure Track Utilization and Inbound-Outbound Route Assignment in Railway Passenger Station[J]. China Railway Science,2009,30(6)：108-113.

[2] Abbink E,van den Berg B,Kroon L,et al. Allocation of Railway Rolling Stock for Passenger Trains[J]. Transportation Seience,2004,38(1)：33-41.

[3] Billaut J,Moukrim A,Sanlaville E. Flexibility and Robustness in Scheduling[M]. London：John Wiley&Sons,2008.

[4] 吕红霞. 铁路大型客运站作业计划智能编制的优化技术和方法研究[D]. 成都：西南交通大学,2008.

[5] 陈 彦. 铁路客运站列车过站径路与调机运用优化[D]. 长沙：中南大学,2010.

[6] 雷定猷,张英贵,刘明翔. 铁路客技站车底作业排序模型与算法[J]. 铁道学报,2007,29(6) ：1-5. LEI Ding-you,ZHANG Ying-gui,LIU Mingxiang. Scheduling Model and Algorithm of Carriage Operations Arrangements in Railway Passenger Technology Stations[J]. Journal of Railway Society,2007,29(6)：1-5.

[7] 雷定猷,张英贵,王新宇,等. 铁路客技站车底作业耦合窗时排序模型与算法[J]. 铁道学报,2010,32(4)：1-7. LEI Ding-you,ZHANG Ying-gui,WANG Xin-yu,et al. Coupled Due Windows Scheduling Model and Algorithm of Carriage Operations Arrangements in Railway Technology Stations[J]. Journal of Railway Society,2010,32(4)：1-7.

[8] 陈 韬,吕红霞,王艳艳. 客运专线车站作业计划编制系统的研究[J]. 铁道运输与经济,2009,31(8)：12-15. CHEN Tao,LV Hong-xia,WANG Yan-yan. Study on the System of Railway Station Technical Work Planning for Passenger-dedicated Lines[J]. Railway Transport and Economy,2009,31(8)：12-15.

责任编辑：刘 新

Study on Drawing Algorithm of Technical Operation Planning of Railway Passenger Station based on Technical Operation Time Coordination

Through analyzing the characteristics of each technical operation in railway passenger station, this paper expounds the homogeneity and common character of the technical operation on equipments of arrival-departure line, shunting locomotive, passenger technical line and throat route. Based on above, the surplus time of technical operation was determined, and the drawing model of technical operation planning of passenger station was established by taking maximized stationary use and balanced use of equipments as the objects, and then, the solution idea and algorithm of the model was provided. In the end, through calculation example, the effectiveness of the model and algorithm were validated.

Passenger Station; Technical Operation Planning; Operation Time Coordination; Algorithm

1003-1421(2015)10-0017-06+7；U292.1

A

U291.6

10.16668/j.cnki.issn.1003-1421.2015.10.04

2015-05-28

国家自然科学基金项目 (61273242,61403317, 60776826)；四川省科技厅软科学计划项目 (2015ZR0141)；中央高校基本科研业务费专项资金资助 (2682015CX043)；中国铁路总公司科技研究开发计划项目 (2015X008-B,2014X004-D)