Optimal scheduling of urban transit systems using genetic algorithms

Abstract

Scheduling of urban transit network can be formulated as an optimization problem of minimizing the overall transfer time (TT) of transferring passengers and initial waiting time (IWT) of the passengers waiting to board a bus/train at their point of origin. In this paper, a mathematical programming (MP) formulation of the scheduling problem at one transfer station is presented. The MP problem is large and nonlinear in terms of the decision variables, thereby making it difficult for classical programming techniques to solve the problem. We apply genetic algorithms (GAs)-search and optimization methods based on natural genetics and selection-to solve the scheduling problem. The main advantage of using GAs is that the problem can be reformulated in a manner that is computationally more efficient than the original problem. Further, the coding aspect of GAs inherently takes care of most of the constraints associated with the scheduling problem. Results from a number of test problems demonstrate that the GAs are able to find optimal schedules with a reasonable computational resource. The paper concludes by presenting a number of extensions to the present problem and discusses plausible solution techniques using GAs. The success of GAs in this paper suggests their efficacy as a solution tool for similar optimization problems arising in transportation systems.