A heuristic for routing and scheduling freight trains in a passenger rail network

This paper addresses the problem of routing and scheduling freight trains in a rail network where passenger trains must adhere to a strict schedule and freight train movements can be inserted at any time or as demands arise, without disrupting passenger trains. An exemplar of such a situation is the Indian Railway System. The problem is formulated as a 0–1 mixed integer program to minimise the sum of travel times of the freight trains in a passenger rail network, for which a lower bound is developed. We propose a hierarchical permutation heuristic, which identifies the route and schedule for freight trains one at a time in a passenger rail network. A number of dispatching rules are proposed for identifying the best hierarchy in which trains must be scheduled. We report the computational experience for solving various problems based upon real data.