Problema do caixeiro viajante alugador com passageiro

• Ano de defesa: 2020
• Autor(a) principal: Sabry, Gustavo de Araújo
• Orientador(a): Goldbarg, Marco César
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Rio Grande do Norte
• 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: Problema do Caixeiro viajante alugador com passageiros; Problema do caixeiro viajante; Otimização combinatória
• Link de acesso: https://repositorio.ufrn.br/jspui/handle/123456789/30184

Este trabalho apresenta uma nova variante do Problema do Caixeiro Viajante ainda não descrita na literatura, denominada de Problema do Caixeiro Viajante Alugador com Passageiros. Neste problema são disponibilizados um conjunto de cidades, um conjunto de veículos e um conjunto de passageiros em potencial. O tour do caixeiro pode ser realizado utilizando diferentes automóveis, ou seja, o problema engloba o processo de aluguel de veículos. O modelo proposto também inclui elementos relacionados ao compartilhamento dos assentos do veículos utilizado, ou seja, nas cidades podem haver pessoas interessadas em viajar para um determinado destino e dispostas a dividir os custos com o caixeiro enquanto estão embarcadas no veículo. O objetivo do problema é determinar, em um grafo, o ciclo Hamiltoniano de menor custo considerando as trocas de veículos e os embarques de passageiros durante o percurso. O problema é composto por várias decisões interligadas: a sequência das cidades visitadas, a ordem dos carros utilizados, as cidades onde os automó- veis devem ser alugados/devolvidos, bem como o esquema de embarque dos passageiros. A de nição do problema proposto neste trabalho envolve a combinação de dois conceitos importantes que estão sendo amplamente utilizados no setor de transportes: o aluguel e o compartilhamento de veículos. São propostas três formulações de programação inteira mista. Estas formulações são linearizadas utilizando técnicas diferentes, resultando em seis modelos lineares. Estes modelos são implementados em um solver e validados. Além disso, também são apresentadas três heurísticas ingênuas e três meta-heurísticas para solucionar o problema. Experimentos computacionais comparativos e testes de desempenho são realizados sobre uma amostra de 90 instâncias. Os resultados obtidos são comparados e as conclusões são reportadas.