International Research Journal of Engineering and Technology (IRJET)
e-ISSN: 2395-0056
Volume: 04 Issue: 07 | July -2017
p-ISSN: 2395-0072
www.irjet.net
Particle Swarm Optimization to Solve Multiple Traveling Salesman Problem Sapna 1, Mandeep Kaur 2 1RESEARCH
SCHOOLAR, 2ASSISTANT PROFESSOR of Computer Science and Engineering KITM Kurukshetra Haryana, India ---------------------------------------------------------------------***--------------------------------------------------------------------1,2 Dept.
Abstract In this paper, we have proposed a new genetic ant colony optimization based algorithm for multiple Travelling Salesmen Problem (mTSP). The proposed algorithm has been developed a hybrid algorithm with some properties of GA and some properties of PCO. Each salesman selects his/her route using PCO and the routes of different salesmen (to construct a complete solution) are controlled by the GA. ACO special feature namely ‘refinement’. To show the effectiveness of the algorithm we use some benchmark instances and compare the results with other existing algorithms. From the obtained results, it can be concluded that the newly added features enhance the performance efficiency of the algorithm.
• •
Applications The TSP naturally arises as a subproblem in many transportation and logistics applications. Scheduling of a machine to drill holes in a circuit board or other object. In this case the holes to be drilled are the cities, and the cost of travel is the time it takes to move the drill head from one hole to the next. The travelling salesman problem can be classified as Symmetric Traveling salesman problem (STSP), Asymmetric Travelling Salesman Problem (ATSP), and Multi Travelling Salesman Problem (MTSP).
Key Words: TSP, STSP. PSO ,MTSP I.
INTRODUCTION
Traveling salesman problem (TSP) means to find the shortest path between the given numbers of cities, but the condition is to visit each city only once and return back to the initial city. In TSP, salesman travels N cities and come back to the starting city with the minimal cost. The first attempt of the traveling salesman problem was done by Euler in 1759 whose problem was to traverse a knight on a chess board exactly once. In 1832, German salesman BF Voigt wrote a book[1] on the traveling salesman problem. This book suggested to visit maximum locations without visiting twice is the main aspect of scheduling the tour but not mention this by name TSP. The beginning of mathematically concept of TSP was not exactly known but an estimate of around 1931 it was started.
(1)STSP: In STSP, the distance[4] between two cities is same in both directions which mean this will result in an undirected graph. (2)ATSP: In ATSP, the distance between two cities is different in both directions. It is a directed graph. (3)MTSP: In a given set of nodes, let there be ‘m’ salesmen located at a single depot node. The remaining nodes (cities) are intermediate nodes which are yet to be visited. Then, the MTSP finds the tours for all ‘m’ salesmen, who all start and finish at the place, such that each intermediate node (city) is visited exactly once and the total cost of visiting all nodes is minimized.
The following representation of the symmetric traveling salesman problem mathematically is:
II.METHODS TO SOLVE TSP One procedure that would definitely find the optimal solution of any TSP is the application of comprehensive enumeration and evaluation. This procedure consists of traversing all possible tours and evaluating their corresponding tour length.[7] The tour with the minimum length is selected as the best, which is to be optimal. If we could recognize and evaluate one tour per nanosecond (or one billion tours per second), it would require nearly ten million years (number of possible tours = 3.2×1023) to evaluate all of the tours in a 25-city TSP.”
Given an weighted graph G = (V, E) In which the weight cij of edge is between node i and node j is non-negative value, to find the minimum total cost among the tour of all nodes. TSP is an complete, weighted graph of n nodes, to find the least weight Hamiltonian cycle, that cycle visits every node once. •
Though this problem is easy enough to explain, it is very difficult to solve.
© 2017, IRJET
|
Impact Factor value: 5.181
Finding all the Hamiltonian cycles[2] of a graph takes exponential time. Therefore, TSP is in the class NP. One of the first TSP papers was published in the 1920s.
Obviously there is a strong requirement of an algorithm that will give us a solution in a shorter
|
ISO 9001:2008 Certified Journal
|
Page 1179