IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v32y1998i4p380-404.html
   My bibliography  Save this article

A Survey of Optimization Models for Train Routing and Scheduling

Author

Listed:
  • Jean-François Cordeau

    (GERAD and École Polytechnique de Montréal, 3000, chemin de la Côte-Sainte-Catherine, Montréal H3T 2A7, Canada)

  • Paolo Toth

    (DEIS, Università di Bologna, Viale Risorgimento, 2, 40136 Bologna, Italia)

  • Daniele Vigo

    (DEIS, Università di Bologna, Viale Risorgimento, 2, 40136 Bologna, Italia)

Abstract

The aim of this paper is to present a survey of recent optimization models for the most commonly studied rail transportation problems. For each group of problems, we propose a classification of models and describe their important characteristics by focusing on model structure and algorithmic aspects. The review mainly concentrates on routing and scheduling problems since they represent the most important portion of the planning activities performed by railways. Routing models surveyed concern the operating policies for freight transportation and railcar fleet management, whereas scheduling models address the dispatching of trains and the assignment of locomotives and cars. A brief discussion of analytical yard and line models is also presented. The emphasis is on recent contributions, but several older yet important works are also cited.

Suggested Citation

  • Jean-François Cordeau & Paolo Toth & Daniele Vigo, 1998. "A Survey of Optimization Models for Train Routing and Scheduling," Transportation Science, INFORMS, vol. 32(4), pages 380-404, November.
    • Handle: RePEc:inm:ortrsc:v:32:y:1998:i:4:p:380-404
    DOI: 10.1287/trsc.32.4.380
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.32.4.380
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.32.4.380?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. George J. Beaujon & Mark A. Turnquist, 1991. "A Model for Fleet Sizing and Vehicle Allocation," Transportation Science, INFORMS, vol. 25(1), pages 19-45, February.
    2. William C. Jordan & Mark A. Turnquist, 1983. "A Stochastic, Dynamic Network Model for Railroad Car Distribution," Transportation Science, INFORMS, vol. 17(2), pages 123-145, May.
    3. Roger R. Crane & Frank B. Brown & Robert O. Blanchard, 1955. "An Analysis of a Railroad Classification Yard," Operations Research, INFORMS, vol. 3(3), pages 262-271, August.
    4. K. V. Ramani, 1981. "An Information System for Allocating Coach Stock on Indian Railways," Interfaces, INFORMS, vol. 11(3), pages 44-51, June.
    5. Arjang A. Assad, 1982. "A Class of Train-Scheduling Problems," Transportation Science, INFORMS, vol. 16(3), pages 281-310, August.
    6. Betsy S. Greenberg & Robert C. Leachman & Ronald W. Wolff, 1988. "Predicting Dispatching Delays on a Low Speed, Single Track Railroad," Transportation Science, INFORMS, vol. 22(1), pages 31-38, February.
    7. Edwin Mansfield & Harold H. Wein, 1958. "A Model for the Location of a Railroad Classification Yard," Management Science, INFORMS, vol. 4(3), pages 292-313, April.
    8. Carl D. Martland, 1982. "PMAKE Analysis: Predicting Rail Yard Time Distributions Using Probabilistic Train Connection Standards," Transportation Science, INFORMS, vol. 16(4), pages 476-506, November.
    9. Smith, M.E., 1990. "Keeping Trains on Schedule: On-Line Planning Systems for the Advanced Railroad Electronics System (ARES)," Journal of the Transportation Research Forum, Transportation Research Forum, vol. 31(1).
    10. Daganzo, Carlos F., 1987. "Dynamic blocking for railyards: Part II. Heterogeneous traffic," Transportation Research Part B: Methodological, Elsevier, vol. 21(1), pages 29-40, February.
    11. Pierre J. Dejax & Teodor Gabriel Crainic, 1987. "Survey Paper---A Review of Empty Flows and Fleet Management Models in Freight Transportation," Transportation Science, INFORMS, vol. 21(4), pages 227-248, November.
    12. Glickman, Theodore S. & Sherali, Hanif D., 1985. "Large-scale network distribution of pooled empty freight cars over time, with limited substitution and equitable benefits," Transportation Research Part B: Methodological, Elsevier, vol. 19(2), pages 85-94, April.
    13. Franz J. M. Salzborn, 1970. "The Minimum Fleetsize for a Suburban Railway System," Transportation Science, INFORMS, vol. 4(4), pages 383-402, November.
    14. Warren B. Powell, 1986. "A Stochastic Model of the Dynamic Vehicle Allocation Problem," Transportation Science, INFORMS, vol. 20(2), pages 117-129, May.
    15. Keaton, Mark H., 1989. "Designing optimal railroad operating plans: Lagrangian relaxation and heuristic approaches," Transportation Research Part B: Methodological, Elsevier, vol. 23(6), pages 415-431, December.
    16. Carey, Malachy, 1994. "A model and strategy for train pathing with choice of lines, platforms, and routes," Transportation Research Part B: Methodological, Elsevier, vol. 28(5), pages 333-353, October.
    17. Richard L. Sauder & William M. Westerman, 1983. "Computer Aided Train Dispatching: Decision Support Through Optimization," Interfaces, INFORMS, vol. 13(6), pages 24-37, December.
    18. Kraft, Edwin R., 1987. "A Branch and Bound Procedure for Optimal Train Dispatching," Journal of the Transportation Research Forum, Transportation Research Forum, vol. 28(1).
    19. K. V. Ramani & B. K. Mandal, 1992. "Operational Planning of Passenger Trains in Indian Railways," Interfaces, INFORMS, vol. 22(5), pages 39-51, October.
    20. Powell, Warren B., 1987. "An operational planning model for the dynamic vehicle allocation problem with uncertain demands," Transportation Research Part B: Methodological, Elsevier, vol. 21(3), pages 217-232, June.
    21. Bintong Chen & Patrick T. Harker, 1990. "Two Moments Estimation of the Delay on Single-Track Rail Lines with Scheduled Traffic," Transportation Science, INFORMS, vol. 24(4), pages 261-275, November.
    22. Mark H. Keaton, 1992. "Designing Railroad Operating Plans: A Dual Adjustment Method for Implementing Lagrangian Relaxation," Transportation Science, INFORMS, vol. 26(4), pages 263-279, November.
    23. William P. Allman, 1972. "An Optimization Approach to Freight Car Allocation Under Time-Mileage Per Diem Rental Rates," Management Science, INFORMS, vol. 18(10), pages 567-574, June.
    24. Kikuchi, Shinya, 1985. "Empty freight car dispatching model under freight car pool concept," Transportation Research Part B: Methodological, Elsevier, vol. 19(3), pages 169-185, June.
    25. Haghani, Ali E., 1989. "Formulation and solution of a combined train routing and makeup, and empty car distribution model," Transportation Research Part B: Methodological, Elsevier, vol. 23(6), pages 433-452, December.
    26. Crainic, Teodor G. & Rousseau, Jean-Marc, 1986. "Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 20(3), pages 225-242, June.
    27. Adamidou, Evdokia A. & Kornhauser, Alain L. & Koskosidis, Yiannis A., 1993. "A game theoretic/network equilibrium solution approach for the railroad freight car management problem," Transportation Research Part B: Methodological, Elsevier, vol. 27(3), pages 237-252, June.
    28. Michael Francis Gorman, 1998. "An application of genetic and tabu searches to the freight railroad operating plan problem," Annals of Operations Research, Springer, vol. 78(0), pages 51-69, January.
    29. E. R. Petersen, 1977. "Railyard Modeling: Part II. The Effect of Yard Facilities on Congestion," Transportation Science, INFORMS, vol. 11(1), pages 50-59, February.
    30. Odijk, Michiel A., 1996. "A constraint generation algorithm for the construction of periodic railway timetables," Transportation Research Part B: Methodological, Elsevier, vol. 30(6), pages 455-464, December.
    31. Carlos F. Daganzo, 1986. "Static Blocking at Railyards: Sorting Implications and Track Requirements," Transportation Science, INFORMS, vol. 20(3), pages 189-199, August.
    32. E. R. Petersen, 1974. "Over-the-Road Transit Time for a Single Track Railway," Transportation Science, INFORMS, vol. 8(1), pages 65-74, February.
    33. Jovanovic, Dejan & Harker, Patrick T., 1990. "A Decision Support System for Train Dispatching: An Optimization-Based Methodology," Journal of the Transportation Research Forum, Transportation Research Forum, vol. 31(1).
    34. Larry J. LeBlanc, 1976. "Global Solutions for a Nonconvex Nonconcave Rail Network Model," Management Science, INFORMS, vol. 23(2), pages 131-139, October.
    35. Nozick, Linda K. & Morlok, Edward K., 1997. "A model for medium-term operations planning in an intermodal rail-truck service," Transportation Research Part A: Policy and Practice, Elsevier, vol. 31(2), pages 91-107, March.
    36. E. R. Petersen & A. J. Taylor, 1982. "A Structured Model for Rail Line Simulation and Optimization," Transportation Science, INFORMS, vol. 16(2), pages 192-206, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lin, Bo-Liang & Wang, Zhi-Mei & Ji, Li-Jun & Tian, Ya-Ming & Zhou, Guo-Qing, 2012. "Optimizing the freight train connection service network of a large-scale rail system," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 649-667.
    2. Crainic, Teodor Gabriel & Laporte, Gilbert, 1997. "Planning models for freight transportation," European Journal of Operational Research, Elsevier, vol. 97(3), pages 409-438, March.
    3. Khaled, Abdullah A. & Jin, Mingzhou & Clarke, David B. & Hoque, Mohammad A., 2015. "Train design and routing optimization for evaluating criticality of freight railroad infrastructures," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 71-84.
    4. Arnt-Gunnar Lium & Teodor Gabriel Crainic & Stein W. Wallace, 2009. "A Study of Demand Stochasticity in Service Network Design," Transportation Science, INFORMS, vol. 43(2), pages 144-157, May.
    5. Michael F. Gorman, 1998. "Santa Fe Railway Uses an Operating-Plan Model to Improve Its Service Design," Interfaces, INFORMS, vol. 28(4), pages 1-12, August.
    6. Xin Wang & Teodor Gabriel Crainic & Stein W. Wallace, 2019. "Stochastic Network Design for Planning Scheduled Transportation Services: The Value of Deterministic Solutions," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 153-170, February.
    7. Kaj Holmberg & Martin Joborn & Jan T. Lundgren, 1998. "Improved Empty Freight Car Distribution," Transportation Science, INFORMS, vol. 32(2), pages 163-173, May.
    8. Bojovic, Nebojsa J., 2002. "A general system theory approach to rail freight car fleet sizing," European Journal of Operational Research, Elsevier, vol. 136(1), pages 136-172, January.
    9. Endong Zhu & Teodor Gabriel Crainic & Michel Gendreau, 2014. "Scheduled Service Network Design for Freight Rail Transportation," Operations Research, INFORMS, vol. 62(2), pages 383-400, April.
    10. Belgacem Bouzaiene-Ayari & Clark Cheng & Sourav Das & Ricardo Fiorillo & Warren B. Powell, 2016. "From Single Commodity to Multiattribute Models for Locomotive Optimization: A Comparison of Optimal Integer Programming and Approximate Dynamic Programming," Transportation Science, INFORMS, vol. 50(2), pages 366-389, May.
    11. Phil Ireland & Rod Case & John Fallis & Carl Van Dyke & Jason Kuehn & Marc Meketon, 2004. "The Canadian Pacific Railway Transforms Operations by Using Models to Develop Its Operating Plans," Interfaces, INFORMS, vol. 34(1), pages 5-14, February.
    12. Jin, Jian Gang & Zhao, Jun & Lee, Der-Horng, 2013. "A column generation based approach for the Train Network Design Optimization problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 1-17.
    13. Crainic, Teodor Gabriel, 2000. "Service network design in freight transportation," European Journal of Operational Research, Elsevier, vol. 122(2), pages 272-288, April.
    14. Chen, Chongshuang & Dollevoet, Twan & Zhao, Jun, 2018. "One-block train formation in large-scale railway networks: An exact model and a tree-based decomposition algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 1-30.
    15. Hallowell, Susan F. & Harker, Patrick T., 1998. "Predicting on-time performance in scheduled railroad operations: methodology and application to train scheduling," Transportation Research Part A: Policy and Practice, Elsevier, vol. 32(4), pages 279-295, May.
    16. Alena Otto & Erwin Pesch, 2017. "Operation of shunting yards: train-to-yard assignment problem," Journal of Business Economics, Springer, vol. 87(4), pages 465-486, May.
    17. Zhimei Wang & Avishai Ceder, 2017. "Efficient design of freight train operation with double-hump yards," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(12), pages 1600-1619, December.
    18. Shi, Ning & Song, Haiqing & Powell, Warren B., 2014. "The dynamic fleet management problem with uncertain demand and customer chosen service level," International Journal of Production Economics, Elsevier, vol. 148(C), pages 110-121.
    19. Xiao, Jie & Pachl, Joern & Lin, Boliang & Wang, Jiaxi, 2018. "Solving the block-to-train assignment problem using the heuristic approach based on the genetic algorithm and tabu search," Transportation Research Part B: Methodological, Elsevier, vol. 108(C), pages 148-171.
    20. Boliang Lin & Jingsong Duan & Jiaxi Wang & Min Sun & Wengao Peng & Chang Liu & Jie Xiao & Siqi Liu & Jianping Wu, 2018. "A study of the car-to-train assignment problem for rail express cargos in the scheduled and unscheduled train services network," PLOS ONE, Public Library of Science, vol. 13(10), pages 1-18, October.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:32:y:1998:i:4:p:380-404. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.