Use este identificador para citar ou linkar para este item: http://www.repositorio.ufop.br/jspui/handle/123456789/14038
Título: Exact and heuristic approaches for traveling salesman problems with drones.
Autor(es): Freitas, Júlia Cária de
Orientador(es): Penna, Puca Huachi Vaz
Toffolo, Túlio Ângelo Machado
Palavras-chave: Programação linear
Heurística
Otimização combinatória
Data do documento: 2021
Membros da banca: Penna, Puca Huachi Vaz
Toffolo, Túlio Ângelo Machado
Souza, Marcone Jamilson Freitas
Subramanian, Anand
Referência: FREITAS, Júlia Cária de. Exact and heuristic approaches for traveling salesman problems with drones. 2021. 90 f. Dissertação (Mestrado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2021.
Resumo: 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 410 benchmark instances from the literature, and over 80% of the best known solutions were improved.
Resumo em outra língua: 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 tratar 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 meta-heurí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 410 instâncias de benchmark da literatura, e mais de 80% das soluções conhecidas foram melhoradas.
Descrição: Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
URI: http://www.repositorio.ufop.br/jspui/handle/123456789/14038
Licença: Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 15/11/2021 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho, desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação.
Aparece nas coleções:PPGCC - Mestrado (Dissertações)

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
DISSERTAÇÃO_ExactHeuristicApproaches.pdf1,24 MBAdobe PDFVisualizar/Abrir


Este item está licenciado sob uma Licença Creative Commons Creative Commons