大型客运站调机运用优化模型及算法

2014-03-10崔文霖

交通科技与经济 2014年6期

贺锦，崔文霖

（兰州交通大学交通运输学院，甘肃兰州730070）

调机运用计划是铁路客运站作业计划的重要组成部分，其核心是确定始发和终到旅客列车的车底出入库时间、次序、调机运用及整备计划。调机作业计划是协调客运站各子系统作业的重要依据，具有重要作用。

1 调机运用优化分析

根据铁路客运站的列车径路对调机的优化问题进行分析，现有的铁路客运站调机运用安排研究是在调机数确定的条件下，从均衡利用调机的角度出发，先安排调机的车底出入库作业，并在此基础上，确定车底出入库时间。该文献分析了客运站旅客列车到、发技术的作业特点及车底出入库的时间特点，建立了客运站调机的运用优化模型。

在对调机作业进行优化的过程中，我们将调机作业的最早、最晚开始时间定义为调机作业时间窗口，并且调机所进行的作业时间窗口必须满足列车在客运站各项作业的时间标准，在这样的条件下，安排调机在最适当的时间下去完成调机所担当的任务，并且使得调机的运用达到最佳状态。根据对该问题的分析，我们将此问题划分为三个子问题（成组作业方案优化、调机作业顺序优化、咽喉区交叉干扰优化）进行分析研究:

1）当列车进入车站后，摘取本务机车，由调机将车底由到发线牵入至客车整备，进行相应的整备作业，并在此基础上为了不让调机返回到发场，使得调机有一次空程，通常按照车底出入库时间进行取送车底配对作业方案，使得调机的作业效率达到最佳，减少调车作业占用咽喉时间，在条件允许的情况下，应尽可能组织调机进行该类作业。

2）通过解决第一个问题可以得到调机成组的作业方案，将合并好的取、送车底作业替换为相应的成组取送作业后，可以得到一个调机作业的任务集合。并且其中有取送车底作业合并后调机任务数，则每个调机任务都拥有开始服务作业的时间窗口。调机作业顺序的优化问题，主要是确定每台调机的作业顺序，为每一个调机作业任务分配一个合适的调机作业，并保证调机的均衡作业。

3）第三个子问题就是在考虑调机均衡作业的同时要考虑到咽喉区的干扰情况，研究该问题的思路是在上一个问题确定好调机的作业任务，既要按照相应的任务安排进路，在安排进路时应尽量使得咽喉区的平行进路达到最大，减少敌对进路，根据调机作业的时间窗，去安排在该时间窗所要占用咽喉区的进路，并且计算出在该时间段内，咽喉区的最大平行进路数，根据比选找出最优进路，安排适合相应调机作业的进路。

下面重点分析讨论第二个子问题，即调机顺序安排模型。

2 调机顺序安排模型及算法

2.1 符号定义

J＝｛Ji｜i＝1，2，…，n｝:J为调机的任务集合，n为调机任务总数；

D＝｛dj｜j＝1，2，…，m｝:D为调机集合，m为调机总数；

nnew:取送车底作业合并后调机任务数；

Jnew＝｛jnewi｜i＝1，2，…，nnew｝:Jnew为调机作业的任务集合；每个调机任务拥有开始服务时间窗口；决策变量为第k个调机承担作业后紧接着承担作业j，1≤i≤n，1≤j≤n，1≤k≤m，n为作业项目总数，m为调机总数；

total＿time:所有调机任务需要的总调机作业时间；

work＿timemax:调机的最大作业时间；avg＿time:调机的平均作业时间。

2.2 问题描述

1）调机分工明确。对于某些既可用于办理车底出库作业，又能办理车底入库作业的调机看作“两台”调机，这“两台”调机在同一时刻视为一台调机。

2）一个车底在同一时间内只能占用一台调机，一旦占用则直至完成该次作业为止，中途不能由其它调机占用该车底。一台调机在同一时间只能被一项作业占用，直至该项作业完毕；一个车底同一时间内只能占用一条车底停留线，一旦占用某一车底停留线，不允许有其它车底占用该车底停留线，直至该车底离开该停留线时为止。

3）所有调机的运行速度都相同

2.3 模型建立

Jnew＝｛jnewi｜i＝1，2，…，nnew｝为调机作业的任务集合，其中nnew为取送车底作业合并后调机任务数，则每个调机任务拥有开始服务时间窗口［stei，stli］。

设xki为逻辑变量表示第k个调机承担作业i，车底为加工工件，车底Ji的最早可能入库时刻TRfirst－i为对应工件的到达时间rj，最晚可能出库时刻TClast－i为对应工件的完工期限dj，整备作业时间tj为对应工件的传递时间。将负责办理入库作业的调机集合Z1和出库作业的调机集合Z2作为两组处理机中心，由于取送车底得到调机成组作业方案后，将集合J中合并的取、送车底作业替换为相应的成组取送作业后，得到一个调机作业的任务集合。则将处理机Z1、Z2合并为一个处理中心，且认为该处理中心所有机器均为同速机。

调机作业顺序优化问题，主要确定每台调机的作业顺序，为每一个调机作业任务分配一个合适的调机，并保证调机均衡作业，描述为以下数学模型

由式（2）可以看到Z2为0～1间的正数，Z2越小表示调机作业的均衡性越高。当不需要考虑调机作业均衡性时Z2＝0，因此，解S的评价函数L可以由下式确定

式中:n为没有安排调机的任务数；M为对不可行解的惩罚系数，可以是一个正整数（取1 0000）；ω为解不均衡性的目标函数权重，为正数，可以取10。

采用M与ω的取值意义是在进行局部搜索时应首先保证解的可行性，并在此基础上兼顾调机作业的均衡性，L（S）的取值越小，解的性能越好

每项作业必须且只能安排一台适当的调机承担

在同一时刻每台调机只能承担一项作业

满足车站各项作业时间的标准，即满足列车、车底在站各项作业时间标准的要求，即调机作业时间应在其作业时间窗口内

2.4 算法求解

由于调机运用计划最终可描述为如下:客运站需要完成m项任务取送车底作业，现在恰好有n台机车可承担这些任务。每项任务只能由一台机车完成，每台机车最多只能完成一项任务，由于每台机车的走行距离以及取送车车底的长度不同，各台机车完成不同任务的费用（如时间）略有不同。应指派哪台机车去完成哪项任务，使每一个调机作业任务分配一个合适的调机，并力求调机均衡作业，即目标函数值接近于0。由目标函数可以看出Z为0～1的正数，Z越小表示调机作业的均衡性越高。该问题也可看成变形后的指派问题。

设计模拟退火算法如下:

Step1:用数值计算估计法确定模拟退火的初始温度；

Step2:指定参数，主要包括:数据文件名，人数n，任务数m，初始温度t0，退火速度和实验次数Ne；

Step3:从数据文件中读入费用矩阵；

Step4:构造一个初始解S0作为当前解，t⇐t0，l⇐1；

Step5:根据当前解S0构造一个邻居S′，如果满足条件S′的目标函数值f（S′）小于f（S′），则令S0⇐S′；否则，产生一个［0，1］间的随机数x，如果exp（－f（S′）－f（S′）t）＞x，则S0⇐S′；

Step6:l⇐l＋1；

Step7:如果l＜n2，转到Step5继续执行，否则，转到Step8；

Step8:t⇐αt；

Step9:如果t≥1×10－4，转到Step5继续执行，否则，结束本次实验，记录所得结果；

Step10:如果实验次数不足Ne，转到Step4继续执行，否则，输出所有实验结果，进行统计分析并输出，结束这组实验。

模拟退火算法用于求解大规模不对称指派问题，不仅收敛速度快，而且找到最满意解的概率也较高，具有很高的实用价值。该算法是专门针对人数大于或等于任务数的指派问题设计的，基本思想是从n个人中选出m个人去完成m个任务，如果任务数大于人数（m＞n），而且要求每个人最多只能完成一项任务，可以从m个任务中选出n个任务交给n个人去完成。对上述算法做很少的修改就能实现，因此，上述算法是求解大规模指派问题的通用算法。

第二阶段是对各调机担当的任务进行简单排序。

Step1:对于新任务入库车底，计算其最早入库时刻xj。

Step2:确定调机集合Z中各调机所处的状态，修正车底的最早入库时刻xj和最晚出库时刻yj。

Step3:对于新任务入库车底按其最早入库时刻xj由先到后进行排序，即xj＜xj＋1时，xj≻xj＋1，否则，xj≺xj＋1；若最早入库时刻相等，则按最晚出库时刻由先到后排序，即xj＝xj＋1，且yj＜yj＋1时，xj≻xj＋1，反之，则xj≺xj＋1，由此构成序列I，共n项。

2.5 调机顺序安排流程

调机顺序安排流程如图1所示。

图1 调机顺序安排流程

3 实例验证

某大型客运站一个班白天编制阶段计划，规定每日18时按0min计算，次日18时按1 440min计算。从中取出一个阶段，假设有34项车辆取送、移动任务需要8台取送调机完成，始发、终到列车共34对，取送车底合并后的作业任务数为272项，根据成组配对方案模型，按照建立的模型和算法对调机进行顺序安排、任务分配，在每个调机都有任务的前提下，对调机进行均衡性分析，使得每台调机都在有任务做的前提下实现调机均衡。

3.1 调机任务安排

以某大型客运站为例，将调机数量设为8台，取送车底合并后的作业任务数为272项，按照建立的模型和算法对调机进行顺序安排、任务分配，在每个调机都有任务的前提下，对调机进行均衡性分析，使得每台调机都在有任务做的前提下实现调机均衡。

3.2 调机均衡系数计算

先将各个任务运用快速排序算法按照所用时间长短从小到大进行排序，然后利用给出的模型计算出所有调机任务需要的总调机作业时间total＿time、调机的平均作业时间avg＿time、调机的最大工作时间work＿time，最后，计算出调机作业的均衡性系数h，调机均衡性系数越小，表示调机越均衡。程序中初始温度t0定为10 000℃，α定为0.98，内循环次数定为1 000次，算法终止条件为温度低于1×10－4，将该程序在Visual C＋＋6.0环境下运行，结果如图2所示。