Accelerating column generation for aircraft scheduling using constraint propagation |
| |
Authors: | Mattias Grö nkvist |
| |
Affiliation: | Carmen Systems AB, Odinsgatan 9, S-411 03 Göteborg, Sweden |
| |
Abstract: | We discuss how constraint programming can improve the performance of a column generation solution process for the NP-hard Tail Assignment problem in aircraft scheduling. Combining a constraint model of a relaxed Tail Assignment problem with column generation, we achieve substantially improved performance. A generalized preprocessing technique based on constraint propagation is presented that can dramatically reduce the size of the flight network. We also present a heuristic preprocessing method based on the costs of connections, and show how constraint propagation can be used to improve fixing heuristics. Proof of concept is provided using real world Tail Assignment instances. |
| |
Keywords: | Tail Assignment Aircraft scheduling Constraint Programming Column generation Hybrid optimization |
本文献已被 ScienceDirect 等数据库收录! |