Complex Systems

Solving a Dynamic Traveling Salesman Problem with an Adaptive Hopfield Network Download PDF

Yoshikane Takahashi
NTT Information and Communication Systems Laboratories Yokosuka,
Kanagawa, 239-0847, Japan

Abstract

This paper mathematically solves a dynamic traveling salesman problem (DTSP) with an adaptive Hopfield network (AHN). The DTSP is an extension of the conventional TSP where intercity distances are variable parameters that depend on time; while the AHN, in contrast with current deterministic networks, has the capability to adapt itself to changes in the outside environment. The result is stated as a theorem that the AHN always produces as its final states locally-minimum approximate, feasible solutions to the DTSP. It is also expected that the theorem can provide a solid theoretical basis for developing engineering devices of the AHN to solve the DTSP.