基于位串的调车线受限站顺编组调车问题优化方法

Optimization Approach to Track Capacitated Train Assembly Shunting Problem with Sequence Partition Requirement Based on Bitstring

编组调车是铁路车站的主要日常工作之一,研究其优化方法对于提高车站编组调车作业效率和运输生产质量具有重要作用。研究调车线数量及能力受限下将一列车列按站顺编组为一列车列的编组调车问题,拓展基于位串的调车原理,使用两个0⁃1矩阵准确表示站顺编组调车作业计划;分别设计全线和留线位串法,在前者所有调车线循环连挂,在后者除列车编成线外剩余调车线循环连挂。为两类位串法设计统一的两阶段计算方法,按字典序最小化连挂钩数、调动车数、占用调车线数和溜放钩数。第一阶段给定连挂钩数与可用调车线集合,构建以调动车数最小为目标的0⁃1线性规划模型确定有效矩阵,通过逐步增加连挂钩数和缩减调车线集合迭代求解模型,直到达到预设条件;第二阶段定制3个规则进一步减少第一阶段获得有效矩阵的调动车数和溜放钩数。收集既有编组调车方法设计的多个算例,验证本文所提方法相比于既有方法的优越性。

Assembly shunting is one of the main daily operations in railway stations.Studying optimization approaches to this operation plays an important role in improving the efficiency of assembly shunting operations and transportation pro⁃duction quality of stations.This paper studied the shunting problem of assembling one inbound train into one outbound train with sequence partition requirement(SRP)under limited number and capacity of shunting tracks.By extending the existing shunting principle based on bitstring,two 0⁃1 matrices were used to accurately encode a valid assembly shunting operation plan with SPR.A full⁃track bitstring method and a reserved⁃track bitstring method were designed respectively.In the former,all shunting tracks were pulled out in a round robin sequence,while in the latter all shunting tracks ex⁃cept for the train formation track were pulled out in a round robin sequence.A unified two⁃stage computing approach,which minimized the numbers of pullouts,shunting railcars,occupied shunting tracks and roll⁃ins in a lexicographic or⁃der,was developed for the two bitstring methods.In the first stage,given the number of pullouts and the set of available shunting tracks,a 0⁃1 linear programming model with the objective of minimizing the number of shunting railcars was formulated to find the two valid matrices.The model was iteratively solved by gradually increasing the number of pullouts and reducing the set of shunting tracks,until preset conditions were met.In the second stage,three rules were custom⁃ized to reduce further the numbers of shunting railcars and roll⁃ins of the valid matrices obtained in the first stage.A set of instances designed by existing assembly shunting methods were collected to verify the superiority of the proposed shunting method to existing methods.