Improvements in solving resource constrained shortest path problems in column generation context
17th International Conference on Industrial Engineering and Engineering Management, IE and EM2010, Xiamen, Çin, 29 - 31 Ekim 2010, ss.655-659, (Tam Metin Bildiri)
- Yayın Türü: Bildiri / Tam Metin Bildiri
- Doi Numarası: 10.1109/icieem.2010.5646531
- Basıldığı Şehir: Xiamen
- Basıldığı Ülke: Çin
- Sayfa Sayıları: ss.655-659
- Anahtar Kelimeler: Column generation, Crew scheduling, Graph theory, Resource constrained shortest path problems, Three-stage approach
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Column generation method is an effective way of solving large scale optimization problems. One of the novel improvement methods for column generation applications is the processing of a preprocessing algorithm at the very beginning of the problem to transform the resource constrained shortest path problem of the sub-problem into an unrestricted shortest path problem. This process was previously suggested in the literature as three-stage approach (TSA), in which network reduction, network expansion and iterative solution stages are involved. In this paper, we propose three-stage approach in vectorial form (TSA-V), a variant of TSA, in which the network reduction stage is processed by vectorial comparison of the resources. The effectiveness of both algorithms is compared by solving a real-world airline crew scheduling problem of a medium-haul airline company. Computational results of the airline crew scheduling problem show that TSA-V is more effective in eliminating infeasibilities and solving the iterative solution stage. © 2010 IEEE.