New Approaches for Solving the Block-to-Train Assignment Problem

Jha, Krishna C. and Ahuja, Ravindra K. and Şahin, Güvenç (2006) New Approaches for Solving the Block-to-Train Assignment Problem. (Accepted/In Press)

Warning
There is a more recent version of this item available.
Full text not available from this repository. (Request a copy)

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
Subjects: Q Science > Q Science (General)
T Technology > TF Railroad engineering and operation
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Güvenç Şahin
Date Deposited: 28 Oct 2007 19:25
Last Modified: 22 May 2019 12:02
URI: https://research.sabanciuniv.edu/id/eprint/4787

Available Versions of this Item

Actions (login required)

View Item
View Item