Advanced Optimization Methods for the Knapsack, Traveling Salesman, and Close-Enough Traveling Salesman Problems: A Survey and Case Studies

Abstract

Combinatorial optimization problems (COPs), including the Knapsack Problem (KP), the Traveling Salesman Problem (TSP), and regional variants such as the Close-Enough Traveling Salesman Problem (CETSP), constitute fundamental models for addressing complex decision-making tasks in modern computational systems. Their computational difficulty has motivated the development of a broad range of exact, heuristic, metaheuristic, learning-based, and hybrid optimization approaches. This work presents a structured survey and problem-structure-oriented comparative analysis of these methods, covering Genetic Algorithms (GAs), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), Simulated Annealing (SA), Tabu Search (TS), Artificial Bee Colony (ABC), Graph Neural Networks (GNNs), and learning-enhanced hybrid approaches. Particular attention is given to how differences in problem structure, formulation characteristics, feasibility requirements, computational cost, and evaluation settings influence the suitability of different optimization paradigms. The practical relevance of these approaches is discussed through two case studies based on our prior work: Virtual Machine Placement (VMP) in cloud computing, examined through a simplified single-resource 0–1 KP abstraction, and UAV trajectory optimization for data collection in Wireless Sensor Networks (WSNs), examined through TSP-, CETSP-, and neighborhood-based routing models. The reviewed evidence indicates that metaheuristic approaches can provide flexible search mechanisms in computationally challenging settings, while learning-based models may support rapid inference, prediction, initialization, or search guidance when appropriate training data and generalization conditions are available. Hybrid learning–optimization frameworks may be beneficial when their components address complementary limitations of the underlying problem, although their effectiveness remains dependent on problem structure, training requirements, computational budget, feasibility handling, and implementation design. In cloud environments, knapsack-based VMP formulations provide useful abstractions for resource-allocation decisions, whereas in UAV-assisted WSNs, routing models such as the TSP and CETSP provide structured representations of trajectory and data-collection decisions. Overall, this survey highlights the complementary strengths and limitations of modern optimization paradigms and emphasizes that method selection should be guided by problem structure, operational requirements, feasibility considerations, and computational constraints.