Parallel Random-Key Optimization for the Parallel Drone Scheduling Traveling Salesman Problem

This study addresses the Parallel Drone Scheduling Traveling Salesman Problem, a last-mile logistics challenge that coordinates a single truck with a fleet of drones to minimize total delivery time. To solve this NP-hard problem, this study proposes the application of the Random-Key Optimizer (RKO) framework, which decouples the search mechanism from the problem domain using a specialized decoder. This approach enables the parallel implementation of three distinct metaheuristics, Simulated Annealing, Biased Random-Key Genetic Algorithm, and Iterated Local Search, within a continuous random-key space. Numerical experiments on 45 benchmark instances show that RKO reaches the best known solution in 40 of them, converging in a few seconds in most cases. A statistical analysis indicates no significant difference from state-of-the-art methods when compared on their best solutions. The results indicate that a problem-independent solution representation is competitive with problem-specific approaches, at the cost of a modest loss on the largest instances.