O problema do caixeiro viajante com múltiplos passageiros e quota

• Ano de defesa: 2018
• Autor(a) principal: Carvalho, Allan Vilar de
• Orientador(a): Goldbarg, Marco César
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Programa de Pós-Graduação: PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO
• País: Brasil
• Palavras-chave em Português: Caixeiro viajante; Problemas de Ridesharing; Meta-heurísticas
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
• Link de acesso: https://repositorio.ufrn.br/jspui/handle/123456789/26825

O presente trabalho apresenta o Problema do Caixeiro Viajante com Múltiplos Passageiros e Quota, variante do Problema do Caixeiro Viajante com Quota. O problema consiste em minimizar os custos de um caixeiro viajante que deve coletar uma cota mínima de bônus nas localidades do problema, considerando a possibilidade de rateio das despesas de rota com eventuais passageiros embarcados no veículo do caixeiro. Os passageiros, se embarcados, devem ser transportados obrigatoriamente até seus destinos previamente conhecidos. Os passageiros participam do rateio dos custos da rota nos trechos em que estiverem embarcados. O trabalho propõe e valida um modelo de Programação Matemática Linear para formalizar o problema. São propostos também um banco de instâncias e métodos heurísticos para a solução do problema. Experimentos computacionais validam os métodos propostos através da solução das instâncias do banco proposto. Desenvolve-se um experimento computacional para obter conclusões sobre a eficiência e eficácia dos métodos propostos.