SU Shoubao, CAO Xibin. Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid[J]. Chinese Journal of Electronics, 2013, 22(1): 202-208.
Citation: SU Shoubao, CAO Xibin. Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid[J]. Chinese Journal of Electronics, 2013, 22(1): 202-208.

Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid

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
  • 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.
  • loading
  • 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.
  • 加载中


    通讯作者: 陈斌,
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (445) PDF downloads(1547) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint