Método de geração de colunas e meta-heurísticas para alocação de tripulação
AUTOR(ES)
Andre Gustavo dos Santos
DATA DE PUBLICAÇÃO
2008
RESUMO
In a typical crew scheduling problem, for each crew member is assigned a set of trips (a duty) to be performed. The objective is to select the duties such as the total operational cost is minimized, and no trip is left uncovered. Although there are some constraints about how the trips may be combined in a feasible duty, the total number of feasible duties is generally large. For small instances it is possible to enumerate all feasible duties, and find the optimal solution solving a set partitioning or set covering problem. However, this approach may be time and memory consuming for large instances. On the other hand, some heuristics may be lost in the huge feasible space. As the optimal solution contains only few duties, column generation seems to be the best approach. The problem is then decomposed in master and subproblem, whose objectives are respectively select the best set of duties and generate new duties. The main focus of this work is about solving the subproblem, because, although both problems are NP-hard, the master problem can be quickly solved by linear programming packages if the number of duties is not so big, which usually happens in a column generation approach. In this work Greedy, Grasp and Genetic metaheuristics are used to speed up the column generation approach, assuring optimality by combining them with integer linear programming. Computational results for both real instances and instances from the literature are reported, showing that this hybrid method can solve crew scheduling problems to optimality quicker than using only exact methods.
ASSUNTO(S)
Ônibus linhas empregados administração modelos matematicos teses. problema do caixeiro viajante teses. computação teses. agenda de execução (administração) processamento de dados teses. programação (matematica) teses. algoritmos teses.
ACESSO AO ARTIGO
http://hdl.handle.net/1843/RVMR-7LKMB3Documentos Relacionados
- Estudo de meta-heuristicas populacionais para a programação de maquinas paralelas com tempos de preparação dependentes da sequencia e datas de entrega
- Inteligencia computacional na sintese de meta-heuristicas para otimização combinatoria e multimodal
- Heuristicas e metaheuristicas para otimização combinatoria multiobjetivo
- Modelos e algoritmos para o problema de alocação de tripulação em redes de transporte
- A relaxação Lagrangeana/surrogate e o método de geração de colunas: novos limitantes e novas colunas