Solving the Traveling Salesman Problem Based on The Genetic Reactive Bone Route Algorithm whit Ant Colony System

Yousefikhoshbakht, Majid; Malekzadeh, Nasrin; Sedighpour, Mohammad
July 2016
International Journal of Production Management & Engineering;Jul-Dec2016, Vol. 4 Issue 2, p65
Academic Journal
The TSP is considered one of the most well-known combinatorial optimization tasks and researchers have paid so much attention to the TSP for many years. In this problem, a salesman starts to move from an arbitrary place called depot and after visits all of the nodes, finally comes back to the depot. The objective is to minimize the total distance traveled by the salesman. Because this problem is a non-deterministic polynomial (NP-hard) problem in nature, a hybrid meta-heuristic algorithm called REACSGA is used for solving the TSP. In REACSGA, a reactive bone route algorithm that uses the ant colony system (ACS) for generating initial diversified solutions and the genetic algorithm (GA) as an improved procedure are applied. Since the performance of the Metaheuristic algorithms is significantly influenced by their parameters, Taguchi Method is used to set the parameters of the proposed algorithm. The proposed algorithm is tested on several standard instances involving 24 to 318 nodes from the literature. The computational result shows that the results of the proposed algorithm are competitive with other metaheuristic algorithms for solving the TSP in terms of better quality of solution and computational time respectively. In addition, the proposed REACSGA is significantly efficient and finds closely the best known solutions for most of the instances in which thirteen best known solutions are also found.


Related Articles

  • A Multi-weight s Ant Colony Algorithm for Solving Optimal Path in Tourism. Yuzhong Liu; Huaping Yu; Bing Huang; Yuanfang Zhang // Advanced Materials Research;2014, Vol. 998-999, p789 

    Optimal path selection is a fundamental problem in tourism, the influence factors of which only including the rout length, but also including weather, transportation and the scenery of attractions and other relevant factors. Therefore, route selection only based on the route length cannot...

  • Open Vehicle Routing Problem by Ant Colony Optimization. GurpreetSingh; Dhir, Vijay // International Journal of Advanced Computer Science & Application;2014, Vol. 5 Issue 3, p63 

    Vehicle routing problem (VRP) is real-world combinatorial optimization problem which determine the optimal route of a vehicle. Generally, to provide the efficient vehicle serving to the customer through different services by visiting the number of cities or stops, the VRP follows the Travelling...

  • A DISTRIBUTED APPROACH TO ANT COLONY OPTIMIZATION. Ilie, Sorin; Bădică, Costin // Annals of the University of Craiova, Economic Sciences Series;2013, Vol. 1, p230 

    Swarm Intelligence (SI) is the emergent collective intelligence of groups of simple agents. Economy is an example of SI. Simulating an economy using Ant Colony algorithms would allow prediction and control of fluctuations in the complex emergent behavior of the simulated system. Such a...

  • Ant Colony Optimization (ACO) and a Variation of Bee Colony Optimization(BCO) in Solving TSP Problem, a Comparative Study. Jasser, Muhammed Basheer; Sarmini, Mohamad; Yaseen, Rauf // International Journal of Computer Applications;Jun2014, Vol. 96, p1 

    Traveler sales man problem is known research problem which has a lot of industrial applications. A lot of algorithms has been proposed to solve TSP, some of Ant Colony Optimization (ACO) and Bee Colony Optimization (BCO) algorithms. BCO algorithm has variations and enhancements to improve the...

  • Improved ACO Algorithm with Pheromone Correction Strategy for the Traveling Salesman Problem. Tuba, M.; Jovanovic, R. // International Journal of Computers, Communications & Control;Jun2013, Vol. 8 Issue 3, p477 

    A new, improved ant colony optimization algorithm with novel pheromone correction strategy is introduced. It is implemented and tested on the traveling salesman problem. Algorithm modification is based on undesirability of some elements of the current best found solution. The pheromone values...

  • Ant Colony System with Heuristic Function for the Travelling Salesman Problem. Alobaedy, Mustafa Muwafak; Ku-Mahamud, Ku Ruhana // Journal of Next Generation Information Technology;Apr2013, Vol. 4 Issue 2, p39 

    Ant colony system which is classified as a meta-heuristic algorithm is considered as one of the best optimization algorithm for solving different type of NP-Hard problem including the travelling salesman problem. A heuristic function in the Ant colony system uses pheromone and distance values to...

  • VECTOR ANT COLONY OPTIMIZATION AND TRAVELLING SALESMAN PROBLEM. Patra, Chiranjib; Pratyush // International Journal of Computer Science & Information Technolo;2014, Vol. 6 Issue 5, p31 

    This paper introduces Vector Ant Colony Optimization (VACO), a distributed algorithm that is applied to solve the traveling salesman problem (TSP). In Any Colony System (ACS), a set of cooperating agents called ants cooperate to find good solutions of TSPs. Ants cooperate using an indirect form...

  • An Improved Ant Colony Optimization for the Multi-Robot Path Planning with Timeliness. Shuai Zhou; Guangming Xiong; Yong Li; Xiaoyun Li // International Journal of Smart Home;2014, Vol. 8 Issue 2, p201 

    To achieve efficient search performance for the multi-robot system which carries out the goal search task with consideration of timeliness, a multi-robot collaborative path planning system is designed to guide the robots during the search process. In the system, a planning method based on an...

  • An Ant System-Assisted Genetic Algorithm For Solving The Traveling Salesman Problem. Gaifang Dong; Xueliang Fu; Heru Xue // International Journal of Advancements in Computing Technology;Mar2012, Vol. 4 Issue 5, p165 

    The travelling salesman problem (TSP) is a classic problem of combinatorial optimization and has applications in planning, scheduling, and searching in many scientific and engineering fields. Genetic algorithms (GA) and ant colony optimization (ACO) have been successfully used in solving TSPs...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics