A Dual-Guided Column-Generation-Based Matheuristic for Integrated Railroad Blocking
Abstract
Integrated railroad blocking is a central planning problem in freight railway operations, which requires coordinated decisions on block design, blocking sequences, and block routing. We propose a dual-guided column-generation-based matheuristic (DG-CGM) that uses linear programming (LP) dual information to identify promising transportation paths and incorporates them into restricted mixed-integer programs to improve feasible solutions. Starting from an initial plan built by construction, DG-CGM alternates destroy and local repair with path generation, which uses dual prices from restricted LPs of a Dantzig-Wolfe reformulation to identify promising transportation paths. When local improvements continue to stagnate, we further apply joint repair to combine alternatives across demand groups. To address the coupling between logical and physical path pricing, we introduce a joint reduced cost that eliminates path-specific dual variables from pricing, enabling more efficient column identification through exact labeling algorithms. We evaluate the performance of DG-CGM on both generated instances and real-world cases. On 150 generated instances with 50-150 nodes, DG-CGM achieves the optimal cost on 89 of the 91 instances solved to proven optimality by Gurobi, with a geometric mean runtime equal to 5.2% of that for Gurobi and a mean relative cost reduction of 3.4%. On six full-scale scenarios derived from the 2026 INFORMS Railway Applications Section competition data, each with 47,193 nodes, DG-CGM obtains feasible solutions within two hours that serve 95.9%-99.6% of the requested freight volume, providing practical blocking plans for large-scale railway operations. The code, instances, and computational results are publicly available at https://github.com/Zhengzhong-You/IRBP.
Related
- A large neighborhood search matheuristic for the two-dimensional guillotine flexible stock size cutting stock problem
- MGD: Moment Guided Diffusion for Maximum Entropy Generation
- Verifier-Guided Synthetic Augmentation for 3D Human Shape Generation
- EntroPrefill: Renyi-Guided Context Pruning with Conditional Stability Guarantees for Retrieval-Augmented Generation
- Just for FUNS: LLM-Guided Spatio-Temporal Graph Node Generation for Forecasting Unobserved Node States
BibTeX
@misc{xu2026dualguided,
title = {{A Dual-Guided Column-Generation-Based Matheuristic for Integrated Railroad Blocking}},
author = {Yida Xu and Zhengzhong Ricky You and Baichuan Mo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41403},
eprint = {2610.41403},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41403},
}
RIS
TY - UNPB
TI - A Dual-Guided Column-Generation-Based Matheuristic for Integrated Railroad Blocking
AU - Yida Xu
AU - Zhengzhong Ricky You
AU - Baichuan Mo
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41403
UR - https://arxiv.org/abs/2610.41403
AB - Integrated railroad blocking is a central planning problem in freight railway operations, which requires coordinated decisions on block design, blocking sequences, and block routing. We propose a dual-guided column-generation-based matheuristic (DG-CGM) that uses linear programming (LP) dual information to identify promising transportation paths and incorporates them into restricted mixed-integer programs to improve feasible solutions. Starting from an initial plan built by construction, DG-CGM alternates destroy and local repair with path generation, which uses dual prices from restricted LPs of a Dantzig-Wolfe reformulation to identify promising transportation paths. When local improvements continue to stagnate, we further apply joint repair to combine alternatives across demand groups. To address the coupling between logical and physical path pricing, we introduce a joint reduced cost that eliminates path-specific dual variables from pricing, enabling more efficient column identification through exact labeling algorithms. We evaluate the performance of DG-CGM on both generated instances and real-world cases. On 150 generated instances with 50-150 nodes, DG-CGM achieves the optimal cost on 89 of the 91 instances solved to proven optimality by Gurobi, with a geometric mean runtime equal to 5.2% of that for Gurobi and a mean relative cost reduction of 3.4%. On six full-scale scenarios derived from the 2026 INFORMS Railway Applications Section competition data, each with 47,193 nodes, DG-CGM obtains feasible solutions within two hours that serve 95.9%-99.6% of the requested freight volume, providing practical blocking plans for large-scale railway operations. The code, instances, and computational results are publicly available at https://github.com/Zhengzhong-You/IRBP.
ER -