O Problema do Caixeiro Viajante com Múltiplos Passageiros Bônus Opcionais Quota e Tempo
Problema do Caixeiro Viajante, Programação matemática, Meta-heurística, ACO, GRASP, Transgenética Computacional.
O trabalho apresenta o Problema do Caixeiro Viajante com Múltiplos Passageiros Bônus Opcionais Quota e Tempo. O problema tem o objetivo de maximizar o lucro de um caixeiro viajante que além de transportar mercadorias pode transportar passageiros para ratear as suas despesas de rota. As mercadorias e os passageiros devem ser transportados obrigatoriamente das suas origens para os seus destinos. As mercadorias transportadas requerem tempo de carregamento e descarregamento, e devem contabilizar uma quota mínima definida a priori. O caixeiro também decide se transporta ou não uma mercadoria ou um passageiro quando visita uma localidade. O trabalho descreve o problema, o relaciona com outros problemas, e o formaliza matematicamente. São propostos um modelo de programação matemática não linear, dois algoritmos heurísticos, e treze algoritmos meta-heurísticos. As heurísticas desenvolvidas seguiram as meta-heurísticas ACO, GRASP e Transgenético. Também é proposta uma linearização do modelo de programação matemática não linear. Foram criados dois conjuntos de instâncias de teste. Um experimento computacional que compara e valida os modelos e algoritmos propostos é apresentado.