2026-07-25T23:32:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1172 2024-03-06T10:28:28Z ddc:004 open_access

06. Solving a Real-World Train Unit Assignment Problem Cacchiani, Valentina Caprara, Alberto Toth, Paolo INVALID Windows-1252: We face a real-world train unit assignment problem for an operator running trains in a regional area. Given a set of timetabled train trips, each with a required number of passenger seats, and a set of train units, each with a given number of available seats, the problem calls for an assignment of the train units to trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. With respect to analogous case studies previously faced in the literature, ours is characterized by the fairly large number of distinct train unit types available (in addition to the fairly large number of trips to be covered). As a result, although there is a wide margin of improvement over the solution used by the practitioners (as our results show), even only finding a solution of the same value is challenging in practice. We present a successful approach, based on an ILP formulation in which the seat requirement constraints are stated in a “strong” form, derived from the description of the convex hull of the variant of the knapsack polytope arising when the sum of the variables is restricted not to exceed two, illustrating computational results on our case study. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Valentina Cacchiani and Alberto Caprara and Paolo Toth 2007 Is Part Of OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2007.1172 urn:nbn:de:0030-drops-11726 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1172 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode