A New Approach to Solve the Shortest Route in Urban Networks Based on Evolutionary Algorithms

Today, urban management is one of the most important issues for decision makers and managers in urban areas. The problem of finding the shortest route, as one of the important issues in the field of urban management in order to reduce the travel time between two critical points, has always been the focus of many research fields such as urban management, transportation, communication, etc. During the past decades, the genetic algorithm has worked well in solving complex multi-objective optimization problems, but many genetic algorithms are only suitable for finding the optimal route in local networks. In these networks, if the number of points increases, algorithms will not be effective. The purpose of this research is to find a route in the street network of Tehran that has the least time, distance and cost. Therefore, a new method is proposed to solve the routing problem based on genetic algorithm, with the assumption that all lines in the network have positive weights.

The charactristics of the proposed algorithm is the variability of genetic algorithm operators, which is defined according to the network structure. Accordingly, the mutation operator in the genetic algorithm is defined based on the studied space and the distance between the start and end points. Integer coding is used to solve the problem, and therefore the points in this graph are named using integers and each person in the population is considered as an answer to solve the problem. The population size depends on the number of nodes in the graph and the length of each chromosome. The length of the selected strings is considered equal to the maximum number of nodes in the network, because there is a possibility that the best route is the route that passes through all the nodes. At the end, the proposed algorithm is implemented on the study area, which is a planar graph. The accuracy of the proposed method compared to the conventional genetic algorithm has been evaluated in three pairs of points.

Considering that the goal of solving the problem was to find the route that has the least weight, one combination operator and three mutation operators were presented in the proposed algorithm. This is despite the fact that in traditional genetic algorithms, only one mutation and combination operator is used. In this algorithm, the way to use mutation operators depends on the structure of the network and the distance between the start and end points. The use of the proposed genetic algorithm compared to the traditional genetic algorithm has been associated with a 16% improvement in performance, which shows that the proposed genetic algorithm reaches the solution of the problem faster. As shown in Figure 4, the best route is the route whose fitness function value is closer to one. The results of comparing the proposed method with conventional methods show 16% higher speed.

Considering that the initial assumption of this research was the positive weight of all the lines in the network, the mutation operator in the genetic algorithm was defined based on the studied space and the distance between the start and end points. The results showed that if there is a small search space, fewer points are needed and in order to generate the initial population, the nodes that are next to each other and closer to each other should be selected. In this way, the value of the fitness function of the people in the initial population increases and the answers become closer to reality. For future research, it is suggested that in order to generate the initial population, the points between the start and end points should be selected, and also the selected points should be near the connecting line between the start and end points, because when the weight of the edges of the network is the distance between the points, the best route is in the space between the starting point and the end point. It is also suggested to evaluate the performance of the network with several combination operators.