技术站广义动态配流问题的局部邻域搜索算法

Local Neighborhood Search Algorithm for Generalized Dynamic Wagon-Flow Allocation of Railway Technical Stations

为了实现技术站阶段计划的计算机编制,研究了静态配流和列车解编方案调整的协同优化.在综合考虑优先排空和优先发送较近编组去向车流的编组要求、欠轴列车停运要求,以及到发列车时间和车流接续关系的基础上,以静态配流为主线,通过调整欠轴列车编组顺序以及与其相关到达列车的解体顺序构造邻域,设计了局部邻域搜索算法.该算法的主要思路是:每次搜索只考虑最早出发的欠轴列车;构造其邻域时保证不产生新的欠轴列车;通过邻域搜索后,该列欠轴列车如不能满轴就停运.算例表明,与既有方法相比,该算法能求出编组列车数、编组车辆数和中时的更好解.

To realize computer-aided stage plan making for railway technical stations,the collaborative optimization problem of static wagon-flow allocation for train break-up and make-up sequence adjustment was studied.A local neighborhood search algorithm was designed,which meets the comprehensive requirements for train making-up,such as giving make-up priority to loaded wagon-flows for the nearest destination and the empty wagons,withdrawal of under-loaded trains,and the time and wagon-flow relationship between arrival and departure trains.In the algorithm,the main loop is to solve the static wagon-flow allocation problem,and the neighborhood is constructed by adjusting the make-up sequence of under-loaded trains and the break-up sequence of the arrival trains related to them.In each search loop,the algorithm only searches the earliest under-loaded departure train,its local neighborhood is so constructed that no new under-loaded train is produced,and that a train is withdrew if it is still under-loaded after the neighborhood search.A computational example demonstrated that the proposed algorithm could find a better solution in terms of the numbers of make-up trains and wagons,and average detention time of wagons in transit than the existing algorithms.