Author(s)

K. Ghoseiri

Abstract

This paper develops a new algorithm to the train scheduling problem using Ant Colony System (ACS) meta-heuristic. At first, a mathematical model for a kind of train scheduling problem is developed and then the algorithm based on the meta-heuristic is presented to solve the problem. The problem is considered as a traveling salesman problem (TSP) wherein cities represent the trains. ACS determines the sequence of trains dispatched on the graph of the TSP. Based on the sequence obtained and removing for collisions incurred, train scheduling is determined. Numerical examples in small and medium sizes are solved by using the algorithm. The solutions are compared to the exact optimum solutions to check for quality and accuracy. Comparison of the solutions shows that the algorithm results in good enough quality and time savings. A case study is presented to illustrate the solution. Keywords: meta-heuristic, ant colony optimization, Ant Colony System, train scheduling problem, traveling salesman problem. 1 Introduction Rail transport planning is a very complex task which is carried out based on the mutual reaction among a large number of impressed components. As it was mentioned in Ghoseiri et al [5] and Lindner [10], in respect of complexity of rail transport planning, this process is divided into several steps. These procedures include the demand analysis, line planning, train scheduling, rolling stock planning and crew management [5]. These problems are NP-hard problems and solving them with exact algorithms is very difficult and time consuming.

Keywords

meta-heuristic, ant colony optimization, Ant Colony System, train scheduling problem, traveling salesman problem.