Article Preview
TopIntroduction
Research in meta-heuristics is well known in the artificial intelligence field and has also been very active during the last decades. When facing complex new optimization problems, it is very natural to use meta-heuristics techniques (Christian et al., 2008). With the massive growth of the Information, big data optimization has become one of the main researches. Furthermore, complex networks such as the transportation, communication, Internet and distribution networks, etc., have increasingly attracted the attention from various fields of science and engineering. Combining the meta-heuristic with other optimization techniques so called hybrid meta-heuristic can provide an advanced flexibility and more efficient behavior when dealing with large-scale and real-world problems (Christian et al., 2008). Various applications such as transport applications require the using of a meta-heuristic shortest path rather than one of the standard algorithms. The heuristic algorithm that finds the shortest path is optimal and significant and must quickly find the best paths. Therefore, we have thought about using hybrid meta-heuristics to solve the routing issue in road networks in our work.
The graph is an important complex network to describe the relationship among a set of interconnected nodes (entities). The shortest path computation is a frequent operation. In these situations, it is often valuable to be able to find the k optimal shortest paths. In the last decade, the problem of finding the shortest paths is a challenging task over large graphs; it is also investicated as one of the most widely-studied combinatorial optimization problems. Many of already existing graph algorithms are not appropriate for graphs of larger sizes.
In our work, we study traffic network in large scale routing problems as a field of application. Finding a suitable route to reaching the destination in time with saving energy has significance in real-world applications. The vertices (nodes) of the graph correspond to spatial units (cities) of the road network. Edges connect vertices, and they are weighted with non-negative weights according to the distance between vertices. Operations on a graph can take a long time due to the complexity of structural connectivity and the graph's size. Also, a large graph makes efficiency even more difficult (Hosseinabadi et al., 2018). Hence, in this paper, we aim to find the shortest route starting from the source to the destination where the distances between each city are known.
Because the K- shortest path is NP-hard, we combine exact and heuristic approaches. The optimal shortest path algorithms such as Dijkstra tend to be extremely computationally intensive for real-time applications in practical traffic networks. For this reason, we develop a new algorithm combining the exact algorithm (namely Dijkstra’s algorithm) with a meta-heuristic algorithm (namely Genetic Algorithm - GA) into a shortest path search process. In this study, the new hybrid algorithm, namely IOGA (Improved Optimization Genetic Algorithm), is developed to find one or k optimal paths containing the minimal cost between two vertices in an oriented and non-oriented graph. So, hybridizing a genetic algorithm with Dijkstra’s algorithm is an interesting idea because the classic strategy using Dijkstra’s algorithm minimizes the search space whereas the heuristic strategy optimizes the search problem to return the better solutions.
The experimental study makes a comparison of our approximate hybrid method (i.e., IOGA) with three algorithms (Dijkstra’s algorithm, Genetic algorithm and A* algorithm) in order to ensure the following specific contributions: i) find one or several shortest paths; and ii) minimize the execution time by comparing with the three algorithms previously mentioned. The effectiveness of our approach that employ the heuristic algorithm is confirmed. The final results illustrate that the proposed approach with the new optimization strategy allowed us to obtain good results with high performance.