Detalhes bibliográficos
Ano de defesa: |
2023 |
Autor(a) principal: |
Bastos, Ranmsés Emanuel Martins |
Orientador(a): |
Goldbarg, Elizabeth Ferreira Gouvêa |
Banca de defesa: |
Não Informado pela instituição |
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
|
Departamento: |
Não Informado pela instituição
|
País: |
Brasil
|
Palavras-chave em Português: |
|
Área do conhecimento CNPq: |
|
Link de acesso: |
https://repositorio.ufrn.br/handle/123456789/53356
|
Resumo: |
O Problema do Caixeiro Viajante com Múltiplos Passageiros e Lotação constitui uma generalização do Problema do Caixeiro Viajante que lhe adiciona características do mundo real, transformando-o em um problema de ridesharing com restrições de roteamento. Nessa modalidade, o caixeiro oferece caronas a terceiros ao longo da rota visando compartilhar os custos da viagem. As ligações entre cidades podem conter pedágios do tipo High-Occupancy, no qual há isenção da tarifa caso o veículo esteja com todos os assentos ocupados. Quando cobradas, as despesas de pedágio são inteiramente pagas pelo caixeiro. Os demais custos são divididos igualmente entre o caixeiro e todos os passageiros que ocupam assentos em seus respectivos percursos. O objetivo do PCV-MPL é encontrar o ciclo Hamiltoniano com o menor custo, calculado pela soma das despesas arcadas pelo caixeiro. Tais características promovem a eficiência no uso do espaço urbano e a redução das emissões de gases de efeito estufa, dado o incentivo para compartilhamento do meio de transporte com um número maior de pessoas. Esta tese apresenta o estudo deste novo problema de otimização combinatória, iniciando pela análise da relação existente com outros modelos na literatura. Em seguida, é abordada a formulação matemática do problema com diversas variantes para representação de suas restrições. Por fim, são criados algoritmos para encontrar soluções de boa qualidade em curto espaço de tempo. Com o intuito de realizar experimentos computacionais, é realizada a geração de um banco de instâncias artificiais e a implementação dos métodos de solução. Dez modelos matemáticos são implementados no solver Gurobi para estabelecer um padrão de referência, determinando soluções ótimas para as instâncias e comparando diferentes técnicas de formulação, incluindo restrições lazy e funções lineares piecewise. São propostos também procedimentos para manipular soluções e dez algoritmos heurísticos desenvolvidos com base nas meta-heurísticas Algoritmo Genético, Memético e Transgenética Computacional e na técnica de aprendizado por reforço Q-learning. Três experimentos computacionais são conduzidos: o primeiro controlado pelos parâmetros de iteração máxima, o segundo com limite absoluto de avaliações da função objetivo e o terceiro com limite de avaliações da função objetivo relativo à descoberta da última melhor solução. O ajuste de parâmetros é executado de modo automático pela ferramenta irace. Uma análise estatística baseada no teste Friedman Aligned Ranks indicou um desempenho superior do algoritmo híbrido unindo a Transgenética Computacional, o Algoritmo Memético e a técnica Q-learning. |