旅客列车初始布点优化模型及算法研究.doc

旅客列车初始布点优化模型研究摘要：列车运行图是铁路列车运行组织的基础，是铁路运输部门的基本工作计划。而旅客列车运行方案图决定着列车运行图的骨架，其关键是确定列车的出始布点问题。现有文献对列车方案图的研究主要是单一的考虑方便旅客旅行，到发线运用等因素。本文详细分析了方便旅客旅行、到发线运用及客技线使用等编制旅客列车运行方案的约束条件，以车底运营台数最少为目标，建立了旅客列车最优初始布点的目标规划模型。运用文中所建模型，可以方便地得到既方便旅客旅行，又经济合理使用车底，并且满足到发线和客技线协调使用的旅客列车始发和终到时间。关键词：旅客列车；列车运行图；运行方案；目标Research on Optimization Model of Initial Schedule of Passenger TrainsCHEN Dingjun, NI Shaoquan,(School of Traffic and Transportation, Southwest Jiaotong University, Chengdu, Sichuan 610031,China)Abstract: Train working diagram is the base of railway transportation management and the fundamental working plan of transportation department. The running scheme of passenger train whose essence is to determine the initial schedule decides the skeleton of making the passenger train working diagram. Taking the minimum of passenger carriage as the objective function and considering some constraint conditions such as the convenient to the passengers and the coordinate utilization of arrival and departure tracks and parking lines for rolling stock, an objective programming model for optimizing the initial schedule of passenger trains is constructed. The original time and the end time of passenger trains that satisfy the convenient to the passengers, economical carriage and the coordination between the utilization of arrival and departure tracks and parking lines for rolling stock can be obtained expediently by using this model. Key words: passenger train; train working diagram; running scheme; objective programming编制旅客列车运行图的关键是编制旅客列车运行方案。现有许多文献对编制旅客列车运行方案从不同角度进行了讨论，文献1将旅客列车运行方案图的定量优化编制问题归结为一个多目标问题，并提出用分层序列法求解的基本思想，并给出了方便旅客旅行的算法。文献2把客运站到发线运用优化目标分解为方便旅客旅行、有利于保证行车作业安全与行车技术作业和有效地使用车站各种既有行车技术设备等三个子目标, 并分别建立其优化模型。文献3利用排序理论,以总晚点数最小为第一目标和调机均衡运用为第二目标建立具有柔性流水作业性质的车底取送模型,以客技站股道均衡运用为目标函数构造车底停留线运用模型。文献4考虑客运站到发线能力,以及旅客列车必须在合理的时间域发车等约束条件下,建立旅客列车发车时间域的目标规划模型。但是现有模型都只讨论了该问题的某一个方面，没有综合考虑方便旅客旅行，车底运用、占用客技线和列车占用到发线的因素，这就使得所建模型本身具有局限性。本文详细分析了方便旅客旅行、到发线运用及客技线使用等编制旅客列车运行方案的约束条件，以车底运营台数最少为目标，建立了旅客列车最优初始布点的目标规划模型。本文研究中，设为某类车站，为从站开往路网各站列车的总对数，为与站开往返列车对的任一站，并且仅考虑两站成对往返开行的列车共用车底的情况，暂不考虑车底套用。In this paper, we suppose express a certain station, express the total pairs of trains bound for the other stations from station in the railway network. There are pairs of passenger trains between stationand station.we only consider the condition of sharing passenger carriage.station express a station with the road from the station bound train stations Net total of a few, with the Station from the train station to any one, and only two pairs of trains will start from the bottom of the vehicle to circumstances, will not consider the bottom of the vehicle apply.1 目标函数的确立表示第对列车在站的始发时间；表示第对列车在站的终到时间；表示第对列车在站的始发时间；表示第对列车在站的终到时间。表示第对列车从站至站的旅行时间，表示第对列车车底在站实际停留时间；表示第对列车从站至站的旅行时间，表示第对列车车底在站实际停留时间；表示第对列车的车底周转时间；表示第对列车车底需要数（且）。则 则所求目标函数为 .其中，表示第对列车从站至站的旅行天数；，表示第对列车从站至站的旅行天数。则和是确定的，因此，车底需要数取决于和，故该目标函数可以转换为 其中，表示第对列车车底在站的过夜天数；，表示第对列车车底在站的过夜天数。2 约束条件确定(1)方便旅客旅行约束一般地，客车应在不早于早上7点，不晚于24点的时间范围出发和到达：，(2)最小安全时间间隔约束始发列车应该满足最小安全时间间隔，设最小安全时间间隔为，(3)车底必须满足在配属站/折返站作业的最小停留时间：设表示车底在配属站作业的最小停留时间；表示车底在折返站作业的最小停留时间；，；，(4)到发线约束根据列列车开始占用和结束占用站/站到发线的时刻将列列车划分到为/个时间片5，到发线约束站/站类似，故只考虑列车到达站的情况。表示占用时间片k的列车集合，1)到发线能力约束：设表示站接发旅客列车的到发线数, 2)一列列车同一时间片（）内只能占用一条到发线 3)一条到发线同一时间片（）最多只能接发一列列车 4)同一到发线接发相邻列车时间间隔应大于最小安全时间间隔 为0-1变量，表示列车i占用到发线j，表示列车i不占用到发线j； m表示需要使用到发线的列车总数； 表示列车i占用到发线开始时间；表示列车i占用到发线结束时间；表示列车与列车使用同一条到发线时所需安全间隔时间。 (5)客技线约束1) 客技线能力约束设第（）时间片的客技线能力,到达列车中需要占用客技线的列车集合为, ，2)一列列车车底只能占一条客技线3)一条客技线同一时间片最多只能被一个车底占用 4）占用同一客技线的相邻车底时间间隔要满足最小安全时间间隔 为0-1变量，表示车底使用客技线j，表示车底不占用客技线j；l表示客技线总数；表示需要使用客技线作业的车底总数； 表示车底占用客技线开始时间；表示车底占用客技线结束时间；表示车底与车底使用同一条客技线时所需安全间隔时间.3 旅客列车初始布点优化模型综上所述，旅客列车初始布点优化模型为本文综合考虑方便旅客旅行、车底运用占用客技线和列车占用到发线的因素，建立了旅客列车初始布点优化模型。所建模型为计算机编制旅客列车运行图提供了理论基础。接下来将对该模型的有效算法进行研究。参考文献1符卓.旅客列车运行方案图优化编制方法的研究J.铁道学报，1996（8）：1016.Fu zhuo. Study on optimal methods for making passenger train timetables. Journal of the China Railway society,1996,18(6),10-17.2谢楚农,黎新华.铁路客运站到发线运用优化研究J.中国铁道科学，2004,25（5）：130-133.XIE Chunong , L I Xinhua. Optimization Research for Utilization of Arrival and Departure Tracks in Railroad Passenger Station.CHINA RAILWAY SCIENCE3 雷定猷,张英贵,刘明翔.铁路客技站车底作业排序模型与算法J.铁道学报,2007,29(6):1-6.LEI Dingyou1 , ZHAN G Yinggui1 , L IU Mingxiang. Scheduling Model and Algorithm of Carriage Operations Arrangements in Railway Passenger Technology Stations.4陈团生