Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid  

作　　者：SU Shoubao CAO Xibin 

机构地区：[1]Research Center of Satellite Technology, Harbin Institute of Technology, Harbin 150081, China [2]Department of Computer Science and Technology, West Anhui University, Lu'an 237012, China

出　　处：《Chinese Journal of Electronics》2013年第1期202-208,共7页电子学报（英文版）

基　　金：This work is supported in part by the National Natural Science Foundation of China （No.61075049, No.61273096）, the National Defence Pre-research Foundation of China （No.113020102）, and the Funds for Creative Research Groups of China （No.61021002）.

摘　　要：Path planning on the surfaces of a cuboid-shaped object is a scientific value and practical significance of the research topic, because of its potential applications with many fields. On basis of analysis for calculation of the minimum distance of any two points on a cuboid, by incorporating Expanding neighborhood search （ENS） pro-cedure into the algorithm, a new discrete jumping particle swarm algorithm, ENS-JPSO, is presented for solving the traveling salesman problems on the surfaces of a cuboid, in which the path-relinking strategy is used to update ve-locities and positions of particles in the swarm, in order to improve the exploitation capability of the algorithm. After visual implementation of the experimental system in Java with 3D APIs, The effectiveness of the proposed method are tested on several TSPLIB instances with satisfactory results. And further comparison with other methods for various sets of random points has demonstrated that the proposed algorithm is able to obtain the best route for large-scale instances of TSPs on a cuboid.

关 键 词：Particle swarm optimization Travelingsalesman problem （TSP） Expanding neighborhood search（ENS） PATH-RELINKING Path planning Cuboid. 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置] O224[自动化与计算机技术—控制科学与工程]