 One-block train formation in large-scale railway networks: An exact model and a tree-based decomposition algorithmChongshuang Chen, Twan Dollevoet and Jun Zhao Transportation Research Part B: Methodological, 2018, vol. 118, issue C, 1-30 Abstract: We investigate the one-block train formation problem (TFP) in the railway freight transportation industry. The input to this problem is a railway network and a set of demands for transportation. Each demand is a request for shipping a number of rail cars from one station to another. The one-block TFP now addresses two subproblems in the tactical level: Which pairs of stations are directly connected via a block (or: train service); and which demands are transported by each block. The aim is to service all demands against minimal costs. Moving beyond current researches on service network design, the unitary rule and the intree rule are taken into account in this study based on the Chinese railway background. We develop a linear binary programming formulation to minimize the total sum of train accumulation costs and car classification costs, subject to limitations on the classification capacity and the number of sort tracks at each station. Furthermore, we propose a novel solution methodology that applies a tree-based decomposition algorithm. Here, we first decompose the whole network into a series of rooted trees for each destination separately. Then, we divide the trees further into sufficiently small subtrees, whose size is regulated by a node size parameter. Finally, we construct a restricted linear binary model for each subtree and solve these models sequentially to find their optimal solutions. The algorithm ensures that an overall feasible solution is obtained if one exists. Our computational results on a realistic network from the Chinese railway system with 83 stations, 158 links and 5700 randomly generated demands show that the proposed algorithm can derive high-quality solutions within a few hours of computation time. These solutions are on average 48.05% better than those obtained after solving the linear binary program with a commercial solver for 1 day. Keywords: Railway freight transportation; Train formation problem; Service network design; Tree-based decomposition; Arborescence structure (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:118:y:2018:i:c:p:1-30 Ordering information: This journal article can be ordered from DOI: 10.1016/j.trb.2018.10.003 Access Statistics for this article Transportation Research Part B: Methodological is currently edited by Fred Mannering More articles in Transportation Research Part B: Methodological from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.