Train Routing Model and Algorithm Combined with Train Scheduling
Publication: Journal of Transportation Engineering
Volume 139, Issue 1
Abstract
This paper constructs a train routing model combined with a train scheduling problem, which is a 0–1 mixed-integer nonlinear programming problem. Except for train route choice, the model considers a system of complicated constraints on headway, trip time, meeting-crossing and overtaking between trains, capacity of siding, and so on. Based on the delay information of each train, a route adjustment algorithm is designed to obtain satisfactory route schemes of trains. Moreover, a tabu search procedure is designed to further improve the route schemes. The simulation results show that, relative to the optimal solution, the solutions obtained by the current method exhibit small relative error. The tabu search algorithm exhibits unstable performance because of dependence on the initial solution. Combined with the route adjust algorithm, the tabu search technique can improve the quality and stability of solutions. In addition, the departure order of heterogeneous trains exerts important influences on train route choice.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The National Key Basic Research Program of China (No. 2012CB725400), National Natural Science Foundation of China (No. 71101089, 71171129), Shanghai Municipal Natural Science Foundation (No.10190502500), and the Science and Technology Program of Shanghai Maritime University (No.20120056) financially supported this research. The authors thank anonymous referees and the editor for their comments and suggestions.
References
Assad, A. A. (1980). “Modeling of rail networks: Toward a routing/makeup model.” Transp. Res. Part B, 14(1–2), 101–114.
Borndörfer, R., and Schlechte, T. (2007). “Models for railway track allocation.” 7th Workshop on Algorithmic Methods and Models for Optimization of Railways, Dagstuhl Publishing, Saarbrücken/Wadern, Germany, 62–78.
Cacchiani, V., Caprara, A., and Toth, P. (2008). “Freight transportation in railway networks.” 〈http://arrival.cti.gr/index.php/Documents/0126〉 (Sep. 23, 2012).
Cai, X., Goh, C. J., and Mees, A. I. (1998). “Greedy heuristics for rapid scheduling of trains on a single track.” IIE Trans., 30(5), 481–493.
Caprara, A., Fischetti, M., and Toth, P. (2002). “Modeling and solving the train timetabling problem.” Oper. Res., 50(5), 851–861.
Carey, M. (1994a). “A model and strategy for train pathing with choice of lines, platforms and routes.” Transp. Res. Part B, 28(5), 333–353.
Carey, M. (1994b). “Extending a train pathing model from one-way to two-way track.” Transp. Res. Part B, 28(5), 395–400.
Carey, M., and Lockwood, D. (1995). “A model, algorithms and strategy for train pathing.” J. Oper. Res. Soc., 46(8), 988–1005.
Cordeau, J.-F., Toth, P., and Vigo, D. (1998). “A survey of optimization models for train routing and scheduling.” Transport. Sci., 32(4), 380–404.
Crainic, T. G., Ferland, J.-A., and Rousseau, J.-M. (1984). “A tactical planning model for rail freight transportation.” Transport. Sci., 18(2), 165–184.
Dorfman, M. J., and Medanic, J. (2004). “Scheduling trains on a railway network using a discrete event model of railway traffic.” Transp. Res. Part B, 38(1), 81–98.
Gao, Z. Y., Zhou, H. L., Li, K. P., Ning, B., and Tang, T. (2008). “Analyzing and evaluating the three-line rail traffic.” Sci. China Technol. Sci., 51(7), 949–956.
Gendreau, M., Hertz, A., and Laporte, G. (1994). “A Tabu Heuristic for the vehicle routing problem.” Manage. Sci., 40(10), 1276–1290.
Glover, F. (1986). “Future paths for integer programming and links to artificial intelligence.” Comput. Oper. Res., 13(5), 533–549.
Glover, F. (1990). “Tabu search: A tutorial.” Interfaces, 20(4), 74–79.
Glover, F. (1993). “A users guide to tabu search.” Ann. Oper. Res., 41(1), 3–28.
Gorman, M. F. (1998). “An application of genetic and tabu searches to the freight railroad and operating plan problem.” Ann. Oper. Res., 78(1), 51–69.
Haghani, A. E. (1989). “Formulation and solution of a combined train routing and makeup, and empty car distribution model.” Transp. Res. Part B, 23(6), 433–452.
Higgins, A., Kozan, E., and Ferreira, L. (1996). “Optimal scheduling of trains on a single line track.” Transp. Res. Part B, 30(2), 147–161.
Higgins, A., Kozan, E., and Ferreira, L. (1997). “Heuristic techniques for single line train scheduling.” J. Heuristics, 3(1), 43–62.
Huntley, C. L., Brown, D. E., Sappington, D. E., and Markowicz, B. P. (1995). “Freight routing and scheduling at CSX Transportation.” Interfaces, 25(3), 58–71.
Ingolotti, L., Barber, F., Tormos, P., Lova, A., Salido1, M. A., and Abril, M. (2006). “A scheduling order-based method to solve timetabling problems.” Current topics in artificial intelligence, Springer, Berlin, 52–61.
Jovanovic, D., and Harker, P. T. (1991). “Tactical scheduling of rail operations: The SCAN I system.” Transport. Sci., 25(1), 46–64.
Keaton, M. H. (1989). “Designing optimal railroad operating plan: Lagrangian relaxation and heuristic approaches.” Transp. Res. Part B, 23(6), 415–431.
Keaton, M. H. (1991). “Service-cost tradeoffs for carload freight traffic in the U.S. rail industry.” Transp. Res. Part A, 25(6), 363–374.
Keaton, M. H. (1992). “Designing railroad operating plans: A dual adjustment method for implementing Lagrangian relaxation.” Transport. Sci., 26(4), 263–279.
Kraay, D. R., and Harker, P. T. (1995). “Real-time scheduling of freight railroads.” Transp. Res. Part B, 29(3), 213–229.
Kraft, E. R. (1987). “A branch and bound procedure for optimal train dispatching.” J. Transport. Res. Forum, 28(3), 263–276.
Li, F., Gao, Z. Y., Li, K. P., and Yang, L. X. (2008). “Efficient scheduling of railway traffic based on global information of train.” Transp. Res. Part B, 42(10), 1008–1030.
Li, K. P., Gao, Z. Y., Tang, T., and Yang, L. X. (2010). “Solving the constrained shortest path problem using random search strategy.” Sci. China Technol. Sci., 53(12), 3258–3263.
Marín, A., and Salmerón, J. (1996a). “Tactical design of rail freight networks. Part I. Exact and heuristic methods.” Eur. J. Oper. Res., 90(1), 26–44.
Marín, A., and Salmerón, J. (1996b). “Tactical design of rail freight networks. Part II. Local search methods with statistical analysis.” Eur. J. Oper. Res., 94(1), 43–53.
Morlok, E. K., and Peterson, R. B. (1969). Final report on the development of a geographic transportation network generation and evaluation model, Transportation Center, Northwestern Univ., Evanston, IL.
Pudney, P., and Wardrop, A. (2008). “Generating train plans with problem space search.” Computer-aided systems in public transport, Springer, Berlin, 195–207.
Sauder, L., and Westerman, W. M. (1983). “Computer aided train dispatching: Decision support through optimization.” Interfaces, 13(6), 24–37.
Semet, F., and Taillard, E. (1993). “Solving real life vehicle routing problems efficiently using Tabu search.” Ann. Oper. Res., 41(4), 469–488.
Szpigel, B. (1973). “Optimal train scheduling on a single track railway.” Operational research ’72, Ross, M., ed., North-Holland, Amsterdam, Netherlands, 343–352.
Yang, L. X., Gao, Z. Y., Li, X., and Li, K. P. (2011). “A weighted min-max model for balanced freight train routing problem with fuzzy information.” Eng. Optimiz., 43(12), 1289–1309.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 139 • Issue 1 • January 2013
Pages: 81 - 91
Copyright
© 2013 American Society of Civil Engineers.
History
Received: Feb 2, 2012
Accepted: May 24, 2012
Published online: May 29, 2012
Published in print: Jan 1, 2013
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.