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. © 1999 INFORMS.
Titolo: | A set partitioning approach to the crew scheduling problem | |
Autore/i: | Mingozzi A.; Boschetti M. A.; Ricciardelli S.; Bianco L. | |
Autore/i Unibo: | ||
Anno: | 1999 | |
Rivista: | ||
Digital Object Identifier (DOI): | http://dx.doi.org/10.1287/opre.47.6.873 | |
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. © 1999 INFORMS. | |
Data stato definitivo: | 2022-03-28T12:32:04Z | |
Appare nelle tipologie: | 1.01 Articolo in rivista |