Volume 22 Issue 1
Turn off MathJax
Article Contents
Abstract
References
Related Articles
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.
shu

Jumping PSO with Expanding Neighborhood Search for TSP on a Cuboid

  • 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).
More Information
  • Received Date: October 31, 2011
  • Revised Date: January 31, 2012
  • Published Date: January 04, 2013
    Graphical 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.
    • FullText(HTML)
    • References (15)
  • 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.
    • Related Articles

  • Related Articles

    [1]Li Tong, Ma Zhuangzhuang, Shao Jinliang, Zhao Yuan, Zhang Xilin, Cheng Yuhua. Path Planning for Unmanned Aerial Vehicle Swarm Based on Electromagnetic Environment Sensing[J]. Chinese Journal of Electronics. DOI: 10.23919/cje.2024.00.088
    [2]WEN Tao, YANG Daichuan, LIU Weifeng, WEN Chenglin, CAI Baigen. A Novel Integrated Path Planning Algorithm for Warehouse AGVs[J]. Chinese Journal of Electronics, 2021, 30(2): 331-338. DOI: 10.1049/cje.2021.02.002
    [3]HUANG Dongjin, TANG Pengbin, WANG Yin, LI Hejuan, TANG Wen, DING Youdong. Computer-Assisted Path Planning for Minimally Invasive Vascular Surgery[J]. Chinese Journal of Electronics, 2018, 27(6): 1241-1249. DOI: 10.1049/cje.2018.09.002
    [4]GENG Kui, LI Fenghua, CAO Jin, LI Hui, CHEN Chen, ZHANG Cui. A Trustworthy Path Discovery Mechanism in Ubiquitous Networks[J]. Chinese Journal of Electronics, 2016, 25(2): 312-319. DOI: 10.1049/cje.2016.03.018
    [5]ZHANG Wenbo, LIU Weidong, SONG Jiaxing. Virtual Path Based Routing Scheme for UWASN[J]. Chinese Journal of Electronics, 2013, 22(3): 572-576.
    [6]LIU Changan, YAN Xiaohu, LIU Chunyang, WU Hua. The Wolf Colony Algorithm and Its Application[J]. Chinese Journal of Electronics, 2011, 20(2): 212-216.
    [7]YUAN Zhaohui, SUN Shilei, WANG Gaofeng. Efficient Scheme for Path Recognition fromIntegrated Circuit Layout[J]. Chinese Journal of Electronics, 2010, 19(4): 627-630.
    [8]LIU Changan, YAN Xiaohu, LIU Chunyang and LI Guodong. Dynamic Path Planning for Mobile Robot Basedon Improved Genetic Algorithm[J]. Chinese Journal of Electronics, 2010, 19(2): 245-248.
    [9]LIU Changan, CHANG Jingang, LIU Chunyang. Path Planning for Mobile Robot Based on an Improved Probabilistic Roadmap Method[J]. Chinese Journal of Electronics, 2009, 18(3): 395-399.
    [10]CHEN Weishi, NING Huansheng, LI Jing, MAO Xia, WANG Baofa. Flight Path Detection of Bird Targets in RadarImages[J]. Chinese Journal of Electronics, 2009, 18(1): 192-194.

Catalog

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (770) PDF downloads (1551) Cited by()
    Related

    Links

    IEEE CJE Homepage CNKI Chinese Institute of Electronics Journal of Semiconductors
    E-mail Alert RSS

    Chinese Journal of Electronics

    (Bimonthly)

    ISSN    1022-4653CN  10-1284/TN

    eISSN  2075-5597CODEN CHJEEW

    CJE QR CODE

    CIE QR CODE

    Copyright © Editorial Office of Chinese Journal of Electronics | 京ICP备12041980号-1 | Supported by: Beijing Renhe Information Technology Co., Ltd.  Baidu Analytics

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return