Triple Resolutive Approach: A Repository of Five Combinatorial Optimization Problems with Exact and Metaheuristic Solutions

This work presents a reproducible repository that addresses five classical combinatorial optimization problems: the 0/1 knapsack problem, the traveling salesman problem (TSP), the capacitated vehicle routing problem (CVRP), permutation flowshop scheduling, and job shop scheduling. These problems are representative of resource allocation, routing, and scheduling challenges that are central to industrial and logistics applications, and all of them are NP-hard, which motivates the use of metaheuristic strategies. For each problem, three progressive Tabu Search (TS) configurations are implemented and compared under a unified framework: a basic version with a fixed tabu list, an intermediate version with a dynamic list combined with aspiration criteria and soft restart, and an advanced version that incorporates frequency-based long-term memory, adaptive penalization, and informed diversification. Exact reference models are also provided to characterize optimality gaps on tractable instances. A total of 360 experiments were carried out on widely used benchmarks (TSPLIB, Pisinger, and Taillard), and each configuration was executed with five independent random seeds to validate the stability of the results. The experimental evidence shows that the advanced configuration reduces the average global gap with respect to the best known solution (BKS) from 6.22% for the basic version to 3.06%, with especially notable improvements in CVRP (from 19.22% to 6.38%) and TSP (from 2.42% to 1.22%). The repository includes instance loaders, exact reference models, an experiment orchestrator, and automatic LaTeX table generators, so that the reported results can be replicated, audited, and extended by other researchers in a transparent and systematic manner.