Heuristic Techniques for Single Line Train Scheduling

被引：103

作者：

Higgins A. ^{[1
]}

Kozan E. ^{[1
]}

Ferreira L. ^{[2
]}

机构：

[1] School of Mathematics, Queensland University of Technology, QLD 4001

[2] School of Civil Engineering, Queensland University of Technology, QLD 4001

来源：

Journal of Heuristics | 1997年 / 3卷 / 1期

关键词：

Genetic algorithm; Hybrid algorithm; Local search; Tabu search; Train scheduling;

D O I：

10.1023/A:1009672832658

中图分类号：

学科分类号：

摘要：

Optimising a train schedule on a single line track is known to be NP-Hard with respect to the number of conflicts in the schedule. This makes it difficult to determine optimum solutions to real life problems in reasonable time and raises the need for good heuristic techniques. The heuristics applied and compared in this paper are a local search heuristic with an improved neighbourhood structure, genetic algorithms, tabu search and two hybrid algorithms. When no time constraints are enforced on solution time, the genetic and hybrid algorithms were within five percent of the optimal solution for at least ninety percent of the test problems.

引用

页码：43 / 62

页数：19

共 19 条

[1]

Cai X., Goh C.J., A Fast Heuristic for the Train Scheduling Problem, Computers and Operations Research, 21, pp. 499-510, (1994)

[2]

Davis L., Genetic Algorithms and Simulated Annealing, (1987)

[3]

Davis L., Handbook on Genetic Algorithms, (1991)

[4]

Gendreau M., Hertz A., Laporte G., A Tabu Heuristic for the Vehicle Routing Problem, Management Science, 40, pp. 1276-1290, (1994)

[5]

Glover F., Tabu Search: A Tutorial, Interfaces, 20, pp. 74-79, (1990)

[6]

Glover F., A Users Guide to Tabu Search, Annals of Operations Research, 41, pp. 3-28, (1993)

[7]

Goldberg D.E., Genetic Algorithms in Search, Optimisation, and Machine Learning, (1989)

[8]

Higgins A., Optimisation of Train Schedules to Minimise Transit Time and Maximise Reliability, (1996)

[9]

Higgins A., Kozan E., Ferreira L., Optimal Scheduling of Trains on a Single Line Track, Transportation Research B, 30, pp. 147-161, (1996)

[10]

Jovanovic D., Improving Railroad On-time Performance: Models, Algorithms and Applications, (1989)

← 1 2 →