Publicado no Encontro de Saberes 2017
Evento: XXV Seminário de Iniciação Científica
Área: ENGENHARIAS
Subárea: Engenharia de Produção
Órgão de Fomento: Fundação de Amparo à Pesquisa do Estado de Minas Gerais
| Título |
| Uma heurística para o Problema do Caixeiro Viajante auxiliado por Drone |
| Autores |
|
JULIA CARIA DE FREITAS (Autor) Puca Huachi Vaz Penna (Orientador) |
| Resumo |
| Veículos aéreos não tripulados, também conhecidos como drones possuem o potencial de reduzir o custo e o tempo necessário para realizar entregas de última milha. Este trabalho apresenta o cenário no qual o drone trabalha em colaboração com o caminhão para realizar as entregas de encomendas. Essa variante do Problema do Caixeira Viajante (PCV) possui algumas particularidades, por isso as restrições existentes são insuficientes para sua resolução. Portanto, para complementar o problema novas restrições são consideradas como o limite de tempo de voo do drone, o que o impede de visitar todos os clientes. Além de que, o peso do pacote a ser entregue não pode exceder a carga útil do drone e, por fim não é permitido que o veículo realize múltiplas viagens para o centro de distribuição. A resolução do problema pode ser explicada em dois passos: primeiramente, foi obtida através do resolvedor Concorde a solução ótima do PCV. A seguir, a implementação da heurística Descida em Vizinhança Variável Randômica foi utilizada como busca local para obter a solução do problema. Com o objetivo de testar a heurística proposta foram criados 11 problemas teste baseados nos já bem conhecidos do PCV. Os experimentos computacionais mostraram que o uso de drone para entregas de última milha podem reduzir o tempo de entrega total em até aproximadamente 20%. Além disso, prover um sistema de entrega mais rápido tem um impacto ambiental positivo, uma vez que o tempo de viagem do caminhão é reduzido. |
