IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v35y2001i8p767-787.html
   My bibliography  Save this article

Simultaneous locomotive and car assignment at VIA Rail Canada

Author

Listed:
  • Cordeau, Jean-François
  • Desaulniers, Guy
  • Lingaya, Norbert
  • Soumis, François
  • Desrosiers, Jacques

Abstract

In this paper, we present a sophisticated model and a heuristic solution approach based on mathematical optimization for the assignment of locomotives and cars to passenger trains. Given a periodic schedule and a fleet composed of several types of locomotives and cars, our approach determines a set of equipment cycles that cover all scheduled trains while satisfying a number of operational constraints. We first present a basic formulation that translates maintenance requirements and other fundamental difficulties of the problem. We then discuss several extensions, such as substitution possibilities and the minimization of switching operations, which are required in a real-life application. The resulting model is optimized through a branch-and-bound method in which the linear relaxations are solved by column generation. The model and solution strategy were tested on data from VIA Rail in Canada and a complete system based on this approach is now implemented at the company.

Suggested Citation

  • Cordeau, Jean-François & Desaulniers, Guy & Lingaya, Norbert & Soumis, François & Desrosiers, Jacques, 2001. "Simultaneous locomotive and car assignment at VIA Rail Canada," Transportation Research Part B: Methodological, Elsevier, vol. 35(8), pages 767-787, September.
    • Handle: RePEc:eee:transb:v:35:y:2001:i:8:p:767-787
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(00)00022-9
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dumas, Yvan & Desrosiers, Jacques & Soumis, Francois, 1991. "The pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 54(1), pages 7-22, September.
    2. Jean-François Cordeau & Paolo Toth & Daniele Vigo, 1998. "A Survey of Optimization Models for Train Routing and Scheduling," Transportation Science, INFORMS, vol. 32(4), pages 380-404, November.
    3. K. V. Ramani & B. K. Mandal, 1992. "Operational Planning of Passenger Trains in Indian Railways," Interfaces, INFORMS, vol. 22(5), pages 39-51, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Hong, Sung-Pil & Kim, Kyung Min & Lee, Kyungsik & Hwan Park, Bum, 2009. "A pragmatic algorithm for the train-set routing: The case of Korea high-speed railway," Omega, Elsevier, vol. 37(3), pages 637-645, June.
    2. Rouillon, Stéphane & Desaulniers, Guy & Soumis, François, 2006. "An extended branch-and-bound method for locomotive assignment," Transportation Research Part B: Methodological, Elsevier, vol. 40(5), pages 404-423, June.
    3. Lin, Zhiyuan & Kwan, Raymond S.K., 2016. "A branch-and-price approach for solving the train unit scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 97-120.
    4. Yu Zhou & Leishan Zhou & Yun Wang & Zhuo Yang & Jiawei Wu, 2017. "Application of Multiple-Population Genetic Algorithm in Optimizing the Train-Set Circulation Plan Problem," Complexity, Hindawi, vol. 2017, pages 1-14, July.
    5. Frisch, Sarah & Hungerländer, Philipp & Jellen, Anna & Primas, Bernhard & Steininger, Sebastian & Weinberger, Dominic, 2021. "Solving a real-world Locomotive Scheduling Problem with Maintenance Constraints," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 386-409.
    6. Abdelouahab Zaghrouti & Issmail El Hallaoui & François Soumis, 2020. "Improving set partitioning problem solutions by zooming around an improving direction," Annals of Operations Research, Springer, vol. 284(2), pages 645-671, January.
    7. Zhiyuan Lin & Raymond S. K. Kwan, 2016. "Local convex hulls for a special class of integer multicommodity flow problems," Computational Optimization and Applications, Springer, vol. 64(3), pages 881-919, July.
    8. Issmail Elhallaoui & Daniel Villeneuve & François Soumis & Guy Desaulniers, 2005. "Dynamic Aggregation of Set-Partitioning Constraints in Column Generation," Operations Research, INFORMS, vol. 53(4), pages 632-645, August.
    9. Lingaya, Norbert & Cordeau, Jean-Françcois & Desaulniers, Guy & Desrosiers, Jacques & Soumis, Françcois, 2002. "Operational car assignment at VIA Rail Canada," Transportation Research Part B: Methodological, Elsevier, vol. 36(9), pages 755-778, November.
    10. Prashant Premkumar & P. N. Ram Kumar, 2022. "Locomotive assignment problem: integrating the strategic, tactical and operational level aspects," Annals of Operations Research, Springer, vol. 315(2), pages 867-898, August.
    11. Ruf, Moritz & Cordeau, Jean-François, 2021. "Adaptive large neighborhood search for integrated planning in railroad classification yards," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 26-51.
    12. Prashant Premkumar & P. N. Ram Kumar, 2019. "Literature Review of Locomotive Assignment Problem from Service Operations Perspective: The Case of Indian Railways," IIM Kozhikode Society & Management Review, , vol. 8(1), pages 74-86, January.
    13. Joris C. Wagenaar & Leo G. Kroon & Marie Schmidt, 2017. "Maintenance Appointments in Railway Rolling Stock Rescheduling," Transportation Science, INFORMS, vol. 51(4), pages 1138-1160, November.
    14. Wagenaar, J.C. & Kroon, L.G. & Schmidt, M.E., 2016. "Maintenance Appointments in Railway Rolling Stock Rescheduling," ERIM Report Series Research in Management ERS-2016-001-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    15. Luis Cadarso & Ángel Marín, 2012. "Integration of timetable planning and rolling stock in rapid transit networks," Annals of Operations Research, Springer, vol. 199(1), pages 113-135, October.
    16. Lusby, Richard M. & Haahr, Jørgen Thorlund & Larsen, Jesper & Pisinger, David, 2017. "A Branch-and-Price algorithm for railway rolling stock rescheduling," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 228-250.
    17. Xu, Xiaoming & Li, Chung-Lun & Xu, Zhou, 2018. "Integrated train timetabling and locomotive assignment," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 573-593.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jean-François Cordeau & François Soumis & Jacques Desrosiers, 2000. "A Benders Decomposition Approach for the Locomotive and Car Assignment Problem," Transportation Science, INFORMS, vol. 34(2), pages 133-149, May.
    2. Lingaya, Norbert & Cordeau, Jean-Françcois & Desaulniers, Guy & Desrosiers, Jacques & Soumis, Françcois, 2002. "Operational car assignment at VIA Rail Canada," Transportation Research Part B: Methodological, Elsevier, vol. 36(9), pages 755-778, November.
    3. Prashant Premkumar & P. N. Ram Kumar, 2019. "Literature Review of Locomotive Assignment Problem from Service Operations Perspective: The Case of Indian Railways," IIM Kozhikode Society & Management Review, , vol. 8(1), pages 74-86, January.
    4. Jean-François Cordeau & François Soumis & Jacques Desrosiers, 2001. "Simultaneous Assignment of Locomotives and Cars to Passenger Trains," Operations Research, INFORMS, vol. 49(4), pages 531-548, August.
    5. Albrecht, Amie & Howlett, Phil & Pudney, Peter & Vu, Xuan & Zhou, Peng, 2016. "The key principles of optimal train control—Part 1: Formulation of the model, strategies of optimal type, evolutionary lines, location of optimal switching points," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 482-508.
    6. Jin, Jian Gang & Zhao, Jun & Lee, Der-Horng, 2013. "A column generation based approach for the Train Network Design Optimization problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 1-17.
    7. Sapan Tiwari & Neema Nassir & Patricia Sauri Lavieri, 2024. "Smart Insertion Strategies for Sustainable Operation of Shared Autonomous Vehicles," Sustainability, MDPI, vol. 16(12), pages 1-28, June.
    8. Wang, Dian & D’Ariano, Andrea & Zhao, Jun & Zhong, Qingwei & Peng, Qiyuan, 2022. "Integrated rolling stock deadhead routing and timetabling in urban rail transit lines," European Journal of Operational Research, Elsevier, vol. 298(2), pages 526-559.
    9. Gianmarco Garrisi & Cristina Cervelló-Pastor, 2019. "Train-Scheduling Optimization Model for Railway Networks with Multiplatform Stations," Sustainability, MDPI, vol. 12(1), pages 1-25, December.
    10. Shuaian Wang & Dan Zhuge & Lu Zhen & Chung-Yee Lee, 2021. "Liner Shipping Service Planning Under Sulfur Emission Regulations," Transportation Science, INFORMS, vol. 55(2), pages 491-509, March.
    11. Li, Feng & Gao, Ziyou & Li, Keping & Yang, Lixing, 2008. "Efficient scheduling of railway traffic based on global information of train," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 1008-1030, December.
    12. Zhang, Yongxiang & Peng, Qiyuan & Yao, Yu & Zhang, Xin & Zhou, Xuesong, 2019. "Solving cyclic train timetabling problem through model reformulation: Extended time-space network construct and Alternating Direction Method of Multipliers methods," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 344-379.
    13. Gronalt, Manfred & Hartl, Richard F. & Reimann, Marc, 2003. "New savings based algorithms for time constrained pickup and delivery of full truckloads," European Journal of Operational Research, Elsevier, vol. 151(3), pages 520-535, December.
    14. Santini, Alberto & Plum, Christian E.M. & Ropke, Stefan, 2018. "A branch-and-price approach to the feeder network design problem," European Journal of Operational Research, Elsevier, vol. 264(2), pages 607-622.
    15. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2006. "A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1117-1139, October.
    16. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    17. Andrea D'Ariano & Francesco Corman & Dario Pacciarelli & Marco Pranzo, 2008. "Reordering and Local Rerouting Strategies to Manage Train Traffic in Real Time," Transportation Science, INFORMS, vol. 42(4), pages 405-419, November.
    18. Egan, Malcolm & Jakob, Michal, 2016. "Market mechanism design for profitable on-demand transport services," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 178-195.
    19. Grunert, Tore & Sebastian, Hans-Jurgen, 2000. "Planning models for long-haul operations of postal and express shipment companies," European Journal of Operational Research, Elsevier, vol. 122(2), pages 289-309, April.
    20. Albert H. Schrotenboer & Evrim Ursavas & Iris F. A. Vis, 2019. "A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 53(4), pages 1001-1022, July.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:35:y:2001:i:8:p:767-787. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.