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

RICCIARDELLI, SALVATORE;BIANCO, LUCIO
1999-01-01

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
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 Creative Commons

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/52065
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact