Título: Modelagem e Otimização de Problemas de Roteamento de Veículos em Situações Reais
Comissão Examinadora - Titulares
Prof. Dr. Luis Augusto Angelotti Meira (Presidente)
Prof. Dr. Luiz Leduino de Salles Neto
Prof. Dr. Antônio Augusto Chaves
Profa. Dra. Kelly Cristina Poldi
Prof. Dr. Anibal Tavares de Azevedo
Suplentes
Prof. Dr. Iago Augusto de Carvalho
Prof. Dr. Marco Antonio Garcia de Carvalho
Prof. Dr. Norton Trevisan Roman
Local: Sala de Defesa (Prédio da Pós-Graduação da FT) | https://stream.meet.google.com/stream/ed70d711-8d5a-4e6f-ad11-50466398ee39
Resumo: Eficiência logística é de fundamental importância para o sucesso das civilizações ao longo da história, de rotas fluviais no Antigo Egito e demandas militares nas duas grandes guerras mundiais aos sistemas de GPS e comércio globalizado da atualidade. Um dos problemas logísticos mais estudados dos últimos setenta anos é o Problema de Roteamento de Veículos (VRP), o qual envolve utilizar um conjunto de "veículos" para visitar um conjunto de "clientes" de forma eficiente. Apesar da popularidade do VRP e do grande avanço em poder computacional, a otimização multiobjetivo e de objetivos mais abstratos (e.g., satisfação do cliente) ainda precisa ser adotada em mais situações reais. Neste trabalho, buscamos modelar e otimizar problemas de roteamento de veículos em situações reais. Mais especificamente, trabalhamos com dois casos: roteamento de carteiros a pé, cuja variante é chamada de PostVRP, e roteamento de ônibus fretados, cuja variante chamamos de CharteredBusVRP. Para o PostVRP, oferecemos uns dos primeiros resultados de otimização de um conjunto de instâncias criado em 2019. Nosso foco principal foi minimizar o número de veículos. Para o CharteredBusVRP, primeiro utilizamos dados públicos, como itinerários, estatísticas e valores contratuais, para modelar um conjunto com duas instâncias baseadas no serviço de transporte fretado oferecido para os funcionários da Unicamp. Em seguida, otimizamos essas instâncias aplicando algoritmo genético, para o qual desenvolvemos dois operadores novos: o Centripetal Sweep Algorithm para criar a população inicial e o Line Split Crossover Algorithm para criar descendentes, ambos sensíveis à disposição espacial dos pontos. A modelagem do CharteredBusVRP foi multiobjetivo, minimizando o custo monetário da solução e o tempo médio de viagem dos passageiros. Comparando a solução original, conseguimos decréscimo de 1,18 minutos no tempo médio de viagem (3,88%) e 514 mil reais (6,95%) na primeira instância, e de 38,88$ segundos no tempo médio de viagem e 87.612 reais na segunda instância. Tivemos sucesso na modelagem e otimização de problemas de roteamento de veículos em situações reais, com geração computacional de rotas que, no caso do transporte fretado, superam as rotas atualmente utilizadas pela universidade dentro das métricas consideradas.