O Problema do Caixeiro Viajante com Múltiplos Passageiros Bônus Optativos 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 Optativos Quota e Tempo. O problema tem o objetivo de maximizar o lucro de um caixeiro viajante transportador de mercadorias. O caixeiro 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. São propostos um modelo de programação matemática quadrático, dois algoritmos heurísticos, e onze algoritmos meta-heurísticos. As meta-heurísticas foram desenvolvidas seguindo as meta-heurísticas ACO, GRASP e Transgenético. Também é proposto duas linearizações de modelo de programação matemática quadrático, e dois conjuntos de instâncias de teste. Um experimento computacional que compara e valida os modelos e algoritmos propostos também é apresentado.