Aplicação de Algoritmos Genéticos ao Problema da Geração de Serviços de Tripulações

• Type: Article in International Conference Proceedings Book
• Date: 1994

Authors

Teresa Galvão Dias (Author) FEUP; João Falcão e Cunha (Author) FEUP; Jorge Pinho de Sousa (Author) FEUP

Conference proceedings National

Title: Comunicação apresentada no 'IO94

6° Congresso Nacional de Investigação Operacional

Braga, Portugal, 28 - MARÇO - 1994

Other information

Resumo (PT): No planeamento operacional de transportes, a geração de serviços do pessoal tripulante constitui um problema complexo, altamente combinatório e envolvendo inúmeras restrições, muitas vezes incompletamente definidas e conflituosas. Na prática, existem dois tipos de soluções para o problema: soluções de cobertura, nas quais é permitido que mais do que uma tripulação conduza a mesma viatura ao mesmo tempo e soluções de partição, nas quais em cada instante apenas uma tripulação pode conduzir a viatura, sendo possível, neste último caso, que existam períodos de trabalho das viaturas sem tripulação atribuída. Para a resolução deste problema, são tradicionalmente aplicados procedimentos de Programação Matemática ou técnicas heurísticas do tipo "run-cutting" que têm, em geral, como objectivo reproduzir os procedimentos manuais usados nas empresas. Nesta comunicação, descreve-se a aplicação de Algoritmos Genéticos ao problema da geração de serviços de tripulações. A utilização de algoritmos genéticos tem à partida duas características que podem ser importantes: a interrupção em qualquer momento do processo de cálculo produz soluções com significado e este processo pode ser facilmente paralelizado. São produzidas soluções dos dois tipos, cobertura e partição, e para cada um deles descrevem-se as codificações utilizadas e os diferentes operadores de selecção, cruzamento e mutação implementados. Discute-se também a possível hibridização destes algoritmos com técnicas tradicionais e os processos utilizados para garantir a diversidade das populações e evitar óptimos locais, bem como a importância e a facilidade de tratar características do problema que não são facilmente captáveis pelos algoritmos tradicionais. Finalmente, comparam-se os resultados obtidos por esta abordagem com os que são obtidos pela aplicação de técnicas de Programação Matemática e de heurísticas "run-cutting".

Language: Portuguese

Type (Professor's evaluation): Scientific