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.

Mingozzi, A., Boschetti, M.a., Ricciardelli, S., Bianco, L. (1999). A set partitioning approach to the crew scheduling problem. OPERATIONS RESEARCH, 47(6), 873-888.

### A set partitioning approach to the crew scheduling problem

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
1999
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - RICERCA OPERATIVA
English
Con Impact Factor ISI
Algorithms; Computational methods; Constraint theory; Mass transportation; Matrix algebra; Problem solving; Transportation personnel; Work-rest schedules; Branch-and-bound algorithms; Crew scheduling problem (CSP); Set partitioning method; Scheduling
Mingozzi, A., Boschetti, M.a., Ricciardelli, S., Bianco, L. (1999). A set partitioning approach to the crew scheduling problem. OPERATIONS RESEARCH, 47(6), 873-888.
Mingozzi, A; Boschetti, Ma; Ricciardelli, S; Bianco, L
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

Questo articolo è pubblicato sotto una Licenza Licenza Creative Commons

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/2108/52065`
• ND
• ND
• ND