Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2007/10/01 Vol. E90-ANo. 10pp. 2187-2193 Type of Manuscript: Special Section PAPER (Special Section on Nonlinear Theory and its Applications) Category: Optimization Keyword: traveling salesman problem, Lin-Kernighan heuristic, data structure, three-level trees,