A novel constructive-optimizer neural network for the traveling salesman problem.

Area of Science:

• Artificial Intelligence
• Computational Science
• Operations Research

Background:

• The Traveling Salesman Problem (TSP) is a complex combinatorial optimization challenge.
• Existing neural network (NN) approaches for TSP often face limitations in balancing solution accuracy and computational efficiency.
• There is a need for novel NN architectures that can effectively address the TSP with improved performance.

Purpose of the Study:

• To introduce a novel constructive-optimizer neural network (CONN) designed for solving the Traveling Salesman Problem (TSP).
• To evaluate the performance and efficiency of CONN compared to existing NN and algorithmic approaches for TSP.
• To investigate the relationship between the number of TSP cities and the constructive phase parameters in CONN.

Main Methods:

• CONN integrates a feedback structure similar to Hopfield networks and a competitive training algorithm akin to Kohonen self-organizing maps.
• The training involves alternating constructive phases (adding cities) and optimizer phases (displacing cities) until all cities are included.
• CONN's performance was benchmarked on TSPLIB datasets, comparing its CPU time and accuracy against various NNs and simulated annealing algorithms.

Main Results:

• CONN demonstrated superior performance over several typical NNs and comparable computational variants of simulated annealing in terms of CPU time and accuracy.
• CONN achieved faster convergence than expanding SOM and evolved integrated SOM, and generated shorter tours than KNIES_DECOMPOSE.
• While not matching the accuracy of the most computationally intensive algorithms, CONN offers a significantly faster convergence rate.

Conclusions:

• CONN presents a novel and effective neural network approach for the Traveling Salesman Problem.
• The proposed constructive-optimizer architecture provides a strong balance between computational speed and solution accuracy.
• CONN represents a promising advancement in NN-based TSP solvers, offering a practical compromise for efficient route optimization.