A Collaborative Neurodynamic Optimization Algorithm Based on Boltzmann Machines and 2-Opt Heuristic for Solving the Traveling Salesman Problem
Hongzong Li, Jun Wang · 2025
The traveling salesman problem is a well-known challenge in combinatorial optimization. It involves determining the shortest possible route that visits each city exactly once from a given list, returning to the starting point with the least total distance traveled. It has extensive applications in logistics, planning, and routing. It is a well-known NP-hard optimization problem. In this paper, the traveling salesman problem is formulated as a quadratic assignment problem with constraints to eliminate excessively long paths for enhancing efficiency. We introduce a collaborative neurodynamic optimization algorithm for solving traveling salesman problems with Boltzmann machines with momentum term and the 2-opt heuristic. The proposed algorithm consists of a phase with BMm's and another phase with 2-opt heuristics. It leverages multiple BMm's and 2-opt heuristics, and a particle swarm optimization update rule to re-initialize BMm's for escaping from local optima and moving toward global optimal solutions. We demonstrate its superior performance against two baselines in terms of the objective function values.