29abr2026
10:00 Defesa de Mestrado Por videoconferência
Tema
Formulação e Heurísticas para o Traveling Salesman Problem with Drone
Aluno
Guilherme Pereira Porto Londe
Orientador / Docente
Lehilton Lelis Chaves Pedrosa
Breve resumo
Frotas heterogêneas são utilizadas em missões de resgate, monitoramento e também no planejamento de entregas last-mile. Tipicamente, há dois tipos veículos cooperando para cobrir uma área maior de forma mais eficiente: um operador (e.g. um drone) e um carregador (e.g. um caminhão). O operador possui baixa capacidade ou alcance reduzido, enquanto o carregador, com maior alcance e capacidade, atua como uma facilidade móvel para o operador, servindo como estação de recarga, depósito e, em muitos casos, podendo transportar o operador para outras regiões. Este trabalho faz uma breve revisão sobre problemas de roteamento com essa característica e investiga o uso de algoritmos de aproximação para uma variante que envolve um caminhão e um drone, conhecida como Traveling Salesman Problem with Drone (TSP-D). Neste problema, queremos encontrar tanto uma rota para o caminhão quanto uma rota para o drone, identificando pontos de encontro entre os veículos respeitando as restrições de capacidade. O objetivo é minimizar o tempo total para realizar todas as entregas. Propomos uma nova formulação em Programação Linear Inteira Mista (MILP) para o TSP-D. Também provamos que uma solução ótima de um problema relacionado, chamado Minimum Spanning Caterpillar Tree (MSCT), pode ser reduzido a uma 2-aproximação para o caso métrico do TSP-D. Exploramos o fato de que a formulação em MILP associada ao MSCT é mais leve, e com
isso propomos uma nova heurística baseada em resolver o MSCT usando um resolvedor e melhorar o roteamento final através de Programação Dinâmica. Experimentos mostram que esta heurística produz bons resultados para um grupo de instâncias ainda não coberto por soluções exatas. Além disso, propomos duas heurísticas baseadas em arredondamento de relaxação linear que, embora não executem em tempo polinomial no pior caso, devolvem soluções com garantia de qualidade. Para cada constante ϵ, com 0 < ϵ < 1, apresentamos uma heurística com fator de aproximação 2/ϵ e outra com fator 1/ϵ, mas menos eficiente.
Banca examinadora
Titulares:
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
| Mário César San Felice | CCET/UFSCar |
| Luis Augusto Angelotti Meira | FT/UNICAMP |
Suplentes:
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| Kelly Cristina Poldi | IMECC/UNICAMP |