Formulation and Solution Approaches to the Rail Maintenance Production Gang Scheduling Problem
Publication: Journal of Transportation Engineering
Volume 136, Issue 8
Abstract
The rail industry spends billions of dollars each year on maintenance and renewal of its track infrastructure. The scheduling of these maintenance projects is extremely complex, with numerous hard and soft cost trade-offs and job scheduling constraints. Scheduling requires consideration of efficient maintenance production “gang” routing around the rail network while paying close attention to any train delay such maintenance projects might cause. Despite this importance and complexity, the subject has been largely ignored in the literature. We evaluate two formulations (time-space network mixed integer program and job scheduling) and three modeling formulation and solution methodologies (integer programming, constraint programming, and genetic algorithms) for scheduling rail gangs to annual renewal projects and discuss their relative merits in terms of parsimony of model formulation, solution time, and solution quality. The purpose of this paper is to identify the most fruitful avenues for further research on this novel application.
Get full access to this article
View all available purchase options and get full access to this article.
References
Acharya, D., Sussman, J., and Martland, C. (1990). “Application of expert systems and network optimization techniques in rail relay scheduling.” Journal of Transportation Research Forum, 31(1), 1–16.
Association of American Railroads (AARs). (2007a). “The importance of adequate rail investment.” ⟨http://www.aar.org/GetFile.asp?File_ID=150⟩ (August 13, 2008).
Association of American Railroads (AARs). (2007b). National rail freight infrastructure capacity and investment study, Cambridge Systematics, Washington, D.C.
Balakrishnan, A., Li, G., and Roth, B. (2006). “Spatial scheduling and resource selection: Modeling, algorithm, and application to production gang scheduling for railway maintenance operations.” Working paper, Univ. of Texas at Austin.
Beck, J. C., Prosser, P., and Selensky, E. (2003). “Vehicle routing and job shop scheduling: What’s the difference?” Proc., 13th Int. Conf. on Automated Planning and Scheduling, AAAI, Menlo Park, Calif., 267–276.
Brailsford, S. C., Potts, C. N., and Smith, B. M. (1999). “Constraint satisfaction problems: Algorithms and applications.” Eur. J. Oper. Res., 119, 557–581.
Bräysy, O., and Gendreau, M. (2005). “Vehicle routing problem with time windows. Part I: Route construction and local search algorithms. Part II: Metaheuristics.” Transp. Sci., 39(1), 104–118.
Burns, D., and Clem, G. (2004). “Maximizing use of a track possession.” Railw. Track Struct., 92(11), 31–33.
Burns, D., and Franke, M. (2005). “Analyzing the blitz approach to M/W.” Railw. Track Struct., 93(12), 24–26.
Desrosiers, J., Dumas, Y., Solomon, M., and Soumis, F. (1995). “Time constrained routing and scheduling.” Handbooks in operations research and management science: Network routing, Vol. 8, M. O. Ball, T. L. Magnati, C. L. Monma, and G. L. Nemhauser, eds., North-Holland, Amsterdam, The Netherlands, 35–139.
Goldberg, D. (1989). Genetic algorithms in search, optimization and machine learning, Addison-Wesley, Reading, Mass.
Gorman, M. F. (1998). “An application of genetic and tabu searches to the freight railroad operating plan problem.” Ann. Operat. Res., 78, 51–69.
Grimes, A., and Barkan, C. (2006). “Cost-effectiveness of railway infrastructure renewal maintenance.” J. Transp. Eng., 132(8), 601–607.
Higgins, A. (1998). “Scheduling of railway track maintenance activities and crews.” Journal of the Operational Research Society, 49(10), 1026–1033.
Kanet, J., Ahire, S., and Gorman, M. (2004). “Constraint programming for scheduling.” Handbook of scheduling, J. Leung, ed., Chapman and Hall, New York.
Li, W., and Carter, D. (2002). “Find more like this project control system development for a design/build project.” Coastal Eng., 44(3), 39–48.
Pinedo, M. (1995). Scheduling: Theory algorithms and systems, Prentice-Hall, Englewood Cliffs, N.J.
Simson, S., Ferreira, L., and Murray, M. (1999). “Modeling rail track maintenance planning using simulation.” Proc., 15th National Conf. of the Australian Society for Operations Research, Australian Society for Operations Research, Gold Coast, Brisbane, 1159–1172.
Information & Authors
Information
Published In
Copyright
© 2010 ASCE.
History
Received: Nov 3, 2006
Accepted: Feb 3, 2009
Published online: Jul 15, 2010
Published in print: Aug 2010
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.