Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0799.90068
Cai, X.; Goh, C.J.
A fast heuristic for the train scheduling problem. (English)
[J] Comput. Oper. Res. 21, No.5, 499-510 (1994). ISSN 0305-0548

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.

MSC 2000:: *90B35 Scheduling theory
90C10 Integer programming
90C60 Abstract computational complexity for math. programming problems

Keywords: train scheduling; NP-completeness

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]