Defesa de mestrado da discente Júlia Cária, dia 05/10 as 16:00.

Defesa de mestrado da discente Júlia Cária, dia 05/10 as 16:00.

Título: Exact and heuristic approaches for Travelling Salesman Problems With Drones
Data: 05/10/2021; Horário: 16h
Informações de participação do Google Meet
Link da videochamada: https://meet.google.com/sbj-tahz-hxb
Banca:
Prof. Dr. Puca Huachi Vaz Penna - UFOP
Prof. Dr. Túlio Ângelo Machado Toffolo - UFOP
Prof. Dr. Anand Subramanian - UFPB
Prof. Dr. Marcone Jamilson Freitas Souza - UFOP

Abstract:
The technological advances concerning drones have encouraged the market to consider drone applications in different areas including last mile delivery. However, limitations due to battery capacity, maximum weight, and legal regulations restrict the effective operational range of drones in many practical applications.
To overcome the battery issue, hybrid operations involving one or more drones launching from a larger vehicle have emerged, in which the larger vehicle operates as a mobile depot and a recharging platform.
In this dissertation, we describe a routing model that leverage the drone and truck working as a synchronized unit.
The Flying Sidekick Traveling Salesman Problem (FSTSP) considers a delivery system composed by a truck and a drone. The drone launches from the truck with a single package to deliver to a customer. Each drone must return to the truck to recharge batteries, pick up another package, and launch again to a new customer location.
This work proposes two novel Mixed Integer Programming (MIP) formulations and a heuristic approach to address the problem.
The proposed MIP formulations yields better linear relaxation bounds than previously proposed formulations for all instances, and was capable of optimally solving several unsolved instances from the literature.
We developed a hybrid heuristic based on the General Variable Neighborhood Search metaheuristic to tackle a generalization of the FSTSP called Multiple Traveling Salesman Problem with Drones, in which multiple trucks and drones are considered as part of the delivery system. The heuristic obtained high-quality solutions for large-size instances. The efficiency of the algorithm was evaluated on 1415 benchmark instances from the literature, and over 80% of the best known solutions were improved.

Resumo:
Os avanços tecnológicos em relação a drones têm incentivado o mercado a desenvolver novas aplicações em diferentes áreas, incluindo a entrega de última milha. No entanto, as limitações devido à capacidade da bateria, peso máximo e regulamentos restringem a operação dos drones em muitas aplicações práticas.
Com o intuito de superar a limitação da bateria em operações de entrega, surgiram operações híbridas envolvendo um ou mais drones que são lançados de um veículo maior. Este veículo funciona como um depósito móvel e uma plataforma de recarga.
Nesta dissertação, descrevemos um modelo de roteamento que aproveita o trabalho sincronizado entre drone e o caminhão.
O Flying Sidekick Traveling Salesman Problem (FSTSP) considera um sistema de entrega composto por um caminhão e um drone. O drone é lançado do caminhão com um único pacote para realizar a entrega ao cliente. O drone deve retornar ao caminhão para recarregar as baterias, pegar outro pacote e ser lançado novamente de um novo local.
Este trabalho propõe duas formulações de Programação Inteira Mista (MIP) e uma abordagem heurística para abordar o problema.
Foram propostas duas formulações que produzem melhores limites de relaxação linear do que as formulações já existentes na literatura para todas as instâncias. Além disso, desenvolvemos uma heurística híbrida com base na metaheurística General Variable Neighbourhood Search para lidar com a variante FSTSP chamada Multiple Traveling Salesman Problem with Drones, na qual vários caminhões e drones são considerados como parte do sistema de entrega. A heurística desenvolvida obteve soluções de alta qualidade para instâncias grandes. A eficiência do algoritmo foi avaliada em 1415 instâncias de benchmark da literatura, e mais de 80 % das soluções conhecidas foram melhoradas.