A non-compact formulation for job-shop scheduling problems in transportation

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.