Kohonen Self-Organizing Map based Route Planning: A Revisit
Qingshu Guan, Xiaopeng Hong, Wei Ke, Liangfei Zhang, Guanghui Sun, Yihong Gong
Abstract
In this paper, we revisit the long-standing Traveling Salesman Problem (TSP) and focus on the challenging, yet practical route planning problem with limited computational resources. We make contributions to TSP, one of the most famous NP-hard problems by providing a new improved approximate solution, which we term TOpology Preserving Self-Organizing Map (TOPSOM). TOPSOM well preserves the topology of the node map to be traversed by maintaining the continuity of nodes and the distances between them. In addition, to satisfy the requirements of convex hull, we design an elastic competitive Hebbian learning rule. TOPSOM can solve large-scale TSPs with high precision and high efficiency with limited computational costs. Extensive experimental results on mainstream route planning benchmarks including TSPLIB and National TSP’s show that our method consistently outperforms baseline methods, by up to 7.7% in terms of the Percent Deviation of Mean solution to best known solution.