A set partitioning approach to the crew scheduling problem
成果类型：
Article
署名作者：
Mingozzi, A; Boschetti, MA; Ricciardelli, S; Bianco, L
署名单位：
University of Bologna; Imperial College London; University of Rome Tor Vergata
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.47.6.873
发表日期：
1999
页码：
873-888
关键词：
摘要：
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.