A dynamic programming based algorithm for the crew scheduling problem

A dynamic programming based algorithm for the crew scheduling problem. There are many papers concerned with the crew scheduling problem in the literature. Most of the research literature views the crew scheduling problem as equivalent of the set covering problem, or as equivalent to the set partitioning problem. In this paper we highlight the fact that the crew scheduling problem is a separate and distinct problem. This leads naturally to a dynamic programming formulation of the problem. Following on from this formulation a new lower bound for the crew scheduling problem is developed based upon dynamic programming. Incorporating this lower bound into a tree search procedure we are able to solve to proven optimality a number of problems involving a relatively large number of tasks. In this paper we consider the crew scheduling problem, that is the problem of assigning K crews to tasks with fixed start and finish times such that each crew does not exceed a limit on the total time it can spend working. This problem is formulated as a problem of finding K time limit constrained vertex disjoint paths which visit all vertices on a network. A lower bound for the problem is found via dynamic programming. This lower bound is improved via a Lagrangean based penalty procedure and subgradient optimisation. Computational results are given for a number of randomly generated problems involving between 50 and 500 tasks.