Integrating Neural networks and GIS for solving the travelling salesman problem

Abstract

In this thesis, we investigate the use of neural networks for solving the Traveling Salesman Problem (TSP). First, we review the main elements of the theory of NP-completeness. Then, we explain what makes some problems computationally intractable. We review some heuristic approaches used to provide near-optimal solutions to NP-complete problems. Then, we introduce the topic of neural networks and describe some of the most popular neural network models. We pay a special attention to a recent model, named the Hybrid Neural Network model (HNN), used for solving optimization problems and the Hybrid Network Updating Algorithm (HNUA). We propose a modification version of the HNUA that modify the H|NUA to produce an optimal to near-optimal solutions and demonstrate its efficiency using a specific NP-complete problem known as the Traveling Salesman Problem (TPS) as an example. Our simulation shows how the modification version derives an efficient result. Also, a comparison is made between the results derived from the proposed modification model and the Depth First Search (DFS) model both for TSP to analyze and reduce the degree of optimization and validation for the proposed modification. Besides, we build a TSP interface application using Geographic Information System (GIS) MapObject (MO) on Microsoft Visual Basic environment to create mapping application and adding mapping functionality for a better visualization of the problem where the user can easily view the cities and observe the resultant tour geographically.