Freight train routing and scheduling in a passenger rail network: computational complexity and the stepwise dispatching heuristic

Freight train routing and scheduling in a passenger rail network: computational complexity and the stepwise dispatching heuristic

0.00 Avg rating0 Votes
Article ID: iaor20083275
Country: Singapore
Volume: 24
Issue: 4
Start Page Number: 499
End Page Number: 533
Publication Date: Aug 2007
Journal: Asia-Pacific Journal of Operational Research
Authors: , ,
Keywords: vehicle routing & scheduling
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.

Reviews

Required fields are marked *. Your email address will not be published.