编组站调度计划0-1规划法
货运列车编组调度的科学性和合理性直接影响着货物运输的效率。某货运车站担负着国内东西和南北两大铁路干线上货运列车的编组调度任务，是我国沟通南北、连接东西的交通要道,素有铁路“心脏”之称。每天最多有400多列货车（无客车）在这里进出,有20000多辆（节）车辆在这里集结和解编。该站南北长6000余米、东西宽800余米，占地5.3平方公里（如附件1图），采用双向纵列式三级六场机械化驼峰编组站站型，即上行线方向（发往北、西）和下行线方向（发往南、东），上行线和下行线又分别包含有到达场、编组场和出发场。共有l51条站线,全长390多公里，其下行线的到达场12条，记为XD(k)(k ＝1,2,…，12)；编组场36条，记为XB(k)(k ＝1,2,…，36)；出发场24条,记为XF(k)(k ＝1,2,…，24)。上行线的到达场12条，记为SD(k)(k ＝1,2,…，12)；编组场36条，记为SB(k) (k ＝1,2,…，36)；出发场23条，记为SF(k)(k ＝1,2,…，23)。另外下行线和上行线各有一个转发场（用于下行线与上行线之间的转换场地），各有4条线路，分别记为XZF(k)和SZF(k)(k =1,2,3,4)。从每个到达场都有两条线路经驼峰区与相应的编组场相连，场区示意图如图1所示。注意：在这个问题里不考虑该车站装卸场的装卸作业。
图1：编组站场区示意图
实际中，货运列车编组的流程是：对于从上行线和下行线的各方向经过该站的每一列货运列车分别驶入各自的到达场内停靠，然后根据每一辆车的货物去向通过驼峰解体，分别向各自的编组场不同轨道线集结，从而编组成一列新的发往某一个方向的列车，最后转往上行线或下行线的出发场待发。编组工作每天分为白班和夜班两个班次，从早晨6:00点到18:00点为白班，18:00点到第二天早晨6:00点为夜班。每班各分为四个时段，白班：6:00～8:00，8:00～12:00，12:00～15:00，15:00～18:00；夜班：18:00～20:00，20:00～24:00，0:00～3:00，3:00～6:00。铁路管理部门希望车站的编组调度工作快速高效，衡量编组调度效率的主要指标是“中时”（从列车进入到达场至重新编组成新的列车驶入出发场后，其每辆车的平均时间，即每辆车在车站的平均中转停留时间）。每个时段都有相应的任务指标要求，一般要求列车在到达场停留时间最多不得超两个时段，中时最多不得超过8小时。
根据实际作业情况可知，机车将待解体的列车从到达场推到驼峰轨道线上，缓慢运动中进行解体操作，解体后的车辆靠惯性（无动力）运行至编组场轨道上。每组车辆（一辆或同方向的若干辆）从到达场经驼峰解体到编组场集结平均大约需要10分钟；从编组场牵引一列车到出发场大约需要5分钟；无调车（无需编组的列车，含专列）直接经过转发场做必要的技术处理后进入出发场大约需要15分钟；由上（下）行线编组场经转发场到达下（上）行线出发场一次约需20分钟。编组调度规程规定每辆重车不超过80T（含车自重20T），一般要求每列车总重量不超过4800T，总长最多不超过70辆。列车编组的各操作环节都是定班、定点、定人作业，自动控制流程。一般新编列车的车辆均发往同一方向，按到站次序由远至近依次排列，同一到站的车辆相连。通常情况下，货物列车的相关信息（列车车次、列车到站、编组车辆数、列车重量、列车长度等）有具体的预确报制度（附件3），但确切的信息在列车到站时方能确定。
附件2给出某一天24小时内经过该车站货运列车的相关数据，请根据实际情况和相关数据依次研究解决下列问题：
（1）试设计快速自动实现车辆编组调度方案的优化模型或算法，并给出附件2中车辆可行的编组方案（包括解体程序、轨道编号、车辆数量、集结程序、新列车的组成等），主要使每班的中时尽量地少。
（2）发往S1的货物和军用物资都为特别专供货物，需要保障优先运送。如果要求装载这类物资的车辆必须在2小时内发出（即中时不超过2小时）；同时发往地震灾区（向西方向某些车站）的救灾货物车辆要求中时不超过1小时，请你们给出相应的调度方案，并计算相应每班的中时。
（3）如果调度室在列车到达前两小时能够获取列车的相关信息，请利用这些信息制定可行的列车编组调度方案，使每班的中时尽量少，发出的车辆尽量多。
（4）如果因自然灾害导致S3以南的铁路中断，需要将有关的车辆转向东方向经E4向南绕行，请你们给出相应的调度方案，并计算相应每班的中时。
（5）假设编组完成的列车都能及时发出，按照你们的编组调度方案分析研究该编组站一天24小时最多能编组完成多少车辆，相应每班的中时是多少？即根据所建立模型进一步分析该编组站能否再提高资源的利用率和运行效率。
（6）目前我国的铁路资源紧张，需大于求，如何改进编组调度方案，才使得现有的铁路设施有更高的利用率，产生更高效益，谈谈建议和意见。
编组站调度计划0-1规划法
汤志高，谢冰，于琳
指导: 梁希泉、曹华林[2]
（[1]青岛科技大学数理学院，青岛266061）
([2]海军航空工程学院(青岛)航空机械系，青岛266041）
摘 要：本文针对货车编组问题,采用半分离式两阶段0-1线性规划模型对各阶段联合求解,对局部最优解采用调度时序图可视化表述。首先,对无、有调车辆分离,无调车采用启发式安排。有调车推峰顺序可以转化为零件加工问题,以驼峰总工作量最大、等待时间最小为目标建立模型I。列车解体时间与解体方向数成正比增长,但在未确定具体解体方案时无法确定(即模型I的独立),我们通过在模型II中对解体时间模糊化来处理两步独立的缺陷,从而达到两步规划的连续特性。车辆新编,决策变量属于多维结构,本文通过将多维稀疏变量转化为一维序列，有效解除其稀疏特性,形成二维决策变量建立规划模型II直接求解。其次，通过仿真创建模拟数据,运用主模型求解,得到了驼峰是编组站主要瓶颈的结论。最后,我们还对铁路资源的紧缺性、编组效率建模给出了较详细改进措施。
关键字： 0-1线性规划 列车编组 调度时序图
0-1 Programming of Marshalling Station Dispatching Plan
Tang ZHi-gao, Xie bing, Yu lin
Advisor: Liang Xi-quan, Cao Hua-lin[2]
([1] Department of Mathematical, Qingdao University of Science & Technology, Qingdao 266061)
([2] Department of Mechanical, Naval Aeronautical Engineering Academy ,Qingdao 266041)
Abstract:Considering the problem of freight train formation ,this paper adopts semi-sparated two-stages of linear 0-1 programming model for combined solution of each stage . Besides , in allusion to local optimal solution , we express it by sequence diagram . First , according to the split of the non-resorting or shunting trains,the former can be used heuristic arrangement . As to the later , it’s sequence of pushing train stock to hump may be transformed into part maching case . We regard the max of total hump workloads and the min of waiting time as objective functions , then establish ModelⅠ. Trains’ disintegration time is rising by disintengration direction number’s increasing . However , it can’t be confirmed under the condition of no concrete disintegration scheme . (That is the independence of Model I. ) Through fuzzification of disintegration time in Model II , we deal with the defects of independeces of Model I and Model II to reach continuous characteristic of two models’ planning . Trains’ new edition and decision variable are multidimensional structures . This paper transforms multi-dimensional sparse variables to one-dimensional series , which relieves the sparseness , then can get weo-dimensional decision variable . Afterward , build planning Model II for direct solution . Secondly , we gets the conclusion that the hump is the main bottleneck of railway marshalling . The method is establishing simulated data by simulation . In the end , we give out more detailed improvement measures for the scarcity of railway resources and the modeling of marshalling efficiency .
Keywords:0-1 Linear Programming, Train Dispatching, Dispatching Scheduling Chart
下载题目： 【Download】
下载原稿(适合学习，但请务必自己先练习后看本文，否则将事倍功半)： 【Download】
下载出版论文*： 【Download】
附2006全国研究生赛获奖名单： 【Download】
注：作者保留一切权利，转帖请注明出处，不得用于商业用途。*已出版论文禁止转载。