An Efficient, Scalable, and Robust Neuro-Processor-Based Concept for Solving Single-Cycle Traveling Salesman Problems in Complex and Dynamically Reconfigurable Graph Networks

Abstract

We develop, for the first time, and validate through some illustrative examples a new neuro-processor based concept for solving (single-vehicle) traveling salesman problems (TSP) in complex and dynamically reconfigurable graph networks. Compared to existing/competing methods for solving TSP, the new concept is accurate, robust, and scalable. Also, the new concept guarantees the optimality of the TSP solution and ensures subtours avoidance and thus an always-convergence to a single-cycle TSP solution. These key characteristics of the new concept are not always satisfactorily addressed by the existing methods for solving TSP. Therefore, the main contribution of this paper is to develop a systematic analytical framework to model (from a nonlinear dynamical perspective) the TSP, avoid/eliminate subtours, and guarantee/ensure convergence to the true/exact TSP solution. Using the stability analysis (nonlinear dynamics), analytical conditions are obtained to guarantee both robustness and convergence of the neuro-processor. Besides, a bifurcation analysis is carried out to obtain ranges (or windows) of parameters under which the neuro-processor guarantees both TSP solution's optimality and convergence to a single-cycle TSP solution. In order to validate the new neuro-processor based concept developed, two recently published application examples are considered for both benchmarking and validation as they are solved by using the developed neuro-processor.

Keywords

• Basic differential multiplier method
• bifurcation analysis
• constrained optimization
• convergence to a single-cycle TSP tour/solution
• dynamically externally reconfigurable TSP
• local stability