Signal and Data Processing Journal A scientific journal officially licensed by the Commission for Scientific Publications of the (MSRT). Publisher: Research Ceter for Developmen of Technologies
Volume 23, Issue 1 (6-2026)
JSDP 2026, 23(1): 19-36 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Heydari A, Alipour M M, Abdolhosseinzadeh M, Emami H. A novel Near Distance Order Crossover to improve the performance of genetic algorithms for solving the TSP. JSDP 2026; 23 (1) : 2
URL: http://jsdp.rcisp.ac.ir/article-1-1476-en.html
URL: http://jsdp.rcisp.ac.ir/article-1-1476-en.html
Assistant professor, Department of Computer Engineering, Faculty of Engineering, University of Bonab, Bonab, Iran
Abstract: (562 Views)
The traveling salesman problem is one of the well-known and oldest combinatorial optimization problems in computer science, operations research, and artificial intelligence. It is widely used as a standard benchmark for measuring the performance of optimization algorithms and has special importance in the literature due to its conceptual and computational challenges. In the general definition of this problem, a salesman must travel through a set of cities such that each city is visited only once, and finally return to his starting point, while minimizing the total distance traveled or cost. According to its NP-Hard nature, this problem quickly becomes more complex as the number of cities increases, and finding its optimal solution with exact methods on large scales is practically impossible or very time-consuming.
The practical applications of this problem go far beyond its title and are used in fields such as transportation planning, vehicle routing optimization, distribution network design, routing in computer networks, industrial operation scheduling, robotics, and even genomics. Due to the limitations of exact methods such as dynamic programming, branch and bound, and linear methods, researchers have turned to using meta-heuristic methods such as genetic algorithms, differential evolution algorithms, particle swarm algorithms, simulated annealing and ant algorithms. And among them, genetic algorithms have become very popular due to their conceptual simplicity, high adaptability, and ability to search the solution space extensively.
Inspired by the principles of Darwinian natural selection, these algorithms evolve a population of solutions over time using operators such as selection, crossover, and mutation to reach optimal or near-optimal responses. One of the essential components in the efficiency of genetic algorithms is the implementation and selection of operators, especially the crossover operator, which is responsible for combining the characteristics of two parents, playing a vital role in producing high-quality offspring. In this study, a new crossover operator called Near Distance Order Crossover (NDOX) was introduced and investigated. Based on this crossover operator, a genetic algorithm called GNDOX is proposed, which applies NDOX to generate high-quality tours efficiently. It is designed based on the order crossover.
The difference is that it optimizes the selection process of the remaining genes by considering distance information between cities. In classical crossovers, the remaining genes are usually introduced into the offspring randomly or in apparent order, but in NDOX, an attempt has been made to perform the chromosome completion process in a more intelligent manner by utilizing the knowledge of the problem, i.e., the distance between nodes. This results in routes that are likely to be more geometrically optimal, with cities closer together. The proposed algorithm works by first transferring a section of the first parent's chromosome directly to the child, then using the distance between the last transferred gene and the remaining genes to complete the remainder of the path, instead of randomly inserting genes from the second parent and thus, each stage of chromosome completion is based on step-by-step distance minimization, ultimately leading to more coherent structures and shorter paths.
To evaluate the performance of the proposed operator, a series of experiments have been conducted on several standard TSP datasets, and the results of these experiments show that GNDOX was able to provide competitive performance among common meta-heuristic algorithms, achieving better or comparable results in terms of average tour length, standard deviation, and convergence speed compared to other common algorithms such as PSO, ACO and SA. In many datasets, the proposed algorithm has been able to quickly reach high-quality solutions. In conclusion, it can be said that the design and implementation of the NDOX not only improved the performance of the genetic algorithm in solving the TSP, but showed that combining meta-heuristic methods with structural information of the problem can lead to more efficient and reliable algorithms and this finding can provide a platform for future research to use this approach in other complex problems, and achieve more effective optimization. Also, the proposed operator can be used as a model for developing other genetic operators in similar problems.
The practical applications of this problem go far beyond its title and are used in fields such as transportation planning, vehicle routing optimization, distribution network design, routing in computer networks, industrial operation scheduling, robotics, and even genomics. Due to the limitations of exact methods such as dynamic programming, branch and bound, and linear methods, researchers have turned to using meta-heuristic methods such as genetic algorithms, differential evolution algorithms, particle swarm algorithms, simulated annealing and ant algorithms. And among them, genetic algorithms have become very popular due to their conceptual simplicity, high adaptability, and ability to search the solution space extensively.
Inspired by the principles of Darwinian natural selection, these algorithms evolve a population of solutions over time using operators such as selection, crossover, and mutation to reach optimal or near-optimal responses. One of the essential components in the efficiency of genetic algorithms is the implementation and selection of operators, especially the crossover operator, which is responsible for combining the characteristics of two parents, playing a vital role in producing high-quality offspring. In this study, a new crossover operator called Near Distance Order Crossover (NDOX) was introduced and investigated. Based on this crossover operator, a genetic algorithm called GNDOX is proposed, which applies NDOX to generate high-quality tours efficiently. It is designed based on the order crossover.
The difference is that it optimizes the selection process of the remaining genes by considering distance information between cities. In classical crossovers, the remaining genes are usually introduced into the offspring randomly or in apparent order, but in NDOX, an attempt has been made to perform the chromosome completion process in a more intelligent manner by utilizing the knowledge of the problem, i.e., the distance between nodes. This results in routes that are likely to be more geometrically optimal, with cities closer together. The proposed algorithm works by first transferring a section of the first parent's chromosome directly to the child, then using the distance between the last transferred gene and the remaining genes to complete the remainder of the path, instead of randomly inserting genes from the second parent and thus, each stage of chromosome completion is based on step-by-step distance minimization, ultimately leading to more coherent structures and shorter paths.
To evaluate the performance of the proposed operator, a series of experiments have been conducted on several standard TSP datasets, and the results of these experiments show that GNDOX was able to provide competitive performance among common meta-heuristic algorithms, achieving better or comparable results in terms of average tour length, standard deviation, and convergence speed compared to other common algorithms such as PSO, ACO and SA. In many datasets, the proposed algorithm has been able to quickly reach high-quality solutions. In conclusion, it can be said that the design and implementation of the NDOX not only improved the performance of the genetic algorithm in solving the TSP, but showed that combining meta-heuristic methods with structural information of the problem can lead to more efficient and reliable algorithms and this finding can provide a platform for future research to use this approach in other complex problems, and achieve more effective optimization. Also, the proposed operator can be used as a model for developing other genetic operators in similar problems.
Article number: 2
Keywords: Traveling salesman problem Genetic algorithm, Order crossover operator, Distance order crossover
Type of Study: Research |
Subject:
Paper
Received: 2025/06/30 | Accepted: 2026/02/3 | Published: 2026/06/21 | ePublished: 2026/06/21
Received: 2025/06/30 | Accepted: 2026/02/3 | Published: 2026/06/21 | ePublished: 2026/06/21
References
1. P. Larrañaga, Kuijpers, C. M., & Poza, J, "Genetic algorithms for the travelling salesman problem: A review of representations and operators," Artificial Intelligence Review, vol. 13, pp. 97-128, 1999. [DOI:10.1023/A:1006529012972]
2. G. B. Dantzig, Fulkerson, R., & Johnson, S, "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, 1954. [DOI:10.1287/opre.2.4.393]
3. M. Gen, & Cheng, R, Genetic Algorithms and Engineering Design. New York, United States: Wiley, 1997. [DOI:10.1002/9780470172254]
4. M. M. Alipour, S. N. Razavi, M. R. F. Derakhshi, and M. A. Balafar, "A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem," Neural Computing and Applications, pp. 1-17, 2018.
5. M. Dorigo, & Stützle, T, Ant Colony Optimization. Cambridge: MIT Press, 2004. [DOI:10.7551/mitpress/1290.001.0001]
6. F. Gutierrez, et al, "A Comparative Study on Metaheuristic Algorithms for Solving NP-Hard Problems," Computational Optimization and Applications, 2020.
7. علیپور میر محمد، عبدالحسین زاده محسن، «ارائۀ الگوریتمی جدید برای تشخیص اجتماع با استفاده از یادگیری تقویتی چندعاملی»، پردازش علائم و دادهها، ۱۹ (۱)، 100-87، ۱۴۰۱.
7. M. M. Alipour and M. Abdolhosseinzadeh, "A Multiagent Reinforcement Learning algorithm to solve the Community Detection Problem," (in eng), Signal and Data Processing, Research vol. 19, no. 1, pp. 87-100, 2022. [Online]. Available: http://jsdp.rcisp.ac.ir /article-1-1084-en.html [DOI:10.52547/jsdp.19.1.87]
8. D. E. Goldberg, & Lingle, R, "Alleles, loci, and the traveling salesman problem," in Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburgh, 1985, pp. 154-159.
9. I. Oliver, Smith, D. R., & Holland, J. H, "A study of permutation crossover operators on the travelling salesman problem," in Proceedings of the 2nd International Conference on Genetic Algorithms, Pittsburgh, 1987, pp. 224-230.
10. J. K. L. E.L. Lawler, A.H.G. Rinnooy Kan, D.B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, 1985.
11. T. Bektas, "The multiple traveling salesman problem: An overview of formulations and solution procedures," Omega, vol. 34, no. 3, pp. 209-219, 2006. [DOI:10.1016/j.omega.2004.10.004]
12. M. F. Demiral, "An artificial intelligence technique: experimental analysis of population-based physarum-energy optimiz ation algorithm," Discover Artificial Intelligence, vol. 5, no. 1, p. 115, 2025/06 /19 2025, doi: 10.1007/s44163-025-00367-w. [DOI:10.1007/s44163-025-00367-w]
13. Y. Wang, "The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem," Computers & Industrial Engineering, vol. 70, pp. 124-133, 2014/04/01/ 2014, doi:
https://doi.org/10.1016/j.cie.2014.01.015 [DOI:10.1016/j.cie.2014.01.015.]
14. K.-P. Wang, L. Huang, C.-G. Zhou, and W. Pang, Particle swarm optimization for traveling salesman problem. 2003, pp. 1583-1585 Vol.3.
15. M. A. H. Akhand, S. Hossain, and S. Akter, "A Comparative Study of Prominent Particle Swarm Optimization Based Methods to Solve Traveling Salesman Problem," International Journal of Swarm Intelligence and Evolutionary Computation, vol. 5, 10/28 2016, doi: 10.4172/2090-4908.1000139. [DOI:10.4172/2090-4908.1000139]
16. M. Dorigo and L. M. Gambardella, "Ant colonies for the travelling salesman problem," Biosystems, vol. 43, no. 2, pp. 73-81, 1997/07/01/ 1997, doi: https://doi.org/ 10.1016/S0303-2647(97)01708- .
https://doi.org/10.1016/S0303-2647(97)01708-5 [DOI:10.1016/S0303-2647(97)01708- .]
17. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, no. 4598, pp. 671-680, 1983/05/13 1983, doi: 10.1126/science.220.4598.671. [DOI:10.1126/science.220.4598.671]
18. P. Victer Paul, C. Ganeshkumar, P. Dhavachelvan, and R. Baskaran, "A novel ODV crossover operator-based genetic algorithms for traveling salesman problem," Soft Computing, vol. 24, no. 17, pp. 12855-12885, 2020/09/01 2020, doi: 10.1007/s00500-020-04712-2. [DOI:10.1007/s00500-020-04712-2]
19. J. de Vasconcelos, J. Ramirez, R. Takahashi, and R. Saldanha, "Improvements in Genetic Algorithms," Magnetics, IEEE Transactions on, vol. 37, pp. 3414-3417, 10/01 2001, doi: 10.1109/20.952626. [DOI:10.1109/20.952626]
20. J. Zhang, "An Improved Genetic Algorithm with 2-Opt Local Search for the Traveling Salesman Problem," in Application of Intelligent Systems in Multi-modal Information Analytics, Cham, V. Sugumaran, Z. Xu, and H. Zhou, Eds., 2021// 2021: Springer International Publishing, pp. 404-409. [DOI:10.1007/978-3-030-74814-2_57]
21. Y. Dong, Q. Wu, and J. Wen, "An improved shuffled frog-leaping algorithm for the minmax multiple traveling salesman problem," Neural Computing and Applications, vol. 33, pp. 1-13, 12/01 2021, doi: 10.1007/s00521-021-06298-8. [DOI:10.1007/s00521-021-06298-8]
22. Y. Fang and J. li, A Review of Tournament Selection in Genetic Programming. 2010, pp. 181-192. [DOI:10.1007/978-3-642-16493-4_19]
23. G. Reinelt, "TSPLIB - A traveling salesman problem library.," ORSA Journal on Computing, vol. 4, no. 376-384, p. 3, 1991. [DOI:10.1287/ijoc.3.4.376]
24. Ş. Dalkılıç, A. Özgür, and H. Erdem, "Comparison of Genetic Crossover Operators for Traveling Salesman Problem," Gazi University Journal of Science, vol. 38, pp. 1-1, 03/09 2025, doi: 10.35378/ gujs.1582521.
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |