New heuristics to crew scheduling problem / Novas heurísticas para o problema de escalonamento de atripulações




The crew scheduling problem consists in attributing to the crews the job of driving vehicles, in such a way that trips of dierent lines assisted by a company are executed with the smallest possible cost. This process is of fundamental importance in planning the operations for the public transportation sector and belongs to a class of dicult problems. Several methods have been applied to this problem presenting dierent results. This work reviews some of them presented in the literature, and presents a hybrid methodology, not yet explored, named ATP/PL, to solve such problem, searching varied solutions for problems considering real characteristics. The ATP/PL is based in a Column Generation technique and implemented through Population Training Algorithm with Linear Programming interaction. Besides, the obtained solutions are compared against solutions obtained by the Simulated Annealing metaheuristic, that had presented good results for real problems in previous works.


algoritmo de treinamento populacional heuristic methods geração de colunas column generation escalonamento de tripulações population training algorithm programação linear crew scheduling linear programming métodos heurísticos

Documentos Relacionados