编组站进路调度优化算法

An Optimization Algorithm for Route Dispatching in Marshalling Station

分析编组站作业进路选排问题的本质,以各任务的延误时间加权值总和最小为最优目标,以任务的前后工序选择路径为动态约束,建立编组站作业进路调度数学模型,采用遗传算法求解。编码采用定长染色体,长度为任务的工序数,每个工序采用2段制,编码中的顺序唯一地确定了每工序对指定进路占用的起讫时间和指标递推,设计基于优先规则的编码算法步骤。为保证解的可行性,将编码合法化,对工序进行拓扑排序。递推计算工序开始时间和结束时间,进而计算编码的目标值,并将其转化为适应值。采用轮盘赌与最优性相结合的方法进行选择,设计基于位置成组移位的杂交算子和随机交换的变异算子。以某编组站为例进行模拟计算,结果证明该算法满足编组站进路调度工作的要求。

The hypostasis characteristics of the problem on how to select route in marshalling yard are analyzed. With the contextual working procedure routes as dynamic restriction and the summation of all jobs daily over weigh minimally as objective, the mathematical model of route dispatching in marshalling station is established. The genetic algorithms for solving problems are put forward. The fixed length of chromosome is chosen for encoding. The length is working procedure number in a job and a working procedure is expressed with 2 segments. The sequence alone in the encoding can fix on the beginning and ending time of a designated route for each working procedure and the recursion of targets is designed. The encoding is designed based on priority and feasibility rule. In order to get feasible encoding the topological sort method is introduced. They are given for recursively computing the beginning or ending time of working procedure, computing each encoding target and transforming it as adaptive value. The combining roulette wheel with optimization selection is used. A position-based and group permutation crossover method and random mutation are introduced. An example is given to explain the computing steps and to illustrate the validity of the idea and algorithms that will meet the demand of route scheduling operations in marshalling yards.