An Effective Peak Period Heuristic for Railway Rolling Stock Planning

In this work the authors tackle a real-world application of railway rolling stock planning, known as the train unit assignment problem (TUAP), arising for a regional train operator in the North of Italy. Given a set of timetabled train trips, each with a demand of passenger seats, as well as a set of train units, each with a cost and a number of available passenger seats, the goal is to determine the minimum cost daily assignment of the train units to the trips, satisfying a set of operational constraints. The context the authors focus on is that of a competitive bid process whereby a train operator competes to win a contract for providing rolling stock circulation in a regional railway network. From a theoretical perspective, the authors prove that even a relaxation of the TUAP is NP-hard. To solve the TUAP, the authors propose a heuristic algorithm based on the optimal solution of the restricted problem associated with a peak period (i.e., a period of the day in which many trips overlapping in time must be performed). The heuristic algorithm is tested on real-world instances provided by the regional train operator and on larger realistic instances of TUAP. The obtained results are compared with those of previously developed methods, showing the effectiveness of the new algorithm that finds optimal or near-optimal solutions and outperforms, for what concerns both the solution quality and the computing time, the considered methods from the literature.

  • Record URL:
  • Availability:
  • Supplemental Notes:
    • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences,
  • Authors:
    • Cacchiani, Valentina
    • Caprara, Alberto
    • Toth, Paolo
  • Publication Date: 2019-5


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01714948
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jun 17 2019 3:36PM