All Title Author
Keywords Abstract

Publish in OALib Journal
ISSN: 2333-9721
APC: Only $99

ViewsDownloads

Relative Articles

More...

A Water Flow-Like Algorithm for the Travelling Salesman Problem

DOI: 10.1155/2014/436312

Full-Text   Cite this paper   Add to My Lib

Abstract:

The water flow-like algorithm (WFA) is a relatively new metaheuristic that performs well on the object grouping problem encountered in combinatorial optimization. This paper presents a WFA for solving the travelling salesman problem (TSP) as a graph-based problem. The performance of the WFA on the TSP is evaluated using 23 TSP benchmark datasets and by comparing it with previous algorithms. The experimental results show that the proposed WFA found better solutions in terms of the average solution and the percentage deviation of the average solution from the best-known solution. 1. Introduction The travelling salesman problem (TSP) is a classic combinatorial optimization problem (COP), which was introduced many years ago in 1985 [1]. The TSP searches for the shortest path among a set of cities with known distances between pairs of cities to find the route solution. The route solution can be articulated as a complete graph with a set of vertices, which is a set of edges weighted by the distance between two vertices (cities), to find the shortest route by visiting each city exactly once and returning to the original city. Numerous approaches have been proposed and have obtained good solutions. However, they vary in terms of complexity and efficiency and in being able to solve the TSP at various levels of complexity and size (small, medium, and large). Earlier studies use linear programming Dantzig et al. [2], dynamic formulation Held and Karp [3], branch and bound [4], and branch and cut [1], but their ability is limited to small problems (less than 40 cities). Later, artificial intelligent approaches were proved to have the ability to solve more complex problems; one of these approaches, the self-organized neural network [5–7], was later expanded as a metaheuristic. A metaheuristic can optimize a complex problem by searching through many candidate solutions with few or no assumptions about the problem being solved and without any guarantee of finding the optimal solution. Some metaheuristics use either a single solution-based approach (e.g. tabu search (TS) and simulated annealing (SA)) or a population-based approach (e.g. genetic algorithm (GA)) [8–10], while others use swarm intelligence (e.g. ant colony optimization (ACO)) [11], and recently, hybrid metaheuristics have been proposed [7, 12]. The results show that hybrid metaheuristics can produce the best result using 23 benchmark TSP datasets. Recently, a new metaheuristic algorithm known as the water flow-like algorithm (WFA) has been proposed [13]. The algorithm is inspired by water flowing from

References

[1]  E. L. Lawler, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics, Wiley, 1985.
[2]  G. Dantzig, R. Fulkerson, and S. Johnson, “Solution of a large-scale traveling-salesman problem,” Operational Research Society Journal, vol. 2, pp. 393–410, 1954.
[3]  M. Held and R. M. Karp, “A dynamic programming approach to sequencing problems,” vol. 10, pp. 196–210, 1962.
[4]  E. Balas and N. Christofides, “A restricted Lagrangian approach to the traveling salesman problem,” Mathematical Programming, vol. 21, no. 1, pp. 19–46, 1981.
[5]  S. Somhom, A. Modares, and T. Enkawa, “A self-organising model for the travelling salesman problem,” Journal of the Operational Research Society, vol. 48, no. 9, pp. 919–928, 1997.
[6]  R. Pasti and L. N. De Castro, “A neuro-immune network for solving the traveling salesman problem,” in International Joint Conference on Neural Networks (IJCNN '06), pp. 3760–3766, July 2006.
[7]  T. A. S. Masutti and L. N. de Castro, “A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem,” Information Sciences, vol. 179, no. 10, pp. 1454–1468, 2009.
[8]  M. Gorges-Schleuter, “Asparagos96 and the traveling salesman problem,” in Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 171–174, April 1997.
[9]  G. Paun, G. Rozenberg, and A. Salomaa, DNA Computing: New Computing Paradigms, Springer, Berlin, Germany, 1998.
[10]  W. Pullan, “Adapting the genetic algorithm to the travelling salesman problem,” in Proceedings of the Congress on Evolutionary Computation (CEC '03), pp. 1029–1035, 2003.
[11]  M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53–66, 1997.
[12]  S. Chen and C. Chien, “Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques,” Expert Systems with Applications, vol. 38, no. 12, pp. 14439–14450, 2011.
[13]  F. C. Yang and Y. P. Wang, “Water flow-like algorithm for object grouping problems,” Journal of the Chinese Institute of Industrial Engineers, vol. 24, no. 6, pp. 475–488, 2007.
[14]  J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proceedings of the IEEE International Conference on Neural Networks, pp. 1942–1948, Perth, Australia, December 1995.
[15]  T. Stützle, M. López-Ibánez, P. Pellegrini et al., “Parameter adaptation in ant colony optimization,” in Autonomous Search, pp. 191–215, Springer, New York, NY, USA, 2012.
[16]  W. Leong and G. G. Yen, “PSO-based multiobjective optimization with dynamic population size and adaptive local archives,” IEEE Transactions on Systems, Man, and Cybernetics B: Cybernetics, vol. 38, no. 5, pp. 1270–1293, 2008.
[17]  K. C. Tan, T. H. Lee, and E. F. Khor, “Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 6, pp. 565–588, 2001.
[18]  G. G. Yen and H. Lu, “Dynamic multiobjective evolutionary algorithm: adaptive cell-based rank and density estimation,” IEEE Transactions on Evolutionary Computation, vol. 7, no. 3, pp. 253–274, 2003.
[19]  K. de Jong, “Parameter setting in EAs: a 30 year perspective,” in Parameter Setting in Evolutionary Algorithms, pp. 1–18, Springer, 2007.
[20]  M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization, vol. 7, Wiley-Interscience, New York, NY, USA, 2000.
[21]  T. Wu, S. Chung, and C. Chang, “A water flow-like algorithm for manufacturing cell formation problems,” European Journal of Operational Research, vol. 205, no. 2, pp. 346–360, 2010.
[22]  P. S. Shahrezaei, R. T. Moghaddam, M. Azarkish, and A. Sadeghnejad-Barkousaraie, “Water flow-like and differential evolution algorithms for a nurse scheduling problem,” American Journal of Scientific Research, pp. 12–32, 2011.
[23]  D. Kaur and M. M. Murugappan, “Performance enhancement in solving traveling salesman problem using hybrid genetic algorithm,” in Proceedings of the Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS '08), pp. 1–6, May 2008.
[24]  S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations Research, vol. 21, pp. 498–516, 1973.
[25]  G. Reinelt, “TSPLIB: a traveling salesman problem library,” ORSA Journal on Computing, vol. 3, no. 4, pp. 376–384, 1991.
[26]  E. M. Cochrane and J. E. Beasley, “The co-adaptive neural network approach to the euclidean travelling salesman problem,” Neural Networks, vol. 16, no. 10, pp. 1499–1525, 2003.

Full-Text

comments powered by Disqus

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133

WeChat 1538708413