一种新的列车编组问题优化模型及算法(2)

即第i列车的到达时刻DT，i要小于等于其分解

（4）

即第i列车的分解时刻JT，j要小于等于其编组

2

2．1

模型求解

遗传算法

20世纪90年代以来，遗传算法（GeneticAlgo-

（5）（6）

rithm）的研究和应用得到了飞速的发展。遗传算法是美国的J．Holland教授于1975年在其专著《自然中首先提出来的，是模拟界和人工系统的适应性》

达尔文生物进化论的自然选择和遗传学机理的生

即编组列车j重车重量与空车重量和不超过

一种新的列车编组问题优化模型及算法

物进化过程的计算模型，后来发展为通过模拟自然进化过程来搜索函数最优解的方法。

遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，它模拟了自然选择和自然遗传交叉和基因突变等现象，在每过程中发生的繁殖、

次迭代中都保留一组候选解，并按某种指标从种群中选取较优的个体，然后利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

与传统的优化算法相比，遗传算法以决策变量可以借鉴生物学中染色体和的编码作为运算对象，

基因的概念，可以模仿自然界生物的遗传和进化机算子操作起来也非常方便。此外，遗传算法使理，

具有隐含并行性。用多个点的搜索信息，

由于遗传算法的整体搜索策略和优化搜索方法在计算上不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以它提供了一种求解复杂系统问题的通用框架，不局限于问题的具体领域，对问题的种类有很强的鲁棒性，所以GA除了广泛应用于函数优化、组合优化等方面外，也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。2．2

遗传算法求解

在求解模型（1）时，我们采用了遗传算法，具体步骤为：

1）将目标函数中的z转换为－z，把最小值问题转换为最大值问题；

2）决策变量的编码：采用二进制编码方式对决DT，JT，YijW等进行编码，策变量BT，构成子串，然j、i、i、“染色体”，并根据所给的货车时刻后把子串拼接成数据确定搜索空间；

3）种群大小：根据所给数据中白天和夜晚到达货车的列数，设置白班种群数为N=88，夜班种群数为N=96；

4）初始种群的产生：根据所给的数据随机选择初始种群；

5）适应度计算：选择目标函数值作为个体的适

应度，目标函数值越小，则适应度越大；

模型采用排序选择策略，即对于个体群P（t），计算每个个体的适应度，并将其按从大到小顺序进行排序，从中选择较优个体作为下一代P（t+1）；

6）算子确定：交叉算子Pc=0．4，变异算子Pn=0．01，最大的遗传代数为260，求解时采用Mat-lab遗传算法工具箱，最终分别求得白班和夜班的中时

［7，8］

。

表1

白班夜班中时

夜班中时/min

128

白班中时/min

146

表2

列车编号

解体开始时刻6：00

解体完成时刻6：08

白班上行解体计划

分解方案（辆数－轨道编号）

SD1

2－SB2，3－SB3，5－SB4，6－SB17，7－SB1，

5－SB18，6－SB19，2－SB20，SB21，……2－SB2，2－SB3，20－SB4，4－SB6，2－SB1，

SD26：086：17SB17，2－SB18，3－SB19，4－SB20，2－SB21，…………

2－SB10，10－SB11，3－SB12，SB13，SB15，2－SB16，8－SB17，SB18，SB19，………SB1，3－SB2，2－SB3，3－SB4，3－SB5，SB6，3－SB8，4－SB9，3－SB17，4－SB18，……………………………………

SD36：176：23

SD4……

6：34……

6：41……

表3

编组结束时间

白班上行编组方案

配流信息

出发车次

出发时间

出发方向

车流来源

（辆数/车编号）

重车数595610…

空车数0029…

车长数595639…

SXB0016：45SXB0026：45SXB0037：02……

……

6：507：057：22……

西西西……

59/s02156/s00239/s003…………

一种新的列车编组问题优化模型及算法

求解的过程中使用了遗传算法，故搜索过程带有一

3编组计划

在求解白班和晚班中时的过程中，我们得到了

同时也确保了搜索的全局性。虽然数定的随机性，

据量比较大，但因采用了Matlab遗传算法工具箱，所以编程比较简单，求解速度仍然很快，提高了模型求解的效率。

参

12

杨

DT，JT，BT，实际上这些值揭示了i、i、j等决策变量的值，到达列车的到达时刻、解体时刻、编组时刻等等，这些数据就是我们制定编组计划的依据。根据它们可以制定编组计划如表2和表3所示：

同样可以得到夜班的编组计划，在这里就不一一列出了。

考文献

2001浩，何世伟．铁路运输组织学．北京：中国铁道出版社，

林柏梁，朱松年．优化编组计划的非线性01规划模型及模拟退1999；21（2）：61—66火算法．铁道学报，

3史峰，孔庆钤，胡安洲．车流径路与编组计划综合优化的网络

1997；19（1）：16方法．铁道学报，

4结论

作为铁路车流组织的主要形式之一，分组列车

4查伟雄．直线方向列车编组计划的模型与算法．长沙铁道学院学1998；16（4）：90—94报，

MartinelliDR，TengHua-liang．Optimizationofrailwayoperationsusingneuralnet-works．TransportationResearch，1996；4（1）：33—49

5

具有减少货车集结时间、减轻途中调车作业负荷和加速车辆周转的显著作用。根据某编组站一天过以白班和夜班最小中时为指站货运列车的数据，

建立了实现列车编组的优化模型，并利用遗传标，

算法和Matlab遗传算法工具箱对其进行了求解，最后给出了列车解体计划和编组方案。由于在模型

67

http：//www．shumo．com/home/

谭湘强，钟映春，张学习，等．基于MATLAB遗传算法实现．广东2002；2：7—9自动化与信息工程，

2005；24（6）：曾日波．Matlab遗传算法工具箱的应用．软件技术，115—116

8

ANovelOptimizedModelforTrainFormationandItsSolution

YANGShu-guo

（MathematicalandPhysicalCollege，QingdaoUniversityofScience＆Technology，Qingdao266061，P．R．China）

［Abstract］Trainformationplanisaregulatorydocumentforrailwaymarshallingstationtocompletetrainma-

neuverandmanagement．Ascientifictrainformationplancanenhancetransportefficiency．Themodelingoftrainformationplanandthemethodformodelsolutionandtheplanmakingarediscussed．Firstly，theoptimizationmod-elsoftraindissolutionandformationbasedonthedataoftrainspassingastationsomedayisbuiltandtheirtargetsaretheminimummedium-timesofdayshiftandnightshift．Secondly，themodelsweresolvedbyGeneticAlgorithmandGeneticAlgorithmToolboxofMatlab．Finally，theschemesfortraindissolutionandformationarepresented．［Keywords］trainformationplan

railwaymarshallingstation

optimizationmodel

geneticalgorithm