放射形铁路专用线直达车流取送车问题的单亲遗传算法研究＊

李海军，朱昌锋

(兰州交通大学交通运输学院，甘肃兰州 730070)

放射形铁路专用线直达车流取送车问题的单亲遗传算法研究＊

李海军，朱昌锋

(兰州交通大学交通运输学院，甘肃兰州 730070)

专用线最佳取送车顺序的确定，有利于减少作业车在站非生产性停留时间，加速车辆周转。通过分析放射形专用线直达车流取送车作业特点，构造了该问题的染色体编码方式，采用轮盘赌策略进行染色体选择，以作业车在站最小停留时间作为适应度函数，设计了该问题的单亲遗传算法，并结合算例进行计算，结果表明，该算法求解直达车流取送车问题取得了较好的效果。

放射形专用线;取送车作业;直达车流;单亲遗传算法

取送车作业是较大的货运站、技术站和大型厂矿企业专用线的联轨站的一项重要工作［1－2］，其效率高低直接关系到车辆周转和货物送达的快慢及运输指标的完成［3－4］。

对于直达车流取送车问题的研究，就放射形专用线，徐忠民等［5］以排列组合理论为基础，穷举所有取送方案，直接计算每一方案的作业中断时间，直至找到中断时间最小的方案或计算完所有方案，但这种方法计算工作量大，需要逐一计算每一方案的作业中断时间，当中断时间不能为零时，必须计算全部方案;宋建业［6］采用表上移动法，以取送同序方案为初始状态，通过在方案计算表上移动相邻送车顺序或取车顺序，使各作业地点的中断时间最大值降低到最小程度，从而得到一个最优取送顺序方案，方法简单实用。李文权［7］将取车、送车及作业分成2个子问题单独考虑，通过建立2类排序论模型，给出了放射形专用线上直达列车取送车计划的一个快速简单的算法。王慈光［8］对放射形专用线非直达车流取送车问题进行了研究，给出了送车需要时间和取车需要时间计算公式，提出了送车增量和取车增量概念，算法的设计遵循分部求解的思路，以隐枚举的方法实现。牟峰等［9］将取送车作业作为一个系统进行整体考虑，以货车在站停留的总车小时消耗最小为优化目标，建立数学模型，设计求解的编码方式，并采用基于云模型的参数自适应蚁群遗传算法进行仿真。

本文根据铁路运输组织的特点，研究运用单亲遗传算法编码构造求解放射形专用线直达车流取送车问题的具体算法，并对其运算过程和结果进行分析。

1 建立模型

1.1 问题的提出

对于直达车流整列到发、一台机车作业条件下的放射形专用线取送顺序问题，其作业方法为:空车整列到达车站，在到发线上进行必要的到达作业后，机车将空车分别送往各条专用线装车，装完的重车由该机车先后取回站内，编组成列出发。其作业特点为:机车每次送车或取车后都要回到车站。如图1所示，S代表车站，Li(i=1，2，…)代表专用线，使用一台机车作业。

图1 放射形专用线布置示意图Fig.1 The sketch map of RPTW

现在的问题是，如何合理确定取送车顺序，使得直达列车在车站的总停留时间最小。

1.2 模型建立

假定车站衔接n条专用线，分别标记为1，2，…，n，调车机车一次向专用线的作业地点送车或取车的走行时间为(i=1，2，…，n)，通过写实，此时间标准是已知的。当各作业地点所需的货物作业时间均大于其取送车时间时，各地点的货物装卸作业是与调机向其他地点取送作业平行地进行。送车过程完毕即可进行取车作业，且在车辆取送过程中为各地点所提供的货物作业时间都能满足需要时，显然，直达列车的作业停留总时间将有最小值，

否则，将产生调机等待货物作业完毕的取送车中断时间t中断，于是直达列车作业停留总时间将增加到

式中，t中断为该取送顺序方案下各货物作业地点所要求的中断时间中的最大值，即

就是说，保证t中断有最小值的取送车顺序方案，即为最佳取送车顺序方案。则有以直达列车作业停留总时间最小为优化目标的放射形专用线取送车问题的数学模型:

2 算法设计

2.1 编码表示

根据专用线取送车问题的特点，采用符号编码的方法。将各作业地点的序号按取(送)车顺序连接在一起，就可构成一个表示取(送)顺序的个体。X:［1，2，…，n］。本问题取送作业包括互相联系的送车和取车2个过程，所以记送车顺序为染色体的X部分，取车顺序为Y部分。如图2为一个取送方案的编码，该编码X部分表示送车顺序，Y部分表示取车顺序(此部分基因排列可由适应度函数的设计得到)。即送车顺序为4－2－3－1，取车顺序为2－3－4－1。

图2 取送车问题编码示意图Fig.2 The sketch figure of coding for RPTW

2.2 初始种群的产生

由于遗传算法的群体型操作需要，所以必须为遗传操作准备一个由若干初始解组成的初始群体。众多的个体组成了群体，在遗传算法处理流程中，继编码设计后的任务是初始群体的设定，并以此为起点逐代进化直到按某种进化停止准则终止进化过程，由此得到最后一代(或群体)。

本问题中，在规模为POP_SIZE种群中，每个染色体的X部分即为基因(作业地点)的随机排列。

2.3 适应度函数的设计

取送车问题的适应度函数计算算法如下:

Step 1 初始化currentTime，intervalTime= 0;

Step 2 遍历染色体X部分的所有基因位，计算各作业地点的完工时间 job［j］.completeTime=currentTime+job［j］.runTime+ job［j］.operTime，currentTime;

Step 3 按先作业完先取的原则确定取车顺序，此顺序即为染色体的Y部分;

Step 4 计算适应度函数值OBJECTIVE［i］。如果当前取车时间与当前作业地点取车走行时间之和小于此点作业完工时刻，即currentTime+fetch［k］.runTime ＜ fetch［k］.sendCtime，会产生机车中断时间intervalTime=fetch［k］.sendC-time － currentTime － fetch［k］.runTime。更新currentTime+=2* fetch［k］.runTime+intervalTime;则适应度函数值 OBJECTIVE［i］ =currentTime。

2.4 选择操作

实现步骤如下:

Step 4 采用模拟赌盘［10］操作(即生成0到1之间的随机数r与每个个体遗传到下一代群体的概率进行匹配)。若r∈［qi－1，qr］，则选择个体xi，(i=1，2，…，M)，q0=0，来确定各个个体是否遗传到下一代群体中。

2.5 变异操作

本问题是符号编码，编码字符集为 {1，2，3，4，…，n}，变异操作就是用这个字符集中的一个随机指定的且与原基因值不相同的符号去替换变异点上的原有符号。具体步骤如下:

Step 1 遍历所有个体，如果myu()产生的(0，1)区间的随机数小于变异概率P_MUTATION，则随机产生(0，N)(N为作业地点数)的2个位置;

Step 2 用shuffle()交换2个位置，更新适应度函数值OBJECTIVE［i］。

2.6 进化策略

为使遗传进化过程能够不断向理想的优化方向前进，本算法综合采用如下控制性进化策略。evaluation()遍历所有个体，找到适应度函数值OBJECTIVE［i］最小的个体(取送车问题的目标是取送作业过程花费最短)，将此个体始终放在种群的第1位。

2.7 终止准则

采用目标值变化控制准则，当连续G代个体最优目标函数值不发生变化时，终止算法。

3 算例分析

铁路某车站连接专用线8条(分别编号1，2，…，8)，该站仅有一台调车机车担当取送作业，各作业地点的机车走行时间、货物作业时间已知，如表1所示，要求确定最合理的取送车顺序，使从送车开始到取车完了的时间最小。

表1 各作业地点走行时间和作业时间Table 1 Running and operating time of each private line min

应用上述遗传算法，种群规模:N=30，变异概率:Pm=0.01，最大终止代数:100。经过多次迭代，得到的最佳送车顺序:4 8 5 3 6 1 7 2，取车顺序:8 4 5 6 3 1 7 2。从送车开始到取车完毕的时间为400 min，调车机车等待装卸的取送中断时间t中断=0 min，计算过程及结果表明算法的效果较好。

4 结论

放射形专用线直达车流取送车顺序优化，能减少货车周转时间，压缩作业车待送、待取等非生产性停留时间，因而对本问题的研究具有重要意义。由于问题本身的NP性质，当作业点数较多，规模较大时，组合方案数急剧增长，文献［5］采用的穷举搜索算法将难以实现。本文根据取送车作业特点，利用遗传算法的原理和方法，对最佳取送顺序进行了具体的算法设计，并编程运算，算例表明在货物作业地点较多时，可以获得较好的效果。

［1］宋建业，谢金宝.铁路行车组织基础［M］.北京:中国铁道出版社，2006.

SONG Jian-ye，XIE Jin-bao.Organization of train operation［M］.Beijing:China Railway Publishing House，2006.

［2］朱昌锋.基于Cross－efficiency DEA的中间站运营绩效分析［J］.铁道科学与工程学报，2010，7(6):95－98.

ZHU Chang-feng.Analysis of operation efficiency for railway intermediary stations based on Cross－efficiency DEA［J］.Journal of Railway Science and Engineering，2010，7(6):95－98.

［3］朱昌锋.铁路生产力布局调整背景下运到期限计算方法的改进［J］.铁道科学与工程学报，2010，7(4):111－115.

ZHU Chang-feng.A study of time limit of freight transport calculating method under adjusting of railway productivity distributing condition［J］.Journal of Railway Science and Engineering，2010，7(4):111 －115.

［4］陈伯羽.铁路编组场线路固定使用方案优选方法研究［J］.铁道科学与工程学报，2006，3(6):80 －82.

CHEN Bo-yu.Studying of optimization of fixed usage plan for railway marshalling yard tracks［J］.Journal of Railway Science and Engineering，2006，3(6):80 －82.

［5］徐忠民，孔庆钤.直达列车取送顺序的优化［J］.北方交通大学学报，1988(2):70－74.

XU Zhong-min，KONG Qing-qian.Optimization of sequencing for placing－in and taking－out of wagon groups of through goods train［J］.Journal of Beifang Jiaotong U-niversity，1988(2):70－74.

［6］宋建业.直达列车多点装卸取送顺序优化的表上移动法［J］.兰州铁道学院学报:自然科学版，2002(1):76－79.

SONG Jian-ye.Method for optimization of car－groupsending－and－fetching schedule［J］.Journal of Lanzhou Railway Institute:Natural Science Edition，2002(1):76－79.

［7］李文权.放射状专用线直达列车取送车问题的算法［J］.西南交通大学学报，1995(5):503 －508.

LI Wen-quan.An algorithm for the problem of fetching and delivering vehicles of through－running train on radial individual line［J］.Journal of Southwest Jiaotong U-niversity，1995(5):503 －508.

［8］王慈光.放射形专用线非直达车流取送车问题研究［J］.交通运输工程与信息学报，2006，4(3):16 －23.

WANG Ci-guang.Study of collection and delivery shunting of non－through wagon flow on actinoid private line［J］.Journal of Transportation Engineering and Information，2006，4(3):16 －23.

［9］牟 峰，王慈光，杨运贵.放射形专用线非直达车流取送车模型及算法［J］.铁道学报，2009(3):2－5.

MU Feng，WANG Ci-guang，YANG Yun-gui.Model and algorithm of taking－out and placing－in shunting of non－ through wagon flow on actinoid private lines［J］.Journal of the China Railway Society，2009(3):2 －5.

［10］玄光男，程润伟.遗传算法与工程优化［M］.北京:清华大学出版社，2004.

GEN Mitsuo，CHEN Run-wei.Genetic algorithms and engineering optimization［M］.Beijing:Tsinghua University Press，2004.

Study of through wagon flow on single－parent genetic algorithm for railway placing－in and taking－out of wagons in actinoid private line

LI Hai-jun，ZHU Chang-feng

(School of Traffic and Transportation，Lanzhou Jiaotong University，Lanzhou 730070，China)

Optimal order of placing－ in and taking－ out of wagons is in favour of reducing wagons non－productivity time in station and accelerating wagons turnaround.According to the analysis of characteristics of the operations on placing－ in and taking－ out of wagons in actinoid private line，this paper proposed a chromosome presentation and realized the genetic algorithm for the problem.Combined with an example，the results illustrated that this algorithm could find the optimal or nearly optimal solution to the placing－ in and taking－ out of wagons in actinoid private line problem effectively.

actinoid private line;operations on placing－ in and taking－ out of wagons;through wagon flow;single－parent genetic algorithm

U291.2

A

1672－7029(2011)06－0114－04

2011－11－25

教育部“春晖计划”资助项目(Z2005－1－62008);兰州交通大学青年科学研究基金项目

李海军(1978－)，男，青海乐都人，讲师，博士研究生，从事交通运输系统优化研究