Valentina
Cacchiani
Title:
Solving a real-world train unit assignment problem
Abstract:
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. Among the many approaches that we tried, we
present the most successful one, 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. We present preliminary computational results on our case
study.