Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid

SU Shoubao; CAO Xibin

Article Contents

Article Navigation > Chinese Journal of Electronics > 2013 > 22(1): 202-208

SU Shoubao and CAO Xibin, “Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid,” Chinese Journal of Electronics, vol. 22, no. 1, pp. 202-208, 2013,

Citation:

SU Shoubao and CAO Xibin, “Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid,” Chinese Journal of Electronics, vol. 22, no. 1, pp. 202-208, 2013,

SU Shoubao and CAO Xibin, “Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid,” Chinese Journal of Electronics, vol. 22, no. 1, pp. 202-208, 2013,

Citation:

SU Shoubao and CAO Xibin, “Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid,” Chinese Journal of Electronics, vol. 22, no. 1, pp. 202-208, 2013,

PDF( 914 KB)

Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid

SU Shoubao^1,2,
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

Funds: 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).

Received Date: 2011-11-01
Rev Recd Date: 2012-02-01
Publish Date: 2013-01-05

Abstract

Abstract

Path planning on the surfaces of a cuboidshaped 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) procedure 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 velocities 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,
- Traveling salesman problem (TSP),
- Expanding neighborhood search (ENS),
- Path-relinking,
- Path planning,
- Cuboid

FullText(HTML)

References(15)

References

F. Greco, Traveling Salesman Problem, InTech Publisher, Vienna,Austria, pp.75-96, 2008.

F. Glover, G.A. Kochenberger, Handbook of Metaheuristics,Kluwer Academic Publishers, Boston, pp.1-36, 2003.

C. Mehmet, M.Y. Özsağlam, “A comparative study on particleswarm optimization and genetic algorithms for traveling salesmanproblems”, Cybernetics and Systems, Vol.40, No.6, pp.490-507, 2009.

A.W. Mohemmed, N.C. Sahoo, T.K. Geok, “Solving shortestpath problem using particle swarm optimization”, Applied SoftComputing, Vol.8, No.4, pp.1643-1653, 2008.

E.F.G. Goldbarg, G.R. de Souza, M.C. Goldbarg, “Particleswarm for the traveling salesman problem”, Lecture Notes inComputer Science, Vol.3906, pp.99-110, 2006.

S.B. Su, S.H. Yu, Y. Ma et al., “Routing on a spherical surfaceusing hybrid PSO”, Communications in Computer and InfromationScience, Vol.237, pp.45-51, 2011.

D. Eppstein, “TSP for cubic graphs”, Journal of Graph Algorithmand Applications, Vol.11, No.1, pp.61-81, 2007.

H.B. Duan, Y.X. Yu, X.Y. Zhang et al., “Three-dimension pathplanning for UCAV using hybrid meta-heuristic ACO-DE algorithm”,Simulation Modeling Practice and Theory, Vol.18,No.8, pp.1104-1115, 2010.

A. Uğur, “Path planning on a cuboid using genetic algorithms”,Information Sciences, Vol.178, No.16, pp.3275-3287, 2008.

S.B. Su, X.B. Cao, M. Kong, “Stability analysis of particleswarm optimization using swarm activity”, Control Theory andApplications, Vol.27, No.10, pp.1411-1417, 2010.

W.N. Chen, J. Zhang, H.S. Chung et al., “A novel set-basedparticle swarm optimization method for discrete optimizationproblems”, IEEE Transactons on Evolutionary Computation,Vol.14, No.2, pp.278-300, 2010.

S. Consoli, J.A. Moreno-Pérez, K. Darby-Dowman et al., “Discreteparticle swarm optimization for the minimum labelingsteiner tree problem”, Natural Computing, Vol.9, No.1, pp.29-46, 2009.

J.H. Hao, M. Liu, C. Wu, “Particle swarm optimization for parallelmachine scheduling problem with machine eligibility constraints”,Chinese Journal of Electronics, Vol.19, No.1, pp.103-106, 2010.

Y. Marinakis, M. Marinaki, G. Dounias, “A hybrid particleswarm optimization algorithm for the vehicle routing problem”,Engineering Applications of Artificial Intelligence, Vol.23, No.4,pp.463-472, 2010.

P. Hansen, N. Mladenovic, “Variable Neighborhood search:principles and applications”, European Journal of OperationalResearch, Vol.130, No.3, pp.449-467, 2001.

Relative Articles

Supplements(0)

Cited By

Proportional views