Title: Local Clustering Organization Based Subtour Extract Approach for Large-Scale TSP

Year of Publication: Nov - 2014
Page Numbers: 123-133
Authors: Yohko Konno , Hidenori Kawamura, Keiji Suzuki
Conference Name: The International Conference on Artificial Intelligence and Pattern Recognition (AIPR2014)
- Malaysia

Abstract:


“Traveling Salesman Problem” (TSP) is one of most difficult and important problems in combinatorial optimization on industrial circles. “Local Clustering Organization” (LCO) was developed to solve large-scale TSP high-speed. LCO is reasonable for implementation to general optimization problems, it has a simple framework based on the principle of “Self-Organization Map” (SOM) for TSP. However, LCO has the defect of operation that was easy to be caught in a local minima. This paper will elucidate the LCO behavior and show two improvements to lack of LCO that is necessary to solve large-scale TSPs. First,LCO operator is explained as compared with k-opt method that is a well-known effective operation in TSP. Two improvements are the extension of LCO operator, and the control of “concentrations of search” which computes on a large search-pace effectively. In analysis of LCO and k-opt method, it is proposed “Insert method” (IM) to “Extended LCO” (ELCO) as a new method of 3-opt type. For making a concentration of search, it is proposed the method that 1-tour is divided into sub-tours and bridges for “Sub-tour extract ELCO” (SELCO). The performances of LCO, ELCO and SELCO are analyzed using “usa13509” of TSP instances. The experiment shows the improvement in the accuracy of solutions and the concentration of searches.