Problema do Caixeiro Viajante com Coleta de Prêmios, Passageiros e Penalidades por Atrasos
Problema do Caixeiro Viajante com Coleta de Prêmios, Passageiros e Penalidades; Meta-heurísticas, Oimização combinatória.
Este trabalho introduz uma nova variante do Problema do Caixeiro Viajante denominada por Problema do Caixeiro Viajante com Coleta de Prêmios, Passageiros e Penalidades por Atrasos. Neste, o caixeiro dispõe, ao longo do grafo, de potenciais passageiros que necessitam se locomoverem entre as localidades. Cada passageiro embarcado contribuirá com uma parcela para a divisão dos custos de viagem entre todos os ocupantes do veículo em um determinado trecho. Além disso, cada vértice possui um valor de bônus agregado que poderá ou não ser coletado pelo caixeiro durante o seu trajeto. Os bônus possuem um tempo para a realização da coleta e um tempo mínimo estimado para ser coletado sem que haja uma redução no seu valor, caracterizando a penalidade. Desse modo, o objetivo consiste em encontrar uma rota que maximize o valor de bônus coletado subtraído dos custos de viagem rateados com os passageiros e das eventuais penalidades impostas aos bônus. Como instrumento de formalização e validação do problema, um modelo de Programação Matemática é proposto e solucionado através de um solver matemático para instâncias de testes geradas para o problema em questão. Uma análise de acoplamento das instâncias é relatada mediante experimentos com métodos heurísticos ad hoc e métodos exatos que consideram casos particulares do modelo. Ainda, são propostas três meta-heurísticas evolucionárias visando a eficiência na obtenção de soluções de qualidade.