XROUTE: A knowledge-based routing system using neural networks and genetic algorithms

This dissertation is concerned with applying alternative methods of artificial intelligence (AI) in conjunction with mathematical methods to Vehicle Routing Problems. The combination of good mathematical models, knowledge-based systems, artificial neural networks, and adaptive genetic algorithms (GA)--which are shown to be synergistic--produces near-optimal results, which none of the individual methods can produce on its own.;A significant problem associated with application of the Back Propagation learning paradigm for pattern classification with neural networks is the lack of high accuracy in generalization when the domain is large. In this work, a multiple neural network system is employed, using two self-organizing neural networks that work as feature extractors, producing information that is used to train a generalization neural network. The technique was successfully applied to the selection of control rules for a Traveling Salesman Problem heuristic, thus making it adaptive to the input problem instance.;The GA--a generally computation intensive approach--conducts an adaptive search to refine control parameters of the model. Three mechanisms for improving the performance of the genetic search were developed: first, a method of using multiple evaluation functions is employed, permitting the parallel investigation of multiple peaks in the search space; second, a parallel function evaluation is conducted, using a network of heterogeneous processors in which a variety of constrained network topologies are identified with attributes particularly suited to parallelizing GA; and third, a neural network system is employed to inject heuristic knowledge into the initial population of the GA, resulting in relatively fast convergence. The neural network modules store previously solved problems and their solutions, facilitating the solving of new problems. The knowledge-based system stores partial solutions from various knowledge sources, like the neural network and GA modules, in the working memory, and closely supervises the solution process in heuristic mathematical models.;XROUTE provides an interactive visualization system, using state-of-the-art vehicle routing models and AI tools, yet allows an interactive environment for human expertise to be utilized in powerful ways. XROUTE provides an experimental, exploratory framework that allows many variations, and alternatives to problems with different characteristics. XROUTE is dynamic, expandable, and adaptive, and typically outperforms alternative methods in computer-aided vehicle routing.