# Shortest Path And Combinatorial Optimization Problems 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.

## CHAPTER 1

Shortest Path (SP) network problems are found all over the world in various forms. They are one of the most fundamental Combinatorial Optimization (CO) problems with many applications, both direct and as sub-problems in other CO algorithms. Algorithms to find efficient solutions for these problems have been studied for the past 60 years and still remain an active area of research. Center for Discrete Mathematics and Theoretical Computer Science, New Jersey (Johnson, 2001 and DIMACS, 2006) has announced awards for finding efficient solutions for SP routing and Traveling Salesman Problems.

The SP network problems find their applications in communication such as routing in networks, email and teleconference, transportation such as the daily commutation, garbage collection, delivery of milk and newspaper, social networks such as the interaction among knowledge workers, control of infectious diseases and disaster evacuation. The optimization techniques which are used to describe, analyze and solve these problems are embedded in various technologies and services that make the people utilize the services of telephone, surfing on the Internet and shipping holiday gifts more efficiently and pleasantly. Indeed, networks provide a rich framework for studying a wide range of practical problems of underlying physical or logical network structure.

The advancements in the research field of SP network problems have made a significant impact on the United States (US) economy for the past few decades. For example, United Parcel Service (UPS), the world's largest package delivery company, saved around $276 million over a decade after it had restructured its overnight delivery network using the concepts of advanced network optimization (Chen, 2007). The practice of using SP network models and concepts to improve efficiency and convenience has an increasingly significant role in today's service driven society. The reasons are as follows: 1). The increasing material costs, due to hike in oil and diesel prices is putting a heavy burden on the world economy. Furthermore, organizations in developed countries also face the problem of high labour costs due to shortage of manpower. As a result, achieving higher efficiency through cost reduction has become the need of the hour. 2). The advancements in computing technology, as demonstrated by the state-of-the-art Blue Gene system which has a peak speed of 360 trillion calculations per second enable researchers and practitioners to tackle much larger and more complicated problems sophisticatedly. In summary, the growing pressure for cost reduction and the continuous advancements in computing technology have offered great incentives and generated numerous opportunities for studying and applying network optimization (Chen, 2007).

However, though it is conceptually simple - one may ask how to find the shortest distance route to deliver all the mail in a particular town or city - these network problems are often combinatorial in nature. In general, instances of these problems are considered to be difficult to solve optimally. Therefore, in practice, the people often rely on efficient heuristics to get high quality solutions. This thesis addresses two real world SP network problems that arise in the application domains of transportation and telecommunications. Nature inspired hybrid AI-heuristic search procedures and softcomputing techniques are proposed to solve these problems.

## 1.2 BACKGROUND

Lot of realworld 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. For example the points may be communication routers and the lines may represent communication links between them. A mathematical representation of problems of such type gives rise to the development of the basic concept of graph. In the eighteenth century, seven bridges connected four different regions in the city of Konigsberg. In those days, the people of the city thought hard about the availability of any sequence for traveling across all seven bridges and returning to the starting point without crossing each bridge more than once. It is probably considered to be the starting point of today's modern path finding algorithms. Euler solved this problem in 1735 popularly known as the Konigsberg Bridge Problem. This is the base of what is now known as graph theory and this theory in turn paves the way for many path finding algorithms.

The study of mathematical graphs used to model the relationships between a network of vertices and edges is called graph theory. The efficient combinatorial methods found in graph theory have been used to derive significant and well-known results in various branches of mathematics. Graph theory is growing increasingly significant as it is applied almost to all areas of mathematics, business, and science and technology. The application of an algorithm based on graph theory can be explained with a simple scenario of connecting various cities of a country in a map. From the map, the distances between various cities can be identified. This information can be represented using a graph. The points in the graph represent the cities and the lines represent the distances between them. Given such a graph, it is possible to answer questions such as ``What is the shortest distance between given two cities?'' or ``What is the shortest route that connects all of the cities?''. The most common data structures for the representation of graphs and some fundamental graph algorithms are given in the next section.

## 1.2.1 Graphs

Graphs are used to represent nodes and edges graphically (Bondy and Murty, 1982). This graphical representation helps to understand many inherent properties easily. A graph is simply a set of vertices together with a set of edges connecting various points. Each vertex is indicated by a point and each edge by a line joining the points which represent its ends. A graph may be undirected or directed. If there is no distinction between the two vertices, then the graph is undirected.

Definition 1: A graph G is an ordered triple (V(G), E(G), ÏˆG) consisting of a non-empty set V(G) of vertices, a set E(G), disjoint from V(G), of edges, and an incidence function ÏˆG that associates with each edge of G and an unordered pair of (not necessarily distinct) vertices of G. If e is an edge and p and q are vertices such that ÏˆG(e) = pq, then e is said to join p and q; the vertices p and q are called the ends of e (Bondy and Murty, 1982).

A Graph will be simple, if it has no loops and no pair of its edges join the same pair of vertices. A Graph is finite if both of its vertex set and edge set are finite. The path is any route taken along the edges of the graph. If a path originates and terminates at the same location, then it is known as a circuit. The degree of a vertex refers to the number of edges that are connected to that particular vertex.

Definition 2: To any graph G there exists a v x Îµ matrix called the incidence matrix of G. Let us denote the vertices of G by v1,v2, v3,â€¦.,vv and the edges by e1,e2,â€¦,eÎµ. Then the incidence matrix of G is the matrix M(G) = [mij], where mij is the number of times (0,1) that vi and ej are incident. The incidence matrix is just another method of describing the graph.

Definition 3: Adjacency matrix is a v x v matrix A(G) = [aij], in which aij is the number of edges joining vi and vj.

## 1.2.2 Graph Algorithms and Their Practical Applications

A graph algorithm is an algorithm that takes one or more graphs as inputs for computing. Performance constraints on graph algorithms are normally described in terms of the number of vertices and the number of edges in the input graph. After the invention of Euler's Konigsberg Bridge Problem, the basic concept behind it has been expanded and the graph theory is being used in modern mathematical research, chemical and biological science and computer engineering (Rusin, 2001). The graph algorithms are being effectively used in various fields such as,

Electrical and Electronics Engineering (Circuit design, Network connectivity, Communications and coding theory)

Computer Science (Computer networking algorithms, The design and analysis of algorithms and computation)

Operations research (scheduling) and Business administration (Resource allocation)

For analyzing Deoxyribonucleic Acid (DNA) in biology and

Mathematical research (Optimization).

The various graph algorithms are given in figure 1.1. They can be classified into two major categories (Musser and Osman, 2003).

Edge comparison based algorithms and

Structure based algorithms

## Figure 1.1 Graph Algorithms

An edge comparison based graph algorithm is a graph algorithm whose computation depends on the weights associated with the edges of the graph. Most of the well-known graph algorithms are based on this concept. A structure based graph algorithm is a graph algorithm which operates strictly on the structural components of the graph. No edge or vertex property matrices like edge or vertex weights are required. Some of the graph algorithms are briefly given in the following sections.

## 1.2.2.1 Shortest Path Algorithm

The problem of determining the SP from one vertex to another or all other vertices is called as single source shortest path. For example, if the edges are given weights, then a shortest path is simply the path connecting two vertices where the sum of weights for the edges between the two vertices used is smallest. The shortest path between two vertices is also referred to as source-sink shortest path. Given a start vertex 's' and a finish vertex 'd', the shortest path in the graph from 's' to 'd' is to be calculated. It is assumed that the start vertex as the source and the finish vertex as the sink.

Definition 4: 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.

With each edge e of graph G, let there be associated a real number w(e), called its weight. Then G, together with these weights on its edges, is called a weighted graph. Weighted graphs occur frequently in applications of graph theory. In the communication graph, for example, weights might represent the construction or maintenance costs or signal strength of the various communication links. If H is a sub-graph of a weighted graph, the weight w(H) of H is the sum of the weights on its edges.

Many optimization problems amount to finding a sub-graph of certain type with minimum weight in a weighted graph. One such is the Shortest Path Problem (SPP). For example, from a road map network connecting various towns, determining the shortest route between two specified towns in the network, one must find, in a weighted graph, a path of minimum weight connecting two vertices s and t; the weights represent distances by road between directly-linked towns, and are therefore non-negative. It may be assumed that the weight of a path in a weighted graph as its length; similarly the minimum weight of a (s,t)-path will be called the distance between s and t and denoted by d(s,t). It is assumed as simple graph with positive weights. The algorithm based on the above concept is probably the most often used algorithm. It may be applied in real world situations where the shortest path between any two points is required. Not only SPPs are intuitive for many direct applications but they also take the people into a powerful and general realm, where they seek efficient algorithms to solve general problems that can encompass a large variety of specific applications.

## 1.2.2.2 Hamiltonian Path/Circuit

A path that contains every vertex of a graph G is called a Hamilton path of G. If a circuit visits every vertex exactly once and ends at the starting point, it becomes known as a Hamiltonian circuit (or Hamiltonian cycle). Such paths and cycles are named after Hamilton. A graph is Hamiltonian if it contains a Hamiltonian cycle.

The Traveling Salesman Problem: A traveling salesman wishes to visit a number of cities and then returns to his starting point. Given the traveling time between cities, how should he prepare his traveling plan so that he can visit each city exactly once and travel through all the cities with minimum possible time? This is known as the famous traveling salesman problem (TSP). In graphical terms, the aim is to find a minimum-weight Hamiltonian cycle in a weighted complete graph. In contrast to the shortest path problem, no conventional efficient algorithm for solving the traveling salesman problem is available. It is therefore desirable to have an algorithm for getting a reasonably good (near optimal) solution. The problem is similar to Chinese postman problem, but instead of visiting a set of streets (edges), he has to visit each node (house) exactly once.

## 1.2.2.3 Minimal Spanning Tree

A spanning tree S is a subset of a tree T in which all the vertices of tree T are present but it may not contain all the edges. The spanning tree of a weighted connected graph G is called minimum spanning tree if its weight is minimum. Consider some communications points for telephony, local area network, cable television, or Internet services and a list of possible links of different costs between them. It is necessary to find the cheapest way to connect these points in a network so that a point is connected to another directly, or through intermediate points.

## 1.2.2.4 All Pairs Shortest Path Algorithm

An all pairs shortest path algorithm is any algorithm which calculates the shortest path between all pairs of vertices in a given graph.

## 1.2.2.5 Eulerian Path/Circuit

An Euler tour is a tour which traverses each edge exactly once. A graph is Eulerian if it contains an Euler tour. If the circuit crosses every edge once but still reaches all the points it becomes an Eulerian graph. A postman has to visit a set of streets in order to deliver mails. It is required to find the shortest path that starts and ends at the post-office, and that passes through each street exactly once. This way the postman will deliver mails to all streets he has to, and at the same time will spend minimum time in travelling. It is important to note that not all graphs have an Eulerian circuit.

Chinese Postman Problem: The same problem as afore-mentioned, but instead of visiting each street exactly once, the postman can visit them more than once if needed. Thus the path should pass through each street at least once and should have the minimum cost.

## 1.2.2.6 Network Flows

With Maximum Flow algorithm it is possible to determine the most loaded roads or rails in a certain transportation network, and also to determine its maximum intensity. This information may be then used to improve the traffic conditions in those roads.

## 1.3 PROBLEM DESCRIPTION

Among the various graph algorithms, the shortest path algorithm and Hamiltonian cycle algorithm (traveling salesman problem/vehicle routing problem) have a lot of applications in various real world situations. The following are the two important problems based on the afore-mentioned graph algorithms.

Multiple traveling salesman problem and

Shortest path routing in multi-hop wireless sensor networks.

Therefore this thesis focuses on finding efficient solutions for these problems.

## 1.3.1 Traveling Salesman and Vehicle Routing Problems

## 1.3.1.1 Supply Chain Management and Logistics Management

## A supply chain can be defined as a network of various stakeholders of an origination involved directly or indirectly in procuring raw materials, processing them into finished products, and delivering the finished goods to the customers. The supply chain may involve a variety of stages as shown in figure 1.2. They are:

Customers

Retailers

Wholesalers/distributors

Manufacturers

Raw material suppliers.

## Customer

## Supplier

## Retailer

## Distributor

## Manufacturer

## Figure 1.2 Stages of a Supply Chain

## Supply Chain Management (SCM) is the process of planning, implementing, integrating and controlling the various functions of the supply chain with the purpose of satisfying customer requirements as efficiently as possible. SCM activities involved in all movement and storage of raw materials, work-in-process items, and finished products from supplier to customer (Chopra and Meindl, 2007). In reality, a manufacturer may receive raw material from various suppliers and then supply the finished goods to several distributors. Thus, mostly supply chains are actually network problems.

## Logistics Management is the main component of the supply chain. It plans, implements and controls the efficient, effective forward and reverse movement and storage of goods, services and related information between the supplier and the customer in order to meet customers' needs. Reducing transport costs and optimizing hired resources are the goals of logistic work. This is exactly the background from which the optimization methods and different algorithms are developed to find solutions for solving the problems that organizations are facing now.

## 1.3.1.2 Vehicle Routing Problem

Vehicle routing problem (VRP) is the most common problem of logistics management existing in every organization. The main goal is to find the most efficient route to minimize the total distance travelled by a vehicle. It will reduce the total time and cost of the travel. Thus by reducing the total distance travelled, the firm is able to provide better service to the customers and possibly increasing its market share. It generally includes simultaneously determining the routes for several vehicles from a central depot to a number of customers and returning to the depot. This problem is of economic importance to the organizations because of the time and the cost associated with providing vehicles to transport products to a set of geographically dispersed customers (Bell and McMullen, 2004).

## In addition, all such problems are also significant in the public sector where vehicle routes must be determined for oil and gas distribution, public distribution system, postal carriers, water supply, transport systems, and other public service vehicles. In these examples, the problem generally involves finding the minimum costs of the combined routes for a group of vehicles in order to provide delivery from the depot to a number of customer locations. Since the cost and time is closely linked with the amount of distance travelled, the organization might try to find the minimum distance travelled by a group of vehicles in order to satisfy customer demand.

## 1.3.1.3 Travelling Salesman Problem- A Real Life Problem

TSP is one of the well-known routing problems. The mathematical structure of the TSP is a graph where the cities are the nodes of the graph, the links between pairs of cities are called edges and each edge has a cost associated with it which can be distance, time or other attribute. In solving the TSP one tries to construct the route so that the total distance travelled is minimized. If n is the input number of vertices representing cities, for a weighted graph G, the TSP problem is to find the Hamiltonian cycle of minimum cost that visits each of the vertices of G exactly once. Due to the combinatorial complexity of the TSP, approximate or AI-heuristic solution procedures are almost always employed in practice (Skiena, 2008). Figure 1.3 a) shows a simple example for a weighted graph with 6 nodes and figure 1.3 b) shows a TSP path for the given weighted graph with the shortest distance of 58 units.

8

15

8

7

15

5

1

2

4

3

5

6

7

10

20

15

8

30

8

15

5

15

1

2

4

3

5

6

## Figure 1.3 a) A simple Graph b) Graph with Hamiltonian Cycle

TSP is a prominent illustration of a class of problems in computational complexity theory which are classified as Non-deterministic Polynomial-time (NP)-Hard. The TSPs are classified in two categories. They are:

Symmetric TSP

Asymmetric TSP (ATSP).

Many Travelling Salesman Problems (TSPs) are symmetric - that is, for any two cities A and B, the distance from A to B is the same as that from B to A. In ATSP, the weights (distance) of A to B and B to A are different. In the former case, it will give exactly the same tour length if the order is reversed in which they are visited.

## 1.3.1.4 Multiple Traveling Salesman Problem

The mTSP is a superset of TSP. A generalization of the well-known TSP is the mTSP, which consists of determining a set of routes for m salesmen who all start from and return back to a home city (depot). The mTSP can in general be defined as follows: Given a set of cities, let there are m salesmen located at a single depot node. The remaining cities that are to be visited are called intermediate nodes. Then, the mTSP consists of finding tours for all m salesmen, who all start and end at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. In the mTSP problem, m salesmen have to cover the given cities and each city must be visited exactly once by exactly one salesman.

## 1.3.1.5 Applications of VRP/mTSP

Compared to the TSP, the mTSP is more adequate to model real life situations, since it is capable of handling more than one salesman. These situations arise mostly in various routing and scheduling problems. Some reported applications are presented below (Bektas, 2006):

Print press scheduling

Soft drink distribution

Crew scheduling

School bus routing problem

Hot rolling scheduling

Design of global navigation satellite system surveying networks and

Public distribution system- vehicle routing

## 1.3.2 SHORTEST PATH ROUTING PROBLEM

## Shortest Path Routing (SPR) is one of the simplest routing schemes and the main concept involved here is the determination of the optimal /shortest available path between a source and a destination. The term optimal/shortest path in SPR problem may refer the following:

## Path of the shortest time, least geographical distance, or least cost in various networks

## Path of the least network congestion, or least number of hops in communication networks

## Path of the least propagation or transmission delays in communication networks.

## 1.3.2.1 Graph Theory and Communications

Routing concept is the primary component in the performance of any network. Graph theory comes up in solving communications problems. 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 (nodes) may be routers or computers or mobile communication devices. The simple example for this type of network is the Internet, where the nodes represent routers (or hubs) and edges represent wires or wireless communication media between pairs of routers. In the same manner the graphs can be used to describe various SPR network problems (Sedgewick, 2003). Figure 1.4 a) shows a simple weighted graph with 6 nodes. The shortest path between nodes 1 and 6 is shown in figure 1.4 b). The SP distance is 23 units.

## 7

## 10

## 20

## 15

## 8

## 30

## 8

## 15

## 5

## 15

## 1

## 2

## 4

## 3

## 5

## 6

## 1

## 2

## 4

## 3

## 5

## 6

## 5

## 10

## 30

## 8

## 15

## 15

## 20

## 15

## 8

## 7

## Figure 1.4 a) A simple weighted graph b) Graph with its Shortest Path

## 1.3.2.2 Shortest Path Routing in Multi-hop Wireless Sensor Networks

SP routing algorithms have been widely used in today's computer networks. In such algorithms, each node attempts to route packets to their respective destinations over paths of minimum distance and updates the distances periodically to adapt topological and traffic changes. SPR algorithms serve remarkably well in the communication network environment where network traffic is less and network conditions change slowly. SP algorithms are able to respond to topological changes automatically and adjust routing decisions when traffic changes (Wang and Crowcroft, 1992).

Routing is one of the major issues in the Mobile Ad-hoc Networks (MANET), Wireless Sensor Networks and other multi-hop networks. The purpose of the routing algorithm is to find the optimum path between source and destination nodes for packet transmission within a specified time. As per the definition from encyclopedia, SPR is a form of routing which attempts to send packets of data over a network in such a way that the path taken from the sending node to the recipient node is minimized. The path can be calculated in either physical distance or in the number of hops. This form of routing normally uses a non-adaptive routing algorithm (Ince, 2001).

Almost all the current multi-hop packet switching networks use SP routing computation based on routing algorithms in the network layer. Normally the weighted links concepts are used here. The weights of the links based on various factors related to routing like link transmission capacity, the signal strength of the link, the congestion of networks and the estimated transmission status such as the queuing delay or the link failure. Hence, the SP routing problem can be formulated as an optimization problem to find the minimal cost path between the source and the destination nodes. i.e. it is a classical NP-hard CO problem.

The simple example for dynamic multi-hop routing networks is wireless sensor networks. Here all the nodes collectively and cooperatively form the network connectivity without using any fixed infrastructure. The Wireless Sensor Network (WSN) topology is dynamic in nature due to frequent node failures. For real time communications an optimal shortest path has to be computed within a very short period of time i.e. in milli or micro seconds.

Sensors are electronic devices that sense the physical environment, for example, there are sensors for temperature, pressure, light, metal, smoke and proximity to an object. The sensor sends the signals to computer or controller. Sensors have computational, communication, and networking capabilities. They are deployed to communicate information to a network, a central computer, or a controller. The sensors are constrained by their small size, limited energy availability, and limited memory. Since greater computational speed needs greater energy, these sensors operate at limited speed. WSN is a network of sensors having computational, communication, and networking capabilities. Sensor devices are cooperative with each other to disseminate the sensed data in the network. Sensor networks deploy special routing protocols such as Dynamic Source Routing (DSR) protocol, Ad-hoc On-demand Distance Vector (AODV) routing protocol, or shortest path routing.

## 1.3.2.3 Applications of Shortest Path Problems (SPPs)

SP computation is one of the main concepts in Graph theory. It has large number of applications. The following are a few of them.

Routing in communication networks

Vehicle routing problems

Robot arm motion planning

Road maps- Tables that give distances between all pairs of major cities and

Airline routes- Route maps and schedules for airlines or other transportation networks

SPPs for such applications not only bridge the gap between elementary algorithms and unsolved algorithmic challenges but also offer us powerful and general problem-solving mechanisms.

## 1.4 SOLUTIONS FOR VRP/mTSP

The Brute Force Method is a method that will search all possible solutions and always yield an optimal solution. The problem with the Brute Force Method is that it can be time consuming due to its exhaustive search, especially when dealing with large size problems, and there are generally too many vertices to perform by pencil and paper (Cheung, 2009). The number of solutions becomes extremely large for large n, so that an exhaustive search is impracticable. Efforts have been concentrated on the development of heuristics that are not guaranteed of finding the shortest tour, but are likely to quickly find either the optimal solution or a near-optimal alternative. The two most important categories of solution procedures are classified as 1) exact and 2) approximate heuristics.

## 1.4.1 Exact Algorithms

## Various branch-and-bound algorithms, which can be used to process small size mTSPs containing 40-60 cities.

## Progressive improvement algorithms which use techniques reminiscent of linear programming, work well for medium size mTSPs up to 200 cities.

## Implementation of branch-and-bound and problem-specific cut generation is the method of choice for solving large size mTSPs.

Exact approaches for solving the TSP are successfully used only for relatively small problem sizes but they can guarantee optimality based on different techniques (Wikipedia, 2010).

## 1.4.2 Approximate Solution Procedures-Heuristics

Heuristic solution procedures cannot guarantee optimality. They are approximate approaches based on algorithms that construct feasible solutions within a reasonable computing time. As a result two very important criteria are considered in all the proposed heuristics: 1) speed, meaning the total computational time, and, 2) closeness to optimal solution, meaning how far away in percentage from the optimal solution. Various approximation algorithms, which quickly yield good solutions with high probability, have been devised. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability, just 2-3% away from the optimal solution. Several categories of heuristics are recognized. The two main categories in which heuristics are classified as 1) constructive and 2) improvement (Wikipedia, 2010).

## 1.4.2.1 Constructive Heuristics

Constructive heuristics are algorithms that try to build up feasible solutions step by step and then stop when a solution is found and never try to improve upon its solution. The problem with constructive heuristics is that, although they are often fast, they do not produce a very good solution. The nearest neighbour method is based on the idea, to always visit the closest city.

## 1.4.2.2 Improvement Heuristics

Improvement heuristics are algorithms that start with an initial feasible solution and successively improve it through a sequence of exchanges. The initial solution can be chosen at random by means of nearest neighbor, for example. As such, an initial feasible solution can be one that does not violate any of the constraints. The improvement heuristics can be classified into two types, as follows. The various algorithms are also given.

Iterative improvement

Pair-wise exchange or Lin-Kernighan heuristics

k-opt heuristic

V'-opt heuristic

Randomized improvement

Optimized Markov chain algorithms

Random path change algorithms

## 1.5 ALGORITHMS FOR SHORTEST PATH ROUTING PROBLEMS

Routing algorithms in computer networks can be classified as given below according to how adaptive they are.

Static

Quasi-static and

Dynamic.

In a static routing algorithm, the route is predetermined and remains same for relatively long duration. Static routing algorithms are easy to implement but vulnerable to network resource failures and traffic changes. A dynamic routing algorithm allows continuous time-to-time changes in routing decisions to adapt the current network traffic and topological changes. But such routing algorithms are often too complex and need huge amounts of information exchange and computation. The SPR algorithms widely used today, fall approximately into the quasi-static category, in which the route distances remain constant for a short period of time but can be updated when major changes happen (Wang and Crowcroft, 1992).

There are various algorithms available for SPPs. The following are some of the algorithms.

Dijkstra

Bellman-ford dynamic programming algorithm and

The Breadth First Search (BFS) algorithm.

SPR problem can be solved by using the well-known Dijkstra's algorithm which would provide a global optimization solution in most instances. However, as the size of problem increases, this algorithm is inefficient and may consume a significant amount of Central Processing Unit (CPU) time (Wang et al, 2009). The afore-mentioned algorithms solve the SP problems in polynomial time and they are effective in static infrastructure based wired or wireless networks. But these algorithms provide less performance for quasi-static and dynamic routing problems related to real time communications. The time required to obtain solutions with these algorithms grows polynomially with the number of nodes in the network, making these algorithms somewhat inefficient for larger problems. Similarly, if the number of nodes increases then these algorithms will take considerably more CPU time. Therefore, to solve these problems various approximation algorithms are used. To solve the SP problems various nature based approximation algorithms like Genetic algorithm, Neural networks, Ant colony optimization, and Tabu search are used.

## 1.6 LIMITATIONS OF EXISTING ALGORITHMS

## 1.6.1 mTSP and SPP as a Combinatorial Optimization Problem and Computational Complexity

## Computer networking and routing problem has become an active research area in the last few decades and numerous solutions and products have been developed through successful networking research. Due to the demands for higher data transfer rate and more seamless network connectivity, new technologies keep on being developed, customized and merchandised, including wireless sensor networks, wireless mesh networks, social networks, and smart grid communications. Therefore, lots of new problems have been proposed and most of which can be formulated as combinatorial optimization problems. However, many such CO problems do not have the corresponding good algorithms developed or they are so hard (usually classified as NP-hard) that no algorithm is available to find the optimal solution in polynomial time.

NP problems are non-deterministic problems that cannot be solved in polynomial time (reasonable computing time, short time), where non-deterministic means that taking a guess in the solution is involved. However such an efficient algorithm has not yet been found. It is a decision problem where instances of the problem for which the answer is yes have proofs that can be verified in polynomial time. NP-complete problem is a class of problems for which one can make out the guess of solution of these problems which will get solved in polynomial time. An NP problem Q for which it is possible to reduce any other NP problem R to Q in polynomial time. Intuitively this means that one can solve R quickly if they know how to solve Q quickly. Informally, in NP-complete, solving the problem is very difficult and verification of the solution is simple. NP-hard problems are the problems that are even harder than the NP-complete problems. These problems are at least as hard as the hardest problems in NP. These problems may not be in NP category. Informally, in NP-hard, solving the problem is very difficult but verification is also difficult for some of the problems.

Researchers on the TSP and SPP have proved that the mTSP and SPP are NP-hard CO problems. The TSP remains NP-hard, even for the case when the cities are in the plane with Euclidean distances, as well as in a number of other restrictive cases. Removing the condition of visiting each city "only once" does not remove the NP-hardness, since it is easily seen that in the planar case an optimal tour visits cities only once (Wikipedia, 2010).

If n is the number of cities to be visited for the TSP then (n-1)! will be the total number of possible routes. Following this basic formulation, an exponential relationship will exist between the number of cities and possible routes. For instance, if there are 5 cities there are 24 possible routes, for 6 cities 120, for 10 cities 362,880, and so on. As the amount of input data increases the problem increases in complexity. Thus the computational time needed renders this method impractical for all but a smaller number of cities. The challenge of combinatorial optimization is to develop algorithms that consume a reasonable amount of computer time. This challenge is of interest to mathematicians as well as to computer scientists.

## 1.6.2 Reasons for Nature Inspired Algorithms

Utilizing classical methods of Operations Research (OR) for CO problems, often fail due to the exponentially growing computational times. Therefore, in practice various nature inspired intelligent techniques based heuristics, AI-heuristics and soft computing algorithms are normally used even if they are unable to guarantee an optimal solution. AI-heuristics, otherwise called as Meta-heuristic techniques that mimic natural processes, developed over the last thirty years and have produced 'good' results in reasonable short runs for this class of optimization problems. Even though those bionic heuristics are much more flexible regarding modifications in the problem description when being compared to classical problem specific heuristics, they are often superior in their results. For example, rather than considering all possible tours, heuristic algorithms for solving the mTSP are capable of substantially reducing the number of tours to be taken into consideration. A heuristic is considered "good" if the number of elementary computational steps is bounded by a polynomial in the size of the problem. Although it may be difficult to find the optimal solutions for these problems, it is possible to still find the near optimal solutions. Since the evolutionary computational approaches have been developed for the past few decades, many works rely on the nature-inspired algorithms to do optimization.

## Soft Computing can be defined as follows. Iis a new multidisciplinary field, whose objective is to develop new generation Artificial Intelligence, called as Computational Intelligence. The various applications of soft computing have proved two major advantages. First, it made solving nonlinear CO problems, in which mathematical models are not available and possible. Second, it introduced the human knowledge such as cognition, identification, understanding, learning, training and others into the fields of computing. This resulted in the possibility of developing various nature inspired intelligent systems such as autonomous self-tuning systems, and automated designed systems (Chakraborty, 2010).

## 1.7 SCOPE AND OBJECTIVES OF RESEARCH

The increasing material costs and the rapid advancements in computing technology have both motivated and promoted the study of shortest path routing network problems that arise in several different application domains. The core idea of this research is to apply nature inspired AI-heuristic search procedures and CO techniques to two well known NP-hard shortest path routing problems.

Although the TSP has received a great deal of attention, the research on the mTSP is limited. Many of the authors have suggested the use of a constructive heuristic to obtain good initial solutions for an AI-heuristic so that its convergence can be accelerated. 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. This couldÂ yield quality solutions at reasonable computation time.

## Only a few authors have considered the use of hybrid approaches to solve different variants of large sized mTSP CO problems. The hybrid algorithms concentrate on improving the strengths and compensating for the weaknesses of two or more complementary techniques. The aim is the development of superior solutions by combining the crucial elements of competing methodologies.

Most of the real life problems utilise more than one salesperson or vehicle. Therefore this thesis assumes the TSP as a multiple travelling salesman problem. There is a scope for applying hybrid multi stage nature inspired intelligent techniques for mTSPs. By using clustering concept the large sized complex mTSP is converted into a simple TSP and then softcomputing and metaheuristics concepts have been applied in multiple phases to solve the problem. A hybrid based hierarchical Multi (two/three) stage Improved GA (MIGA) is proposed for the mTSP. For clustering k-means clustering is the well known efficient algorithm. After clustering a new algorithm called Basic Solution Algorithm is proposed for initial solution. Global search algorithms like improved genetic algorithm and ant colony optimization and the local search algorithms like tabu search and simulated annealing can be used for optimization.

WSN is emerging as a new network technology in various fields of application. It is a multi hop infrastuctureless wireless network deployed in remote areas. Due to energy constraint of sensors, 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 hybrid three-stage improved genetic algorithm to find the shortest path routing is proposed in solar powered WSNs. Probably this may be the first attempt to use hybrid based AI-heuristics for routing in WSNs. The algorithms k-means clustering, basic solution algorithm, and improved genetic algorithm (IGA) are used in hybrid manner to improve the solution.

The iteration based AI-heuristics and soft computing algorithms normally consume more time for better convergence. Finally, to reduce the convergence time, a simple single layer feed-forward neural network is proposed for routing to improve the life of the WSNs.

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

## 1.8 CONTRIBUTIONS AND ORGANIZATION OF THE THESIS

It is considered the following to be the major contributions of this thesis:

Vehicle routing and multiple traveling salesman problems and the various algorithms to solve them that have appeared in the last twenty years are reviewed and summarized.

Routing algorithms in solar powered wireless sensor networks and shortest path routing algorithms that have appeared in the last decades are reviewed and summarized.

Two new hybrid algorithms based on multi (two/three) stage improved GA (MIGA) are proposed for mTSP and analyzed their computational performance for large sized mTSPs.

The other hybrid based two/three phase algorithms such as ACO, SA and TS are proposed and their computational performances are compared with MIGA using different benchmark problems.

The MIGA based shortest path routing is proposed for routing in solar powered WSNs. The computational performance of the algorithm is compared with other GAs.

A tuning free single layer feedforward neural network based on extreme learning machine concept is proposed for shortest path routing in solar powered WSNs and the computational performance of the algorithm is compared with other standard neural networks.

Chapter 1 provides an introduction to Graph concepts, Applications of Graph algorithms, Shortest path concepts, Traveling salesman problem, limitations of existing algorithms, Nature inspired algorithms and scope and objectives of the proposed research. Chapter 2 gives a brief literature review related to the fields of mTSP and shortest path routing in WSNs. It also discusses the drawbacks of the existing AI-heuristics and soft-computing concepts for the aforementioned problems. Chapter 3 deals with the mTSP that arises in various real life transportation problems. A two stage hybrid improved GA is used for solving mTSP. It deals with k-means clustering algorithm for clustering of the cities and improved genetic algorithm for route optimization within the cluster. To compare the results of two stage GA, two phase ant colony optimization is used for solving the problem. The algorithm concepts are explained with their simulation results. Chapter 4 presents the solution for mTSP using three-stage hybrid AI-heuristics. The proposed algorithm uses k-means clustering algorithm in the first stage for clustering of cities, a new algorithm called basic solution algorithm in the second stage to find the initial solution and AI-heuristics in the third stage for route optimization. To demonstrate the functioning of the three-stage algorithm, local search algorithms such as tabu search and simulated annealing are used. The algorithm details and the results are given. Finally, the results of the three stage improved GA is compared with three phase ACO, SA and TS algorithms based on seven benchmark TSP Library (TSPLIB) problems with various sizes. Chapter 5 provides the shortest path routing problem for routing in solar powered wireless sensor networks. The three stage improved GA proposed in the previous chapter is used to find the shortest path in solar powered WSNs. The chapter gives the details of k-means clustering, basic solution algorithm and improved genetic algorithm for solving the problem. The results are compared with other genetic algorithms and Dijkstra's algorithm. Chapter 6 analyses the scope of single layer feed forward neural networks for the shortest path routing in solar powered wireless sensor networks. A new tuning free single layer feedforward network is proposed. The results are given and compared with other neural networks. Chapter 7 provides concluding remarks on the proposed algorithms and the future scope of the nature inspired algorithms for shortest path network problems.

## 1.9 CONCLUSION

This chapter provides an introduction to the graph algorithms, applications of graph algorithms, description of traveling salesman and shortest path routing problems and various applications of them. It also discusses the existing solution methods for TSPs and SPPs, limitations of the existing methods and the need for nature inspired soft computing algorithms. Finally, the scope and objective of the research work has been presented.