Loading…

General hybrid column generation algorithm for crew scheduling problems using genetic algorithm

This paper describes a general hybrid column generation algorithm for crew scheduling problems, using genetic algorithm to speed up the generation of new columns, combined with an integer programming exact method to assure optimality. The subproblem of the column generation must generate a new feasi...

Full description

Saved in:
Bibliographic Details
Main Authors: dos Santos, A.G., Mateus, G.R.
Format: Conference Proceeding
Language:English
Subjects:
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper describes a general hybrid column generation algorithm for crew scheduling problems, using genetic algorithm to speed up the generation of new columns, combined with an integer programming exact method to assure optimality. The subproblem of the column generation must generate a new feasible set of tasks to be assigned to a crew member. It is modeled as a shortest path with resource constraints problem in a graph, which virtually can be applied to all kinds of crew scheduling problems. The genetic algorithm is also general, and knowledge about specific problems may be incorporated. The hybrid algorithm is tested with instances from the literature and also with real instances, and the results show that the genetic algorithm is able to quickly generate most of the columns needed to solve the problem, while the exact method generates the last columns to find the optimal solution. The algorithm can also incorporate other kind of heuristics.
ISSN:1089-778X
1941-0026
DOI:10.1109/CEC.2009.4983159