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

En savoir plus sur le livre

The integrated treatment of planning problems, often addressed separately, can yield better solutions by exploring a broader decision space. This thesis examines the integrated locomotive scheduling and driver assignment problem in rail freight transport, alongside its generalization known as graph 2-list-colouring with compatibility constraints. The study is motivated by collaboration with DB Cargo Polska within the ROMSOC Programme and is divided into two parts. Part I focuses on modeling and solving the integrated problem, beginning with a literature review and introducing a novel optimization model. It also presents an improved formulation and a decomposition-based solution approach, ensuring global feasibility through four classes of valid inequalities and a presolve heuristic. The algorithm demonstrates efficiency, creating locomotive timetables and driver assignments in under two hours across two sets of instances. Part II generalizes the problem into graph 2-list-colouring with compatibility constraints, defining it within the context of well-known combinatorial problems. It offers two formulations and discusses potential tightening, including a complete polyhedral description for a specific case. The decomposition-based solution approach from Part I is adapted and tested against modified standard instances from the literature. Overall, this work contributes practically to solving the integrated locomotive schedulin