Sammendrag
A central problem in transportation is that of routing and scheduling the movements of
vehicles so as to minimize the cost of the schedule. It arises, for instance, in timetabling,
dispatching, delay and disruption management, runway scheduling, and many more. For
fixed routing, the problem boils down to finding a minimum cost conflict-free schedule, i.e.
a schedule where potential conflicts are prevented by a correct timing of the vehicles on
the shared resources. A classical mathematical representation involves continuous variables
representing times, (time-precedence) linear constraints associated with single vehicles, and
disjunctive (precedence) linear constraints associated with pairs vehicles. There are two
standard ways to linearize disjunctions, namely by means of BigM formulations or by timeindexed
formulations. BigM formulations tend to return notoriously weak relaxations, whereas
time-indexed formulations quickly become too large for instances of some practical interest.
In this work we develop a new, non-compact formulation for such disjunctive programs with
convex piece-wise linear cost, and solve the resulting problems by row-generation. Our initial
tests show that the new approach favourably compares with the so-far most effective approach
on a large number of real-life test instances from railway traffic management. Moreover, it
opens up for several research directions, ranging from investigating polyhedral properties to
algorithmic speed-ups.
vehicles so as to minimize the cost of the schedule. It arises, for instance, in timetabling,
dispatching, delay and disruption management, runway scheduling, and many more. For
fixed routing, the problem boils down to finding a minimum cost conflict-free schedule, i.e.
a schedule where potential conflicts are prevented by a correct timing of the vehicles on
the shared resources. A classical mathematical representation involves continuous variables
representing times, (time-precedence) linear constraints associated with single vehicles, and
disjunctive (precedence) linear constraints associated with pairs vehicles. There are two
standard ways to linearize disjunctions, namely by means of BigM formulations or by timeindexed
formulations. BigM formulations tend to return notoriously weak relaxations, whereas
time-indexed formulations quickly become too large for instances of some practical interest.
In this work we develop a new, non-compact formulation for such disjunctive programs with
convex piece-wise linear cost, and solve the resulting problems by row-generation. Our initial
tests show that the new approach favourably compares with the so-far most effective approach
on a large number of real-life test instances from railway traffic management. Moreover, it
opens up for several research directions, ranging from investigating polyhedral properties to
algorithmic speed-ups.