Document Open Access Logo

Multi-Column Generation Model for the Locomotive Assignment Problem

Authors Brigitte Jaumard, Huaining Tian

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2016.6.pdf
  • Filesize: 0.88 MB
  • 13 pages

Document Identifiers

Author Details

Brigitte Jaumard
Huaining Tian

Cite As Get BibTex

Brigitte Jaumard and Huaining Tian. Multi-Column Generation Model for the Locomotive Assignment Problem. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/OASIcs.ATMOS.2016.6

Abstract

We propose a new decomposition model and a multi-column generation algorithm for solving the Locomotive Assignment Problem (LAP). The decomposition scheme relies on consist configurations, where each configuration is made of a set of trains pulled by the same set of locomotives. We use the concept of conflict graphs in order to reduce the number of trains to be considered in each consist configuration generator problem: this contributes to significantly reduce the fraction of the computational times spent in generating new potential consists. In addition, we define a column generation problem for each set of variables, leading to a multi-column generation process, with different types of columns.

Numerical results, with different numbers of locomotives, are presented on adapted data sets coming from Canada Pacific Railway (CPR). They show that the newly proposed algorithm is able to solve exactly realistic data instances for a timeline spanning up to 6 weeks, in very reasonable computational times.

Subject Classification

Keywords
  • Railway optimization
  • Locomotive assignment
  • Column Generation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. R.K. Ahuja, J. Liu, J.B. Orlin, D. Sharma, and L.A. Shughart. Solving real-life locomotive-scheduling problems. Transportation Science, 39(4):503-517, 2005. Google Scholar
  2. R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993. Google Scholar
  3. V. Cacchiani, A. Caprara, and P. Toth. Models and algorithms for the train unit assignment problem. In R. Mahjoub, V. Markakis, I. Milis, and V.T. Paschos, editors, Combinatorial Optimization, volume 7422 of Lecture Notes in Computer Science, pages 24-35. Springer, 2012. Google Scholar
  4. S. Chen and Y. Shen. An improved column generation algorithm for crew scheduling problems. Journal of Information and Computational Science, 10(1):175-183, 2013. Google Scholar
  5. V. Chvátal. Linear programming. A series of books in the mathematical sciences, 1983. Google Scholar
  6. J.-F. Cordeau, F. Soumis, and J. Desrosiers. A benders decomposition approach for the locomotive and car assignment problem. Transportation science, 34(2):133-149, 2000. Google Scholar
  7. G. Desaulniers, J. Desrosiers, and M. M. Solomon. Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems. Springer, 2002. Google Scholar
  8. A. Fügenschuh, H. Homfeld, A. Huck, A. Martin, and Z. Yuan. Scheduling locomotives and car transfers in freight transport. Transportation Science, 42(4):478-491, 2008. Google Scholar
  9. J.-L. Goffin and J.-P. Vial. Multiple cuts in the analytic center cutting plane method. SIAM Journal on Optimization, 11(1):266-288, 2000. Google Scholar
  10. B. Jaumard, H. Tian, and P. Finnie. Locomotive assignment under consist busting and maintenance constraints. Submitted, 2014. URL: https://www.gerad.ca/en/papers/G-2014-54.
  11. B. Jaumard, H. Tian, and P. Finnie. Best compromise in deadheading and locomotive fleet size in locomotive assignment. In 2015 Joint Rail Conference, pages V001T04A003-V001T04A003. American Society of Mechanical Engineers, 2015. Google Scholar
  12. A Mingozzi, M. A. Boschetti, S. Ricciardelli, and L. Bianco. A set partitioning approach to the crew scheduling problem. Operations Research, 47(6):873-888, 1999. Google Scholar
  13. F. Piu and M. G. Speranza. The locomotive assignment problem: a survey on optimization models. International Transactions in Operational Research, 21(3):327-352, 2013. Google Scholar
  14. S. Rouillon, G. Desaulniers, and F. Soumis. An extended branch-and-bound method for locomotive assignment. Transportation Research. Part B, Methodological, 40(5):404-423, June 2006. Google Scholar
  15. M. Saddoune, G. Desaulniers, I. Elhallaoui, and F. Soumis. Integrated airline crew pairing and crew assignment by dynamic constraint aggregation. Transportation Science, 46(1):39-55, 2012. Google Scholar
  16. R. Sadykov, F. Vanderbeck, A. Pessoa, and E. Uchoa. Column generation based heuristic for the generalized assignment problem. XLVII Simpósio Brasileiro de Pesquisa Operacional, Porto de Galinhas, Brazil, 2015. Google Scholar
  17. C. Surapholchai, G. Reinelt, and H. G. Bock. Solving city bus scheduling problems in bangkok by eligen-algorithm. In Modeling, Simulation and Optimization of Complex Processes, pages 557-564. Springer, 2008. Google Scholar
  18. B. Vaidyanathan, R.K. Ahuja, J. Liu, and L.A. Shughart. Real-life locomotive planning: new formulations and computational results. Transportation Research, Part B 42:147-168, 2008. Google Scholar
  19. K. Ziarati, F. Soumis, J. Desrosiers, S. Gelinas, and A. Saintonge. Locomotive assignment with heterogeneous consists at CN North America. European Journal of Operational Research, 97(2):281-292, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact