博士学位论文 区段站到发线运用计划编制优化
针对具体的区段站到发线运用计划编制问题，在制订计划时具体的车站线路布局是固定的。文献[33]对客运站接发列车进路安排可行性问题的复杂性进行了研究,认为在客运站线路布置固定条件下的到发线运用计划编制可行性问题同网络图最短路问题类似，其时间复杂度为O(JSet*?1logJ)，J表示办理的接发列
车数，Set*表示关键轨道路段数，即除无岔轨道线路以外的其它轨道路段数。因区段站的接发列车进路与客运站没有本质区别，可直接利用其研究成果，因此本文由于增加了接车列车进路约束而引起的区段站到发线运用计划编制优化问题的时间复杂度增加量为O(nQ?1logn)。本文进路集合的主要元素采用道岔组而非单个道岔，也一定程度上降低了计算的复杂度。
3.4 本章小结
根据以上研究，可得到以下结论：
（1）以尽量按固定使用方案运用到发线和尽量使接发列车作业对调车作业的延误最小为优化目标，较以往研究更加符合铁路现场生产实际。
（2）在约束条件中考虑避免接发列车进路间冲突、列车进出站进路排列对到发线运用安排的限制和运用同一到发线的两列车间必要的安全间隔时间等绝对约束，提高了所编制计划的可行性。
（3）不采用传统的整数规划模型求解方法，结合现代排序理论，把模型转化为特殊的平行机固定工序排序模型，采用设计的启发式算法进行求解，可得到比较满意的到发线运用方案。
本章所讨论的到发线运用计划编制方法可利用目前铁路使用的列车调度指挥系统（TDCS）阶段计划中的列车预计到发时刻信息，合理地编制计划时段到发线运用计划，为构建区段站综合自动化系统车站作业计划的到发线运用计划编制优化部分提供理论支撑，同时也为复杂区段TDCS系统升级为调度集中控制系统（CTC），从而实现接发列车进路的自动编排提供理论支持。
35
博士学位论文 列车配流与调机运用计划综合编制优化
4 列车配流与调机运用计划综合编制优化
4.1 问题描述
列车配流问题是根据调车场和到达场的现车、到达列车所编组的车辆和货物、专用线、段管线能取回的车辆，确定列车运行图规定出发列车的具体编组内容，在出发列车停运的列数最少的基础上使得车辆在车站的总停留时间最短。前方技术站发送的预确报信息和车站掌握的现车提供了出发列车的车流来源；列车运行图规定了计划时段内本站出发的所有列车发车时刻；列车编组计划规定了列车的编组方法和出发列车的编组去向；车站行车工作细则记载了主要技术作业的平均作业时间。出发列车只有在满足满轴、正点和不违编的要求才能开行，不满足开行要求的出发列车可能被停运。满轴要求为出发列车的重量和长度必须在列车运行图规定的波动范围之内；正点要求为必须在列车运行图规定的出发时刻前完成列车的编组作业和出发作业；不违编要求为列车编组内容和位置必须符合列车编组计划的要求和铁路技术管理规程的相关规定。
调车机车运用计划规定了车站每台调车机车在计划时段内应完成的调车作业任务的项目、顺序和每项作业的起止时间。调车机车运用尽量按照作业固定区域分配作业任务，尽量减少作业间的交叉干扰，同时也要注意调机间作业任务和时间的相互配合。
区段站的列车配流和调机运用计划问题是两个相互关联的决策问题，由于摘去本务机车的车列本身没有动力，所以列车的解体、编组、取送、整场等作业任务都须由调车机车完成，因此合理的配流计划必须以调机运用计划可行为前提。由于区段站调机配备少，若只考虑往往使车流接续的合理性问题，可能会出现因调机的繁忙而使得到的配流方案无法实现，因此对区段站的列车配流问题建模和求解时，必须将考虑调机运用的可行性。
为有效完成解编列车和取送车辆等调车作业任务，区段站配备有一定数量的调车机车。对于只有配备一台调车机车的区段站，车站调车作业除本务机车出入段外，理所当然只有依靠这台调车来完成，因而不存在调车机车作业分工问题。配备两台及以上的区段站，一般按照车站的场区布置情况划分了调车机车的作业区域，也就是说对调车机车有初步的分工，依靠两台机车相互协作和配合完成所有的调车作业任务。
设T0为计划时段的开始时刻，在计划时段内的到达列车可认为由以下4类组成：
36
博士学位论文 列车配流与调机运用计划综合编制优化
（1）在T0时刻已被解入调车场集结，随时可以进行编组的货车，本文认为其为1列虚拟列车，因它可为出发列车直接配流，所以这部分车流对编组作业来说是最可靠的；
（2）在T0时刻已在到发场内等待解体的列车，这类列车的车流必须经过驼峰或者牵出线解体后才能作为出发列车的车流来源；
（3）计划时段内预计将到达列车车流，这部分车流必须经过到发场（到达场）到达作业、驼峰或牵出线解体后才能作为出发列车的车流来源；
（4）从货场、专用线、段管线在特定时间取回的车组可视为特定的到达列车。
上述4类列车分别记为XC、DJ、YD、QC。设DD为到达列车集，则有
DD?XC?DJ?YD?QC。
在计划时段内的出发列车可认为由以下3类组成： （1）列车运行图规定的在计划时段内出发的列车；
（2）计划时段后调车场结存的车辆，可认为其是一个虚拟的出发列车； （3）送往货场、专用线、段管线作业点的车组可视为特定发往货场、专用线、段管线的列车。
上述3类列车分别记为YF、JC、SC。设FF为出发列车集合，则有
FF?YF?JC?SC。
4.2 符号说明
为便于表述，定义以下符号：
设计划时段内到达区段站的列车有n列，集合DD中的列车根据到达时间的先后重新排列得到的新列车集合为J?{J1,J2,...,Jn}，到达时间为X?{x1,x2,...,xn}。从货物、专用线、段管线取回的货车视为的到达列车集合QC的列车到达时刻xi为取回到达调车场的时刻。虚拟列车XC和待解列车DJ的到达时刻为T0。按照
''列车的出发时间先后对出发列车排序，得到新的集合为J'?{J1',J2,...,Jm}，列车
的出发时间为Y?{y1,y2,y3,...,ym}，计划时段后调车场所结存的车辆所视为的列车JC的出发时刻为计划时段结束时刻T1；可将送往货场、专用线、检修线作业点的车组视为的出发列车SC的出发时刻为车组离开调车场时刻。
到达列车Ji(i?1,2,...,n)的到达技术作业时间标准为Tidd，解体作业时间为
Tijt,T0时刻调车场内的现车所构成的到达列车XC是不需要解体的，可直接配流，其解体作业时间可认为Tijt=0；出发列车J'j(j?1,2,...,m)的编组作业时间为
37
博士学位论文 列车配流与调机运用计划综合编制优化
Tjbz，出发作业的时间标准为Tjcf。送车作业视为的列车SC、计划时段后视为的出发列车JC的编组作业时间Tjbz和出发作业时间Tjcf均为0。
重车是按去向、空车是按车种定义去向。设去向集合为L，总去向数为L；
ail为到达列车Ji中l去向车数；?j表示根据车站的列车编组计划，可编入出发列车J'j的车流所有去向的集合；若到达列车Ji有车组的去向符合出发列车J'j的编组要求，则?ij取1，否则?ij取0；mj为出发列车j中的编成辆数。M为无穷大的正数。
定义的决策变量如下：
fijl表示到达列车Ji向出发列车J'j配去向组号l车流数量；tijt表示列车Ji的
'解体作业开始时间；tbzj表示列车Jj的编组作业开始时间；?ij表示到达列车Ji的
车组是否满足出发列车J'j的车流接续时间要求，满足要求则取1，否则取0；?j表
示出发列车J'j是否欠轴停运，停运则取1；否则取0。
4.3 模型建立
4.3.1 目标函数
列车配流与调机运用计划问题是车站作业计划编制的两个联系紧密的主要问题，其综合优化问题可描述为：根据车站目前的存车情况及预计到达列车的到达时间及编组信息、按照车站列车编组计划、相邻区段的列车运行图、铁路技术管理规程和车站行车工作细则的相关规定，合理确定计划时段内所有出发列车的编组内容及车辆来源，合理安排各调机承担的解体、编组、取送车及其它作业任务，确定各项调车作业的起止时间，使得出发列车满足不违编的要求并能正点出发，调机运用可行并比较合理，在停运列车尽可能少的条件下实现尽量压缩车辆在站总停留时间。因此，可用停运的出发列车数、铁路货车在站总停留时间两负指标作为列车配流与调机运用计划综合编制优化问题的优化目标。
一般来说出发列车中直达列车、直通列车、区段列车必须达到列车运行区段规定的牵引定数或换长，而对于摘挂列车、小运转列车、送车作业视为的列车重量和长度不受此限，但必须小于最大重量和牵引长度。因此，在计划时间内出发的列车YF可分为必须满轴出发的列车MYF、可欠轴的列车KYF，即
YF?MYF?KYF。计划时段后调车场结存的车辆视为的列车JC是一个不受重
量、长度限制的列车。往专用线、货场、检修线送往作业点的车组所视为的特定
38
博士学位论文 列车配流与调机运用计划综合编制优化
出发列车SC的重量受到调车机车牵引能力的限制。
第1个优化目标为停运的出发列车数越少越好，可表示为公式（4-1）。
minz1?j?MYF??j （4-1）
第2个优化目标为货车在区段站的总停留时间最小，可表示为公式（4-2）。
minz2????(yj?xi)fijli?1j?1l?1nmL （4-2）
本文对目标函数利用加权系数的方法将多目标优化问题转化为单目标优化问题，如公式（4-3）。
minz??1j?MYF? ?j??2???(yj?xi)fijl （4-3）
i?1j?1l?1nmL公式（4-3）中，?1、?2为权重系数，要求?1??2?1，其值由决策人员根据运输组织规则和个人经验综合确定。相对而言，第1个优化目标较第2个优化目标重要的多，权重系数?1取值应大于?2，以更好地体现第1个优化目标在目标函数的作用。 4.3.2 约束条件
（1）车辆约束
出发列车的车辆只能从符合出发列车的去向要求且编组前能解体或能取回的车辆中选取，出发列车编组车辆的数量必须达到列车运行图规定的重量和长度标准，因此必须满足以下三个条件：
① 车辆去向约束
到达列车Ji的车辆必须与出发列车J'j编组要求去向相符才能编入到列车J'j中，否则fijl?0；可利用公式（4-4）表示。
（4-4） fijl?M?ij ?Ji?J,Jj?J',l??j 公式（4-4）表示若两列车Ji、J'j没有去向相符的车组，则?ij?0，相应地
fijl?0。M为一足够大的正数。
② 车流接续时间约束
39
