A POTTS NEURON APPROACH TO COMMUNICATION ROUTING

A feedback neural network approach to communication routing problems i s developed, with emphasis on multiple shortest path problems, with se veral requests for transmissions between distinct start and end nodes. The basic ingredients are a set of Potts neurons for each request, wi th interactions designed to minimize path lengths and prevent overload ing of network arcs. The topological nature of the problem is convenie ntly handled using a propagator matrix approach. Although the constrai nts are global, the algorithmic steps are based entirely on local info rmation, facilitating distributed implementations. In the polynomially solvable single-request case, the approach reduces to a fuzzy version of the Bellman-Ford algorithm. The method is evaluated for synthetic problems of varying sizes and load levels, by comparing to exact solut ions from a branch- and- bound method, or to approximate solutions fro m a simple heuristic. With very few exceptions, the Potts approach giv es high-quality legal solutions. The computational demand scales merel y as the product of the numbers of requests, nodes, and arcs.