SHORTEST PATH ALGORITHMS FOR TRAVELLING SALESMAN PROBLEM
Priyanka Wadhavane
Information Technology Pune university , IN
Varsha Purane
Information Technology Pune university , IN
Sangita Munje
Information Technology Pune university , IN
Riya Lakhotiya
Information Technology Pune university , IN
Keywords: MTSP algorithm, CTSP algorithm, S-CTSP algorithm, MBMS problem, GA, VNS algorithm, ACO algorithm
Abstract
In this paper, different improved shortest path optimized algorithm surveyed. The travelling salesman problem (TSP) is problem tasked to find the shortest path between a set of nodes and locations that must be visited. The nodes are the cities a salesman might visit. Both the travel costs and the distance travelled should be as low as possible. It widely and successfully applied the practical cases in which multiple travelling individuals (salesmen) shared the common workspace (city set).Multiple travelling salesperson problems MTSP unable to share a group of tasks with each other so a genetic algorithm (GA) with dual-chromosome coding for Colored travelling salesperson problems CTSP was proposed. Further a new CTSP was proposed in which each city had one to all salesmen’s colors and formulated its integer programming model. VNS was addressed for CTSP. CTSP was examined and newly called
S-CTSP. The basic scheduling problems of MBMS was modeled by S-CTSP. Then DTSP was addressed and ACObased memetic Algorithm was proposed. A new class of discretization based look-ahead algorithms (DLAAs) for the Dubins travelling salesperson problem (DTSP) was presented. Then transformation of the multi-region inspection into a clustered travelling salesman problem (CTSP) developed a fast branch-and-bound CTSP solver .A new CTSP was proposed in which each city has one to all salesmen’s colors and formulates its integer programming model
How to Cite
References
NA