基于概率局域搜索的动车组平日运用计划编制算法

介绍动车组运用计划的含义、计划方案的评价准则;平日运用计划自动编制的启发式算法;算法将问题分为两个部分,即定期检修计划生成和动车组接续运用部分.将接续运用部分转化为某种旅行商问题,定义了动车组运用网络;在构造新的回路时能够考虑日常检修条件和动车组的利用效率.利用实际线路数据进行实验,证明算法有效.

An Algorithm for Train-set Scheduling on Weekday Based on Probabilistic Local Search

The Train-Set Scheduling(TSS) is one of the most important tasks in railway field. In fact, it is constrained by many maintenance conditions, station capacity and other factors, and is a NP-hard problem. This paper focuses on algorithm to quickly work out an approximate optimal schedule. The TSS work is divided into two sub-problems: Train-Set Regular Inspection(TSRI) and Train-Set Connecting(TSC). The TSC is transformed into a Traveling Salesperson Problem (TSP) on a network called TSS network, nodes respond to trains and arcs respond to connections of trains in the network, and weight for arcs are assigned. In our algorithm, first, a regular inspection plan is made, and then, a Hamilton tour is found. If a Hamilton tour satisfies the constraints concerning daily inspection too, it could represent a train-set schedule. Therefore, when finding a new Hamilton tour based on local search, the algorithm is not only considered the connection of nodes, but also the inspection regulations. Based on the design, we developed an approximation algorithm based on the probabilistic local search method, and proved that it can be obtained train-set schedule quickly.