Efficient convex-elastic net algorithm to solve the Euclidean traveling salesman problem

Area of Science:

• Computational Intelligence
• Operations Research
• Computer Science

Background:

• The Traveling Salesman Problem (TSP) is a classic optimization challenge.
• The Euclidean TSP (E-TSP) variant involves finding the shortest route connecting points in a plane.

Purpose of the Study:

• To introduce a novel hybrid algorithm for solving the E-TSP.
• To demonstrate the algorithm's effectiveness in finding near-optimal solutions.

Main Methods:

• A hybrid algorithm combining an adaptive neural network (convex-elastic net - CEN) and a nondeterministic iterative improvement (NII) algorithm was developed.
• The CEN algorithm generates an initial tour using convex-hull properties and elastic nets.
• The NII algorithm refines the tour using rearrangement operators.

Main Results:

• The proposed Efficient Convex-Elastic Net (ECEN) algorithm was tested on randomly generated and benchmark E-TSP instances.
• Simulation results indicate the ECEN algorithm finds near-optimal solutions.
• The algorithm demonstrates superior performance compared to many existing methods.

Conclusions:

• The ECEN algorithm offers an effective approach to solving the E-TSP.
• The hybrid method shows significant advantages in solution quality and efficiency.
• Potential extensions for future research were discussed.