Local Clustering Organization (LCO) Solving a Large-Scale TSP
Masashi Furukawa*, Michiko Watanabe**,
and Yusuke Matsumura***
*Department of Information Technology Integration, Asahikawa National College of Technology, 2-2 Shunkodai, Asahikawa 071-8142, Japan
**Technical Official with Ministry of Education and Science IT Promoting Room, Asahikawa National College of Technology, 2-2 Shunkodai, Asahikawa 071-8142, Japan
***Advanced Course of Production System Engineering, Asahikawa National College of Technology, 2-2 Shunkodai, Asahikawa 071-8142, Japan
The traveling salesman problem (TSP) is one of the most difficult problems that occur in different types of industrial scheduling situations. We propose a solution, involving local clustering organization (LCO), for a large-scale TSP based on the principle of the self-organizing map (SOM). Although the SOM can solve TSPs, it is not applicable to practical TSPs because the SOM references city coordinates and assigns synapses to coordinates. LCO indirectly uses the SOM principle and, instead of city coordinates, references costs between two cities, to determine the sequence of cities. We apply LCO to a large-scale TSP to determine its efficiency in numerical experiments. Results demonstrate that LCO obtains the desired solutions.
-  C. Macmillan Jr., “Mathematical Programming,” John Wiley & Sons, Inc., pp. 407-415, 1975.
-  K. Nakano et al., “Nurocomputing,” Corona publishing company, pp. 148-161, 1990 (in Japanese).
-  T. Kohonen, “Self-Organizing Maps,” Spring-Verlag, Berlin, 1995.
-  J. Grefenstette, R. Gopal, B. Rosmatia, and D. V. Gucht, “Genetic Algorithms for the Traveling Salesman Problem,” Proc. of International Conference of Genetic Algorithms and Their Applications, Lawrence Erlbaum, Hillsdale, NJ, pp. 160-168, 1985.
-  S. Toma, K. Endo, and K. Yamada, “Application of immunity algorithm to nTSP,” Proc. of 55th Annual conference on Japan of Society Information Processing, Vol.2, pp. 453-454, 1997.
-  K. Wada, and Y. Wada, “GA + Hill Climbing + Immune System,” J. of Mathematical Sciences (SURIKAGAKU), Vol.11, pp. 12-230, 1992 (in Japanese).
-  H. Youssef, “Interactive Computer Algorithm with Application in Engineering,” IEEE Computer Society, 1999.
-  TSP-JPN,
-  TSPLIB,
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.
Copyright© 2005 by Fuji Technology Press Ltd. and Japan Society of Mechanical Engineers. All right reserved.