O Problema do Caixeiro Viajante com Passageiros
Palavras-chave: Caixeiro Viajante. Passageiros. Algoritmos Evolucionários. Algoritmo Genético. Algoritmo Memético.
Este trabalho apresenta um modelo de compartilhamento de assentos veicular de modo a reduzir os custos de viagem de motoristas e passageiros, contribuindo de maneira significativa ao meio ambiente e à sociedade. O problema também é descrito através de um modelo de programação linear e são discutidas algumas variantes de um subproblema importante para resolução do modelo proposto. Além disso, algumas abordagens computacionais são implementadas, compostas de algoritmos evolucionários (genético e mémetico) e construtivos (formigas e GRASP). Além da adaptação de algoritmos já existes para o problema do caixeiro viajante tradicional como o algoritmo de Lin-Kernighan. Após a realização de experimentos, o algoritmos baseado em formiga revela-se promissor para instâncias assimétricas enquanto que o algoritmo de Lin-Kernighan leva vantagem pela sua robustez através da implementação de Helsgaun e desempenha bom resultados para instâncias simétricas.