A tree search algorithm for the crew scheduling problem

A tree search algorithm for the crew scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor1999916
Country: Netherlands
Volume: 94
Issue: 3
Start Page Number: 517
End Page Number: 526
Publication Date: Nov 1996
Journal: European Journal of Operational Research
Authors: ,
Keywords: crew scheduling, Lagrangean relaxation
Abstract:

In this paper we consider the crew scheduling problem, that is the problem of assigning K crews to N tasks with fixed start and finish times such that each crew does not exceed a limit on the total time it can spend working. A zero–one integer linear programming formulation of the problem is given, which is then relaxed in a lagrangean way to provide a lower bound which is improved by subgradient optimisation. Finally a tree search procedure incorporating this lower bound is presented to solve the problem to optimality. Computational results are given for a number of randomly generated test problems involving between 50 and 500 tasks.

Reviews

Required fields are marked *. Your email address will not be published.