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, pages 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 a Stepwise Dispatching Heuristic for 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 proposed Stepwise Dispatching Heuristic.

Keywords: Freight train scheduling; passenger rail network; computational complexity; stepwise dispatching heuristic (search for similar items in EconPapers)
Date: 2007
References: Add references at CitEc
Citations Track citations by RSS feed

Downloads: (external link)
http://www.worldscinet.com/cgi-bin/details.cgi?type=pdf&id=pii:S0217595907001358 (application/pdf)
http://www.worldscinet.com/cgi-bin/details.cgi?typ ... ii:S0217595907001358 (text/html)
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: http://EconPapers.repec.org/RePEc:wsi:apjorx:v:24:y:2007:i:04:p:499-533

Ordering information: This journal article can be ordered from

Access Statistics for this article

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

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