Multi-Commodity Network Flow Based Approaches for the Railroad Crew Scheduling Problem

Balachandran Vaidyanathan

No 207928, 48th Annual Transportation Research Forum, Boston, Massachusetts, March 15-17, 2007 from Transportation Research Forum

Abstract: In this paper, we study one of the most important railroad optimization problems, the crew scheduling problem, in the context of North American railroads. Crew scheduling for North American railroads is very different from that of European railroads, which has been well studied. The crew scheduling problem is to assign crew (train operators) to scheduled trains over a time horizon (generally a week) at minimal cost while honoring several operational and contractual requirements. Each North American Class I railroad spends at least a billion dollars in crew costs annually and does not have any decision support system available that can assist it in all levels of decision making: tactical, planning, and strategy. Indeed, all decisions related to crew are made manually, thereby leaving sufficient room for improvement. We have developed a network-flow based crew-optimization model that has applications in all levels of decision making in crew scheduling: tactical, planning, and strategy. Our network-flow model maps the assignment of crew to trains as the flow of crew on an underlying network where different crew types are modeled as different commodities in this network. We formulate the crew assignment problem as an integer-programming problem on this network, which allows this problem to be solved to optimality. We also develop several highly efficient algorithms using problem decomposition and relaxation techniques, where we use the special structure of the underlying network model to obtain significant speed-ups. We present very promising computational results of our algorithms on the data provided by a major North American railroad. Our network flow model is likely to form a backbone for a decision-support system for crew scheduling.

Keywords: Research and Development/Tech Change/Emerging Technologies; Research Methods/ Statistical Methods; Resource/Energy Economics and Policy (search for similar items in EconPapers)
Pages: 33
Date: 2007-03
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://ageconsearch.umn.edu/record/207928/files/2007_7B_RailCrew_paper.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ags:ndtr07:207928

DOI: 10.22004/ag.econ.207928

Access Statistics for this paper

More papers in 48th Annual Transportation Research Forum, Boston, Massachusetts, March 15-17, 2007 from Transportation Research Forum
Bibliographic data for series maintained by AgEcon Search ().