689. A partial duty formulation for the crew scheduling problem
Invited abstract in session TA-57: Railways applications, stream Transportation.
Tuesday, 8:30-10:00Room: Liberty 1.12
Authors (first author is the speaker)
| 1. | Bart van Rossum
|
| Erasmus School of Economics, Erasmus University Rotterdam | |
| 2. | Twan Dollevoet
|
| Econometric Institute, Erasmus University of Rotterdam | |
| 3. | Remy Spliet
|
| Econometric Institute, Erasmus University Rotterdam |
Abstract
The goal of crew scheduling is to cover tasks with a minimum-cost set of duties. The state-of-the art solution approach for this problem is to formulate it as a set partition problem, each column corresponding to a duty, and solve it using column generation. However, we show that the pricing problem for this standard formulation is weakly NP-hard. To avoid this complexity, we propose a partial duty formulation, where columns represent either the first or second half of a duty and are later combined in the master problem. We prove that the pricing problem for this formulation can be solved in polynomial time. Furthermore, we introduce matching-based cuts that restore the bound of the regular duty formulation and can be separated in polynomial time. Incorporating these cuts renders the partial duty pricing problem weakly NP-hard again. Experimental results on large synthetic instances demonstrate the effectiveness of our approach.
Keywords
- Column Generation
- Railway Applications
Status: accepted
Back to the list of papers