05 mar 2020
14:00 Defesa de Doutorado Auditório 1 - IC 3
Tema
Algorithms and mathematical formulations for arc routing problems
Aluno
Rafael Kendy Arakaki
Orientador / Docente
Fábio Luiz Usberti
Breve resumo
Problemas de roteamento em arcos têm por objetivo determinar rotas de custo mínimo que visitam um subconjunto de arcos de um grafo, com uma ou mais restrições adicionais. Esta tese estuda três problemas NP-difíceis de roteamento em arcos: (1) o problema de roteamento em arcos capacitado (CARP); (2) o problema de roteamento em arcos capacitado e aberto (OCARP); e (3) o problema do carteiro chinês com cobertura (CCPP). Apresentamos formulações matemáticas e métodos exatos e heurísticos para tratar computacionalmente esses problemas: (i) uma heurística construtiva gulosa e randomizada é proposta para o CARP; (ii) uma metaheurística de algoritmos genéticos híbrido e dois métodos de limitantes inferiores por programação inteira, um branch-and-cut e um baseado em fluxos, são propostos para o OCARP; (iii) um método exato branch-and-cut com desigualdades válidas é proposto para o CCPP. Extensivos experimentos computacionais utilizando instâncias de benchmark foram executados para comprovar que os métodos propostos superaram os métodos anteriores substancialmente e apresentam-se como estado da arte.
Os problemas estudados apresentam aplicações práticas relevantes: o CARP possui aplicações em coleta de lixo e remoção de neve de estradas; o OCARP em roteamento de leituristas e na definição de caminhos de corte em chapas metálicas; e o CCPP em roteamento de leituristas com tecnologia wireless. A solução desses problemas remete à diminuição de custos logísticos, melhorando a competitividade das empresas.
Banca examinadora
Titulares:
| Fábio Luiz Usberti | IC/UNICAMP |
| Franklina Maria Bragion de Toledo | ICMC/USP |
| Mário César San Felice | DC/UFSCar |
| Celso Cavellucci | IC/UNICAMP |
| Paulo Morelato França | FEEC/UNICAMP |
Suplentes:
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| Pedro Henrique del Bianco Hokama | UNIFEI |