International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 17, No. 4, 8 Aug. 2025
Cover page and Table of Contents: PDF (size: 713KB)
Exploratory Heuristics for Scalable Combinatorial Optimization
PDF (713KB), PP.58-68
Views: 0 Downloads: 0
Author(s)
Index Terms
Traveling Salesman Problem, Heuristic Algorithm, Local Optimization, Combinatorial Optimization, Performance Comparison, Deterministic Algorithm, Algorithmic Trade-off
Abstract
This paper introduces a deterministic insertion-based heuristic named the Localized Selective Insertion Heuristic, which incorporates adaptive mechanisms such as dynamic adjustment of evaluated neighbors and systematic seed route initialization, contributing to the heuristic's novelty and robust performance, designed to provide a reliable balance between the quality of solutions and computational efficiency. The proposed heuristic builds a complete solution incrementally, systematically inserting each unvisited node into an evolving tour by evaluating a limited number of potential insertion points based on their spatial proximity to already visited locations. This localized and selective evaluation strategy substantially reduces computational effort, typically allowing large problem instances to be solved in under 150 milliseconds, with achieved solution quality consistently within 2–14% of known optimal values. To clearly illustrate the effectiveness of this trade-off, we propose a Normalized Performance Index, integrating both solution accuracy and computational speed into a unified metric. The Localized Selective Insertion Heuristic demonstrated superior performance according to this index, achieving the best score in 16 out of 17 tested benchmark scenarios. The simplicity, deterministic nature, minimal parameter sensitivity, and ease of practical implementation make the proposed approach particularly suitable for applications requiring scalability, consistent performance, and straightforward reproducibility, such as logistics, transportation planning, and industrial automation.
Cite This Paper
Makhovoi Oleksandr, Vasyl Yurchyshyn, "Exploratory Heuristics for Scalable Combinatorial Optimization", International Journal of Intelligent Systems and Applications(IJISA), Vol.17, No.4, pp.58-68, 2025. DOI:10.5815/ijisa.2025.04.06
Reference
[1]E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. New York, NY, USA: Wiley, 1985.
[2]G. Gutin and A. P. Punnen, The Traveling Salesman Problem and Its Variations. Berlin, Germany: Springer, 2002.
[3]R. M. Karp, “Reducibility among combinational problems,” in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. New York, NY, USA: Plenum, 1972, pp. 85–103.
[4]D. S. Johnson and L. A. McGeoch, “The traveling salesman problem: A case study,” in Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra, Eds. Chichester, U.K.: Wiley, 1997, pp. 215–310.
[5]S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, May 1983.
[6]D. E. Goldberg and R. Lingle, “Alleles, loci, and the traveling salesman problem,” in Proc. 1st Int. Conf. Genetic Algorithms, Pittsburgh, PA, USA, Jul. 1985, pp. 154–159.
[7]D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, “An analysis of several heuristics for the traveling salesman problem,” SIAM J. Comput., vol. 6, no. 3, pp. 563–581, Sep. 1977.
[8]V. Pacheco-Valencia et al., “Simple constructive insertion heuristics,” Algorithms, vol. 13, no. 1, Art. no. 5, Jan. 2020.
[9]E. O. Asani, P. Marković, and M. V. Yamamoto, “A novel insertion solution for the travelling salesman problem,” Comput. Mater. Continua, vol. 79, no. 1, pp. 1579–1599, Jan. 2024.
[10]J. L. Bentley, “Fast algorithms for geometric traveling-salesman problems,” ORSA J. Comput., vol. 4, no. 4, pp. 387–411, Nov. 1992.
[11]N. Christofides, “Worst-case analysis of a new heuristic for the traveling salesman problem,” Tech. Rep. 388, Grad. Sch. Ind. Admin., Carnegie Mellon Univ., Pittsburgh, PA, USA, 1976.
[12]M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 53–66, Apr. 1997.
[13]Ş. Gülcü, A. Y. Okur, and O. Baykasolu, “A hybrid ant colony optimization and 3-Opt heuristic for solving the traveling salesman problem,” Soft Comput., vol. 22, no. 5, pp. 1669–1685, Mar. 2018.
[14]A. Zhou et al., “A traveling salesman problem algorithm based on simulated annealing,” Information, vol. 10, no. 1, Art. no. 7, Jan. 2019.
[15]S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Oper. Res., vol. 21, no. 2, pp. 498–516, Mar./Apr. 1973.
[16]K. Helsgaun, “An effective implementation of the Lin–Kernighan traveling salesman heuristic,” Eur. J. Oper. Res., vol. 126, no. 1, pp. 106–130, Oct. 2000.
[17]J. Zheng et al., “A hybrid genetic algorithm for the traveling salesman problem,” Comput. Oper. Res., vol. 149, Art. no. 106249, Jul. 2023.
[18]M. Malik, A. K. Singh, and G. K. Sharma, “A survey of metaheuristics for the traveling salesman problem,” IEEE Trans. Syst. Man Cybern. Syst., vol. 50, no. 2, pp. 891–902, Feb. 2020.
[19]L. Xin, W. Song, Z. Cao, and J. Zhang, “NeuroLKH: Combining deep learning models with the Lin–Kernighan–Helsgaun heuristic for solving the traveling salesman problem,” in Advances in Neural Information Processing Systems, vol. 34, pp. 7472–7483, Dec. 2021.
[20]J. Sui, B. Zhang, H. Ma, and L. Liu, “Learning 3-Opt heuristics for the traveling salesman problem via deep reinforcement learning,” in Proc. Asian Conf. Mach. Learn. (ACML), PMLR, vol. 157, pp. 1301–1316, Nov. 2021.
[21]J. M. Castro and P. M. Pardalos, “Adaptive candidate list strategies for the traveling salesman problem,” Ann. Oper. Res., vol. 89, pp. 229–249, Oct. 1999.
[22]G. Reinelt, “TSPLIB — a traveling salesman problem library,” ORSA J. Comput., vol. 3, no. 4, pp. 376–384, Nov. 1991.
[23]R. S. Barr, H. I. Karwan, and G. F. Schrader, “Reporting computational experiments in OR/MS,” J. Heuristics, vol. 1, no. 1, pp. 9–32, Jun. 1995.
[24]Y. A. Malkov and D. A. Yashunin, “Efficient and robust approximate nearest-neighbor search using hierarchical navigable small-world graphs,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 42, no. 4, pp. 824–836, Apr. 2020.