# 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)

 PDF - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader306Kb

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

## Abstract

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 railroad scheduling • transportation • combinatorial optimization • heuristics • Lagrangian relaxation • shortest path • mixed integer programming • assignment problems 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 10122 Güvenç Şahin 08 Nov 2008 10:47 22 May 2019 12:16

### Available Versions of this Item

Repository Staff Only: item control page