Solving The Multiple Traveling Salesman Problem Computer Science Essay

Published: Last Edited:

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 oriented network problems. The shortest-path problem has been analyzed by many researchers in recent years. It is a well-known problem and can be used to solve many real world oriented problems such as routing in telecommunication networks, vehicle routing in logistics management, pickup and delivery systems and web page searching for information retrieval through Internet systems. The rapid developments in computing technology and the increasing fuel and material costs have both motivated and promoted the study of network problems that arise in various different application fields.

The shortest path based network problems such as multiple traveling salesman problem and point-to-point shortest path problem are complex and Non-deterministic Polynomial-time hard (NP-hard) combinatorial optimization problems. If the problem size increases the complexity also increases. It is difficult and time-consuming to derive mathematical formulation based solutions for such type of problems and therefore, they are considered to be infeasible. The nature inspired approximation algorithms such as Artificial Intelligence (AI) heuristics and soft computing based concepts are suitable to such type of problems. Though, these algorithms could not provide optimal solutions, they could provide near optimal solutions within a reasonable span of time. Soft computing is the fusion of different methodologies that are designed to model and enable solutions to real world problems, which have not been modelled or too difficult to model mathematically. These problems are typically associated with complex and dynamic systems with uncertain parameters. These system models are used to solve real world problems amicably and attract the interest of the researchers in the scenario of modern technology.

This research focuses on solving the two important real-world shortest path network problems by using improved AI-heuristics and soft computing techniques due to their applications in various fields. They are:

1) Multiple traveling salesman problem (mTSP) and

2) Shortest path routing in solar powered wireless sensor networks.

The existing algorithms for traveling salesman problem have some limitations. Most of the researchers have solved simple traveling salesman problems by using various approximation algorithms. But most of the traveling salesman problems are concerned with multiple salespersons in reality. The simple traveling salesman problem is not suitable for representing such real world problems having multiple salespersons. The existing algorithms are rarely used the hybrid concepts to solve the mTSP with large number of cities. The mTSP has two main tasks. One is to allot suitable number of cities to a salesman in efficient manner and another is to find the shortest path among the allotted cities. These two issues have not been properly addressed by the researchers. Therefore, this research proposes a hybrid based hierarchical multi-stage nature inspired intelligent heuristics for city allocation and finding optimal sequence of different cities through which a salesperson can travel. The main aim is to solve the large sized mTSPs by converting them into simple TSPs using new multistage hybrid AI-heuristics. Hybrid based hierarchical Multi-stage (two/three stage) Improved Genetic Algorithms (MIGA) are developed and applied on mTSP. Initially, two stage AI-heuristics is applied and then, three stage AI-heuristics is applied to solve the problem. In the first stage, a well-known k-means clustering algorithm is used to allot different cities to a particular salesperson. Where k is the number of clusters. After performing the clustering, the problem is solved by assuming a simple traveling salesman problem for each cluster. In two stage AI-heuristics, after clustering, the optimal sequence of different cities for each salesman is determined using Improved Genetic Algorithm (IGA). The results are compared with two-stage hybrid ant colony optimization. For three stage AI-heuristics, after clustering, a new neighborhood algorithm called basic solution algorithm is proposed in the second stage to derive an initial feasible solution. Then in the third stage, the solution can be optimized by using AI-heuristics. To demonstrate the three-stage algorithm, the local search algorithms such as tabu search and simulated annealing are used to optimize the solutions. Finally, the three stage IGA is applied to various benchmark problems and the results are compared with three stage ant colony optimization, simulated annealing and tabu search.

Wireless Sensor Networks (WSNs) play an important role in monitoring and collecting data from difficult geographical terrains. They find useful applications in various fields ranging from environmental monitoring, to monitoring the parameters of vital signs of patients in hospitals. The inherent constraints such as limited battery life, memory and less processing capability of the sensors make the processing and routing of WSNs a tedious and challenging task. A great emphasis is laid down on the development of alternate sources of power and energy efficient routing protocols to maximize the life of network. This research proposes the utilization of solar energy with a view to extend the life of the networks in WSNs perspective.

The existing routing algorithms in WSNs are quite complex in nature and many of them use data-centric based concept. Almost all the algorithms consume considerable amount of time for data aggregation. Sometimes data loss may occur in the process of data aggregation. The route convergence time is also a critical factor in WSNs due to energy constraints existing in them. To avoid such types of drawbacks, this research proposes a simple location based hierarchical, straightforward point-to-point shortest path routing for solar powered wireless sensor networks. By using energy efficient clustering and routing concepts, the battery consumption and computational overhead will be considerably reduced. After deploying the sensors in the field, the nodes can be grouped into small sized clusters. The routing overhead will further be reduced with the grouping of sensors into small sized network topologies. One node will act as a cluster head for each cluster. The nodes can communicate through cluster heads, if any event occurs. The nature inspired approximation algorithms such as genetic algorithm and neural networks have been seldom used so far, for routing in WSNs. In this research, the soft computing concepts like genetic algorithm and neural networks are used for routing within the clusters. The three stage improved genetic algorithm with k-means clustering is proposed for clustering and routing in WSNs. The shortest path route from source node to cluster head within the cluster is calculated using three stage IGA. The results are compared with other well known genetic algorithms. Finally, the suitability of feedforward neural networks for routing in WSNs is analyzed by applying a single layer feedforward neural network called Extreme Learning Machine (ELM). The neural network is deemed to be a suitable accompaniment as it maintains the ability of learning and adapting to dynamic topologies. Once the feedforward neural network is initially designed, any change in the network routing environment can easily be learned by this adaptive artificial intelligence method. The capability of learning and adapting to dynamic network topology is an essential aspect in the scenario of the rapidly growing modern network technology.

The results obtained are encouraging and these results are compared with the results obtained through traditional techniques to prove the better performance of the hybrid MIGA. The results have proved that the simple clustering like k-means clustering proves to be effective as it is able to group the nodes as clusters in an optimal manner with reduced convergence time. It is known from the results of multiple traveling salesman problem that the MIGA provides an efficient solution for large scale problems and hybrid ACO provides efficient solution for small sized problems. The three phase genetic algorithm also provides efficient solution for routing in WSNs with fast convergence rate. The results show that the single layer feedforward neural network is a suitable algorithm for providing routing solutions in WSNs perspective. The proposed neural network reduces the algorithm execution time significantly compared to other neural network algorithms. The proposed neural network is also able to solve the large-sized problems compared to other neural networks. The results also indicate that the hybrid multi phase 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.