Banca de DEFESA: RANMSÉS EMANUEL MARTINS BASTOS

Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.
DISCENTE : RANMSÉS EMANUEL MARTINS BASTOS
DATA : 27/03/2023
HORA: 14:00
LOCAL: : https://meet.google.com/iyh-vwzt-pbw
TÍTULO:

Investigação de Modelos e Algoritmos para o Problema do Caixeiro Viajante com Múltiplos Passageiros e Lotação


PALAVRAS-CHAVES:

Problema do Caixeiro Viajante, Problema Ridesharing, Meta-Heurísticas, Aprendizado Por Reforço, Pedágios High-Occupancy, Restrições Lazy, Funções Piecewise


PÁGINAS: 124
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.


MEMBROS DA BANCA:
Presidente - 1201268 - ELIZABETH FERREIRA GOUVEA GOLDBARG
Interna - 2859606 - SILVIA MARIA DINIZ MONTEIRO MAIA
Externo à Instituição - LUCÍDIO DOS ANJOS FORMIGA CABRAL - UFPB
Externo à Instituição - MARCO CESAR GOLDBARG
Externo à Instituição - MATHEUS DA SILVA MENEZES - UFERSA
Notícia cadastrada em: 07/03/2023 10:24
SIGAA | Superintendência de Tecnologia da Informação - (84) 3342 2210 | Copyright © 2006-2024 - UFRN - sigaa08-producao.info.ufrn.br.sigaa08-producao