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:
Alipour M M, Heydari A, 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
University of Bonab
Abstract: (13 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.
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
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |