Evolução Diferencial Probabilística para o Problema do Caixeiro Viajante com Drone

Será defendida no dia 27 de janeiro de 2026, às 16:00 horas, por videoconferência, a Proposta de Tese de Doutorado intitulada “Evolução Diferencial Probabilística para o Problema do Caixeiro Viajante com Drone”, do candidato ao título de Doutor em Computação – Israel Pereira de Souza.

Link para defesa: meet.google.com/ugb-pnno-gho

Evolução Diferencial Probabilística para o Problema do Caixeiro Viajante com Drone

Resumo:

As empresas têm buscado métodos para encontrar a maneira mais econômica de distribuir mercadorias pela rede logística e usualmente caminhões são responsáveis para atender a demanda de diversos clientes ao longo do tempo. O problema do caixeiro viajante é um problema conhecido de otimização combinatória e possui grande impacto na otimização dos processos logísticos.

A literatura tem apresentado um estudo emergente na aplicação de drones para solução de problemas, que podem impulsionar o comércio e a economia, diminuindo tempos de entrega e possibilitando entregas onde caminhões não teriam acesso.

Neste trabalho, propomos um novo algoritmo, denominado PDELS, para solucionar um problema chamado, do inglês flying sidekick traveling salesman problem (FSTSP), que consiste em uma variação do problema do caixeiro viajante com uso de drones. O FSTSP consiste na existência de um caminhão e um drone, que partem de um depósito e precisam visitar um conjunto que clientes e é preciso minimizar o tempo de atendimento total neste percurso, visitando todas as clientes apenas uma vez, pelo caminhão e/ou drone e retornar o depósito origem. 

O FSTSP é um problema difícil de ser resolvido com otimalidade. Há várias aplicações deste problema no mundo real, como em logística e transportes, em que é possível modelar os cenários de entrega e minimizar trajetórias e custos de transportes, diminuindo o trânsito de veículos e podendo reduzir diretamente o custo de produtos.

Entre os métodos para solução do problema do FSTSP estão as meta-heurísticas, que são reconhecidas na literatura por serem eficientes para solução de problemas computacionais difíceis.

Apresentamos um novo algoritmo híbrido baseado na meta-heurística evolução diferencial com busca local, que apresenta uma adaptação da evolução diferencial para problemas combinatórios, considerando probabilidades que apresentam maiores prioridades para posições consideradas superiores.

Abstract:

Companies have been looking for alternatives to find the most economical way to distribute goods through the logistics network and trucks are usually responsible for meeting the demands of several customers over time. The traveling salesman problem is a well-known combinatorial optimization problem and has a major impact on optimizing logistics processes.

The literature presents an emerging study on the application of drones to problem-solving, which can boost trade and the economy, reducing delivery times and enabling deliveries where trucks would not have access.

In this work, we propose a new algorithm, called PDELS, to solve the flying sidekick traveling salesman problem (FSTSP), that consists of a salesman and a drone, that departs from a deposit and are required to visit a set of customers. The problem seeks to minimize the total service time, visiting all customers only once, by the salesman and/or drone and returning to the deposit of origin.

The FSTSP is a difficult problem to solve optimally. Several applications of this problem in the real world can be observed, such as in logistics and transportation, where it is possible to model delivery scenarios and minimize trajectories and transportation costs, reducing vehicle traffic and directly reducing product costs.

Meta-heuristics are recognized in the literature as efficient methods for solving difficult computational problems and are among the methods for solving the flying sidekick traveling salesman problem.

  We present a new hybrid algorithm based on differential evolution metaheuristic with local search, that presents a new adaptation for the differential evolution to combinatorial problems, based on permutation components considering probabilities that provide higher priorities for positions that are considered superior.

Banca  examinadora:

Prof. Igor Machado Coelho, UFF

Profa. Simone de Lima Martins, UFF

Prof. Yuri Abitbol de Menezes Frota, UFF

Prof. Marcone Jamilson Freitas Souza, UFOP

Profa. Maria Claudia Silva Boeres, UFES