# Study On The Shortest Path Algorithm Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Many real world problems are mainly based on the concept of the shortest path (SP) oriented network problems. The shortest path problem (SPP) has been analyzed by many researchers in recent years. It is a well-known problem and can be used to solve many real world problems such as vehicle routing in transportation, routing in communication networks and web page searching for Internet information retrieval systems. The growing pressure for cost reduction, the need for efficient techniques for border surveillance of countries and the continuous advancements in computing technology have motivated for studying and applying network optimization. This research work addresses two SP network problems that arise in the application domains of transportation and telecommunications. Nature inspired AI-heuristic search procedures and soft computing techniques are proposed to solve these problems.

## 1.2 PROBLEM DESCRIPTION

Lot of real world problems can be described by means of diagrammatic representation consisting of a set of points together with a set of lines connecting certain pairs of these points. A mathematical representation of problems of such type gives rise to the development of the basic concept of graph. The study of mathematical graphs used to model the relationships between a network of vertices and edges is called graph theory. If a path visits every vertex exactly once and ends at the starting point, it becomes known as a Hamiltonian cycle Bondy and Murty (1982).

Shortest Path Algorithm: The problem of determining the SP from one vertex to another is called as single source shortest path. For example, if the edges are given weights, then a SP is simply the path connecting two vertices where the sum of weights for the edges between the two vertices used is smallest. In the more typical communication problem, an edge between two nodes is used to represent the presence of a communications channel between the two end points. The end points may be routers or mobile communication devices. The simple example for dynamic multi-hop routing networks is wireless sensor networks (WSN).

Definition 1: The shortest path between two vertices 's' and 'd' in a network is a simple path from 's' to 'd' with the property that no other such path has a lower weight.

Multiple Traveling Salesman Problem (mTSP): The mathematical structure of the Traveling Salesman Problem (TSP) is a graph where the cities are the vertices of the graph, the links between pairs of cities are called edges and each edge has a weight associated with it. In solving the TSP one tries to construct the route so that the total distance travelled is minimized. In graphical terms, the aim is to determine a minimum weight Hamiltonian cycle in a weighted complete graph. Given a set of cities, let there are m salesmen located at a single depot node. Then, the mTSP consists of finding tours for all m salesmen, who all start and end at the depot, such that each city is visited exactly once and the total cost of visiting all nodes is minimized.

The SP algorithm and Hamiltonian cycle algorithm have a lot of applications in various real world situations. The following are the two important problems based on the afore-mentioned graph algorithms. Therefore this thesis focuses on finding efficient solutions for these problems:

Multiple traveling salesman problem and

Shortest path routing in multi-hop wireless sensor networks.

## 1.3 LIMITATIONS OF EXISTING ALGORITHMS

Researchers on the mTSP and SPP have proved that the mTSP and SPP are NP-hard Combinatorial Optimization (CO) problems. The time required to obtain solutions with the existing algorithms grows polynomially with the number of nodes in the network, making these algorithms somewhat inefficient for larger problems. For example, if n is the number of cities to be visited for an asymmetrical TSP then (n-1)! will be the total number of possible routes. Thus the computational time needed renders this method impractical for all but a smaller number of cities. The challenge of CO is to develop algorithms that consume a reasonable amount of computer time. Therefore, to solve these problems various approximation algorithms are used.

## 1.4 SCOPE AND OBJECTIVES OF RESEARCH

There is a scope for the application of hybrid multi-stage heuristics that use a combination of intuitive and classical methods to construct good initial solutions which, in turn, serve as inputs for an intensive search using AI-heuristics.

Most of the real life problems utilise more than one salesperson. Therefore this research assumes the TSP as a mTSP. By using clustering concept the mTSP is converted into a simple TSP and then soft computing and metaheuristics concepts have been applied in multiple phases to solve the problem. Also, there is a scope for heuristics based route balancing.

Due to energy constraint of WSNs, solar energy is a suitable and efficient alternate energy source. Time is the main constraint in WSNs for energy efficient routing. So far a simple straight-forward shortest path routing and soft computing concepts have been rarely used in WSNs. A three-phase hybrid algorithm to find the shortest path routing is proposed in solar powered WSNs.

This research is focused on highlighting the improved nature inspired intelligent techniques to find shortest path routing for WSNs and multiple Travelling Salesman Problems (mTSPs) which demonstrate advantages and improvements in some aspects over the existing methods.

## 2.1 NATURE INSPIRED ALGORITHMS

Many computational techniques simulate ideas of nature in one way or another (Goldberg 2006). Heuristic solution procedures are approximate techniques based on algorithms that generate feasible solutions within reasonable computing time. An AI-heuristic is a set of concepts that can be used to guide the other heuristics to find their way out of local optima by continuing the search for better areas of the solution space. Soft computing is a framework in which it is possible to encode domain knowledge to develop such AI-heuristics. The following are some of the important well known soft computing and AI-heuristics algorithms:

Ant Colony Optimization (ACO)

Genetic Algorithm (GA)

Simulated Annealing (SA)

Tabu Search (TS) and

Neural networks (NN)

## 2.2 MULTIPLE TRAVELING SALESMAN PROBLEM

mTSP handles more than one salesman. Thus, this problem is analogous to many real life situations.

Junjie and Dingwei (2006) have worked on the mTSP which is a computationally complex CO problem which is an extension of TSP. They have made an attempt to show how ACO can be applied to mTSP with the ability constraints. The results show that the proposed algorithm is better than the existing standard methods for mTSP. However, the ACO methods used in their research are not as efficient in finding solutions for larger problems.

Lau et al (2010) proposed the optimization of Vehicle Routing Problem (VRP) in which multiple depots are considered. They proposed to use a technique called Fuzzy Logic guided Genetic Algorithms (FLGA) to solve the VRP. To demonstrate the performance of the proposed algorithm, a number of benchmark problems are used to check the performance. The simulation results show that FLGA performs better than other algorithms. But due to fuzzy concepts the convergence time of their algorithm is more compared to other algorithms.

## 2.3 ROUTING IN SOLAR POWERED WSNs

Voigt et al (2003) proposed an algorithm that permits the routing only through solar powered sensor nodes. Due to this, the energy of the battery powered nodes will be saved. Among the sensor nodes, they assumed that some of them are solar powered and the rest of them are conventional battery powered. They demonstrated two protocols to perform solar aware routing in WSNs.

Al-Karaki et al (2009) proposed heuristic algorithms for routing in WSNs. They presented an algorithm called Grid-based Routing and Aggregator Selection Scheme (GRASS) based on exact as well as heuristic concepts to determine the minimum number of aggregation points while sending the sensed data to the sink such that the WSN lifetime is increased. When compared to other routing approaches, GRASS improved WSN lifetime significantly.

Ahn and Ramakrishna (2002) proposed an algorithm for SP routing in multi-hop networks. The results are relatively independent of network sizes and various topologies. A repair function has also been proposed and lack of positional dependency in respect of crossing sites is an advantage here compared to other GAs.

Yussof et al (2009) proposed a parallel GA for solving the SP routing problem. This algorithm is developed and run on message passing interface cluster. Based on experimental result, there is a tradeoff between computation time and the result accuracy.

## 3. TWO PHASE HYBRID NATURE INSPIRED ALGORITHMS FOR mTSP

A careful analysis of literature on the variants and methodologies of CO problems reveals that some of the variants of CO problems are yet to be explored for solution using hybrid nature inspired intelligent heuristics and soft computing techniques. mTSP is one among them. In the cases which are dealing with the mTSP, the AI-heuristic algorithms are used for clustering as well as optimization. There is no specialized algorithm for the purpose of clustering or optimal allocation of cities to each salesman. Hence, it is decided to deal with the less frequently approached and more realistic multiple traveling salesman problem along with a specialized clustering heuristic, namely k-means clustering algorithm. This also breaks down a large sized problem into a simpler one. Usually, ACO is effective for small problems. GA makes a compromise between time and optimality of the result. Hence, it is decided to compare the results of GA and ACO to find which is more efficient. Finally, the performances of the algorithms are compared by using benchmark problems.

## 3.1 PROPOSED TWO PHASE AI-HEURISTICS

The performance of k-means clustering based two phase hybrid GA, ACO, SA and TS algorithms to solve mTSP are not yet much explored by the researchers. This chapter discusses the combination of 1) k-means clustering and GA and 2) k-means clustering and ACO algorithms for solving the mTSP. In the first phase of the algorithm, all the cities are grouped into number of clusters by using k-means clustering algorithm, where k is the number of salespersons in the given mTSP. In the second phase of the algorithm, the clustered cities are provided as input to GA and ACO algorithms. By using the input provided to them, GA and ACO algorithms compute the improved routes for each cluster. Finally the results of two phase GA and ACO are compared.

## 3.2 IMPLEMENTATION AND RESULTS

To illustrate the concepts of the proposed two phase hybrid AI-heuristics a mTSP with 180 cities and 6 salespersons is considered. All the algorithms are implemented on a Pentium IV processor with 2.8 GHz processor machine using MATLAB 7.0. The final results of GA and ACO are given in figure 3.1. The results show that ACO performs well, compared to GA. The proposed algorithms are applied to 7 TSPLIB benchmark problems. In this work, two phase hybrid ACO has clearly produced better results for large size mTSPs also when compared to two phase hybrid GA. This is because of the given mTSP, the large group of cities is broken down into smaller sized clusters efficiently by k-means clustering algorithm.

## 4.1 PROPOSED METHODOLOGY

The AI-heuristics algorithms normally consume more time for convergence. If initial solutions are provided by using some heuristic algorithms then the AI-heuristics algorithms will reach the convergence quickly Ganesh and Narendran (2007). Three phase hybrid simulated annealing, tabu search, GA and ACO algorithms are not analyzed much by researchers. Initial solution based three phase hybrid AI-heuristics are proposed in this chapter.

The solution to the problem is attained using three-stage AI-heuristics. The first phase involves the conversion of a mTSP to TSPs. This thesis used a concept of grouping the given cities depending upon the number of salespersons and each cluster is allotted to a salesman. k-means clustering algorithm has been used in the first phase for clustering of the cities. Second phase of the heuristic comprises of forming the initial tour for each salesperson using an algorithm called shrink wrap algorithm. In the third phase, an optimized route is to be generated for each salesman in his allotted cluster. The initial route obtained from the second phase is optimized by using SA and TS in the third phase. After completion of the route optimization for each cluster, the routes are balanced by using a simple heuristic. Finally, the three phase approach is used with SA, TS, GA and ACO to different size benchmark problems and the results are compared.

## 4.2 RESULTS AND DISCUSSIONS

To demonstrate the proposed three phase heuristics, initially, a simple 60 cities mTSP with 6 salespersons is selected. If second phase of the heuristic is skipped off, it may be noticed that achieving optimality for the salesperson's tour is difficult as the SA and TS are very slow processes and they take more time to converge. Hence, SWA is applied to form the initial tour and it serves as the input for SA and TS. Between the sequences generated by both methods, the sequence generated by SA was more optimized. The proposed three phase heuristics with GA, ACO, SA and TS is applied for the seven TSPLIB benchmark problems and the results are given in table 4.1. From the results, both ACO and GA perform better than other algorithms.

## Table 4.1 Results of 3 Phase Heuristics for TSPLIB Problems

TSPLIB problem

Number of salespersons

Total distance to be travelled (units)

GA

ACO

SA

TS

Pr124

6

63272

683217

69545

Pr144

6

71528

79458

80102

Pr226

6

134654

156248

164296

Pr299

6

67584

78351

82206

Pr439

6

140844

158526

156482

Pr1002

6

341563

362692

365891

Pr2392

6

462764

482213

482316

## 5. APPLIACTION OF THREE PHASE HYBRID GA FOR ROUTING IN SOLAR POWERED WSNs

From the literature, wireless sensor networks have various resource constraints, asymmetric many-to-one data flow and unreliable network nodes. Their primary objective is for energy conservation and increasing network lifetime. From the previous chapter it is understood that the three phase hybrid GA provides clustering and route optimization in an efficient manner compared to other algorithms for large size problems. Therefore, the same k-means clustering and GA based routing concepts with modifications are proposed here for solar powered WSNs.

## 5.1 PROPOSED ALGORITHM FOR WSNs

This thesis proposes three phase GA for the routing in solar powered WSNs. Data centric routing concepts consume more time for aggregation. The proposed routing algorithm is based on the hierarchical routing concepts in WSNs. The sensors are grouped into number of small size clusters using k-means clustering algorithm. Grouping the sensors into small sized clusters will make routing easy and also save the energy of the sensors due to less number of hops and reduced computation overhead. Within each cluster, the heuristic initial population based GA is used for SP computing. Initial solutions are created by using a new algorithm called basic solution algorithm and these will be provided to GA as initial population. Then GA operations are used to find the optimized SP route between source and destination nodes (cluster head) of WSN.

## 5.2 IMPLEMENTATION AND RESULTS

After clustering the sensor nodes, the SP routing algorithm is applied for each cluster. To demonstrate the performance of the proposed three phase GA, a cluster of a weighted WSN topology with 20 nodes is assumed. The algorithm is terminated when the number of iterations reached or all the chromosomes have converged to the same solution. Figure 5.1 shows the shortest path in bold line found by the proposed GA for the given source-destination pair.

Simulation results indicate that the proposed algorithm is insensitive to changes in WSN topologies in respect of both route optimality and convergence time. The route failure ratio of the proposed algorithm is significantly low compared to the existing GAs for different size WSN topologies. The convergence performance of the proposed GA is better than that of the standard GA and Dijkstra's algorithm. GA routing introduces the concept of using sub-optimal paths randomly at times to reduce and distribute energy consumption in routing thus increasing lifetime of the network.

## 6. SCOPE OF FEEDFORWARD NETWORKS FOR ROUTING IN WSNs

From the literature, the use of feedforward NNs are very limited for routing problems. Therefore, this chapter discusses the scope of feedforward NNs for routing in WSNs. In WSNs the execution time of algorithm is also a critical factor to save the energy of the sensor nodes. Generally GA and NNs are iteration based algorithms. Therefore, these algorithms consume considerable amount of execution time and battery energy of nodes. Finding a feedforward NN algorithm for SP routing in WSNs with fast convergence nature is focused on. The Extreme Learning Machine is one of such new algorithms for Single hidden Layer Feedforward Networks (SLFNs) Huang et al (2006). A NN based straight-forward hierarchical shortest routing algorithm for WSNs employing a SLFN that guarantees a highly efficient computation has been proposed in this chapter.

The computation performance of the proposed NN algorithm is compared with other NN algorithms. The results indicate that the proposed NN exhibits fastest rate of convergence as well as good quality of solution on par with other algorithms. It is suitable for multi-hop WSNs due its fastness. Compared with Hopfield and other NNs, the proposed NN can be implemented easily since, there is no parameter to be tuned except an insensitive parameter - output weight.

## 7. CONCLUSION AND FUTURE SCOPE

Firstly, the mTSP has been investigated. This thesis has developed a new multi stage efficient AI-heuristics that combines a k-means clustering algorithm, shrink wrap algorithm and AI-heuristics like GA,ACO.SA and TS. This adds to the paradigm of combining AI-heuristics and other algorithms to solve combinatorial optimization problems. Initially, two phase AI-heuristics has been used to solve the mTSP. To convert the mTSP into simple TSP k-means clustering has been used first and then GA and ACO have been used for route optimization. Then, initial solution based three phase AI-heuristics are applied. The results show that heuristics based route balancing concept is useful in balancing the routes. The results on benchmark problems show that basic solution algorithm based three phase GA performs better than the other algorithm approaches. The ACO performs well for small sized problems.

Secondly, this thesis employs the GA and NN based shortest path routing algorithms for routing in solar powered WSNs. The routing in WSNs is the critical requirement for energy savings of the battery powered sensor nodes. To save the energy and prolong the life of the sensors this thesis proposes solar power for WSNs and soft computing based SP routing for routing in WSNs. The results of three phase GA show that the algorithm performs better than other GAs and the results are closer to Dijkstra's algorithm. The k-means clustering provides efficient small sized grouping of sensors. The small sized clusters reduce the message and computational overheads at the nodes as well as at cluster heads. The simulation results show that the algorithm is insensitive to the variations in the network topologies. The SLFN based Extreme Learning Machine algorithm produces the results for SP routing on par with other NNs with fast convergence rate. Due to the fast convergence of the algorithm, the energy consumption of the sensors will be reduced which in turn will increase the life of the WSNs. The results show that the feedforward neural networks are suitable for SP routing in WSNs.

From the results of various proposed hybrid algorithms, it could be concluded that the nature inspired algorithms are efficient concepts for various complex real world oriented shortest path routing problems. The results also indicate that the nature inspired algorithms are able to solve the shortest path routing network problems of two different applications quite efficiently. Consequently, with the practical application, they can significantly improve the operational efficiency of an organization in its application domain.

The future direction of this research would be, solving the mTSP with different constraints such as total time, cost and workload balance. The other AI-heuristics and soft computing concepts can also be used to solve these problems. The present problem is mTSP with single depot and this can be extended to mTSP with multiple depots. The current routing protocols in WSNs optimize only the constrained capacities of the sensors and the application specific character of the WSNs. But they do not consider security. It is important to consider the security aspect of the WSN as these protocols have not been designed with the view of security as goal. Other hybrid AI-heuristics concepts can also be used for WSNs and mTSPs.