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 1). pp. 48-62. ISSN 0028-3045 (Print) 1097-0037 (Online)

This is the latest version of this item.

[img]PDF - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1002/net.20195


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
ID Code:10122
Deposited By:Güvenç Şahin
Deposited On:08 Nov 2008 10:47
Last Modified:22 May 2019 12:16

Available Versions of this Item

Repository Staff Only: item control page