A Set Partitioning Approach to the Crew Scheduling Problem
A. Mingozzi, M. A. Boschetti, S. Ricciardelli, L. Bianco
Operations Research · 1999 · Volume 47 · Issue 6
Abstract
The crew scheduling problem (CSP) appears in many mass transport systems (e.g., airline, bus, and railway industry) and consists of scheduling a number of crews to operate a set of transport tasks satisfying a variety of constraints. This problem is formulated as a set partitioning problem with side constraints (SP), where each column of the SP matrix corresponds to a feasible duty , which is a subset of tasks performed by a crew. We describe a procedure that, without using the SP matrix, computes a lower bound to the CSP by finding a heuristic solution to the dual of the linear relaxation of SP. Such dual solution is obtained by combining a number of different bounding procedures. The dual solution is used to reduce the number of variables in the SP in such a way that the resulting SP problem can be solved by a branch-and-bound algorithm. Computational results are given for problems derived from the literature and involving from 50 to 500 tasks.
Keywords
programming algorithms, dual ascent procedures, transportation, personnel scheduling, mass transit
Enable JavaScript for citation tools and additional paper interactions.