第３９卷第１６期
２００９年８月数学的实践与认识ＭＡＴＨＥＭＡＴＩＣＳＩＮＰＲＡＣＴＩＣＥＡＮＤＶ０１．３９Ｎｏ．１６ＴＨＥＯＲＹＡｕｇｕｓｔ，２００９
货运列车编组调度问题的模型与算法研究
刘盾１，赵军２，韩冬３，陈滋利４
（１．西南交通大学经济管理学院．四ＪＩ』成都６１００３１）
（２．西南交通大学交通运输学院。四川成都６１００３１）
（３．西南交通大学信息科学与技术学院，四川成都
（４．西南交通大学数学学院，四川成都６１００３１）６１００３１）
摘要：从双向编组站运输生产实际情况出发，以最大化车站发出车数和最小化车辆在站平均停留时问（中
时）为目标，综合考虑解体、编组调机能力限制、到发列车车流接续、车流在站停留时间约束的影响，建立了车
站货运列车编组调度问题的多目标非线性混合整数规划模型，结合该优化模型难以求解的特点，将编组调度
问题分解为配流、待解车列解体和待编车列编组三个子问题，进而设计了求解该问题的分层启发式算法，对
正常和特殊运输组织条件下的列车编组调度问题进行了求解．
关键词：编组站；调度；中时；启发式算法
０引言
货运列车在各编组站能否顺利调度，物资能否顺利运送，已成为连接我国东西、沟通南北经济命脉的纽带．一般而言，货车驶入某编组站要经过“到达一解体一集结一编组一出发”这五个作业过程，作为货运列车编组调度的核心，如何合理地组织列车解体、集结和编组作业，降低待解、待编、待发等现象的发生率，减少货车停留时间延长带来的损失，并将解编作业进行优化，成为提高整个编组调度效率，优化整个计划体系的关键内容之一［１七］．本文根据实际情况，建立“编组站中转停留的时间尽量少”的优化模型，并通过计算机仿真技术实现编组优化调度方案的制定．
１符号说明
ⅣＤ。：本时间段内，本系统的到达解体列车数量（包括时段初的现车列车）；
以ｄ。：本时间段内，本系统的待解车列数量（包括时段初的现车车列），ｎｄ。＝ⅣＤ。；
ⅣＤ。：本时间段内，本系统的无改编中转列车数量；
ⅣＤ：本时间段内，本系统的到达列车数量，ⅣＤ一ⅣＤ。ＵⅣＤ：；
ｎｆ。：本时间段内，由本系统编组的，将在本系统始发的集结车列（简称自编始发车列）１．１常量说明数量；
，ｚ厂２：本时间段内，由本系统编组的，去上行系统始发的交换车列（简称下行交换车列）数量；
ｒ／ｆ３：本时间段内，由上行系统编组的，来本系统始发的交换车列（简称上行交换车列）收稿日期：２００９－０４－３０
１６期刘盾，等：货运列车编组调度问题的模型与算法研究１６３数量；
ｎｆ：本时间段内，本系统的编组车列数量，ｎｆ＝ｎｆ。Ｕｎｆ２；
ⅣＦ：本时间段内，本系统的待发列车数量，ＮＦ—ｎｆ。Ｕｎｆ３ＵⅣＤ：；
丁，：本时间段的开始时刻；Ｔ。：本时间段的结束时刻ｌ
咄：解体延误惩罚系数，ｉ一１，２，…，ｎｄ，；Ａ，：编组延误惩罚系数，．『＝１，２，…，ｎｆ；
ｋ：一个待解车列的解体过程对应一个时段ｋ，ｋ一１，２，…，ｎｄ。；
愚五：一个集结车列的编组过程对应一个时段矗五，ｋｋ一１，２，…，ｎｆ；
Ａｉ：第ｉ车列的最早可能解体时刻，如果是现车，等于本时间初时刻，否则等于列车到达时刻，ｉ＝１，２，…，ｎｄｌ；
Ｅ：第ｉ车列的到站数，ｉ＝１，２，…，ｎｄ。；
ｆＪ，：第ｉ待解车列的解体时间，ｉ＝１，２，…，ｎｄ。；
ｚ优以第ｉ待解车列中厂到站的重车数，ｉ一１，２＇．．・，ｎｄ。，ｆ＝１，２，…，Ｆｉ；
ｅｍｌ，．第ｉ待解车列中厂到站的空车数，ｉ一１，２，…，ｎｄ。，ｆ一１，２，…，Ｆｚ｝
ｍ墨：编组Ｄ去向集结车列的最大长度，Ｄ∈｛ｗ，Ｅ，５，Ｎ｝；
Ｇ呈：编组Ｄ去向集结车列的最大重量，Ｄ∈｛Ⅳ，Ｅ，ｓ，Ⅳ｝；
加ｉ：第．『集结车列的编组和转线时间，Ｊ一１，２＇．－・，ｎｆ；
Ｄ：编组方向，Ｄ∈｛Ⅳ，Ｅ，５，Ⅳ），分别表示东、西、南、北四个方向ｌ
｛Ｄ，）：编组方向Ｄ上的车站集合；
ＤＳ：到达场股道数量；ＣＳ：出发场股道数量．
１．２变量说明
ｔ。：待解车列在时段ｋ解体开始时刻，ｋ＝１，２，…，ｎｄ，；
Ｊｉ：０—１变量，当第ｉ待解车列在时段ｋ解体时，取为１，否则为０；ｉ＝１，２，…，ｎｄ，，ｋ一１，２，…，ｎｄｌ；
ｔｔ川集结车列在时段五尼编组开始时刻，ｋｋ一１，２，…，ｎｆ；
Ｂｉ。：０—１变量，当第歹集结车列在时段五五编组时，取为１，否则为０，Ｊ＝１，２，…，ｎｆ，ｋｋ＝１，２，…，ｎｆ；
Ｕ，：０—１变量，当待解车列解体延误时，取为１，否则为０．ｉ＝１，２，…，ｎｄ，；
０，：０—１变量，当集结车列编组延误时，取为１，否则为０．歹＝１，２，…，ｎｆ；
Ｑ夕：０一ｌ变量，当第歹集结车列编组Ｄ去向车辆时，取为１，否则为０，＿『＝１，２，…，咒厂，Ｄ∈｛Ⅳ，Ｅ，５，Ⅳ）；
户绺‘：０—１变量，当在时段ｋ解体的待解车列ｉ中的重车为时段点五编组的集结车列歹提供接续车流时，取为１，否则为０；
ｇ绺‘：０—１变量，当在时段ｋ解体的待解车列ｉ中的空车为时段志志编组的集结车列Ｊ提供接续车流时，取为１，否则为０；
ｌｘｇｙｊ：集结车列Ｊ编组时吸收的待解车列ｉ中，到站的重车数；ｉ＝１，２，…，以ｄ。，ｆ＝１，２，…，Ｆｆ＇Ｊ＝１，２，…，ｎｆ；
ｅｘ。，Ｊ：集结车列歹编组时吸收的待解车列ｉ中，到站的空车数；ｉ一１，２，…，挖ｄ。，厂一１，２，…，Ｆ。，Ｊ＝１，２，…，ｎｆ；
１６４数学的实践与认识３９卷
ｑ¨０—１变量，当到达列车ｉ和ｉ７在列车占用股道上有时间冲突时，取为１，否则为Ｏ；局，：０—１变量，当始发列车歹和歹’在出发占用股道上有时间冲突时，取为１，否则为０．２模型假设
１）在考察当天，不考虑上行线和下行线到达场、编组场和出发场的容量问题；
２）在考察当天开始计算时（即早上６点时），上行线和下行线的编组场和出发场均没有停放列车；
３）在考察当天中途不会发生由自然或人为原因造成的故障；
４）假设驼峰实行双推单溜作业方案时，解体作业时间标准为ｌｏ分钟；从编组场编组并牵引－－Ｎ车到出发场为２０分钟；从由上（下）行线编组场编组经转发场到达下（上）行线出发场为３０分钟；
５）编组调度规程规定每辆重车不超过８０Ｔ（含车自重２０Ｔ），一般要求每列车总重量不超过４８００Ｔ，总长最多不超过７０辆；
６）下（上）行无调车、上（下）行交换车在走形路径上都不存在干扰；
７）机车数量满足实际工作需求，出发场能力不受限制，编组完成的列车都能及时发出；８）根据研究车站场区布置图，假定其驼峰采用双推单溜的作业方案，解体作业过程中不能再解体；峰尾只一条编组线可用于列车编组，编组作业过程中不能再编组．
３优化模型
双向三级六场编组站下（上）行改编系统在编组东、南（西、北）方向集结车列时与上（下）行改编系统相互独立，在编组西、北（东、南）方向集结车列时又与上（下）行改编系统在出发场相互联系，主要是协调使用出发线．这里我们假设出发场能力不受限制，编组完成的列车都能及时发出，即两个改编系统相互独立，特点相同，只需要对某一个改编系统的某个时间段的车辆编组调度问题进行建模，便可以描述整个车站的车流变动情况．下行改编系统货运列车编组调度的优化模型为：
１）到达场股道数约束
ｔＩ＋ｔｊ，・Ｊ：一Ａ，ＮＭ・（１＋％，～以），ｉ一１，２，…，（ｎｄｌ—１）
ｉ７＝２，３，…，ｎｄｌ，ｋ一１，２，…，ｎｄｌ（１）
ｉ７一ｌ
西∑口ｆＩ，ＮＤＳ一１，ｉ，＝２，３，…，ｎｄｌ（２）
式（１）表示待解车列ｉ和ｉ７在到达场占用股道时，发生冲突的条件；式（２）表示到达场股道数对股道占用时间发生冲突的列车数的限制条件．
２）车列解体开始时刻约束
材ｌ
ｔｌ＋１一ｔ＾一∑ｔｊｉ・以≥０，五＝１，２，…，（ｎｄｌ一１）（３）
ｌ＝１
ｎｄｌ
０≤ｔ＾一∑Ａｆ・以≤６，ｋ＝１，２，…，（ｎｄｌ—１）百（４）
耐ｌ，
∑以＝１，五＝ｌ，２，…，ｎｄｌ（５）
１６期刘盾，等：货运列车编组调度问题的模型与算法研究１６５
∑以一１，ｉ＝１，２，…，ｎｄ，函（６）
式（３）表示驼峰单溜放第ｋ＋１个时段对应车列解体开始时刻必须在第忌时段对应车列解体结束之后；式（４）表示第ｋ时段车列解体开始时刻必须在车列最早可能解体时刻之后，且在到达场停留时间不超过６小时；式（５）为逻辑约束，表示同一时段只能解体一个待解车列；式（６）为逻辑约束。表示同一待解车列只需在一个时段解体．
３）车流分配约束
≈，＋】
∑ｌｘ，疗＝ｌｍ巾ｉ＝１，２，…，ｎｄ。，ｆ∈Ｆ，
，＝１（７）
（８）
（９）
（１０）Ｚｚｆ，Ｊ≤ｌｍｉ，，Ｈ，＋１ｉ一１，２，…，，ｚｄｌ，厂∈Ｆ，，歹＝１。２，…，（ｎｆ＋１）∑ｅｘ∞一ｅｍｆ，’ｉ＝１，２，…，ｎｄ，，ｆ∈Ｆｉ，＝１ｅｘ，疗≤ｅｍ∥，ｉ＝１，２，…，ｎｄｌ，厂∈Ｆ，，Ｊ＝ｌ，２，…，（ｎｆ＋１）
式（７）、（９）分别表示第ｉ待解车列中厂到站的重、空车数在编组的集结车列和本时段末现车之间的分配关系；式（８）、（１０）分别表示集结车列Ｊ编组时吸收的待解车列ｉ中厂到站的重、空车数应小于其所在车列该到站的重、空车数；这里ｎｆ＋１表示本时段末的现车．
４）车流接续约束
ｎｄＩ材１月，，ｌ
∑∑∑∑（ｋ，Ｊ户绺‘＋∞疗瓠Ｊ，。ｋ‘）≤优呈ＱＤ
ｔ＝１Ｉ＝ｌ＾＾＝１，＝１
Ｊ＝１，２，…，ｎｆ，Ｆｉ∈Ｆ，ｎ｛Ｄ，），Ｄ∈｛Ⅳ，Ｅ，５，Ⅳ）
ｎｄｌ村ｌ（１１）ｎ，‘
∑∑∑∑（８０ｌｘ，ｚｊ夕？∥＋２０ＰＸ…６…ｊ．ｋ‘）≤Ｇ警Ｑ？
ｆ—ｌ＾＝１＾＾＝ｌ』＝１
．『＝１，２，…，ｎｆ，Ｆｉ∈Ｆｉｎ｛Ｄ，｝，Ｄ∈｛Ⅳ，Ｅ，５，Ⅳ）
肠乃（１２）＜一Ｍ∥ｍ。ｉ＝１，２，…，，ｚｄｌ，厂∈Ｆｉ，Ｊ一１，２，…，ｎｆ（１３）
．凹∞＜一Ｍ
＾ｆｎｆ畸∑㈣畸∑目∥∑一∥∑一靠从。ｉ＝１，２，…，咒ｄｌ，厂∈Ｆｉ，Ｊ＝１，２，…，ｎｆ（１４）
户理‘≤Ｍ・Ｊ＇ｋ，ｉ＝１，２，…，ｎｄｌ，是＝１，２，…，押ｄ１∑∑
Ｊ—ｌ“＝１
Ｈｆ＾ｆ（¨
∑∑口靠‘≤Ｍ・以，ｉ＝１，２，…，ｎｄｌ，ｋ＝１，２，…，挖ｄ１
ｊ一１“盅１（¨
ｎｄｌ耐ｌ
∑∑Ｐｆ：Ｉ＊≤Ｍ・尉＾，Ｊ＝１，２，…，ｎｆ，ｋｋ＝１，２，…，ｎｆ
ｉ；１＾＝１＂
∑∑ｑ瑶‘≤Ｍ・或，Ｊ一１，２，…，挖厂，ｋｋ＝１，２，…，，ｚｆ
ｉ暑１ｔ鲁１坞
均ｎｆ
∑２＝钟，．『＝１，２，…，ｎｆ，Ｄ∈｛彬，Ｅ，５，Ⅳ）
１６６数学的实践与认识３９卷
＞：Ｑ尹＝１，Ｄ∈｛Ⅳ，Ｅ，５，Ｎ）
Ｄ＝１（２０）
式（１１）和（１２）表示编组Ｄ去向的集结车列需满足该方向上列车最大长度和最大重量的限制；式（１３）和（１４）为逻辑关系，分别表示当集结车列Ｊ编组时吸收的待解车列ｉ中厂到站的重车和空车数不为零时，在某时段解体的待解车列ｉ中的重车和空车为另一时段编组的某集结车列提供了接续车流；式（１５）和（１６）为逻辑关系，分别表示如果在时段ｋ解体的待解车列ｉ中的重车和空车为另一时段编组的某集结车列提供了接续车流，那么第ｉ个待解车列在时段ｋ肯定解体；式（１７）和（１８）为逻辑关系，分别表示某时段解体的某待解车列为第志矗时段的集结车列Ｊ提供了接续车流，那么第Ｊ集结车列在第志五时段肯定编组；式（１９）为逻辑关系，表示如果第歹集结车列在某时段编组，那么第Ｊ集结车列肯定开往某一方向；式（２０）为逻辑关系，表示第歹集结车列编组时只开往一个方向．
５）车列编组开始时刻约束
”，
ｔｔ“＋ｌ—ｔｔ船一≥：ｔｂＪ・Ｂ磊≥０，
Ｊ＝１ｋｋ＝１，２，…，（ｎｆ一１）（２１）
柑ｌ＾，村１
ｔｔ＋∑ｔｊ，・一一ｔｔ“≤Ｍ・（１一∑∑户群‘）
ｋ＝１，２，…，ｎｄｌ，ｋｋ＝１，２，…，ｎｆ
ａｄｌ（２２）耐ｌ＂ｆ
ｔｔ＋∑ｔｊ，・以一ｔｔ从≤Ｍ・（１一∑∑倒ｊ∥．ｋ）
ｌ一１ｌ＝１Ｊ＝ｌ
五＝１，２，…，ｎｄｌ，ｋｋ＝１，２，…，，ｚ厂
ｎｆ（２３）
（２４）∑Ｂ厶一１，
Ｊ；１
＾，ｋｋ＝１，２，…，，ｚ，
“＝ｌ∑Ｂ“＝１。（２５）
式（２１）表示峰尾只有一台编组调机作业时，时段五五＋１对应车列编组开始时间必须在时段愚忌对应车列编组完成之后；式（２２）和式（２３）分别表示如果时段ｋ解体的待解车列ｉ为时段志是编组的集结车列Ｊ提供了重车和空车流，时段矗五待编组集结车列开始编组时刻必定在时段ｋ待解车列ｉ解体完成之后；式（２４）为逻辑约束，表示同一时段只能编组一个集结车列；式（２５）为逻辑约束。表示同一集结车列只需在一个时段编组．
６）出发场股道数约束
ＤＪ—ｔｔ“一ｆ６，・Ｂ磊≤Ｍ（１＋凡，一Ｂ矗），
ＮＦＪ＝１，２，…，ⅣＦＪ’＝１，２，…，ｎｆ，ｋｋ＝１，２，…，（，２，一１）（２６）
∑办ｒ≤Ｄｓ一１，Ｊ＝１，２，…，（ＮＦ一１）
Ｊ’＝Ｊ＋１（２７）
式（２６）表示始发车列．『和歹７在出发场占用股道时，发生冲突的条件；式（２７）表示出发场股道数对股道占用时间发生冲突的车列数的限制条件．７）中时约柬
１６期刘盾，等：货运列车编组调度问题的模型与算法研究１６７
生上兰卫生些量—１—五—————————————一≤８，∑∑（，ｚ仍＋ｅｘ西）
ｆ一１Ｊ＝１∑∑∑∑｛［（ｆｆ“＋ｔｂｌ）Ｂｉｔ—Ａ，Ｊ＇ｋ］（１ｘ，ｆｊ＋Ｐｘｉｉｊ））
Ｊ＝１，２，…，ｎｆ
一ｌ—ｌｎ，（２８）
。。’生Ｌ生坐生ｌ＿———Ｆ——————————————一≤２，ｔ∑∑∑｛［（ｆ￡“＋ｔｂＪ）巩一ＡｉＪｉｋ］（１ｘｉｙｉ＋ｅｘ仍））ｎｄｌ
∑∑（ｚｚ∞＋ｅｘｉｆｉ）』一１ｆ兰１
＿『＝１，２’．．・，ｎｆ，ｆ＝Ｓ，，军用
耐ｌ一１Ｈ，’（２９）
芏Ｌ竖型盥———Ｆ—荀————————————一≤１，∑∑（ｚｚ仍＋ｅｘｉＩｔ）ｉ耐ｌ∑∑∑｛Ｅ（ｔｔ从＋ｔｂ』）Ｂ厶一Ａ，Ｊｉ，］（１ｘ仍＋ｅｘｉｆｊ．））
』＝１ｆ省１。１’
．『＝１，２，…，ｎ厂，ｆ＝救灾（３０）
式（２８）表示任一出发列车的中时都不超过８小时，这样可以满足每个时间段的任务指标要求；式（２９）表示装有发往Ｓ。货物和军用物资的车辆的中时不超过２小时｛式（３０）表示装有救灾物资的车辆的中时不超过１小时．其中，一，Ｂ厶，Ｑ岁，户联‘，ｇ｜１．，。ｋ‘，口∥，成／都为。一１变量；ｔ★，ｔｔ∽ｌｘ：疗，ｅｘｉ，Ｊ都为整数变量，Ｍ为无穷大正数，ｉ＝１，２，…，ｎｄｌ，ｋ＝１，２，…，行ｄ１，Ｊ＝１，２，…，ｎｆ，ｋｋ＝１，２，…，咒厂，Ｄ∈｛Ｗ，Ｅ，Ｓ，Ｎ），ｆ＝１，２，…，Ｆ，．
８）目标函数
编组站编组调度方案以每个时间段车辆在站平均停留时间最少（中时）最小为第一目标．根据中时的计算方法，第一目标函数的直接表达方式为：
Ｆ｛＇Ｉｄｌｎｄ、ｎｆｎｆ
ｒａｉｎｚｌ＝盟三生生盐坚下可＿：＝＿————————一∑∑∑（红ｆＪ＋ｅｘｉｆｊ’
Ｆｎｄｌ月，ｎ，∑∑∑∑∑｛［（ｆｆ。。＋ｔｂ，）Ｂ缸一ＡｉＪｉｋ］（１ｘ∞＋ｅｚｉｆｊ））（３１）由于本时间段结束时刻固定，当中时最小时，也就是所有车列在编组站发出后至本时间段结束时刻的平均空闲时间最大，所以，目标函数的间接表达方式为：
ｍａｘｚ滓生止＿曼坚ｌ＿—ｒ了————————一∑∑∑（１ｘｉｌｊ＋ｅｘｉｆｊ）
ｆｆｆｉｌｉ＝１Ｊ一１
Ｈ，”ｄ１Ｆｉ∑∑∑∑｛ＩＴ。一（ｔｔ“＋ｔｂＪ）巩］（ｚｚ仍＋ＰＸｉｙｉ））（３２）第二目标是发出的车辆尽量多，即：
ｍａｘ２２一∑∑∑（１ｘ仍＋ｅｘｆｆｊ）（３３）
４分层启发式算法双向编组站货运列车编组调度的优化模型是一个多目标非线性混合整数规划模型‘３。，
１６８数学的实践与认识３９卷也是一个ＮＰＣ问题，现阶段并没有成熟的算法．货运列车的编组方案，可以分为配流［４］、待解车列解体计划、集结车列编组计划和到达场股道三个层次的子问题．配流是指确定新列车的组成，即新列车的车流来源和车辆数目；待解车列解体计划是指待解车列在驼峰上的解体先后顺序，即解体程序．集结车列编组计划是指待编的集结车列在峰尾上的编组先后顺序，即集结程序．
４．１配流
１）车站条件：问题一至问题四驼峰采用双推单溜作业方案，峰尾有一条牵出线可供编组列车；问题五驼峰采用双推单溜作业方案，峰尾有两条牵出线可供编组列车．
２）解体原则：按照列车到达先后顺序，依次解体，同一时间只能解体一列待解车列．解体占用溜放线时间取为解体作业时间，这段时间内不能再解体车列．记录待解车列解体开始、结束时间．先不考虑相邻到达列车时间间隔小于解体作业时间标准的情况，这将在待解车列解体计划中进行调整．
３）一般车辆编组原则：当编组场内某方向集结车列满重或满长时，该方向集结车列开始编组。问题一至问题四同一时间只能编组一列集结车列，问题五同一时间只能编组两列集结车列．编组占用牵出线时间取为编组作业时间，这段时间内不能再编组车列．记录新编集结车列编组开始、结束时间和编组内容（包括车流来源和数量），该方向已编组车列数更新；如果同一时间有多个方向集结车列都满足上述编组条件时，比较待编集结车列的车辆在站总停留时间大小，总停留时间最大的那个待编集结车列最先编组，其余依此类推．当某方向集结车辆总数大于编组条件时。编组选取的车辆按其进入编组场的时间降序选择．
４）特殊车辆编组原则：检验特殊车辆在站停留时间值，若该值加上编组作业时间后等于其要求停留时间（中时）时：如果该特殊车辆所在方向的集结车列数不满足车辆的编组条件要求，也进行编组，全部编完；如果同一时间有多个方向集结车列里的特殊车辆都需要编组，含救灾物资车辆的待编车列优先编组．
５）编组场现车更新：当待解车列解体完毕、待编车列编组完毕，编组场现车按股道别实行更新．
６）现车统计规则：从本时间段初和本时间段内进入车站的，在本时间段末仍没有到达出发场的，都作为本时间段末现车进行统计．
４．２待解车列解体计划
本时间段配流完成后，得到一个初始解体计划．由于驼峰采取双推单溜作业方案，同一时间只能解体一列待解车列．如果在这个解体计划中，相邻两待解车列的到达时间间隔大于解体作业时间标准的话，初始解体计划满足要求，计算各时间段车站“中时”指标，得到货运车辆可行的编组方案；否则初始解体顺序不可行，有些计划解体任务将延迟，需要重新确定待解车列的解体计划．通过列车预确报，可以得到待解车列的最早允许解体时间，即待解车列的发布时刻；根据已经资料，可以得到待解车列的解体作业时间标准，即待解车列的加工时间；根据配流方案，可以得到待解车列的最晚必须完成解体时刻，即待解车列的完工时刻．如果把待解车列比作工件，驼峰比作机器，那么待解车列的解体计划问题可以转换为单机器多任务的排序问题，目标以被延误解体的待解车列数最少．
根据题意，待解车列发布时刻为其到达时间Ａｉ；加工时间为其解体时间ｔｊｉ；交工时刻丁ｉ为保证某列集结车列按初始配流方案进行编组，待解车列最晚必须完成解体的时刻，这
１６期刘盾，等：货运列车编组调度问题的模型与算法研究１６９一时刻配流方案确定的集结车列进行编组的时刻进行推算．。
根据配流方案。令ｔｔ，为第歹列集结车列进行编组的时刻，ｚ幻为０—１凌量，表示根据配流方案，如果待解车列ｉ中有车流接续进行编组的集结车流歹时，取为１，否则为０．待解车列ｉ最晚必须完成解体时刻为：Ｔｉ＝ｍｉｎｔｔｊ，ｉ∈｛１，２，…，ｎｄ，｝．
‘，２１・，２１・２・…，“，
把待解车列解体计划比作单机器多任务的排序问题时，令【，：为。一１变量，当待解车列解体延误时，取为１，否则为０；啦为解体延误惩罚系数，可以对不同等级列车的重要性进行比较，赋予不同的解体延误惩罚系数，以使得较重要列车可以先进行解体．待解车列解体计划的用。一１规划模型描述如下：
ｎｄｌ
ｒａｉｎＺ＝∑咄ｕｉ
“Ｉ
∑以一１，ｋ＝１，２，…，ｎｄ。
ｆ＝１
ｎｄｌ
∑以＝１，ｉ＝１，２＇．．・，ｎｄｌ
，ｕｔｌ
０≤ｔｌ一∑Ａｉ・以≤６，ｋ一１，２，…，ｎｄ。ｆ＝１（３４）
树１
ｔ。＋∑ｔｊｉ・Ｊ＇ｋ—ｚ≤Ｍ・Ｕｉ，ｋ＝１，２，…，（ｒｉｄｌ～１）
Ｔ。＝ｍｉｎｔｔＪ，ｉ一１，２，…，ｎｄｌ
。ｉｉ置１・Ｊ一１，２・…，ｎｆ
以，Ｕｉ∈｛０，１），ｉ一１，２，…，挖ｄ，
目标函数表示被延误解体的待解车列数加权和最小，保证重要列车或有重要车列的列车能够按时解体．第一个约束为逻辑约束，表示同一待解车列只需在一个时段解体；第二个约束为逻辑约束，表示同一时段只能解体一个待解车列；第三个约束表示第ｋ时段车列解体开始时刻必须在车列最早可能解体时刻之后，且在到达场停留时间不超过６小时；第四个约束表示驼峰单溜放第忌＋１个时段对应车列解体开始时刻必须在第ｋ时段对应车列解体结束之后；第五个约束表示当第ｉ个待解车列解体完成时间大于其最晚必须完成解体时间时，表示该待解车列解体延误。此时Ｕ。＝１．
４．３集结车列编组计划
本时间段内，配流完成后，得到了一个可行的集结车列编组计划，然而待解车列解体计划有可能在配流方案下有所冲突，利用模型二对待解车列解体计划进行优化调整后，集结车列编组计划有可能因此而产生冲突，所以需要在调整后的待解车列解体计划的基础上，对集结车列编组计划进行优化调整，最后计算各时间段车站“中时”指标，得到货运车辆可行的编组方案．
本阶段内，通过待解车列解体计划，可以得到集结车列的最早允许编组时间，即集结车列的发布时刻；根据已知资料，可以得到集结车列的编组作业时问标准。即集结车列的加工时间；根据配流方案可以得到集结车列的最晚允许编组完成时刻，即集结车列的完工时刻．如果把待编集结车列比作工件，峰尾比作机器，因为峰尾就只有～条牵出线，那么集结车列
１７０数学的实践与认识３９卷的编组计划问题也可以转换为单机器多任务的排序问题，目标以被延误编组的集结车列数最少．
根据题意，集结车列最晚允许完成编组的时刻为丁Ｔｊ，加工时间为其编组时间ｔｂｊ；集结车列发布时刻为Ｂ，．记第ｉ列待解车列解体完成时刻为Ｃｉ（ｉ＝１，２，…，ｎｄ。），这可以通过解体计划确定．令ｚ幻为。一１变量，通过配流，若第ｉ列待解车列中的某一车组（或其中一部分）是某一进行编组的集结车列Ｊ的接续车流时，取为１，否则为０．集结车列＿『发布时刻，一定得大于第ｉ列待解车列解体完成时刻Ｃ，，否则。就意味着集结车列＿『编组时不能满轴．这样，集结车列歹的最早允许编组时刻应为组成该车列的车组所在待解车列ｉ的最晚解体完成时刻，即：Ｂ，＝１ＴＩａＸ
％２１，‘∈１，２・…・树ｌ｛Ｃｆ），歹∈｛１，２，…，ｎｆ）．
把集结车列编组计划比作单机器多任务的排序问题时，令ｏ，为Ｏ一１变量，当集结车列编组延误时，取为１，否则为０；Ａ，为编组延误惩罚系数，可以对不同等级列车的重要性进行比较，赋予不同的编组延误惩罚系数．使得较重要列车可以先进行编组．集结车列编组计划的０—１规划模型描述如下：
”，
ｍｉｎＺ＝∑Ａ，ｑ
ｉ一１
Ｂ厶＝ｋｋ一１，２，…，ｎｆ
Ｂ，¨＝
∥∑州∥∑一
”，
Ｊ薯１Ｊ＝１，２，…，ｎｆｔｔ雎一∑Ｂ』・ＢＩ★≥０，ｋｋ＝１，２，…，挖，
ｔｔ“＋∑ｆ以・瓯一丁ｔ
Ｊ２１（３５）ＮＭ・０，，ｋｋ一１，２，…，ｎｆ
Ｂｊ—ｍａｘ
～２１，‘∈１・２…。・“１｛Ｃｉ），Ｊ—ｌ，２，…，ｎｆ
Ｂ厶，Ｏｉ∈｛０，１），Ｊ＝１，２，…，ｎｆ
目标函数表示被延误编组的集结车列数加权和最小，保证重要列车或有重要车列的列车能够按时编组．第一个约束为逻辑约束，表示同一时段只能编组一个集结车列；第二个约束为为逻辑约束，表示同一集结车列只需在一个时段编组；第三个约束表示第触时段车列编组开始时刻必须在车列最早可能编组时刻之后；第四个约束表示时段是是＋１对应车列编组开始时间必须在时段矗忌对应车列编组完成之后；第五个约束表示当第歹个待编车列编组完成时间大于其最晚必须完成编组时间时，表示该集结车列编组延误，此时０，＝１．
４．４分层启发式算法
步骤１输入本时间段初的现车；若到达列车编组内容、解体和编组作业时间标准，转下
‘
一步．
步骤２配流．根据本时间段初现车和本时间段内到达列车编组内容，根据解体和编组作业时间标准，给出初始配流方案．若求得的配流方案所对应的初始解体计划满足时间要求，初始配流方案即为可行编组方案，转Ｓｔｅｐ５；若不满足，通过初始配流方案可得到待解车列的最晚必须完成解体时刻，转下一步．
１６期刘盾，等：货运列车编组调度问题的模型与算法研究１７１
步骤３待解车列解体计划．将车列解体计划问题转化为单机器排序问题，建立模型（３４）并求解，得到可行的待解车列解体计划和集结车列的最早允许编组时刻，转下一步．
步骤４集结车列编组计划．将车列编组计划问题转化为单机器排序问题，建立模型（３５）并求解，得到可行的车列的编组计划，转下一步．
步骤５输出车站车辆可行的编组方案，每班的中时．
５问题求解
对于问题一，将货运列车编组方案分解为配流、待解车列解体计划、集结车列编组计划三个层次的子问题．初始配流方案按启发式规则生成，解体计划和编组计划被类比于单机器排序问题，分别通过建立Ｏ一１规划模型依次制定．在满足模型假设４，且解体延误惩罚系数和编组延误惩罚系数都取１的前提下，计算出白班的中时为４．８４小时，晚班的中时为５．６７小时，满足中时约束条件．
问题二在问题一的基础上考虑了有特殊车辆优先运送的情况，在满足两个中时的约束条件的情况建立了一个非线性混合整数规划模型，按启发式规则得到调度方案．设定装有救灾物资的车辆所在待解车列的权值为４，装有发往Ｓ１货物和军用物资的车辆所在待解车列的权值为２，一般待解车列的权值为１；有救灾物资的车辆所在集结车列的权值为４，有发往Ｓ１货物和军用物资的车辆所在集结车列的权值为２，一般集结车列的权值为１．计算得到白班的中时为４．９８小时，晚班的中时为６．０１小时，救灾车的中时为０．８３小时，发Ｓ１和军用物资车的中时为１．６７小时，１天最多能编组完成７９１３辆车辆．
对于问题三，在保证有优先运送条件的同时，考虑在列车编组调度２小时内的快速反应能力，并通过建立一个货运列车日编组调度的阶段协同优化模型，来设计一种既满足中值尽量少又兼顾发车尽量多的编组调度方案．结果表明，该方案具有较好的稳定性和鲁棒性．
问题四主要考虑了在不可抗拒事件发生时，编组调度方案的应急能力．将Ｓ３站点转移到Ｅ４站点，在问题一的基础上对开往Ｓ３站点的所有列车（包括无调车）进行重新调配，生成新的调度方案，并在保证有优先运送和解体、编组延误惩罚系数取值同问题二的条件下计算得到白班的中时为４．７８小时，晚班的中时为６．０３小时，救灾车的中时为０．８３小时，发Ｓ１和军用物资车中时为１．８３小时，１天２４小时内最多能编组完成８４８６辆车．
对于问题五，提出驼峰采用双推单溜，设置两条牵出线的工作方案，来研究２４小时的编组凋度计划，解体、编组延误惩罚系数取值同问题二，得到白班的中时为２．５４小时，晚班的中时为１．７４小时，救灾车的中时为０．６７小时，发Ｓ１和军用物资的车中时为０．８３小时，１天最多能编组完成８８５８辆车辆，结果较双推单溜，单条牵出线的工作方案更好．
６结论
本文在分析了编组站各类车辆在站内走形路径的前提下，建立数学建模并利用计算机仿真技术分别研究了在正常和异常情况下编组调度方案的优化编制问题，对驼峰采用双推单溜、峰尾设置两条牵出线的扩能方案的效率进行了实验，表明扩能方案的优越性．然而，本文研究的编组调度问题只是编组站生产工作组织中较典型的问题，其他的问题如到达场、出发场股道安排，调车机车的运用，牵引机车的周转，双向编组站系统分工等，将在后续研究中展开．
１７２数学的实践与认识３９卷参考文献：
［１］郑时德．吴汉琳．铁路行车组织［Ｍ］．北京：中国铁道出版社，］９８７．
［２］胡思继．铁路行车组织［Ｍ］．北京：中国铁道出版社，１９９８．
［３３韩中庚．数学建模方法及其应用［Ｍ］．北京：高等教育出版社。２００５．
［４］王慈光．运输模型及优化［Ｍ］．北京：中国铁道出版社，２００４．
ＭｏｄｅｌａｎｄＡｌｇｏｒｉｔｈｍｆｏｒｔｈｅＭａｒｓｈａｌｌｉｎｇａｎｄ
ＤｉｓｐａｔｃｈｉｎｇＰｒｏｂｌｅｍｏｆＲａｉｌｗａｙＦｒｅｉｇｈｔＴｒａｉｎ
ＬＩＵＤｕｎｌ，ＺＨＡＯＪｕｎ２，ＨＡＮＤｏｎ９３，ＣＨＥＮＺｉ—ｌｉ４
（１．ＳｃｈｏｏｌｏｆＥｃｏｎｏｍｉｃｓａｎｄＭａｎａｇｅｍｅｎｔ，ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，
Ｃｈｅｎｇｄｕ６１００３１，Ｃｈｉｎａ）
（２．ＣｏｌｌｅｇｅｏｆＴｒａｆｆｉｃａｎｄＴｒａｎｓｐｏｒｔａｔｉｏｎ，ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ。
Ｃｈｅｎｇｄｕ６１００３１，Ｃｈｉｎａ）
（３．ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄ
Ｃｈｅｎｇｄｕ６１００３１，Ｃｈｉｎａ）
（４．ＣｏｌｌｅｇｅｏｆＭａｔｈｓ，ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ６１００３１，Ｃｈｉｎａ）Ｔｅｃｈｎｏｌｏｇｙ，ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，
Ａｂｓｔｒａｃｔ：ＢａｓｅｄＯｎｔｈｅｐｒａｃｔｉｃａｌｔｒａｎｓｐｏｒｔａｔｉｏｎｐｒｏｄｕｃｅｐｒｏｃｅｓｓｉｎａｒａｉｌｗａｙｔｗｉｃｅｄｉｒｅｃｔｉｏｎａｌ
ｍａｒｓｈａｌｌｉｎｇｓｔａｔｉｏｎ，ｔｈｅｍａｘｉｍｉｚｉｎｇｔｈｅｎｕｍｂｅｒｏｆｄｅｐａｒｔｕｒｅｗａｇｏｎｆｌｏｗｓａｎｄｍｉｎｉｍｉｚｉｎｇｔｈｅ
ａｖｅｒａｇｅｔｒａｎｓｆｅｒｔｉｍｅｐｅｒｗａｇｏｎｆｌｏｗｓｔａｙｉｎｇ
ｉｎｆｌｕｅｎｃｅｏｆｉｄｌｅｔｈｅａｔｓｔａｔｉｏｎａｒｅｃｏｎｓｉｄｅｒｅｄａｓｏｕｒｏｂｊｅｃｔｓｉｍｕｌｔａｎｅｏｕｓｌｙ．Ｔｈｅｎ，ｔａｋｉｎｇｔｈｅｃａｐａｃｉｔｙｌｉｍｉｔｏｆｓｏｒｔｉｎｇａｎｄｃｌａｓｓｉｆｙｉｎｇ
ｓｈｕｎｔｉｎｇｌｏｃｏｍｏｔｉｖｅ，ｔｈｅｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎａｒｒｉｖａｌａｎｄｄｅｐａｒｔｕｒｅｔｒａｉｎｓ，ｔｈｅｓｔａｙｔｉｍｅｏｆ
ｗａｇｏｎｓａｔｓｔａｔｉｏｎｉｎｔｏａｃｃｏｕｎｔ，ａ
ｔＯｎｏｎｌｉｎｅａｒｍｉｘｅｄｉｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌｗｉｔｈｍｕｌｔｉｉｐｈｏｂｊｅｃｔｉｖｅｓｈａｓｂｅｅｎｅｓｔａｂｌｉｓｈｅｄ
Ａｉｍｉｎｇ
ｗａｇｏｎａｔｍａｒｓｈａｌｌｉｎｇａｎｄｄｉｓｐａｔｃｈｉｎｇｐｒｏｂｌｅｍｏｆｒａｉｌｗａｙｆｒｅｉｇｈｔｔｒａｉｎ．ｔｈｅｈａｒｄｌｙｔｏｓｏｌｖｅｃｈａｒａｃｔｅｒｏｆｔｈｉｓｏｐｔｉｍｕｍｍｏｄｅｌ，ｗｅｄｉｖｉｄｅｄｔｈｉｓｐｒｏｂｌｅｍｉｎｔｏｂｒｅａｋ—ｕｐｏｆｗａｉｔｉｎｇｔｒａｉｎｆｌｏｗａｌｌｏｃａｔｉｏｎｐｒｏｂｌｅｍ，ｔｈｅｐｒｏｂｌｅｍａｎｄｔｈｅｍａｋｅ—ｕｐｏｆ
ｔｏｗａｉｔｉｎｇｔｒａｉｎｐｒｏｂｌｅｍ．Ｆｉｎａｌｌｙ，ａｄｉｓｊｏｉｎｔｌｅｖｅｌｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｈａｓｂｅｅｎｄｅｓｉｇｎｅｄ
ｔｈｉｓｐｒｏｂｌｅｍｉｎｔｈｅｏｒｄｉｎａｒｙａｎｄｅｓｐｅｃｉａｌｔｒａｎｓｐｏｒｔａｔｉｏｎｏｒｇａｎｉｚａｔｉｏｎｓｉｔｕａｔｉｏｎ．
Ｋｅｙｗｏｒｄｓ：ｓｏｌｖｅｍａｒｓｈａｌｌｉｎｇｓｔａｔｉｏｎｆｄｉｓｐａｔｃｈｉｎｇ；ｔｈｅａｖｅｒａｇｅｔｒａｎｓｉｔｔｉｍｅ；ｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍ
万方数据
货运列车编组调度问题的模型与算法研究
作者：
作者单位：刘盾， 赵军， 韩冬， 陈滋利， LIu Dun， ZHAO Jun， HAN Dong， CHEN Zi-li刘盾,LIu Dun(西南交通大学,经济管理学院,四川,成都,610031)， 赵军,ZHAO Jun(西南交
通大学交通运输学院,四川,成都,610031)， 韩冬,HAN Dong(西南交通大学信息科学与技术
学院,四川,成都,610031)， 陈滋利,CHEN Zi-li(西南交通大学数学学院,四川,成都
,610031)
数学的实践与认识
MATHEMATICS IN PRACTICE AND THEORY
2009，39(16)
0次刊名：英文刊名：年，卷(期)：被引用次数：
参考文献(4条)
1. 郑时德. 吴汉琳 铁路行车组织 1987
2. 胡思继 铁路行车组织 1998
3. 韩中庚 数学建模方法及其应用 2005
4. 王慈光 运输模型及优化 2004
相似文献(10条)
1.期刊论文 牛惠民. NIU Huimin 双向编组站列车调度调整的优化模型及算法 -中国铁道科学2007,28(6)
研究双向编组站调度优化问题,以解决到达列车接入系统和出发列车编组系统的实时调度调整.在分析双向编组站作业机理和规律的基础上,以列车的编成辆数、编组内容、接续时间、集结地点和作业能力为约束条件,以列车的走行距离、所产生的交换车数为综合优化目标,构造双向编组站列车调度调整的非线性优化模型.根据模型NP-Hard性和变量高度相关性的特点,建立基于网络流技术的遗传算法求解理论.算法的主要思想是在假定0-1变量已经确定的条件下,将整数变量的确定归结为求解网络最小费用流问题.以郑州北编组站为背景,给出算法的实际求解过程.求解算例表明,提出的方法能够有效解决到达列车和出发列车作业地点的实时选择问题.
2.学位论文 薛锋 编组站调度系统配流协同优化理论与方法研究 2009
编组站综合自动化是整个铁路运输现代化的重要组成部分，已建成的成都北编组站综合集成自动化系统(CIPS系统)和建设中的新丰镇编组站综合自动化系统(SAM系统)代表了我国铁路编组站信息化的发展趋势，它们整合并集成我国目前编组站各种成熟的过程控制分系统，统一信息管理，建立信息共享平台，有机地构建成管控一体化的整体系统。编组站CIPS系统和SAM系统实际上包括作业控制自动化、数据处理自动化和调度指挥智能化三大部分。这三大部分实际上形成按功能划分的三个子系统，它们紧密相联，互相依托，共同构成编组站综合自动化系统。其中，调度指挥子系统本质上属于决策支持系统(DSS)，而数据处理子系统本质上属于管理信息系统(MIS)，二者虽有联系，但面向不同层次，实现不同目标，具有不同功能。编组站调度指挥子系统(简称“调度系统”)是编组站综合自动化系统的核心，只有从优化作业计划入手，改善编组站作业，才能发挥出编组站调度系统“神经中枢”的作用。编组站调度系统配流问题是一个老问题，国内外学者一直在研究但未得到很好的解决方案，虽取得了一定的成果，但各有偏重，未能很好地从编组站整体角度考虑综合优化，有待进一步完善。
论文立足铁路编组站工作实际，从编组站调度大系统的角度出发，深入研究配流协同优化问题。论文借鉴了国内外相关研究成果，以理论研究为主，首先总结分析编组站的车流组织规律以及配流机理，然后在编组站调度系统界定和边际假设的基础上，综合运用大系统优化理论、协同论、组合数学等理论和观点，对编组站各单项作业进行系统的分析，同时注重作业环节的协调，将单项作业关联起来作为一个整体进行研究。论文的主要研究工作包括以下几个方面：
1．在深入分析编组站作业特征和作业流程的基础上，总结了编组站的车流组织规律，并对编组站调度系统进行了界定。通过分析配流问题的组合优化性质以及出发车流的来源，进一步揭示了编组站配流的内部机理。
2．以确定的编组站作业时间标准为依据，分别按调机的台数、调机作业方式、考虑固定作业和调机干扰与否，给出了计算到达列车的最早可能解体时刻和出发列车的最晚必须编组时刻的算法。在此基础上，以解体方案树模型及回溯算法确定列车的解体顺序，并提出列车编组顺序的调整方法。以先编组出发列车的单个配流方案为主线，建立了解编方案同步调整与协调匹配的协同优化模型。
3．汲取大系统优化理论、协同论的观点和方法，对到调机运用、到发线运用、调车线运用、取送车作业等建立一系列既相关又相对独立的模型和算法，包括静态与动态配流协同优化、到发线运用与解编作业协同优化、调车线运用与解编作业协同优化、取送车作业与解编作业协同优化等内容；引入系统综合的思想，将所建模型和算法进行有效地整合，建立编组站配流的综合协同优化模型，体现出系统的整体涌现性，构建了比较完善的编组站配流优化理论体系。
4．针对双向编组站衔接方向较多、易产生折角车流的特点，利用数学方法对交换车进行处理，同时考虑到达列车的接入场、出发列车的出发场以及股道调整等问题。在既有双向编组站系统作业分工方案的基础上，对于到发列车需要调整作业地点的情况，建立协同模型进行优化，尽可能地减少折角车流给编组站带来的能力损耗，实现到达车流在全站范围内的合理分配。
5．通过研究遗传算法和蚁群算法的融合，设计出一种集时间效率和求解精度于一体的快速算法——基于信息熵和混沌理论的遗传一蚁群协同优化算法，应用于求解编组站调度系统配流优化问题。
6．对所设计的算法应用计算机程序进行实现，并对郑州北站大量的现场数据进行测试，结果表明该算法能够在较短的时间内生成合理的配流方案，充分验证了优化模型和算法的有效性和实用性。
论文采用先局部后整体、由定性到定量、分层逐步解决的研究方法，加强了模型和算法的针对性设计，体现了配流整体优化的原则。论文的研究涵盖了与配流相关的编组站作业优化的主要内容，形成了一个相对完整的理论体系。编组站调度系统配流协同优化研究，作为编组站调度指挥智能化的应用基础理论研究，是编组站配流理论的深化，对提高编组站调度决策水平，实现编组站调度指挥科学化、智能化具有十分重要的作用，同时为建立编组站智能调度系统奠定可靠的理论基础。编组站配流的优化可以实现车站车流资源的优化配置，大力提高运输生产效率，进而产生巨大的经济和社会效益，因此论文的研究成果具有广阔的应用前景。
3.期刊论文 刘敏 大型钢铁企业编组站调度信息管理系统研究 -中国铁道科学2002,23(5)
从作业、任务、调度组织机构、列车种类等多个方面分析了钢铁企业编组站与铁路干线编组站的同异性,提出了钢铁企业调度信息管理系统应具备的系统功能,根据系统功能,将其软件结构划分成运输计划管理、预确报收集与处理、到达作业管理、现车管理、决策支持等八个子系统,并对各子系统进行了进一步划分,对系统硬件网络结构,提出可选用结构简单、可靠、传输距离远、负载重且实时性强的局域网,如千兆以太网组网方案,并给出系统网络结构图,对企业编组站的列车信息、车辆信息、股道信息、车场信息、作业信息、作业处理过程进行了数学描述,这对研制一个通用的钢铁企业编组站调度
信息管理系统有着重要的参考价值.
4.学位论文 胡猛 计算机编制编组站阶段计划的模型和算法的研究 2006
阶段计划是铁路编组站作业计划的核心部分，一个好的阶段计划应该反映出本阶段的工作重点，并按照列车编组计划的要求，把车流及时编成各种列车，保证本阶段的所有列车都正点发车，传统手工编制方法的弊端日趋明显。随着我国铁路现代化建设步伐的加快，作为铁路调度指挥自动化重要内容之一的编组站阶段计划自动化编制的研究势在必行。
本文在前人研究成果的基础上，针对编组站阶段计划编制的重点和难点，从我国铁路编组站实际情况出发，利用人工智能的最新研究成果—Agent及多Agent方法，结合启发式搜索及离散事件动态系统，对编组站阶段计划编制内容进行详细的分析，并对阶段计划编制系统的进行了初步探讨。论文主要内容如下：
1.对目前铁路编组站阶段计划编制的内容和流程进行了详细分析，指定编组站阶段计划编制问题的难点，论述了编组站阶段计划编制方法研究的紧迫性，并给出编组站阶段计划形式化描述。
2.基于人工智能最新成果—Agent及多Agent方法的编组站阶段计划编制方法研究中，讨论了系统的基本结构、功能及实现方法，并完成了各主要Agent子系统的设计与实现。
3.在完成编组站阶段计划编制系统构建的基础上，提出了阶段计划主要问题的模型和求解算法。在基于前人研究成果上，重点研究了“车流接续”的启发式搜索模型与算法，对原有的车流接续模型与算法进行了改进；利用离散事件动态系统的Job-Shop生产调度方法构建了到发线运用计划的模型与算法，并从空间和时间两个方面构建了疏解冲突模型与算法；在调车机车运用计划的研究中，在求得以“调车机车作业时间最小”为目标的单目标较优解的基础上，结合“调车机车走行距离最短”的目标，构建了双目标加权求和的目标函数，求出满足权重约束的双目标最优解。
4.结合实际科研项目，本文对编组站阶段计划编制系统进行了研究开发，系统能够对简单的原始资料进行整理、分析和设计，并在人工干预的条件下最终得到阶段计划表、技术作业图表及车流信息等一系列重要资料。
5.期刊论文 娄正良. Lou Zhengliang 编组站CIPS系统的调度计划管理 -铁路通信信号工程技术2006,3(4)
调度计划管理是编组站综合集成自动化系统的核心部分,本文阐述了编组站调度计划管理的原则和方法,并在此基础上将MAS具体应用于调度计划管理,在实时和优化之间取得一个比较好的平衡,满足了编组站调度计划的动态调整要求,取得了良好的效果.
6.期刊论文 崔炳谋. 马钧培. 张朴. CUI Bingmou. MA Junpei. ZHANG Pu 编组站进路调度优化算法 -中国铁道科学2007,28(2)
分析编组站作业进路选排问题的本质,以各任务的延误时间加权值总和最小为最优目标,以任务的前后工序选择路径为动态约束,建立编组站作业进路调度数学模型,采用遗传算法求解.编码采用定长染色体,长度为任务的工序数,每个工序采用2段制,编码中的顺序唯一地确定了每工序对指定进路占用的起讫时间和指标递推,设计基于优先规则的编码算法步骤.为保证解的可行性,将编码合法化,对工序进行拓扑排序.递推计算工序开始时间和结束时间,进而计算编码的目标值,并将其转化为适应值.采用轮盘赌与最优性相结合的方法进行选择,设计基于位置成组移位的杂交算子和随机交换的变异算子.以某编组站为例进行模拟计算,结果证明该算法满足编组站进路调度工作的要求.
7.学位论文 阳勇杰 编组站调度管理信息系统的应用开发研究 2006
随着我国铁路TMIS、DMIS系统的建成，联系铁道部、铁路局和车站的信息网已经形成。作为货车信息产生的节点——编组站，由于缺乏总体的规划，各个信息系统管理的信息和数据相对独立，难以互相共享。信息化作为实现铁路跨越式发展的必要条件，目前的信息系统已越来越不能满足我国编组站运营组织与管理现代化的需要。因此结合当前信息技术的发展状况及趋势，进一步提高编组站调度信息化水平的时机已经成熟。
本文首先分析了编组站信息系统的发展状况，指出目前各个系统存在的问题，然后以编组站调度指挥信息系统为前提，通过分析作业流程和信息流程的变化，提出了作业过程及工作岗位的整合方案和信息共享下业务内容的调整。在系统的分析、设计和实现部分，本文运用面向对象方法对编组站调度计划编制、信息流程做了详尽的系统分析，结合实际开发的特点设计了该系统的结构，并以郑州北站为背景，利用VisualC++程序开发工具和ORACLE数据库管理系统实现了编组站调度指挥信息管理系统的图形绘制、基础数据管理、数据分析、技术作业图表自动生成与打印等功能。最后，论文对我国编组站信息系统未来的发展提出了自己的看法与展望。
8.期刊论文 代科建. 薛锋 提高编组站调度人员的科学文化素质 -铁道运营技术2007,13(2)
由于编组站调度人员所承担繁重的工作任务,面对高新技术设备和铁路所采取的新措施,要求调度人员必须具有较高的科学文化素质.但在岗调度人员因专项业务培训不足和选用人员标准不高等原因,造成有的调度人员知识层次和文化水平不高,对掌握新技术设备和适应新的运输生产形势的能力出现困难,跟不上运输生产的现代化步伐,应采取相应措施进一步提高调度人员的科学文化素质.
9.学位论文 郝鹏飞 基于Multi-Agent编组站调度支持平台研究 2006
MAS(Multi-AgentSystem)是随着人工智能AI(ArtificialIntelligence)的发展而出现的一个具有自觉性、社会性、学习性的智能系统。它具有并行、健壮和易扩展的优点，为空间和图形以及没有集中处理数据的环境等问题提供了非常好的解决途径。MAS现在已经运用到了很多的领域：机器人足球、网络运输管理、Agent图书馆、互联网信息过滤、网络路由以及远程教育等。将MAS引入调度决策是一个很有研究意义的课题。
编组站的作业方式是根据上级调度部门下达的作业计划和确报系统发送的确报，结合自己站场的机车使用情况、现车在站场的分布的实际状况，制定出低耗、高效的作业计划，并且在实际作业中不断的修正计划的方式。
本文对编组站生产运行方式进行研究后，建立相应的模型，根据Multi-Agent的分散、独立、智能的计算模式构建了编组站智能调度决策平台，具有实时性、可靠性、可预测性，方便未来系统功能扩展，以及系统应用的领域扩展。
本文重点阐述了编组站智能调度决策平台中单agent模型、agent分类、agent间的协作，结合现行调度作业方式和JADEX的特点建立Agent模型，最后给出了平台的数据层设计。
10.期刊论文 刘霆. 何世伟. 王保华. 安健. LIU Ting. HE Shi-wei. WANG Bao-hua. AN Jian 编组站调度计划随机机会约束规划模型及算法研究 -铁道学报2007,29(4)
运用随机规划方法,研究列车解编时间随机变动情况下编组站阶段计划的优化编制问题,建立了以压缩车辆中时和减少出发列车晚点时间为目标的随机机会约束规划模型.将模型中的随机机会约束转化为相应等价形式,从而将随机规划模型转化为确定性模型,并提出了一种改进遗传算法对之进行求解.该算法基于列车解编顺序对染色体进行编码,并针对问题的特殊性设计了相应的交叉和变异操作.算例表明,设计的改进遗传算法能够在较短时间内收敛至最优解,编组站阶段计划的随机机会约束规划模型能取得可靠性更高的调度计划,为改进编组站的决策质量提供了一条解决的途径与方法.
本文链接：http://d.g.wanfangdata.com.cn/Periodical_sxdsjyrs200916017.aspx
授权使用：武汉大学(whdx)，授权号：0ddb991b-ab14-455e-95d5-9db5018343c5
下载时间：2010年7月16日
第３９卷第１６期
２００９年８月数学的实践与认识ＭＡＴＨＥＭＡＴＩＣＳＩＮＰＲＡＣＴＩＣＥＡＮＤＶ０１．３９Ｎｏ．１６ＴＨＥＯＲＹＡｕｇｕｓｔ，２００９
货运列车编组调度问题的模型与算法研究
刘盾１，赵军２，韩冬３，陈滋利４
（１．西南交通大学经济管理学院．四ＪＩ』成都６１００３１）
（２．西南交通大学交通运输学院。四川成都６１００３１）
（３．西南交通大学信息科学与技术学院，四川成都
（４．西南交通大学数学学院，四川成都６１００３１）６１００３１）
摘要：从双向编组站运输生产实际情况出发，以最大化车站发出车数和最小化车辆在站平均停留时问（中
时）为目标，综合考虑解体、编组调机能力限制、到发列车车流接续、车流在站停留时间约束的影响，建立了车
站货运列车编组调度问题的多目标非线性混合整数规划模型，结合该优化模型难以求解的特点，将编组调度
问题分解为配流、待解车列解体和待编车列编组三个子问题，进而设计了求解该问题的分层启发式算法，对
正常和特殊运输组织条件下的列车编组调度问题进行了求解．
关键词：编组站；调度；中时；启发式算法
０引言
货运列车在各编组站能否顺利调度，物资能否顺利运送，已成为连接我国东西、沟通南北经济命脉的纽带．一般而言，货车驶入某编组站要经过“到达一解体一集结一编组一出发”这五个作业过程，作为货运列车编组调度的核心，如何合理地组织列车解体、集结和编组作业，降低待解、待编、待发等现象的发生率，减少货车停留时间延长带来的损失，并将解编作业进行优化，成为提高整个编组调度效率，优化整个计划体系的关键内容之一［１七］．本文根据实际情况，建立“编组站中转停留的时间尽量少”的优化模型，并通过计算机仿真技术实现编组优化调度方案的制定．
１符号说明
ⅣＤ。：本时间段内，本系统的到达解体列车数量（包括时段初的现车列车）；
以ｄ。：本时间段内，本系统的待解车列数量（包括时段初的现车车列），ｎｄ。＝ⅣＤ。；
ⅣＤ。：本时间段内，本系统的无改编中转列车数量；
ⅣＤ：本时间段内，本系统的到达列车数量，ⅣＤ一ⅣＤ。ＵⅣＤ：；
ｎｆ。：本时间段内，由本系统编组的，将在本系统始发的集结车列（简称自编始发车列）１．１常量说明数量；
，ｚ厂２：本时间段内，由本系统编组的，去上行系统始发的交换车列（简称下行交换车列）数量；
ｒ／ｆ３：本时间段内，由上行系统编组的，来本系统始发的交换车列（简称上行交换车列）收稿日期：２００９－０４－３０
１６期刘盾，等：货运列车编组调度问题的模型与算法研究１６３数量；
ｎｆ：本时间段内，本系统的编组车列数量，ｎｆ＝ｎｆ。Ｕｎｆ２；
ⅣＦ：本时间段内，本系统的待发列车数量，ＮＦ—ｎｆ。Ｕｎｆ３ＵⅣＤ：；
丁，：本时间段的开始时刻；Ｔ。：本时间段的结束时刻ｌ
咄：解体延误惩罚系数，ｉ一１，２，…，ｎｄ，；Ａ，：编组延误惩罚系数，．『＝１，２，…，ｎｆ；
ｋ：一个待解车列的解体过程对应一个时段ｋ，ｋ一１，２，…，ｎｄ。；
愚五：一个集结车列的编组过程对应一个时段矗五，ｋｋ一１，２，…，ｎｆ；
Ａｉ：第ｉ车列的最早可能解体时刻，如果是现车，等于本时间初时刻，否则等于列车到达时刻，ｉ＝１，２，…，ｎｄｌ；
Ｅ：第ｉ车列的到站数，ｉ＝１，２，…，ｎｄ。；
ｆＪ，：第ｉ待解车列的解体时间，ｉ＝１，２，…，ｎｄ。；
ｚ优以第ｉ待解车列中厂到站的重车数，ｉ一１，２＇．．・，ｎｄ。，ｆ＝１，２，…，Ｆｉ；
ｅｍｌ，．第ｉ待解车列中厂到站的空车数，ｉ一１，２，…，ｎｄ。，ｆ一１，２，…，Ｆｚ｝
ｍ墨：编组Ｄ去向集结车列的最大长度，Ｄ∈｛ｗ，Ｅ，５，Ｎ｝；
Ｇ呈：编组Ｄ去向集结车列的最大重量，Ｄ∈｛Ⅳ，Ｅ，ｓ，Ⅳ｝；
加ｉ：第．『集结车列的编组和转线时间，Ｊ一１，２＇．－・，ｎｆ；
Ｄ：编组方向，Ｄ∈｛Ⅳ，Ｅ，５，Ⅳ），分别表示东、西、南、北四个方向ｌ
｛Ｄ，）：编组方向Ｄ上的车站集合；
ＤＳ：到达场股道数量；ＣＳ：出发场股道数量．
１．２变量说明
ｔ。：待解车列在时段ｋ解体开始时刻，ｋ＝１，２，…，ｎｄ，；
Ｊｉ：０—１变量，当第ｉ待解车列在时段ｋ解体时，取为１，否则为０；ｉ＝１，２，…，ｎｄ，，ｋ一１，２，…，ｎｄｌ；
ｔｔ川集结车列在时段五尼编组开始时刻，ｋｋ一１，２，…，ｎｆ；
Ｂｉ。：０—１变量，当第歹集结车列在时段五五编组时，取为１，否则为０，Ｊ＝１，２，…，ｎｆ，ｋｋ＝１，２，…，ｎｆ；
Ｕ，：０—１变量，当待解车列解体延误时，取为１，否则为０．ｉ＝１，２，…，ｎｄ，；
０，：０—１变量，当集结车列编组延误时，取为１，否则为０．歹＝１，２，…，ｎｆ；
Ｑ夕：０一ｌ变量，当第歹集结车列编组Ｄ去向车辆时，取为１，否则为０，＿『＝１，２，…，咒厂，Ｄ∈｛Ⅳ，Ｅ，５，Ⅳ）；
户绺‘：０—１变量，当在时段ｋ解体的待解车列ｉ中的重车为时段点五编组的集结车列歹提供接续车流时，取为１，否则为０；
ｇ绺‘：０—１变量，当在时段ｋ解体的待解车列ｉ中的空车为时段志志编组的集结车列Ｊ提供接续车流时，取为１，否则为０；
ｌｘｇｙｊ：集结车列Ｊ编组时吸收的待解车列ｉ中，到站的重车数；ｉ＝１，２，…，以ｄ。，ｆ＝１，２，…，Ｆｆ＇Ｊ＝１，２，…，ｎｆ；
ｅｘ。，Ｊ：集结车列歹编组时吸收的待解车列ｉ中，到站的空车数；ｉ一１，２，…，挖ｄ。，厂一１，２，…，Ｆ。，Ｊ＝１，２，…，ｎｆ；
１６４数学的实践与认识３９卷
ｑ¨０—１变量，当到达列车ｉ和ｉ７在列车占用股道上有时间冲突时，取为１，否则为Ｏ；局，：０—１变量，当始发列车歹和歹’在出发占用股道上有时间冲突时，取为１，否则为０．２模型假设
１）在考察当天，不考虑上行线和下行线到达场、编组场和出发场的容量问题；
２）在考察当天开始计算时（即早上６点时），上行线和下行线的编组场和出发场均没有停放列车；
３）在考察当天中途不会发生由自然或人为原因造成的故障；
４）假设驼峰实行双推单溜作业方案时，解体作业时间标准为ｌｏ分钟；从编组场编组并牵引－－Ｎ车到出发场为２０分钟；从由上（下）行线编组场编组经转发场到达下（上）行线出发场为３０分钟；
５）编组调度规程规定每辆重车不超过８０Ｔ（含车自重２０Ｔ），一般要求每列车总重量不超过４８００Ｔ，总长最多不超过７０辆；
６）下（上）行无调车、上（下）行交换车在走形路径上都不存在干扰；
７）机车数量满足实际工作需求，出发场能力不受限制，编组完成的列车都能及时发出；８）根据研究车站场区布置图，假定其驼峰采用双推单溜的作业方案，解体作业过程中不能再解体；峰尾只一条编组线可用于列车编组，编组作业过程中不能再编组．
３优化模型
双向三级六场编组站下（上）行改编系统在编组东、南（西、北）方向集结车列时与上（下）行改编系统相互独立，在编组西、北（东、南）方向集结车列时又与上（下）行改编系统在出发场相互联系，主要是协调使用出发线．这里我们假设出发场能力不受限制，编组完成的列车都能及时发出，即两个改编系统相互独立，特点相同，只需要对某一个改编系统的某个时间段的车辆编组调度问题进行建模，便可以描述整个车站的车流变动情况．下行改编系统货运列车编组调度的优化模型为：
１）到达场股道数约束
ｔＩ＋ｔｊ，・Ｊ：一Ａ，ＮＭ・（１＋％，～以），ｉ一１，２，…，（ｎｄｌ—１）
ｉ７＝２，３，…，ｎｄｌ，ｋ一１，２，…，ｎｄｌ（１）
ｉ７一ｌ
西∑口ｆＩ，ＮＤＳ一１，ｉ，＝２，３，…，ｎｄｌ（２）
式（１）表示待解车列ｉ和ｉ７在到达场占用股道时，发生冲突的条件；式（２）表示到达场股道数对股道占用时间发生冲突的列车数的限制条件．
２）车列解体开始时刻约束
材ｌ
ｔｌ＋１一ｔ＾一∑ｔｊｉ・以≥０，五＝１，２，…，（ｎｄｌ一１）（３）
ｌ＝１
ｎｄｌ
０≤ｔ＾一∑Ａｆ・以≤６，ｋ＝１，２，…，（ｎｄｌ—１）百（４）
耐ｌ，
∑以＝１，五＝ｌ，２，…，ｎｄｌ（５）
１６期刘盾，等：货运列车编组调度问题的模型与算法研究１６５
∑以一１，ｉ＝１，２，…，ｎｄ，函（６）
式（３）表示驼峰单溜放第ｋ＋１个时段对应车列解体开始时刻必须在第忌时段对应车列解体结束之后；式（４）表示第ｋ时段车列解体开始时刻必须在车列最早可能解体时刻之后，且在到达场停留时间不超过６小时；式（５）为逻辑约束，表示同一时段只能解体一个待解车列；式（６）为逻辑约束。表示同一待解车列只需在一个时段解体．
３）车流分配约束
≈，＋】
∑ｌｘ，疗＝ｌｍ巾ｉ＝１，２，…，ｎｄ。，ｆ∈Ｆ，
，＝１（７）
（８）
（９）
（１０）Ｚｚｆ，Ｊ≤ｌｍｉ，，Ｈ，＋１ｉ一１，２，…，，ｚｄｌ，厂∈Ｆ，，歹＝１。２，…，（ｎｆ＋１）∑ｅｘ∞一ｅｍｆ，’ｉ＝１，２，…，ｎｄ，，ｆ∈Ｆｉ，＝１ｅｘ，疗≤ｅｍ∥，ｉ＝１，２，…，ｎｄｌ，厂∈Ｆ，，Ｊ＝ｌ，２，…，（ｎｆ＋１）
式（７）、（９）分别表示第ｉ待解车列中厂到站的重、空车数在编组的集结车列和本时段末现车之间的分配关系；式（８）、（１０）分别表示集结车列Ｊ编组时吸收的待解车列ｉ中厂到站的重、空车数应小于其所在车列该到站的重、空车数；这里ｎｆ＋１表示本时段末的现车．
４）车流接续约束
ｎｄＩ材１月，，ｌ
∑∑∑∑（ｋ，Ｊ户绺‘＋∞疗瓠Ｊ，。ｋ‘）≤优呈ＱＤ
ｔ＝１Ｉ＝ｌ＾＾＝１，＝１
Ｊ＝１，２，…，ｎｆ，Ｆｉ∈Ｆ，ｎ｛Ｄ，），Ｄ∈｛Ⅳ，Ｅ，５，Ⅳ）
ｎｄｌ村ｌ（１１）ｎ，‘
∑∑∑∑（８０ｌｘ，ｚｊ夕？∥＋２０ＰＸ…６…ｊ．ｋ‘）≤Ｇ警Ｑ？
ｆ—ｌ＾＝１＾＾＝ｌ』＝１
．『＝１，２，…，ｎｆ，Ｆｉ∈Ｆｉｎ｛Ｄ，｝，Ｄ∈｛Ⅳ，Ｅ，５，Ⅳ）
肠乃（１２）＜一Ｍ∥ｍ。ｉ＝１，２，…，，ｚｄｌ，厂∈Ｆｉ，Ｊ一１，２，…，ｎｆ（１３）
．凹∞＜一Ｍ
＾ｆｎｆ畸∑㈣畸∑目∥∑一∥∑一靠从。ｉ＝１，２，…，咒ｄｌ，厂∈Ｆｉ，Ｊ＝１，２，…，ｎｆ（１４）
户理‘≤Ｍ・Ｊ＇ｋ，ｉ＝１，２，…，ｎｄｌ，是＝１，２，…，押ｄ１∑∑
Ｊ—ｌ“＝１
Ｈｆ＾ｆ（¨
∑∑口靠‘≤Ｍ・以，ｉ＝１，２，…，ｎｄｌ，ｋ＝１，２，…，挖ｄ１
ｊ一１“盅１（¨
ｎｄｌ耐ｌ
∑∑Ｐｆ：Ｉ＊≤Ｍ・尉＾，Ｊ＝１，２，…，ｎｆ，ｋｋ＝１，２，…，ｎｆ
ｉ；１＾＝１＂
∑∑ｑ瑶‘≤Ｍ・或，Ｊ一１，２，…，挖厂，ｋｋ＝１，２，…，，ｚｆ
ｉ暑１ｔ鲁１坞
均ｎｆ
∑２＝钟，．『＝１，２，…，ｎｆ，Ｄ∈｛彬，Ｅ，５，Ⅳ）
１６６数学的实践与认识３９卷
＞：Ｑ尹＝１，Ｄ∈｛Ⅳ，Ｅ，５，Ｎ）
Ｄ＝１（２０）
式（１１）和（１２）表示编组Ｄ去向的集结车列需满足该方向上列车最大长度和最大重量的限制；式（１３）和（１４）为逻辑关系，分别表示当集结车列Ｊ编组时吸收的待解车列ｉ中厂到站的重车和空车数不为零时，在某时段解体的待解车列ｉ中的重车和空车为另一时段编组的某集结车列提供了接续车流；式（１５）和（１６）为逻辑关系，分别表示如果在时段ｋ解体的待解车列ｉ中的重车和空车为另一时段编组的某集结车列提供了接续车流，那么第ｉ个待解车列在时段ｋ肯定解体；式（１７）和（１８）为逻辑关系，分别表示某时段解体的某待解车列为第志矗时段的集结车列Ｊ提供了接续车流，那么第Ｊ集结车列在第志五时段肯定编组；式（１９）为逻辑关系，表示如果第歹集结车列在某时段编组，那么第Ｊ集结车列肯定开往某一方向；式（２０）为逻辑关系，表示第歹集结车列编组时只开往一个方向．
５）车列编组开始时刻约束
”，
ｔｔ“＋ｌ—ｔｔ船一≥：ｔｂＪ・Ｂ磊≥０，
Ｊ＝１ｋｋ＝１，２，…，（ｎｆ一１）（２１）
柑ｌ＾，村１
ｔｔ＋∑ｔｊ，・一一ｔｔ“≤Ｍ・（１一∑∑户群‘）
ｋ＝１，２，…，ｎｄｌ，ｋｋ＝１，２，…，ｎｆ
ａｄｌ（２２）耐ｌ＂ｆ
ｔｔ＋∑ｔｊ，・以一ｔｔ从≤Ｍ・（１一∑∑倒ｊ∥．ｋ）
ｌ一１ｌ＝１Ｊ＝ｌ
五＝１，２，…，ｎｄｌ，ｋｋ＝１，２，…，，ｚ厂
ｎｆ（２３）
（２４）∑Ｂ厶一１，
Ｊ；１
＾，ｋｋ＝１，２，…，，ｚ，
“＝ｌ∑Ｂ“＝１。（２５）
式（２１）表示峰尾只有一台编组调机作业时，时段五五＋１对应车列编组开始时间必须在时段愚忌对应车列编组完成之后；式（２２）和式（２３）分别表示如果时段ｋ解体的待解车列ｉ为时段志是编组的集结车列Ｊ提供了重车和空车流，时段矗五待编组集结车列开始编组时刻必定在时段ｋ待解车列ｉ解体完成之后；式（２４）为逻辑约束，表示同一时段只能编组一个集结车列；式（２５）为逻辑约束。表示同一集结车列只需在一个时段编组．
６）出发场股道数约束
ＤＪ—ｔｔ“一ｆ６，・Ｂ磊≤Ｍ（１＋凡，一Ｂ矗），
ＮＦＪ＝１，２，…，ⅣＦＪ’＝１，２，…，ｎｆ，ｋｋ＝１，２，…，（，２，一１）（２６）
∑办ｒ≤Ｄｓ一１，Ｊ＝１，２，…，（ＮＦ一１）
Ｊ’＝Ｊ＋１（２７）
式（２６）表示始发车列．『和歹７在出发场占用股道时，发生冲突的条件；式（２７）表示出发场股道数对股道占用时间发生冲突的车列数的限制条件．７）中时约柬
１６期刘盾，等：货运列车编组调度问题的模型与算法研究１６７
生上兰卫生些量—１—五—————————————一≤８，∑∑（，ｚ仍＋ｅｘ西）
ｆ一１Ｊ＝１∑∑∑∑｛［（ｆｆ“＋ｔｂｌ）Ｂｉｔ—Ａ，Ｊ＇ｋ］（１ｘ，ｆｊ＋Ｐｘｉｉｊ））
Ｊ＝１，２，…，ｎｆ
一ｌ—ｌｎ，（２８）
。。’生Ｌ生坐生ｌ＿———Ｆ——————————————一≤２，ｔ∑∑∑｛［（ｆ￡“＋ｔｂＪ）巩一ＡｉＪｉｋ］（１ｘｉｙｉ＋ｅｘ仍））ｎｄｌ
∑∑（ｚｚ∞＋ｅｘｉｆｉ）』一１ｆ兰１
＿『＝１，２’．．・，ｎｆ，ｆ＝Ｓ，，军用
耐ｌ一１Ｈ，’（２９）
芏Ｌ竖型盥———Ｆ—荀————————————一≤１，∑∑（ｚｚ仍＋ｅｘｉＩｔ）ｉ耐ｌ∑∑∑｛Ｅ（ｔｔ从＋ｔｂ』）Ｂ厶一Ａ，Ｊｉ，］（１ｘ仍＋ｅｘｉｆｊ．））
』＝１ｆ省１。１’
．『＝１，２，…，ｎ厂，ｆ＝救灾（３０）
式（２８）表示任一出发列车的中时都不超过８小时，这样可以满足每个时间段的任务指标要求；式（２９）表示装有发往Ｓ。货物和军用物资的车辆的中时不超过２小时｛式（３０）表示装有救灾物资的车辆的中时不超过１小时．其中，一，Ｂ厶，Ｑ岁，户联‘，ｇ｜１．，。ｋ‘，口∥，成／都为。一１变量；ｔ★，ｔｔ∽ｌｘ：疗，ｅｘｉ，Ｊ都为整数变量，Ｍ为无穷大正数，ｉ＝１，２，…，ｎｄｌ，ｋ＝１，２，…，行ｄ１，Ｊ＝１，２，…，ｎｆ，ｋｋ＝１，２，…，咒厂，Ｄ∈｛Ｗ，Ｅ，Ｓ，Ｎ），ｆ＝１，２，…，Ｆ，．
８）目标函数
编组站编组调度方案以每个时间段车辆在站平均停留时间最少（中时）最小为第一目标．根据中时的计算方法，第一目标函数的直接表达方式为：
Ｆ｛＇Ｉｄｌｎｄ、ｎｆｎｆ
ｒａｉｎｚｌ＝盟三生生盐坚下可＿：＝＿————————一∑∑∑（红ｆＪ＋ｅｘｉｆｊ’
Ｆｎｄｌ月，ｎ，∑∑∑∑∑｛［（ｆｆ。。＋ｔｂ，）Ｂ缸一ＡｉＪｉｋ］（１ｘ∞＋ｅｚｉｆｊ））（３１）由于本时间段结束时刻固定，当中时最小时，也就是所有车列在编组站发出后至本时间段结束时刻的平均空闲时间最大，所以，目标函数的间接表达方式为：
ｍａｘｚ滓生止＿曼坚ｌ＿—ｒ了————————一∑∑∑（１ｘｉｌｊ＋ｅｘｉｆｊ）
ｆｆｆｉｌｉ＝１Ｊ一１
Ｈ，”ｄ１Ｆｉ∑∑∑∑｛ＩＴ。一（ｔｔ“＋ｔｂＪ）巩］（ｚｚ仍＋ＰＸｉｙｉ））（３２）第二目标是发出的车辆尽量多，即：
ｍａｘ２２一∑∑∑（１ｘ仍＋ｅｘｆｆｊ）（３３）
４分层启发式算法双向编组站货运列车编组调度的优化模型是一个多目标非线性混合整数规划模型‘３。，
１６８数学的实践与认识３９卷也是一个ＮＰＣ问题，现阶段并没有成熟的算法．货运列车的编组方案，可以分为配流［４］、待解车列解体计划、集结车列编组计划和到达场股道三个层次的子问题．配流是指确定新列车的组成，即新列车的车流来源和车辆数目；待解车列解体计划是指待解车列在驼峰上的解体先后顺序，即解体程序．集结车列编组计划是指待编的集结车列在峰尾上的编组先后顺序，即集结程序．
４．１配流
１）车站条件：问题一至问题四驼峰采用双推单溜作业方案，峰尾有一条牵出线可供编组列车；问题五驼峰采用双推单溜作业方案，峰尾有两条牵出线可供编组列车．
２）解体原则：按照列车到达先后顺序，依次解体，同一时间只能解体一列待解车列．解体占用溜放线时间取为解体作业时间，这段时间内不能再解体车列．记录待解车列解体开始、结束时间．先不考虑相邻到达列车时间间隔小于解体作业时间标准的情况，这将在待解车列解体计划中进行调整．
３）一般车辆编组原则：当编组场内某方向集结车列满重或满长时，该方向集结车列开始编组。问题一至问题四同一时间只能编组一列集结车列，问题五同一时间只能编组两列集结车列．编组占用牵出线时间取为编组作业时间，这段时间内不能再编组车列．记录新编集结车列编组开始、结束时间和编组内容（包括车流来源和数量），该方向已编组车列数更新；如果同一时间有多个方向集结车列都满足上述编组条件时，比较待编集结车列的车辆在站总停留时间大小，总停留时间最大的那个待编集结车列最先编组，其余依此类推．当某方向集结车辆总数大于编组条件时。编组选取的车辆按其进入编组场的时间降序选择．
４）特殊车辆编组原则：检验特殊车辆在站停留时间值，若该值加上编组作业时间后等于其要求停留时间（中时）时：如果该特殊车辆所在方向的集结车列数不满足车辆的编组条件要求，也进行编组，全部编完；如果同一时间有多个方向集结车列里的特殊车辆都需要编组，含救灾物资车辆的待编车列优先编组．
５）编组场现车更新：当待解车列解体完毕、待编车列编组完毕，编组场现车按股道别实行更新．
６）现车统计规则：从本时间段初和本时间段内进入车站的，在本时间段末仍没有到达出发场的，都作为本时间段末现车进行统计．
４．２待解车列解体计划
本时间段配流完成后，得到一个初始解体计划．由于驼峰采取双推单溜作业方案，同一时间只能解体一列待解车列．如果在这个解体计划中，相邻两待解车列的到达时间间隔大于解体作业时间标准的话，初始解体计划满足要求，计算各时间段车站“中时”指标，得到货运车辆可行的编组方案；否则初始解体顺序不可行，有些计划解体任务将延迟，需要重新确定待解车列的解体计划．通过列车预确报，可以得到待解车列的最早允许解体时间，即待解车列的发布时刻；根据已经资料，可以得到待解车列的解体作业时间标准，即待解车列的加工时间；根据配流方案，可以得到待解车列的最晚必须完成解体时刻，即待解车列的完工时刻．如果把待解车列比作工件，驼峰比作机器，那么待解车列的解体计划问题可以转换为单机器多任务的排序问题，目标以被延误解体的待解车列数最少．
根据题意，待解车列发布时刻为其到达时间Ａｉ；加工时间为其解体时间ｔｊｉ；交工时刻丁ｉ为保证某列集结车列按初始配流方案进行编组，待解车列最晚必须完成解体的时刻，这
１６期刘盾，等：货运列车编组调度问题的模型与算法研究１６９一时刻配流方案确定的集结车列进行编组的时刻进行推算．。
根据配流方案。令ｔｔ，为第歹列集结车列进行编组的时刻，ｚ幻为０—１凌量，表示根据配流方案，如果待解车列ｉ中有车流接续进行编组的集结车流歹时，取为１，否则为０．待解车列ｉ最晚必须完成解体时刻为：Ｔｉ＝ｍｉｎｔｔｊ，ｉ∈｛１，２，…，ｎｄ，｝．
‘，２１・，２１・２・…，“，
把待解车列解体计划比作单机器多任务的排序问题时，令【，：为。一１变量，当待解车列解体延误时，取为１，否则为０；啦为解体延误惩罚系数，可以对不同等级列车的重要性进行比较，赋予不同的解体延误惩罚系数，以使得较重要列车可以先进行解体．待解车列解体计划的用。一１规划模型描述如下：
ｎｄｌ
ｒａｉｎＺ＝∑咄ｕｉ
“Ｉ
∑以一１，ｋ＝１，２，…，ｎｄ。
ｆ＝１
ｎｄｌ
∑以＝１，ｉ＝１，２＇．．・，ｎｄｌ
，ｕｔｌ
０≤ｔｌ一∑Ａｉ・以≤６，ｋ一１，２，…，ｎｄ。ｆ＝１（３４）
树１
ｔ。＋∑ｔｊｉ・Ｊ＇ｋ—ｚ≤Ｍ・Ｕｉ，ｋ＝１，２，…，（ｒｉｄｌ～１）
Ｔ。＝ｍｉｎｔｔＪ，ｉ一１，２，…，ｎｄｌ
。ｉｉ置１・Ｊ一１，２・…，ｎｆ
以，Ｕｉ∈｛０，１），ｉ一１，２，…，挖ｄ，
目标函数表示被延误解体的待解车列数加权和最小，保证重要列车或有重要车列的列车能够按时解体．第一个约束为逻辑约束，表示同一待解车列只需在一个时段解体；第二个约束为逻辑约束，表示同一时段只能解体一个待解车列；第三个约束表示第ｋ时段车列解体开始时刻必须在车列最早可能解体时刻之后，且在到达场停留时间不超过６小时；第四个约束表示驼峰单溜放第忌＋１个时段对应车列解体开始时刻必须在第ｋ时段对应车列解体结束之后；第五个约束表示当第ｉ个待解车列解体完成时间大于其最晚必须完成解体时间时，表示该待解车列解体延误。此时Ｕ。＝１．
４．３集结车列编组计划
本时间段内，配流完成后，得到了一个可行的集结车列编组计划，然而待解车列解体计划有可能在配流方案下有所冲突，利用模型二对待解车列解体计划进行优化调整后，集结车列编组计划有可能因此而产生冲突，所以需要在调整后的待解车列解体计划的基础上，对集结车列编组计划进行优化调整，最后计算各时间段车站“中时”指标，得到货运车辆可行的编组方案．
本阶段内，通过待解车列解体计划，可以得到集结车列的最早允许编组时间，即集结车列的发布时刻；根据已知资料，可以得到集结车列的编组作业时问标准。即集结车列的加工时间；根据配流方案可以得到集结车列的最晚允许编组完成时刻，即集结车列的完工时刻．如果把待编集结车列比作工件，峰尾比作机器，因为峰尾就只有～条牵出线，那么集结车列
１７０数学的实践与认识３９卷的编组计划问题也可以转换为单机器多任务的排序问题，目标以被延误编组的集结车列数最少．
根据题意，集结车列最晚允许完成编组的时刻为丁Ｔｊ，加工时间为其编组时间ｔｂｊ；集结车列发布时刻为Ｂ，．记第ｉ列待解车列解体完成时刻为Ｃｉ（ｉ＝１，２，…，ｎｄ。），这可以通过解体计划确定．令ｚ幻为。一１变量，通过配流，若第ｉ列待解车列中的某一车组（或其中一部分）是某一进行编组的集结车列Ｊ的接续车流时，取为１，否则为０．集结车列＿『发布时刻，一定得大于第ｉ列待解车列解体完成时刻Ｃ，，否则。就意味着集结车列＿『编组时不能满轴．这样，集结车列歹的最早允许编组时刻应为组成该车列的车组所在待解车列ｉ的最晚解体完成时刻，即：Ｂ，＝１ＴＩａＸ
％２１，‘∈１，２・…・树ｌ｛Ｃｆ），歹∈｛１，２，…，ｎｆ）．
把集结车列编组计划比作单机器多任务的排序问题时，令ｏ，为Ｏ一１变量，当集结车列编组延误时，取为１，否则为０；Ａ，为编组延误惩罚系数，可以对不同等级列车的重要性进行比较，赋予不同的编组延误惩罚系数．使得较重要列车可以先进行编组．集结车列编组计划的０—１规划模型描述如下：
”，
ｍｉｎＺ＝∑Ａ，ｑ
ｉ一１
Ｂ厶＝ｋｋ一１，２，…，ｎｆ
Ｂ，¨＝
∥∑州∥∑一
”，
Ｊ薯１Ｊ＝１，２，…，ｎｆｔｔ雎一∑Ｂ』・ＢＩ★≥０，ｋｋ＝１，２，…，挖，
ｔｔ“＋∑ｆ以・瓯一丁ｔ
Ｊ２１（３５）ＮＭ・０，，ｋｋ一１，２，…，ｎｆ
Ｂｊ—ｍａｘ
～２１，‘∈１・２…。・“１｛Ｃｉ），Ｊ—ｌ，２，…，ｎｆ
Ｂ厶，Ｏｉ∈｛０，１），Ｊ＝１，２，…，ｎｆ
目标函数表示被延误编组的集结车列数加权和最小，保证重要列车或有重要车列的列车能够按时编组．第一个约束为逻辑约束，表示同一时段只能编组一个集结车列；第二个约束为为逻辑约束，表示同一集结车列只需在一个时段编组；第三个约束表示第触时段车列编组开始时刻必须在车列最早可能编组时刻之后；第四个约束表示时段是是＋１对应车列编组开始时间必须在时段矗忌对应车列编组完成之后；第五个约束表示当第歹个待编车列编组完成时间大于其最晚必须完成编组时间时，表示该集结车列编组延误，此时０，＝１．
４．４分层启发式算法
步骤１输入本时间段初的现车；若到达列车编组内容、解体和编组作业时间标准，转下
‘
一步．
步骤２配流．根据本时间段初现车和本时间段内到达列车编组内容，根据解体和编组作业时间标准，给出初始配流方案．若求得的配流方案所对应的初始解体计划满足时间要求，初始配流方案即为可行编组方案，转Ｓｔｅｐ５；若不满足，通过初始配流方案可得到待解车列的最晚必须完成解体时刻，转下一步．
１６期刘盾，等：货运列车编组调度问题的模型与算法研究１７１
步骤３待解车列解体计划．将车列解体计划问题转化为单机器排序问题，建立模型（３４）并求解，得到可行的待解车列解体计划和集结车列的最早允许编组时刻，转下一步．
步骤４集结车列编组计划．将车列编组计划问题转化为单机器排序问题，建立模型（３５）并求解，得到可行的车列的编组计划，转下一步．
步骤５输出车站车辆可行的编组方案，每班的中时．
５问题求解
对于问题一，将货运列车编组方案分解为配流、待解车列解体计划、集结车列编组计划三个层次的子问题．初始配流方案按启发式规则生成，解体计划和编组计划被类比于单机器排序问题，分别通过建立Ｏ一１规划模型依次制定．在满足模型假设４，且解体延误惩罚系数和编组延误惩罚系数都取１的前提下，计算出白班的中时为４．８４小时，晚班的中时为５．６７小时，满足中时约束条件．
问题二在问题一的基础上考虑了有特殊车辆优先运送的情况，在满足两个中时的约束条件的情况建立了一个非线性混合整数规划模型，按启发式规则得到调度方案．设定装有救灾物资的车辆所在待解车列的权值为４，装有发往Ｓ１货物和军用物资的车辆所在待解车列的权值为２，一般待解车列的权值为１；有救灾物资的车辆所在集结车列的权值为４，有发往Ｓ１货物和军用物资的车辆所在集结车列的权值为２，一般集结车列的权值为１．计算得到白班的中时为４．９８小时，晚班的中时为６．０１小时，救灾车的中时为０．８３小时，发Ｓ１和军用物资车的中时为１．６７小时，１天最多能编组完成７９１３辆车辆．
对于问题三，在保证有优先运送条件的同时，考虑在列车编组调度２小时内的快速反应能力，并通过建立一个货运列车日编组调度的阶段协同优化模型，来设计一种既满足中值尽量少又兼顾发车尽量多的编组调度方案．结果表明，该方案具有较好的稳定性和鲁棒性．
问题四主要考虑了在不可抗拒事件发生时，编组调度方案的应急能力．将Ｓ３站点转移到Ｅ４站点，在问题一的基础上对开往Ｓ３站点的所有列车（包括无调车）进行重新调配，生成新的调度方案，并在保证有优先运送和解体、编组延误惩罚系数取值同问题二的条件下计算得到白班的中时为４．７８小时，晚班的中时为６．０３小时，救灾车的中时为０．８３小时，发Ｓ１和军用物资车中时为１．８３小时，１天２４小时内最多能编组完成８４８６辆车．
对于问题五，提出驼峰采用双推单溜，设置两条牵出线的工作方案，来研究２４小时的编组凋度计划，解体、编组延误惩罚系数取值同问题二，得到白班的中时为２．５４小时，晚班的中时为１．７４小时，救灾车的中时为０．６７小时，发Ｓ１和军用物资的车中时为０．８３小时，１天最多能编组完成８８５８辆车辆，结果较双推单溜，单条牵出线的工作方案更好．
６结论
本文在分析了编组站各类车辆在站内走形路径的前提下，建立数学建模并利用计算机仿真技术分别研究了在正常和异常情况下编组调度方案的优化编制问题，对驼峰采用双推单溜、峰尾设置两条牵出线的扩能方案的效率进行了实验，表明扩能方案的优越性．然而，本文研究的编组调度问题只是编组站生产工作组织中较典型的问题，其他的问题如到达场、出发场股道安排，调车机车的运用，牵引机车的周转，双向编组站系统分工等，将在后续研究中展开．
１７２数学的实践与认识３９卷参考文献：
［１］郑时德．吴汉琳．铁路行车组织［Ｍ］．北京：中国铁道出版社，］９８７．
［２］胡思继．铁路行车组织［Ｍ］．北京：中国铁道出版社，１９９８．
［３３韩中庚．数学建模方法及其应用［Ｍ］．北京：高等教育出版社。２００５．
［４］王慈光．运输模型及优化［Ｍ］．北京：中国铁道出版社，２００４．
ＭｏｄｅｌａｎｄＡｌｇｏｒｉｔｈｍｆｏｒｔｈｅＭａｒｓｈａｌｌｉｎｇａｎｄ
ＤｉｓｐａｔｃｈｉｎｇＰｒｏｂｌｅｍｏｆＲａｉｌｗａｙＦｒｅｉｇｈｔＴｒａｉｎ
ＬＩＵＤｕｎｌ，ＺＨＡＯＪｕｎ２，ＨＡＮＤｏｎ９３，ＣＨＥＮＺｉ—ｌｉ４
（１．ＳｃｈｏｏｌｏｆＥｃｏｎｏｍｉｃｓａｎｄＭａｎａｇｅｍｅｎｔ，ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，
Ｃｈｅｎｇｄｕ６１００３１，Ｃｈｉｎａ）
（２．ＣｏｌｌｅｇｅｏｆＴｒａｆｆｉｃａｎｄＴｒａｎｓｐｏｒｔａｔｉｏｎ，ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ。
Ｃｈｅｎｇｄｕ６１００３１，Ｃｈｉｎａ）
（３．ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄ
Ｃｈｅｎｇｄｕ６１００３１，Ｃｈｉｎａ）
（４．ＣｏｌｌｅｇｅｏｆＭａｔｈｓ，ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ６１００３１，Ｃｈｉｎａ）Ｔｅｃｈｎｏｌｏｇｙ，ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，
Ａｂｓｔｒａｃｔ：ＢａｓｅｄＯｎｔｈｅｐｒａｃｔｉｃａｌｔｒａｎｓｐｏｒｔａｔｉｏｎｐｒｏｄｕｃｅｐｒｏｃｅｓｓｉｎａｒａｉｌｗａｙｔｗｉｃｅｄｉｒｅｃｔｉｏｎａｌ
ｍａｒｓｈａｌｌｉｎｇｓｔａｔｉｏｎ，ｔｈｅｍａｘｉｍｉｚｉｎｇｔｈｅｎｕｍｂｅｒｏｆｄｅｐａｒｔｕｒｅｗａｇｏｎｆｌｏｗｓａｎｄｍｉｎｉｍｉｚｉｎｇｔｈｅ
ａｖｅｒａｇｅｔｒａｎｓｆｅｒｔｉｍｅｐｅｒｗａｇｏｎｆｌｏｗｓｔａｙｉｎｇ
ｉｎｆｌｕｅｎｃｅｏｆｉｄｌｅｔｈｅａｔｓｔａｔｉｏｎａｒｅｃｏｎｓｉｄｅｒｅｄａｓｏｕｒｏｂｊｅｃｔｓｉｍｕｌｔａｎｅｏｕｓｌｙ．Ｔｈｅｎ，ｔａｋｉｎｇｔｈｅｃａｐａｃｉｔｙｌｉｍｉｔｏｆｓｏｒｔｉｎｇａｎｄｃｌａｓｓｉｆｙｉｎｇ
ｓｈｕｎｔｉｎｇｌｏｃｏｍｏｔｉｖｅ，ｔｈｅｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎａｒｒｉｖａｌａｎｄｄｅｐａｒｔｕｒｅｔｒａｉｎｓ，ｔｈｅｓｔａｙｔｉｍｅｏｆ
ｗａｇｏｎｓａｔｓｔａｔｉｏｎｉｎｔｏａｃｃｏｕｎｔ，ａ
ｔＯｎｏｎｌｉｎｅａｒｍｉｘｅｄｉｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌｗｉｔｈｍｕｌｔｉｉｐｈｏｂｊｅｃｔｉｖｅｓｈａｓｂｅｅｎｅｓｔａｂｌｉｓｈｅｄ
Ａｉｍｉｎｇ
ｗａｇｏｎａｔｍａｒｓｈａｌｌｉｎｇａｎｄｄｉｓｐａｔｃｈｉｎｇｐｒｏｂｌｅｍｏｆｒａｉｌｗａｙｆｒｅｉｇｈｔｔｒａｉｎ．ｔｈｅｈａｒｄｌｙｔｏｓｏｌｖｅｃｈａｒａｃｔｅｒｏｆｔｈｉｓｏｐｔｉｍｕｍｍｏｄｅｌ，ｗｅｄｉｖｉｄｅｄｔｈｉｓｐｒｏｂｌｅｍｉｎｔｏｂｒｅａｋ—ｕｐｏｆｗａｉｔｉｎｇｔｒａｉｎｆｌｏｗａｌｌｏｃａｔｉｏｎｐｒｏｂｌｅｍ，ｔｈｅｐｒｏｂｌｅｍａｎｄｔｈｅｍａｋｅ—ｕｐｏｆ
ｔｏｗａｉｔｉｎｇｔｒａｉｎｐｒｏｂｌｅｍ．Ｆｉｎａｌｌｙ，ａｄｉｓｊｏｉｎｔｌｅｖｅｌｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｈａｓｂｅｅｎｄｅｓｉｇｎｅｄ
ｔｈｉｓｐｒｏｂｌｅｍｉｎｔｈｅｏｒｄｉｎａｒｙａｎｄｅｓｐｅｃｉａｌｔｒａｎｓｐｏｒｔａｔｉｏｎｏｒｇａｎｉｚａｔｉｏｎｓｉｔｕａｔｉｏｎ．
Ｋｅｙｗｏｒｄｓ：ｓｏｌｖｅｍａｒｓｈａｌｌｉｎｇｓｔａｔｉｏｎｆｄｉｓｐａｔｃｈｉｎｇ；ｔｈｅａｖｅｒａｇｅｔｒａｎｓｉｔｔｉｍｅ；ｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍ
万方数据
货运列车编组调度问题的模型与算法研究
作者：
作者单位：刘盾， 赵军， 韩冬， 陈滋利， LIu Dun， ZHAO Jun， HAN Dong， CHEN Zi-li刘盾,LIu Dun(西南交通大学,经济管理学院,四川,成都,610031)， 赵军,ZHAO Jun(西南交
通大学交通运输学院,四川,成都,610031)， 韩冬,HAN Dong(西南交通大学信息科学与技术
学院,四川,成都,610031)， 陈滋利,CHEN Zi-li(西南交通大学数学学院,四川,成都
,610031)
数学的实践与认识
MATHEMATICS IN PRACTICE AND THEORY
2009，39(16)
0次刊名：英文刊名：年，卷(期)：被引用次数：
参考文献(4条)
1. 郑时德. 吴汉琳 铁路行车组织 1987
2. 胡思继 铁路行车组织 1998
3. 韩中庚 数学建模方法及其应用 2005
4. 王慈光 运输模型及优化 2004
相似文献(10条)
1.期刊论文 牛惠民. NIU Huimin 双向编组站列车调度调整的优化模型及算法 -中国铁道科学2007,28(6)
研究双向编组站调度优化问题,以解决到达列车接入系统和出发列车编组系统的实时调度调整.在分析双向编组站作业机理和规律的基础上,以列车的编成辆数、编组内容、接续时间、集结地点和作业能力为约束条件,以列车的走行距离、所产生的交换车数为综合优化目标,构造双向编组站列车调度调整的非线性优化模型.根据模型NP-Hard性和变量高度相关性的特点,建立基于网络流技术的遗传算法求解理论.算法的主要思想是在假定0-1变量已经确定的条件下,将整数变量的确定归结为求解网络最小费用流问题.以郑州北编组站为背景,给出算法的实际求解过程.求解算例表明,提出的方法能够有效解决到达列车和出发列车作业地点的实时选择问题.
2.学位论文 薛锋 编组站调度系统配流协同优化理论与方法研究 2009
编组站综合自动化是整个铁路运输现代化的重要组成部分，已建成的成都北编组站综合集成自动化系统(CIPS系统)和建设中的新丰镇编组站综合自动化系统(SAM系统)代表了我国铁路编组站信息化的发展趋势，它们整合并集成我国目前编组站各种成熟的过程控制分系统，统一信息管理，建立信息共享平台，有机地构建成管控一体化的整体系统。编组站CIPS系统和SAM系统实际上包括作业控制自动化、数据处理自动化和调度指挥智能化三大部分。这三大部分实际上形成按功能划分的三个子系统，它们紧密相联，互相依托，共同构成编组站综合自动化系统。其中，调度指挥子系统本质上属于决策支持系统(DSS)，而数据处理子系统本质上属于管理信息系统(MIS)，二者虽有联系，但面向不同层次，实现不同目标，具有不同功能。编组站调度指挥子系统(简称“调度系统”)是编组站综合自动化系统的核心，只有从优化作业计划入手，改善编组站作业，才能发挥出编组站调度系统“神经中枢”的作用。编组站调度系统配流问题是一个老问题，国内外学者一直在研究但未得到很好的解决方案，虽取得了一定的成果，但各有偏重，未能很好地从编组站整体角度考虑综合优化，有待进一步完善。
论文立足铁路编组站工作实际，从编组站调度大系统的角度出发，深入研究配流协同优化问题。论文借鉴了国内外相关研究成果，以理论研究为主，首先总结分析编组站的车流组织规律以及配流机理，然后在编组站调度系统界定和边际假设的基础上，综合运用大系统优化理论、协同论、组合数学等理论和观点，对编组站各单项作业进行系统的分析，同时注重作业环节的协调，将单项作业关联起来作为一个整体进行研究。论文的主要研究工作包括以下几个方面：
1．在深入分析编组站作业特征和作业流程的基础上，总结了编组站的车流组织规律，并对编组站调度系统进行了界定。通过分析配流问题的组合优化性质以及出发车流的来源，进一步揭示了编组站配流的内部机理。
2．以确定的编组站作业时间标准为依据，分别按调机的台数、调机作业方式、考虑固定作业和调机干扰与否，给出了计算到达列车的最早可能解体时刻和出发列车的最晚必须编组时刻的算法。在此基础上，以解体方案树模型及回溯算法确定列车的解体顺序，并提出列车编组顺序的调整方法。以先编组出发列车的单个配流方案为主线，建立了解编方案同步调整与协调匹配的协同优化模型。
3．汲取大系统优化理论、协同论的观点和方法，对到调机运用、到发线运用、调车线运用、取送车作业等建立一系列既相关又相对独立的模型和算法，包括静态与动态配流协同优化、到发线运用与解编作业协同优化、调车线运用与解编作业协同优化、取送车作业与解编作业协同优化等内容；引入系统综合的思想，将所建模型和算法进行有效地整合，建立编组站配流的综合协同优化模型，体现出系统的整体涌现性，构建了比较完善的编组站配流优化理论体系。
4．针对双向编组站衔接方向较多、易产生折角车流的特点，利用数学方法对交换车进行处理，同时考虑到达列车的接入场、出发列车的出发场以及股道调整等问题。在既有双向编组站系统作业分工方案的基础上，对于到发列车需要调整作业地点的情况，建立协同模型进行优化，尽可能地减少折角车流给编组站带来的能力损耗，实现到达车流在全站范围内的合理分配。
5．通过研究遗传算法和蚁群算法的融合，设计出一种集时间效率和求解精度于一体的快速算法——基于信息熵和混沌理论的遗传一蚁群协同优化算法，应用于求解编组站调度系统配流优化问题。
6．对所设计的算法应用计算机程序进行实现，并对郑州北站大量的现场数据进行测试，结果表明该算法能够在较短的时间内生成合理的配流方案，充分验证了优化模型和算法的有效性和实用性。
论文采用先局部后整体、由定性到定量、分层逐步解决的研究方法，加强了模型和算法的针对性设计，体现了配流整体优化的原则。论文的研究涵盖了与配流相关的编组站作业优化的主要内容，形成了一个相对完整的理论体系。编组站调度系统配流协同优化研究，作为编组站调度指挥智能化的应用基础理论研究，是编组站配流理论的深化，对提高编组站调度决策水平，实现编组站调度指挥科学化、智能化具有十分重要的作用，同时为建立编组站智能调度系统奠定可靠的理论基础。编组站配流的优化可以实现车站车流资源的优化配置，大力提高运输生产效率，进而产生巨大的经济和社会效益，因此论文的研究成果具有广阔的应用前景。
3.期刊论文 刘敏 大型钢铁企业编组站调度信息管理系统研究 -中国铁道科学2002,23(5)
从作业、任务、调度组织机构、列车种类等多个方面分析了钢铁企业编组站与铁路干线编组站的同异性,提出了钢铁企业调度信息管理系统应具备的系统功能,根据系统功能,将其软件结构划分成运输计划管理、预确报收集与处理、到达作业管理、现车管理、决策支持等八个子系统,并对各子系统进行了进一步划分,对系统硬件网络结构,提出可选用结构简单、可靠、传输距离远、负载重且实时性强的局域网,如千兆以太网组网方案,并给出系统网络结构图,对企业编组站的列车信息、车辆信息、股道信息、车场信息、作业信息、作业处理过程进行了数学描述,这对研制一个通用的钢铁企业编组站调度
信息管理系统有着重要的参考价值.
4.学位论文 胡猛 计算机编制编组站阶段计划的模型和算法的研究 2006
阶段计划是铁路编组站作业计划的核心部分，一个好的阶段计划应该反映出本阶段的工作重点，并按照列车编组计划的要求，把车流及时编成各种列车，保证本阶段的所有列车都正点发车，传统手工编制方法的弊端日趋明显。随着我国铁路现代化建设步伐的加快，作为铁路调度指挥自动化重要内容之一的编组站阶段计划自动化编制的研究势在必行。
本文在前人研究成果的基础上，针对编组站阶段计划编制的重点和难点，从我国铁路编组站实际情况出发，利用人工智能的最新研究成果—Agent及多Agent方法，结合启发式搜索及离散事件动态系统，对编组站阶段计划编制内容进行详细的分析，并对阶段计划编制系统的进行了初步探讨。论文主要内容如下：
1.对目前铁路编组站阶段计划编制的内容和流程进行了详细分析，指定编组站阶段计划编制问题的难点，论述了编组站阶段计划编制方法研究的紧迫性，并给出编组站阶段计划形式化描述。
2.基于人工智能最新成果—Agent及多Agent方法的编组站阶段计划编制方法研究中，讨论了系统的基本结构、功能及实现方法，并完成了各主要Agent子系统的设计与实现。
3.在完成编组站阶段计划编制系统构建的基础上，提出了阶段计划主要问题的模型和求解算法。在基于前人研究成果上，重点研究了“车流接续”的启发式搜索模型与算法，对原有的车流接续模型与算法进行了改进；利用离散事件动态系统的Job-Shop生产调度方法构建了到发线运用计划的模型与算法，并从空间和时间两个方面构建了疏解冲突模型与算法；在调车机车运用计划的研究中，在求得以“调车机车作业时间最小”为目标的单目标较优解的基础上，结合“调车机车走行距离最短”的目标，构建了双目标加权求和的目标函数，求出满足权重约束的双目标最优解。
4.结合实际科研项目，本文对编组站阶段计划编制系统进行了研究开发，系统能够对简单的原始资料进行整理、分析和设计，并在人工干预的条件下最终得到阶段计划表、技术作业图表及车流信息等一系列重要资料。
5.期刊论文 娄正良. Lou Zhengliang 编组站CIPS系统的调度计划管理 -铁路通信信号工程技术2006,3(4)
调度计划管理是编组站综合集成自动化系统的核心部分,本文阐述了编组站调度计划管理的原则和方法,并在此基础上将MAS具体应用于调度计划管理,在实时和优化之间取得一个比较好的平衡,满足了编组站调度计划的动态调整要求,取得了良好的效果.
6.期刊论文 崔炳谋. 马钧培. 张朴. CUI Bingmou. MA Junpei. ZHANG Pu 编组站进路调度优化算法 -中国铁道科学2007,28(2)
分析编组站作业进路选排问题的本质,以各任务的延误时间加权值总和最小为最优目标,以任务的前后工序选择路径为动态约束,建立编组站作业进路调度数学模型,采用遗传算法求解.编码采用定长染色体,长度为任务的工序数,每个工序采用2段制,编码中的顺序唯一地确定了每工序对指定进路占用的起讫时间和指标递推,设计基于优先规则的编码算法步骤.为保证解的可行性,将编码合法化,对工序进行拓扑排序.递推计算工序开始时间和结束时间,进而计算编码的目标值,并将其转化为适应值.采用轮盘赌与最优性相结合的方法进行选择,设计基于位置成组移位的杂交算子和随机交换的变异算子.以某编组站为例进行模拟计算,结果证明该算法满足编组站进路调度工作的要求.
7.学位论文 阳勇杰 编组站调度管理信息系统的应用开发研究 2006
随着我国铁路TMIS、DMIS系统的建成，联系铁道部、铁路局和车站的信息网已经形成。作为货车信息产生的节点——编组站，由于缺乏总体的规划，各个信息系统管理的信息和数据相对独立，难以互相共享。信息化作为实现铁路跨越式发展的必要条件，目前的信息系统已越来越不能满足我国编组站运营组织与管理现代化的需要。因此结合当前信息技术的发展状况及趋势，进一步提高编组站调度信息化水平的时机已经成熟。
本文首先分析了编组站信息系统的发展状况，指出目前各个系统存在的问题，然后以编组站调度指挥信息系统为前提，通过分析作业流程和信息流程的变化，提出了作业过程及工作岗位的整合方案和信息共享下业务内容的调整。在系统的分析、设计和实现部分，本文运用面向对象方法对编组站调度计划编制、信息流程做了详尽的系统分析，结合实际开发的特点设计了该系统的结构，并以郑州北站为背景，利用VisualC++程序开发工具和ORACLE数据库管理系统实现了编组站调度指挥信息管理系统的图形绘制、基础数据管理、数据分析、技术作业图表自动生成与打印等功能。最后，论文对我国编组站信息系统未来的发展提出了自己的看法与展望。
8.期刊论文 代科建. 薛锋 提高编组站调度人员的科学文化素质 -铁道运营技术2007,13(2)
由于编组站调度人员所承担繁重的工作任务,面对高新技术设备和铁路所采取的新措施,要求调度人员必须具有较高的科学文化素质.但在岗调度人员因专项业务培训不足和选用人员标准不高等原因,造成有的调度人员知识层次和文化水平不高,对掌握新技术设备和适应新的运输生产形势的能力出现困难,跟不上运输生产的现代化步伐,应采取相应措施进一步提高调度人员的科学文化素质.
9.学位论文 郝鹏飞 基于Multi-Agent编组站调度支持平台研究 2006
MAS(Multi-AgentSystem)是随着人工智能AI(ArtificialIntelligence)的发展而出现的一个具有自觉性、社会性、学习性的智能系统。它具有并行、健壮和易扩展的优点，为空间和图形以及没有集中处理数据的环境等问题提供了非常好的解决途径。MAS现在已经运用到了很多的领域：机器人足球、网络运输管理、Agent图书馆、互联网信息过滤、网络路由以及远程教育等。将MAS引入调度决策是一个很有研究意义的课题。
编组站的作业方式是根据上级调度部门下达的作业计划和确报系统发送的确报，结合自己站场的机车使用情况、现车在站场的分布的实际状况，制定出低耗、高效的作业计划，并且在实际作业中不断的修正计划的方式。
本文对编组站生产运行方式进行研究后，建立相应的模型，根据Multi-Agent的分散、独立、智能的计算模式构建了编组站智能调度决策平台，具有实时性、可靠性、可预测性，方便未来系统功能扩展，以及系统应用的领域扩展。
本文重点阐述了编组站智能调度决策平台中单agent模型、agent分类、agent间的协作，结合现行调度作业方式和JADEX的特点建立Agent模型，最后给出了平台的数据层设计。
10.期刊论文 刘霆. 何世伟. 王保华. 安健. LIU Ting. HE Shi-wei. WANG Bao-hua. AN Jian 编组站调度计划随机机会约束规划模型及算法研究 -铁道学报2007,29(4)
运用随机规划方法,研究列车解编时间随机变动情况下编组站阶段计划的优化编制问题,建立了以压缩车辆中时和减少出发列车晚点时间为目标的随机机会约束规划模型.将模型中的随机机会约束转化为相应等价形式,从而将随机规划模型转化为确定性模型,并提出了一种改进遗传算法对之进行求解.该算法基于列车解编顺序对染色体进行编码,并针对问题的特殊性设计了相应的交叉和变异操作.算例表明,设计的改进遗传算法能够在较短时间内收敛至最优解,编组站阶段计划的随机机会约束规划模型能取得可靠性更高的调度计划,为改进编组站的决策质量提供了一条解决的途径与方法.
本文链接：http://d.g.wanfangdata.com.cn/Periodical_sxdsjyrs200916017.aspx
授权使用：武汉大学(whdx)，授权号：0ddb991b-ab14-455e-95d5-9db5018343c5
下载时间：2010年7月16日