Banca de QUALIFICAÇÃO: RANMSÉS EMANUEL MARTINS BASTOS

Uma banca de QUALIFICAÇÃO de DOUTORADO foi cadastrada pelo programa.
DISCENTE : RANMSÉS EMANUEL MARTINS BASTOS
DATA : 19/08/2022
HORA: 14:00
LOCAL: https://meet.google.com/xmj-rzoe-qgw
TÍTULO:

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

PALAVRAS-CHAVES:

Problema do Caixeiro Viajante, Transporte Compartilhado, Meta-heurísticas, Pedágio

PÁGINAS: 120
RESUMO:

O  Problema do Caixeiro Viajante com Múltiplos Passageiros e Lotação é uma extensão do PCV que o transforma, de um problema puro de roteamento, em um problema de ridesharing com restrições de roteamento determinadas por características do mundo real. Neste novo cenário, o caixeiro oferece caronas aos passageiros ao longo da rota do PCV para compartilhar despesas. Entre as estradas que ligam as cidades, algumas delas são estradas com pedágio, e estes são do tipo High-Occupancy, nos quais os veículos são isentos de pagar a tarifa se estiverem com todos os assentos ocupados. Quando cobradas, as despesas de pedágio são inteiramente pagas pelo vendedor, mas à exceção destes, todos os outros custos são compartilhados, sendo divididos igualmente entre o caixeiro e todos os passageiros que ocupam assentos em seus respectivos percursos. O objetivo do PCVMPL é encontrar o ciclo hamiltoniano com o menor custo, que é definido pela soma das despesas pagas pelo caixeiro ao longo da rota. Tais características colaboram para o uso eficiente do espaço urbano e para a redução das emissões de gases de efeito estufa, uma vez que há claro incentivo para mover mais pessoas usando os mesmos meios de transporte. Este trabalho apresenta o estudo deste novo problema de otimização combinatória, desde a concepção de um modelo matemático para representar todas as suas restrições, passando pela análise da relação existente com outros problemas na literatura e indo até a criação de algoritmos experimentais para encontrar soluções de boa qualidade. Para suportar a realização de experimentos computacionais e testar os métodos propostos, um conjunto de recursos também é apresentado, incluindo a geração de instâncias artificiais e a implementação dos métodos de solução. Quatro algoritmos experimentais baseados nas meta-heurísticas Algoritmo Genético, Memético e Transgenética Computacional são introduzidos. Procedimentos auxiliares para gerar e manipular soluções também são expostos. As instâncias são submetidas ao solver Gurobi para estabelecer um padrão de referência. O ajuste de parâmetros das heurísticas é feito usando a ferramenta iRace, as quais são em seguida comparadas por meio de dois experimentos computacionais, um sem critério adicional de parada e outro com um número máximo de avaliações da função objetivo. Uma análise estatística baseada em testes de Friedman indicou um desempenho superior do algoritmo que empregou a Transgenética Computacional e procedimentos de Busca Local.

MEMBROS DA BANCA:
Presidente - 1201268 - ELIZABETH FERREIRA GOUVEA GOLDBARG
Interna - 2859606 - SILVIA MARIA DINIZ MONTEIRO MAIA
Externo à Instituição - MATHEUS DA SILVA MENEZES - UFERSA