Modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2-list-colouring problem with compatibility constraints

Abstract

The integrated treatment of planning problems which are usually considered separately and sequentially has been studied for a long time, due to the better solutions one may find in the extended decision space of an integrated problem. This thesis considers the integrated locomotive scheduling and driver assignment problem in rail freight transport. We also consider the generalization of this problem, which we call graph 2-list-colouring with compatibility constraints. The motivation to study this problem originates from our collaboration with DB Cargo Polska within the ROMSOC Programme. The thesis consists of two parts. Part I focuses on modelling and solving the integrated locomotive scheduling and driver assignment problem in rail freight transport. After a literature review, we present a novel optimization model for the problem studied and a way to improve its formulation. Next, we introduce the decomposition-based solution approach we derive for the problem. To ensure the global feasibility of the solutions to the decomposed subproblems, we devise four classes of valid inequalities. We also develop a presolve heuristic. We then test our algorithm against two sets of instances. In general, the methods presented enabled the creation of locomotive timetables and driver assignments in less than two hours. In Part II, we study a generalization of the integrated locomotive scheduling and driver assignment problem, which we call graph 2-list-colouring with compatibility constraints. We begin by defining the problem studied and putting it in the context of other, more famous combinatorial problems. Then we present two formulations for the problem and discuss how they may be tightened. We also study a case for which we may find a complete polyhedral description. Next, we present a decomposition-based solution approach which adapts the algorithm introduced in Part I. We then test the performance of our method against a set of standard instances drawn from the literature, which were appropriately modified. Altogether, our work is a practical contribution to the solvability of the integrated locomotive scheduling and driver assignment problem. We also show how the developed method may be extended to successful use in more general graph-theoretic contexts.