单向编组站配流与调机运用综合问题

Integrated Wagon-flow Allocation and Shunting Locomotive Scheduling Problem at Single-directional Marshalling Station

单向编组站配流与调机运用综合问题研究的是确定出发列车的编组内容,指派并调度解体和编组调机的任务,使得出发列车满足列车编组要求,调机任务没有冲突,且车辆在站总停留时间最小。基于并行机调度和资源分配理论,建立该问题的混合整数线性规划模型。设计有偏随机键遗传算法求解该优化模型,基于平均分配和随机分配规则生成初始种群,并采用参数均匀交叉算子以使子代能有效继承父代的优化特征。最后,以1个实际算例对所提出方法的有效性进行测试,并与现场采用的贪婪算法、直接求解模型的优化求解器CPLEX进行比较。算例结果显示所提算法在计算质量和计算效率上的优越性。

The integrated wagon-flow allocation and shunting locomotive scheduling problem lies to determine the make-up of departure trains and assign and schedule the break-up（make-up） tasks for break-up（make-up） shunting locomotives such that departure trains satisfy the train make-up rules and operations of shunting locomotives have no conflicts and are optimized to attain the shortest total time for wagons staying idle at railyard.Based on the theory of parallel machine scheduling and resource allocation,the mixed integer linear programming model was established.The biased random-key genetic algorithm was designed to solve the proposed optimization model.Initial population was generated on the principles of average allocation and random allocation,and the parameterized uniform crossover operator was adopted to help the offspring efficiently inherit the optimal characters of the parent.At last,the efficiency of the proposed method was tested on a practical instance and compared with the greedy algorithm and optimization solver CPLEX.Computational results verify the superiority in solution quality and computation time of the proposed algorithm.