A fast heuristic for the train scheduling problem. (English) Zbl 0799.90068

Summary: The train scheduling problem is an integer programming problem known to be NP hard. In practice such a problem is often required to be solved in real time, hence a quick heuristic that allows a good feasible solution to be obtained in a predetermined and finite number of steps is most desired. We propose an algorithm which is based on local optimality criteria in the event of a potential crossing conflict. The suboptimal but feasible solution can be obtained very quickly in polynomial time. The model can also be generalized to cater for the possibility of overtaking when the trains have different speed. We also furnish a complexity analysis to show the NP-completeness of the problem. Simulation results for two non-trivial examples are presented to demonstrate the effectiveness of the proposed algorithm.


90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI


[1] Mees, A. I., Railway scheduling by network optimization, Mathl. Comput. Modeling, 15, 33-43 (1991) · Zbl 0716.90057
[2] Goh, C. J.; Mees, A. I., Optimal control on a graph with application to train scheduling problems, Mathl. Comput. Modeling, 15, 49-58 (1991) · Zbl 0716.90034
[3] Mills, R. G.J.; Perkins, S. E., (Nonlinear programming applied to the dynamic rescheduling of trains, Internal report (1989), Department of Mathematics, South Australia Institute of Technology) · Zbl 0786.90032
[4] Garey, M. R.; Johnson, D. S., Computers and Intractability: A guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.