期刊名称：International Journal of Production Management and Engineering
印刷版ISSN：2340-4876
出版年度：2016
卷号：4
期号：2
页码：65-73
语种：
出版社：Universitat Politècnica de València
摘要：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.
其他摘要：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.
关键词：Reactive Bone Route Algorithm;Genetic Algorithm;Ant Colony System;Traveling Salesman Problem;NP-hard Problems
其他关键词：Reactive Bone Route Algorithm↓Genetic Algorithm↓Ant Colony System↓Traveling Salesman Problem↓NP-hard Problems
