DEFESA DO PROJETO DE TESE DE DOUTORADO

TÍTULO:

“Redução de Dimensionalidade Online para Problema de Roteamento de Veículos com Transporte Reativo a Demanda”.

Profª. Drª. Elizabeth Fialho Wanner (Orientadora)

Prof. Dr. Flávio Vinícius Cruzeiro Martins (Coorientador)

CEFET-MG

CEFET-MG

Prof. Dr. Alan Robert Resende de Freitas

Prof. Dr. Adriano Chaves Lisboa

Prof. Dr. Douglas Alexandre Gomes Vieira

UFOP

CEFET-MG

CEFET-MG

LOCAL:

Auditório 101 do Prédio 17 – Departamento de Computação (DECOM), Campus II, CEFET-MG - Av. Amazonas, 7675 - Nova Gameleira

DIA:

27 de agosto de 2018 - segunda-feira

HORA:

09 horas

RESUMO:

Neste trabalho foi estudada uma formulação com muitos objetivos para o Problema de Roteamento de Veículos com Transporte Reativo a Demanda (PRVTRD). O problema relaciona-se ao modo de transporte semelhante a serviços de transporte por demanda com compartilhamento de corridas fornecidos por empresas como Uber e Bridj, nos quais os passageiros são transportados da sua origem para o seu destino, compartilhando o mesmo veículo. O objetivo desse tipo de transporte é reduzir os custos de operação/deslocamento, atendendo às necessidades dos passageiros e oferecendo serviços de alta qualidade. Devido à complexidade e às características conflitantes do problema, uma abordagem evolutiva é aplicada para resolver o PRVTRD na qual nove funções objetivo diferentes são usadas. Este trabalho propõe o algoritmo OnCL τ -NSGA-II que utiliza uma análise de cluster online baseada em τ de Kendall como medida de similaridade para realizar a redução de dimensionalidade a cada geração do algoritmo NSGA-II. Para avaliar o desempenho da abordagem proposta, o OnCL τ -NSGA-II é comparado às reduções de dimensionalidade offline feitas pela Árvore de Agregação, cluster com os coeficientes de correlação de Pearson e cluster com τ de Kendall. A API do Google Maps foi usada para se gerar as instâncias com dados reais dos valores de distância e tempo de deslocamento para a cidade de Belo Horizonte. Em relação à dispersão de soluções, foi utilizada a métrica de Contagem de Clusters Hierárquicos (Hierachical Cluster Counting - HCC) que avalia a qualidade de conjuntos não dominados. Uma outra métrica foi a cobertura de conjuntos para comparar os resultados no espaço objetivo original em R 9 . Os resultados mostram que a abordagens online baseada em cluster alcançam soluções com maior diversidade em 75% das instâncias testadas, quando comparadas às suas versões offline.

Palavras-chave: Problema de Roteamento de Veículos com Transporte Reativo a Demanda. Otimização com Muitos Objetivos. Técnicas de Redução de Dimensionalidade. Análise de Cluster. Correlação de Kendall.