Método de geração de colunas e meta-heurísticas para alocação de tripulação

AUTOR(ES)
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.

Documentos Relacionados