Banca de DEFESA: EDUARDO PINHATA
DISCENTE	: EDUARDO PINHATA
DATA	: 11/02/2019
LOCAL: na sala 303, 3º andar do Bloco B, no campus Santo André
Uma modalidade de entrega que está sendo considerada por grandes empresas como Amazon e DHL é a entrega de pacotes utilizando um caminhão com um drone como seu assistente. Diversos autores estão propondo variações de problemas de otimização que modelam esse tipo de entrega, e os resolvendo com heurísticas e métodos exatos.
Este trabalho propõe dois algoritmos para encontrar soluções para instâncias de uma dessas variações de problemas, chamada de Flying Sidekick Travelling Salesman Problem (FSTSP). O algoritmo de Triplas Vantajosas usa um modelo de programação quadráica para encontrar possíveis combinações de sub-rotas com drones, para resolver o problema. Desenvolvemos também uma heurística, chamada de Heurística de Expansão, que utiliza de algumas propriedades do problema para tentar melhorar soluções de instâncias do FSTSP.
Pelas análises realizadas, o algoritmo de Triplas Vantajosas pode obter, em média, soluções melhores que o algoritmo do autor que propôs o FSTSP. A Heurística de Expansão obteve resultados positivos com uma baixa complexidade computacional.