Combining neural networks and Tabu search in a fast neural network simulation for combinatorial optimization

Since Hopfield and Tank proposed their neural model for the TSP, many researchers have tried to improve their model. While some of these researchers used operations research techniques to improve the solution quality of the model, these improvements still have been plagued by slow computer simulation. This dissertation presents an extension of Vaithyanathan's Tabu Neural Network (TANN) called the Improved Tabu Neural Network (ITANN). ITANN not only improves solution quality when compared to TANN and other HT-based neural models such as mean field annealing and the Boltzmann machine, but also improves simulation speed. The effectiveness of ITANN is illustrated by solving traveling salesman problems of up to 442 cities. The solution quality for ITANN is within a few percent of optimal for all traveling salesman problems tested. These results improve over the best-known HT-based neural network solutions including mean field annealing. In addition, longer term memory tabu search based on clustering all solutions is added to ITANN's structure. This longer term memory is designed to cluster all solutions to allow new areas of the search space with promising solution attributes to be searched. Finally, ITANN is extended to the multiple traveling salesman problem (MTSP) and simple plant location problem (SPLP) to illustrate the fast simulation method of ITANN on these problems.