Abstract
This paper addresses the joint train-scheduling and demand-flow problem for a major US freight railroad. No efficient optimization techniques are known to solve the NP-hard combinatorial optimization problem. Genetic search is used to find acceptable solutions; however, its performance is found to deteriorate as the problem size grows. A "tabu-enhanced" genetic search algorithm is proposed to improve the genetic search performance. The searches are applied to test problems with known optima to gauge them for solution speed and nearness to optimality. The tabu-enhanced genetic search is found to take on average only 6% of the iterations required by genetic search, consistently achieves better approximations to the optimum and maintains its performance as the problem size grows. The tabu-enhanced search is then applied to the full-scale operating plan problem. Model results reveal a potential for 4% cost savings over the current railroad operating plan coupled with a 6% reduction in late service.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A.A. Assad, Multicommodity network flows - a survey, Networks 8(1978)37 -91.
A.A. Assad, Models for rail transportation, Transportation Research A14(1980)205 - 220.
A.A. Assad, Modelling of rail networks: Toward a routing/makeup model, Transportation Research B14(1980)101 - 114.
A.A. Assad, A class of train-scheduling problems, Transportation Science 16(1982)281 - 310.
C. Barnhart and Y. Sheffi, A network-based primal-dual heuristic for the solution of multicommodity network flow problems, Transportation Science 27(1993)102 - 117.
L.D. Bodin, B.L. Golden, A. Schuster and W. Romeg, A model for the blocking of trains, Transportation Research 14B(1980)115-120.
C.K. Chih and C.D Van Dyke, The intermodal equipment distribution model, Transportation Research Forum 29(1989)97 - 103.
T. Crainic, J. Ferland and J. Rousseau, A tactical planning model for rail freight transportation, Transportation Science 18(1984)165 - 184.
T. Crainic and J.M. Rousseau, Multicommodity, multimode freight transportation: A general modelling and algorithmic framework for the service network design problem, Transportation Research 208(1986)225 - 242.
T. Crainic, Rail tactical planning: Issues, models and tools, Proceedings of the International Seminar on Freight Transportation Planning and Logistics Bressanone, Italy, 1986.
L. Davis, (ed.), Handbook of Genetic Algorithms Van Nostrand Reinhold, New York, 1991.
S. Forrest (ed.), Proceedings of the 5th International Conference on Genetic Algorithms Morgan Kaufmann, San Mateo, CA, 1993.
B.L. Fox and M.B. McMahon, Genetic operators for sequencing problems, in: Foundations of Genetic Algorithms G.E. Rawlins, ed., Morgan Kaufmann, San Mateo, CA, 1991.
B.L. Fox, Integrating and accelerating tabu search, simulated annealing, and genetic algorithms, Annals of Operations Research 41(1993)47 - 67.
F. Glover, Tabu search - Part I, Journal on Computing 1(1989)190 - 206.
F. Glover, Tabu search - Part II, Journal on Computing 2(1990)4 - 32.
F. Glover, Tabu search: A tutorial - a heuristic procedure for solving optimization problems explained, Interfaces 20(1990)74.
F. Glover, Artificial intelligence, heuristic frameworks and tabu search, Managerial and Decision Economics 11(1990)365.
D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning Addison-Wesley, Reading, MA, 1989.
A.E. Haghani, Formulation and solution of combined train routing and makeup, and empty car distribution model, Transportation Research 23B(1989)433- 452.
J. Holland, Adaptation in Natural and Artificial Systems University of Michigan Press, 1975.
M.H. Keaton, Designing optimal railroad operating plans: Lagrangian relaxation and heuristic approaches, Transportation Research 23B(1989)415- 431.
M.H. Keaton, Service-cost tradeoffs for carload freight traffic in the U.S. rail industry, Transportation Research 25A(1991)363 - 374.
M.H. Keaton, Designing railroad operating plans: A dual adjustment method for implementing Lagrangian relaxation, Transportation Science 26(1992)263.
M.H. Keaton, The impact of train timetables on average car time in rail classification yards, Journal of the Transportation Research Forum 32(1992)345 - 354.
G.E. Liepins and M.R. Hilliard, Genetic algorithms: Foundations and applications, Annals of Operations Research 21(1989)31 - 58.
Z. Michalwicz, Genetic Algorithms + Data Structures = Evolution Programs Springer, Berlin/ Heidelberg, 1992.
E.K. Morlok and R.B. Petersen, Railroad freight train scheduling, a mathematical programming formulation, The Transportation Center and The Technological Institute, Northwestern University, 1970.
A. Nagurney, The formulation and solution of large-scale multicommodity equilibrium problems over space and time, European Journal of Operational Research 42(1989)166 - 177.
B. Sheffi, A relaxation/decomposition algorithm for the fixed charged network problem, Naval Research Logistics 37(1990)327 - 340.
B. Shetty, Reoptimization procedures for networks with side constraints, Computers in Engineering 20(1991)243 - 299.
M.A. Thomet, A user-oriented freight railroad operating policy, IEEE Trans. on Systems, Man and Cyber., SMC-1(1971)349 - 359.
C.D. Van Dyke, The automated blocking model: A practical approach to freight railroad blocking plan development, in: Proceedings of the 27th Annual Meeting of the Transportation Research Forum Vol. 27, 1986, pp. 116 - 121.
Rights and permissions
About this article
Cite this article
Francis Gorman, M. An application of genetic and tabu searches to the freight railroad operating plan problem. Annals of Operations Research 78, 51–69 (1998). https://doi.org/10.1023/A:1018906301828
Issue Date:
DOI: https://doi.org/10.1023/A:1018906301828