FREIGHT TRAIN ROUTING AND SCHEDULING IN A PASSENGER RAIL NETWORK: COMPUTATIONAL COMPLEXITY AND THE STEPWISE DISPATCHING HEURISTIC

T. Godwin (), Ram Gopalan () and T. T. Narendran ()
Additional contact information
T. Godwin: Marketing and Planning Systems, Chennai 600034, India
Ram Gopalan: Fox School of Business and Management, Temple University, Philadelphia, PA 19122, USA
T. T. Narendran: Department of Management Studies, Indian Institute of Technology, Madras, Chennai 600036, India

Asia-Pacific Journal of Operational Research (APJOR), 2007, vol. 24, issue 04, 499-533

Abstract: In many countries, freight trains have to share a rail network with passenger trains. In this paper, we consider a situation where passenger trains must adhere to a strict published schedule, whereas freight train movements can be inserted at any convenient time, without disrupting scheduled passenger trains. We propose an algorithm for the problem of routing and scheduling of a single freight train in a passenger rail network. However, the multiple freight train routing and scheduling problem is shown to be NP-complete, even for simplified instances. Specifically, we show that both routing and scheduling of freight trains are difficult, even when only two freight trains are considered. It is also difficult when freight train movements are restricted to reach their destinations with no idling permitted at intermediate stations. We have developed aStepwise Dispatching Heuristicfor routing and scheduling multiple freight trains in a passenger rail network. Computational results confirm the efficacy of our algorithm for single freight train routing and of the proposedStepwise Dispatching Heuristic.

Keywords: Freight train scheduling; passenger rail network; computational complexity; stepwise dispatching heuristic (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595907001358
Access to full text is restricted to subscribers

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:wsi:apjorx:v:24:y:2007:i:04:n:s0217595907001358

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595907001358

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().