New approaches for solving the block-to-train assignment problem

Jha, Krishna C. and Ahuja, Ravindra K. and Şahin, Güvenç (2008) New approaches for solving the block-to-train assignment problem. Networks, 51 (issue ). pp. 48-62. ISSN 0028-3045 (Print) 1097-0037 (Online)

This is the latest version of this item.

[thumbnail of 2008_NETWORKS_JhaAhujaSahin.pdf] PDF
Restricted to Repository staff only

Download (314kB) | Request a copy


Railroad planning involves solving two optimization problems: (i) the blocking problem, which determines what blocks to make and how to route traffic over these blocks; and (ii) the train schedule design problem, which determines train origins, destinations, and routes. Once the blocking plan and train schedule have been obtained, the next step is to determine which trains should carry which blocks. This problem, known as the block-to-train assignment problem, is considered in this paper. We provide two formulations for this problem: an arc-based formulation and a path-based formulation. The latter is generally smaller than the former, and it can better handle practical constraints. We also propose exact and heuristic algorithms based on the path-based formulation. Our exact algorithm solves an integer programming formulation with CPLEX using both a priori generation and dynamic generation of paths. Our heuristic algorithms include a Lagrangian relaxation-based method as well as a greedy construction method. We present computational results of our algorithms using the data provided by a major US railroad. We show that we can obtain an optimal solution of the block-to-train assignment problem within a few minutes of computational time, and can obtain heuristic solutions with 1–2% deviations from the optimal solutions within a few seconds.
Item Type: Article
Uncontrolled Keywords: railroad scheduling • transportation • combinatorial optimization • heuristics • Lagrangian relaxation • shortest path • mixed integer programming • assignment problems
Subjects: T Technology > TF Railroad engineering and operation > TF501-668 Railway operation and management
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Güvenç Şahin
Date Deposited: 08 Nov 2008 10:47
Last Modified: 26 Apr 2022 08:23

Available Versions of this Item

Actions (login required)

View Item
View Item