An Ant Colony System Heuristic for Train Scheduling Problem

Train scheduling problem is one of the severe problems in rail transport planning. Mathematical programming, simulation, expert systems, heuristic and meta-heuristic methods, and combinational methods are amongst techniques for train scheduling. This paper develops an algorithm to train scheduling problem using Ant Colony System meta-heuristic. At first, a kind of train scheduling problem is formulated in a mathematical model and then the algorithm based ACS is presented to solve the problem. The problem is considered as a traveling salesman problem wherein cities represent the trains.ACS determines sequence of trains dispatched on the graph of TSP. According to the sequence as well as removing trains collisions incurred, train scheduling is determined. Numerical examples in small and medium size are solved by using the algorithm and compared to exact optimum solutions to check for the quality and accuracy. To analyze the solution results obtained, they are compared with those of exact optimization method of the train scheduling model. For this purpose, computations are carried out for 45 problems including 3 to 8 trains and 2 to 8 track sections. Comparison of the solutions shows good enough quality and time savings. Sensitivity of the run times of the algorithm with respect to variation of number of track sections as well as with respect to variation of number of trains have been shown and compared with those of exact optimization method. To clarify use of the proposed algorithm, a problem with 30 trains and 4 track sections is solved to illustrate the solution. Structure of the paper is as follows: section 1 presents a hierarchical process of rail transport planning and ant’s behavior which gives inspiration for ant algorithms, is presented. Section 2 reviews the literature of the train scheduling problem and then the manner of creating, developing and applying the ant algorithms is put forward. Section 3 presents the proposed ACS-based model and solution method using ACS for train scheduling. In this section a mathematical model for train scheduling on a single track line is presented. Section 4 illustrates the analysis of the model. This chapter compares the solution results obtained from the model with those of exact optimization method of the train scheduling. Section 5 presents a case study that supports the qualified results of the model. This section describes how to determine the ACS algorithm parameters and section 6 summarizes the paper