Evolutionary Metaheuristics for the Flying Sidekick Traveling Salesman Problem

In this paper we address the Flying Sidekick Traveling Salesman Problem, where a truck and a drone collaborate to make deliveries in the shortest possible time. To tackle it, we employed two evolutionary metaheuristics, the Hybrid Genetic Search with Adaptive Diversity Control and the Multi-Parent Biased Random-Key Genetic Algorithm, both using decoders based on the SplitLazy algorithm. We also proposed a local search based on the 2-opt, and a family of heuristics, called Elliptic Bubbles. Our methods improved the literature results for 96% of the categories of instances evaluated, where each category has 10 instances with the same size and distribution type.