An Effective Peak Period Heuristic for Railway Rolling Stock Planning

Valentina Cacchiani (), Alberto Caprara and Paolo Toth ()
Additional contact information
Valentina Cacchiani: Department of Electrical and Information Engineering “Guglielmo Marconi” (DEI), University of Bologna, I-40136 Bologna, Italy
Alberto Caprara: Department of Electrical and Information Engineering “Guglielmo Marconi” (DEI), University of Bologna, I-40136 Bologna, Italy
Paolo Toth: Department of Electrical and Information Engineering “Guglielmo Marconi” (DEI), University of Bologna, I-40136 Bologna, Italy

Transportation Science, 2019, vol. 53, issue 3, 746-762

Abstract: In this work we 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 we 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, we prove that even a relaxation of the TUAP is NP-hard. To solve the TUAP, we 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.

Keywords: train unit assignment; lower bound; lower bound; real-world application (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0858 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:3:p:746-762

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().