Locomotive assignment problem: integrating the strategic, tactical and operational level aspects

Over the past couple of centuries, with the increase in the significance of the railways to the economy, the complexity of the railway network and consequently the decision making involved and the number of problems faced has only increased. Among the host of problems in railways management, one of the most important is the locomotive assignment problem (LAP). The LAP is as old as the railways itself. The objective of the LAP is to assign a fleet of locomotives at minimum cost to pre-scheduled trains subject to a host of constraints. Most of the models in literature either work on improving the efficiency of solving the LAP or attempt to solve the three levels of LAP separately. Our attempt in this paper is to arrive at a linear mathematical model that integrates the strategic, tactical and operational level aspects of the LAP. We also demonstrate that by the addition of a valid inequality, the lower bounds can be improved substantially resulting in a substantial reduction in solution times for the problem instances. Further, we develop a Dijkstra's algorithm-based heuristic to test the problem instances and compare the solution times and quality of solutions. Finally, we develop a case based on Southern Zone of the Indian Railways and test the heuristic to solve the LAP for this zone.

Automated summary

This paper proposes a linear mathematical model for the locomotive assignment problem, integrating the strategic, tactical, and operational aspects of LAP. By adding a valid inequality, the lower bounds are substantially improved, resulting in a significant reduction in solution times. The paper also develops a heuristic algorithm based on Dijkstra's algorithm to test problem instances and compare solution times and quality.