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.