Author(s)

P Zhao, N Tomii, N Fukumura & T Sakaguchi

Abstract

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 an algorithm to quickly work out an approximate optimal schedule. The TSS work is divided into two sub-problems: the Train-Set Regular Inspection (TSRI) problem and the Train-Set Connecting (TSC) problem. The TSC is transformed into a Travelling Salesperson Problem (TSP) on a network called a TSS network, where the nodes correspond to trains and the arcs correspond to connections of trains, and a weight expressing the desirability of connection is put on each arc. In our algorithm, first, a regular inspection plan is made and then, a Hamilton tour is found. If the Hamilton tour satisfies the constraints concerning daily inspection, it could represent a feasible train-set schedule. Therefore, when finding a new Hamilton tour based on the local search method, the algorithm considers not only the connection of nodes, but also the inspection regulations. Based on the design, we have developed an approximation algorithm, and through experiments using actual data, we have proved practical train-set schedules can be obtained quickly.

Keywords