Exact and heuristic approaches for traveling salesman problems with drones.

Simple item page
dc.contributor.advisorPenna, Puca Huachi Vazpt_BR
dc.contributor.advisorToffolo, Túlio Ângelo Machadopt_BR
dc.contributor.authorFreitas, Júlia Cária de
dc.contributor.refereePenna, Puca Huachi Vazpt_BR
dc.contributor.refereeToffolo, Túlio Ângelo Machadopt_BR
dc.contributor.refereeSouza, Marcone Jamilson Freitaspt_BR
dc.contributor.refereeSubramanian, Anandpt_BR
dc.date.accessioned2021-11-24T23:50:14Z
dc.date.available2021-11-24T23:50:14Z
dc.date.issued2021pt_BR
dc.descriptionPrograma 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.pt_BR
dc.description.abstractThe 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.pt_BR
dc.description.abstractenOs 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.pt_BR
dc.identifier.citationFREITAS, 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.pt_BR
dc.identifier.urihttp://www.repositorio.ufop.br/jspui/handle/123456789/14038
dc.language.isoen_USpt_BR
dc.rightsabertopt_BR
dc.rights.licenseAutorizaçã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.pt_BR
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/us/*
dc.subjectProgramação linearpt_BR
dc.subjectHeurísticapt_BR
dc.subjectOtimização combinatóriapt_BR
dc.titleExact and heuristic approaches for traveling salesman problems with drones.pt_BR
dc.typeDissertacaopt_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
DISSERTAÇÃO_ExactHeuristicApproaches.pdf
Size:
1.21 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
PPGCC - Mestrado (Dissertações)