Author(s)

T Lambropoulos

Abstract

The optimal train dispatching problem has been studied by various researchers from 1965 onwards. The objective posed in this problem is to identify departure and arrival times of trains circulating over a single or partially double track railway axis while minimizing the total delays incurred by trains due to meets and satisfying the constrains posed by the infrastructure and the operation’s regulations. This problem, which is known to be NP-complete, is usually formulated as a Mixed-Integer Programming problem and solved via branch- and-bound algorithms. In order to give the optimal or near-optimal solutions to real-life instances of this problem efficient heuristics are required. This paper presents the application of a Genetic Algorithm (GA) for the solution of the problem. It proposes the appropriate binary encoding of the feasible solutions to the problem along with the necessary genetic operators and termination criteria and then explores the behavior of the algorithm as a function of Population size and mutation and crossover parameters. The investigation (with problem instances up to 20-30 meets) GAS have satisfactory performance but the population size which leads to accurate results grows exponentially as the number of meets grows which in turn leads to a proportional growth of the number of chromosome decodings. However the inherent capability of GAS for parallel processing, promises the possibility for reductions in running time through parallel implementations of the algorithm.

Keywords