Station Dispatching Problem for a Large Terminal: A Constraint Programming Approach

Abstract

At Howrah Station, the largest railway station in India, planners manually determine the routing and scheduling of train movements (referred to as train dispatching) at present. This approach to train dispatching, which is a complex combinatorial optimization problem, can result in long delays because planners have many resource-allocation options in the spatial and temporal domains. In this paper, we discuss a computational model to provide the best feasible solution(s) for minimizing the dispatching delays within a planning horizon. We consider an integrated station dispatching problem that consists of allocating and scheduling platforms and routes for trains at Howrah Station, and we develop a constraint programming (CP)-based approach to model the problem. We show that the delay that the model generates is approximately half the delay currently observed in practice. The solutions have been verified by Howrah Station authority, and the model is being considered for implementation. The novelty of the solution is that it uses a CP-based model for the integrated station dispatching problem and successfully deals with a large station with specific operational protocols.