WSEAS Transactions on Computers
Print ISSN: 1109-2750, E-ISSN: 2224-2872
Volume 14, 2017
Accelerating Column Generation Approach for the Crew Pairing Problem with Time Windows
Authors: ,
Abstract: The airline crew pairing problem with time windows is solved using a mixed linear programming method. The problem is to cover cost of all flights of the company. Given the large size of the problems encountered in industry, these models are solved by an approach based on column generation that can handle implicitly all feasible solutions and a master problem determining the best solution. We present a new approach to improve the acceleration of the method of column generation problem for the construction crew pairing, it is projected in each arc, the resources on a vector of dimension less using a Lagrangean relaxation algorithm to determine the coefficients of the projection arc combined with an algorithm for re-optimization, well generates a subset of complementary solutions to the master problem. The computational experiments were conducted on a broad range of instances, many of them published in the literature. They show a significant reduction of the number of column generation iterations and computing time.
Search Articles
Pages: 189-192
WSEAS Transactions on Computers, ISSN / E-ISSN: 1109-2750 / 2224-2872, Volume 14, 2017, Art. #21