A Set Partitioning Approach to the Crew Scheduling Problem

A. Mingozzi, M. A. Boschetti, S. Ricciardelli and L. Bianco
Additional contact information
A. Mingozzi: Department of Mathematics, University of Bologna, Bologna, Italy
M. A. Boschetti: The Management School, Imperial College, 53 Prince's Gate, Exhibition Road, London SW7 2PG, England
S. Ricciardelli: Department of Electrical Engineering, University “Tor Vergata”, Rome, Italy
L. Bianco: Department of Electrical Engineering, University “Tor Vergata”, Rome, Italy

Operations Research, 1999, vol. 47, issue 6, 873-888

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 (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.6.873 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:47:y:1999:i:6:p:873-888

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().