A probabilistic discrete differential evolution for the flying sidekick traveling salesman problem

This paper presents a novel probabilistic discrete adaptation of the Differential Evolution (DE) metaheuristic for solving the Flying Sidekick Traveling Salesman Problem (FSTSP), a Traveling Salesman Problem variant that integrates trucks and drones for coordinated deliveries and constitutes a challenging combinatorial optimization problem. Although DE was originally designed for continuous optimization, recent advances have extended its application to discrete domains. In this work, a probability-based mechanism is introduced to operate directly in the discrete domain, avoiding transformations from continuous space. Notably, it operates in linear time, which is asymptotically more efficient than approaches relying on comparison-based sorting procedures.  Computational experiments demonstrate that the proposed method is competitive with the state-of-the-art, outperforming classical heuristics and recent algorithms. Moreover, the proposed algorithm found 5 of 20 optimum solutions while maintaining a low computation time (3.38s average in the experiments). These results highlight the potential of probabilistic discrete adaptations of DE.