Improvements in Solving Resource Constrained Shortest Path Problems in Column Generation Context
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.
Column Generation Graph Theory Resource Constrained Shortest Path Problems Crew Scheduling Three-Stage Approach
Isik Bicer Taner Bilgic
Department of Industrial Engineering,Bogazici University,Istanbul,Turkey
国际会议
厦门
英文
655-659
2010-10-29（万方平台首次上网日期，不代表论文的发表时间）