The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, with wide-ranging applications in logistics, manufacturing, and network design. In addition to the classical formulation, recent years have witnessed the emergence of complex variants, such as the TSP with Drones (TSP-D), TSP with Time Windows, and Prize-Collecting TSP, that incorporate novel constraints reflecting real-world requirements like last-mile delivery and multimodal logistics. This review presents a comprehensive survey of metaheuristic approaches for solving both the classical TSP and its emerging extensions, with particular emphasis on metaheuristic, hybrid methods, and machine learning-enhanced strategies. Recent algorithmic developments, benchmark datasets, and evaluation metrics are investigated, and critical challenges in addressing drone coordination, synchronization, and uncertainty are identified, as well. Bibliometric analysis is further provided to map research trends and the evolution of the field. By synthesizing foundational techniques and state-of-the-art innovations, this review outlines current progress and proposes future directions for metaheuristic optimization in increasingly dynamic and heterogeneous routing scenarios.
A Comprehensive Review of Metaheuristics for the Modern Traveling Salesman Problem and Drone-Assisted Delivery
Mezzina, Alessio;Pavone, Mario
2026-01-01
Abstract
The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, with wide-ranging applications in logistics, manufacturing, and network design. In addition to the classical formulation, recent years have witnessed the emergence of complex variants, such as the TSP with Drones (TSP-D), TSP with Time Windows, and Prize-Collecting TSP, that incorporate novel constraints reflecting real-world requirements like last-mile delivery and multimodal logistics. This review presents a comprehensive survey of metaheuristic approaches for solving both the classical TSP and its emerging extensions, with particular emphasis on metaheuristic, hybrid methods, and machine learning-enhanced strategies. Recent algorithmic developments, benchmark datasets, and evaluation metrics are investigated, and critical challenges in addressing drone coordination, synchronization, and uncertainty are identified, as well. Bibliometric analysis is further provided to map research trends and the evolution of the field. By synthesizing foundational techniques and state-of-the-art innovations, this review outlines current progress and proposes future directions for metaheuristic optimization in increasingly dynamic and heterogeneous routing scenarios.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
