O PROBLEMA DO CAIXEIRO VIAJANTE COM MÚLTIPLOS PASSAGEIROS E QUOTA

- 83908
Artigo Completo
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Este trabalho apresenta o Problema do Caixeiro Viajante com Múltiplos Passageiros e Quota, uma variante do Problema do Caixeiro Viajante com Quota relacionada com outros modelos de roteamento enriquecido. O problema consiste em desenvolver uma solução do problema do Caixeiro Viajante com Quota considerando que o caixeiro é o motorista de carro que deseja compartilhar os custos de viagem com passageiros que podem ser embarcados e desembarcados em cidades da sua rota. Cada passageiro cuja solicitação de transporte é atendida compartilha os custos da viagem no caminho entre sua origem e seu destino com o caixeiro e outros passageiros no carro. Um modelo de programação matemática e um banco de instâncias são propostos para o problema. As soluções exatas para instâncias com até 10 vértices são apresentadas. Uma heurística ad hoc e duas heurísticas baseadas na meta-heurística colônia de formigas são propostas. Os resultados de um experimento computacional são relatados.

Instituições
  • 1 Universidade Federal do Rio Grande do Norte
Eixo Temático
  • OC – Otimização Combinatória
Palavras-chave
Caixeiro Viajante
Problemas de Ridesharing
Meta-heurísticas