A graph theory approach to the synthesis and optimization of a modified transportation network
MetadataShow full item record
A transportation network is typically a network of roads, pipes, or any other structure which allows a flow of some commodity such as vehicular traffic. In this research, we have proposed a novel optimization technique based on graph transformations which enables both the synthesis as well as the optimization of such modified transportation networks. The most important contribution of this work is in the form a brand new method which enables topology optimization. Previous efforts in the field have been limited to using parametric or numerical optimization. For illustrative purposes we have rephrased the transportation network problem with certain simple assumptions and renamed it as the Resistor problem. The new method has been demarcated into four separate modules named representation, generation, evaluation and guidance. The modules correspond to problem formulation (representation), topology synthesis (generation), determining the worth of each topology (evaluation), and navigating the search space towards progressively better solutions (guidance). The optimization end of the problem has been treated as large tree search. Although algorithms such as depth-first search, breadth-first search, and A* exist as tree searching techniques, these can be extremely slow and require high computational resources for network problems of the magnitude we are trying to solve. Hence we have developed our own optimization routine which has been inspired from the more commonplace Genetic Algorithm but harnesses the fact that the search space is a tree of candidate topologies of various stages of development. A stochastic element has been introduced to aid the decision making of this optimization method. The abstraction afforded by the usage of mathematical graphs as part of this new method ensures that this could be used to solve topology problems in several domains such as traditional mechanical engineering, computer science or even artificial intelligence. This work has been an attempt to combine the teachings of classical graph theory and artificial intelligence in coming up with an approach to solving topology optimization problems such as the transportation network problem.