A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 13 Issue 10
Oct.  2026

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 18.3, Top 1 (SCI Q1)
    CiteScore: 28.2, Top 1% (Q1)
    Google Scholar h5-index: 95， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2026  >  13(10): 2327-2342
C. Yue, Y. Shen, J. Liang, B. Qu, and M. Yu, “A weight-guided multimodal multiobjective ant colony optimization algorithm for traveling salesman problems,” IEEE/CAA J. Autom. Sinica, vol. 13, no. 10, pp. 2327–2342, Oct. 2026. doi: 10.1109/JAS.2026.125924
Citation: C. Yue, Y. Shen, J. Liang, B. Qu, and M. Yu, “A weight-guided multimodal multiobjective ant colony optimization algorithm for traveling salesman problems,” IEEE/CAA J. Autom. Sinica, vol. 13, no. 10, pp. 2327–2342, Oct. 2026. doi: 10.1109/JAS.2026.125924
shu

A Weight-Guided Multimodal Multiobjective Ant Colony Optimization Algorithm for Traveling Salesman Problems

doi: 10.1109/JAS.2026.125924
Funds:  This work was supported in part by the National Natural Science Foundation of China (62473340, 62306285, U23A20340, 62373389), the National Key Research and Development Program of China (2022YFD2001200), the Natural Science Foundation of Henan (242300421004, 242300421168, 241111210100), the Science and Technology Innovation Team of Colleges and Universities in Henan Province (23IRTSTHN010, 22IRTSTHN015), the Key Laboratory of Big Data Intelligent Computing, Chongqing University of Posts and Telecommunications Open Foundation (BDIC-2023-A-007), the Leading Talents of Science and Technology in the Central Plain of China (254000510055), and the China Postdoctoral Science Foundation (2023TQ0318, GZC20232397)
More Information
    Abstract
  • In practical applications, the traveling salesman problem (TSP) usually has both multimodal and multiobjective characteristics. The multimodal multiobjective traveling salesman problem (MMTSP) presents greater challenges than traditional single-objective TSP, owing to the need for simultaneous optimization of conflicting objectives and identification of diverse Pareto-optimal solutions. To address the above challenges, this study investigates MMTSP and proposes a weight-guided multimodal multiobjective ant colony optimization algorithm (WGACO). First, aiming at optimizing multiple objectives, a solution construction strategy based on weight decomposition is designed. The strategy divides the population into multiple subpopulations based on weights, with each subpopulation sharing a probability matrix, thereby enhancing the diversity of the population. Second, in order to explore more multimodal solutions, the initial population is optimized by combining the 2-opt local search, thereby effectively improving the quality of the solutions and mining multimodal characteristics. Finally, an individual selection mechanism based on dynamic archiving is proposed to optimize the evolutionary direction of pheromone update. This archive utilizes crowding distances to enhance the diversity of the objective space. Meanwhile, the distance in the decision space is measured by evaluating the similarity of edges between different solutions, thereby enhancing the diversity in decision space. Individuals participating in pheromone updates will be screened from this archive. Extensive experiments and validations on 40 test problems of different scales demonstrate that the proposed algorithm demonstrates superior optimization capability in solving MMTSP problems.

     

    • FullText(HTML)
  • loading
    • References(59)
  • [1]
    K. Ilavarasi and K. S. Joseph, “Variants of travelling salesman problem: A survey,” in Proc. Int. Conf. Information Communication and Embedded Systems, Chennai, India, 2014, pp. 1−7.
    [2]
    G. Reinelt, “TSPLIB—A traveling salesman problem library,” ORSA J. Comput., vol. 3, no. 4, pp. 376−384, Nov. 1991.
    [3]
    A. F. Alkaya and E. Duman, “Application of sequence-dependent traveling salesman problem in printed circuit board assembly,” IEEE Trans. Compon. Packag. Manuf. Technol., vol. 3, no. 6, pp. 1063−1076, Jun. 2013. doi: 10.1109/TCPMT.2013.2252429
    [4]
    C. Ding, Y. Cheng, and M. He, “Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs,” Tsinghua Sci. Technol., vol. 12, no. 4, pp. 459−465, Aug. 2007.
    [5]
    H. Mansouri, K. Elkhanchouli, N. Elghouate, A. Bencherqui, M. A. Tahiri, H. Karmouni, M. Sayyouri, H. Moustabchir, S. S. Askar, and M. Abouhawwash, “A modified black-winged kite optimizer based on chaotic maps for global optimization of real-world applications,” Knowledge-Based Syst., vol. 318, Art. no. 113558, Jun. 2025. doi: 10.1016/j.knosys.2025.113558
    [6]
    M. Reda, A. Onsy, M. A. Elhosseini, A. Y. Haikal, and M. Badawy, “A discrete variant of cuckoo search algorithm to solve the travelling salesman problem and path planning for autonomous trolley inside warehouse,” Knowledge-Based Syst., vol. 252, Art. no. 109290, Sep. 2022. doi: 10.1016/j.knosys.2022.109290
    [7]
    K. Zhao, X. Sui, J. Liang, C. Yue, G. Li, and K. Yu, “Multi-sensor planning and scheduling of dual unmanned flight platforms,” J. Zhengzhou Univ. Eng. Sci., vol. 44, no. 4, pp. 67−73, Jul. 2023.
    [8]
    T. Huang, Y. Gong, Y. Zhang, Z. Zhan, and J. Zhang, “Automatic planning of multiple itineraries: A niching genetic evolution approach,” IEEE Trans. Intell. Transp. Syst., vol. 21, no. 10, pp. 4225−4240, Oct. 2020. doi: 10.1109/TITS.2019.2939224
    [9]
    J. Wang, Y. Zhou, Y. Wang, J. Zhang, C. L. P. Chen, and Z. Zheng, “Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: Formulation, instances, and algorithms,” IEEE Trans. Cybern., vol. 46, no. 3, pp. 582−594, Mar. 2016. doi: 10.1109/TCYB.2015.2409837
    [10]
    B. Y. Qu, Y. S. Zhu, Y. C. Jiao, M. Y. Wu, P. N. Suganthan, and J. J. Liang, “A survey on multi-objective evolutionary algorithms for the solution of the environmental/economic dispatch problems,” Swarm Evol. Comput., vol. 38, pp. 1−11, Feb. 2018.
    [11]
    T. Lust and J. Teghem, “The multiobjective traveling salesman problem: A survey and a new approach,” in Advances in Multi-Objective Nature Inspired Computing, C. A. C. Coello, C. Dhaenens, and L. Jourdan, Eds. Berlin, Germany: Springer, 2010, pp. 119−141.
    [12]
    V. A. Shim, K. C. Tan, and C. Y. Cheong, “A hybrid estimation of distribution algorithm with decomposition for solving the multiobjective multiple traveling salesman problem,” IEEE Trans. Syst., Man, Cybern. Part C Appl. Rev., vol. 42, no. 5, pp. 682−691, Sep. 2012. doi: 10.1109/TSMCC.2012.2188285
    [13]
    J. Liang, Y. Zhang, K. Chen, B. Qu, K. Yu, C. Yue, and P. N. Suganthan, “An evolutionary multiobjective method based on dominance and decomposition for feature selection in classification,” Sci. China Inf. Sci., vol. 67, no. 2, Art. no. 120101, Jan. 2024. doi: 10.1007/s11432-023-3864-6
    [14]
    C. Yue, J. Liang, B. Qu, K. Yu, Y. Wang, and Y. Hu, “A survey on multimodal multiobjective optimization,” Control Decis., vol. 36, no. 11, pp. 2577−2588, Nov. 2021.
    [15]
    Y. Liu, L. Xu, Y. Han, X. Zeng, G. G. Yen, and H. Ishibuchi, “Evolutionary multimodal multiobjective optimization for traveling salesman problems,” IEEE Trans. Evol. Comput., vol. 28, no. 2, pp. 516−530, Apr. 2024.
    [16]
    J. Liang, H. Lin, C. Yue, P. N. Suganthan, and Y. Wang, “Multiobjective differential evolution for higher-dimensional multimodal multiobjective optimization,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 6, pp. 1458−1475, Jun. 2024. doi: 10.1109/JAS.2024.124377
    [17]
    S. Li, F. Wang, Q. He, and X. Wang, “Deep reinforcement learning for multi-objective combinatorial optimization: A case study on multi-objective traveling salesman problem,” Swarm Evol. Comput., vol. 83, Art. no. 101398, Dec. 2023.
    [18]
    M. R. Gholamian, S. M. T. F. Ghomi, and M. Ghazanfari, “A hybrid system for multiobjective problems—A case study in NP-hard problems,” Knowledge-Based Syst., vol. 20, no. 4, pp. 426−436, May 2007. doi: 10.1016/j.knosys.2006.06.007
    [19]
    I. D. Psychas, E. Delimpasi, and Y. Marinakis, “Hybrid evolutionary algorithms for the multiobjective traveling salesman problem,” Expert Syst. Appl., vol. 42, no. 22, pp. 8956−8970, Dec. 2015. doi: 10.1016/j.eswa.2015.07.051
    [20]
    Y. Liu, L. Xu, Y. Han, N. Masuyama, Y. Nojima, H. Ishibuchi, and G. G. Yen, “Multi-modal multi-objective traveling salesman problem and its evolutionary optimizer,” in Proc. IEEE Int. Conf. Systems, Man, and Cybernetics, Melbourne, Australia, 2021, pp. 770−777.
    [21]
    T. Zheng, J. Liu, Y. Jin, X. Wang, and Y. Liu, “Large-scale multimodal multiobjective optimization based on multiview diversity enhancement mechanism,” IEEE Trans. Evol. Comput., vol. 30, no. 4, pp. 1630−1644, Aug. 2026. doi: 10.1109/tevc.2025.3594189/mm1
    [22]
    Y. Liu, L. Zhang, X. Zeng, and Y. Han, “Evolutionary multimodal multiobjective optimization guided by growing neural gas,” Swarm Evol. Comput., vol. 86, Art. no. 101500, Apr. 2024.
    [23]
    T. Hu, X. Wang, L. Tang, and Q. Zhang, “A clustering-assisted adaptive evolutionary algorithm based on decomposition for multimodal multiobjective optimization,” Swarm Evol. Comput., vol. 91, Art. no. 101691, Dec. 2024.
    [24]
    Y. Wang, Z. Liu, and G.-G. Wang, “Improved differential evolution using two-stage mutation strategy for multimodal multi-objective optimization,” Swarm Evol. Comput., vol. 78, Art. no. 101232, Apr. 2023.
    [25]
    Y. Hu, J. Wang, J. Liang, Y. Wang, U. Ashraf, C. Yue, and K. Yu, “A two-archive model based evolutionary algorithm for multimodal multi-objective optimization problems,” Appl. Soft Comput., vol. 119, Art. no. 108606, Apr. 2022. doi: 10.1016/j.asoc.2022.108606
    [26]
    C. Yue, J. Song, J. Liang, M. Liu, K. Yu, H. Lin, and Y. Bi, “A multimodal multiobjective evolutionary algorithm based on neighborhood and enhanced special crowding distance,” Knowledge-Based Syst., vol. 315, Art. no. 113340, Apr. 2025. doi: 10.1016/j.knosys.2025.113340
    [27]
    A. S. Manne, “On the job-shop scheduling problem,” Oper. Res., vol. 8, no. 2, pp. 219−223, Mar.−Apr. 1960.
    [28]
    T. Guo, Y. Mei, M. Zhang, R. Sun, Y. Zhu, and W. Du, “Genetic programming with multifidelity surrogates for large-scale dynamic air traffic flow management,” IEEE Trans. Evol. Comput., vol. 29, no. 6, pp. 2671−2685, Dec. 2025. doi: 10.1109/tevc.2024.3512552/mm1
    [29]
    M. Xu, Y. Mei, F. Zhang, and M. Zhang, “Niching genetic programming to learn actions for deep reinforcement learning in dynamic flexible scheduling,” IEEE Trans. Evol. Comput., vol. 30, no. 1, pp. 61−75, Feb. 2026. doi: 10.1109/tevc.2024.3395699/mm1
    [30]
    X. Chen, R. Bai, R. Qu, J. Dong, and Y. Jin, “Deep reinforcement learning assisted genetic programming ensemble hyper-heuristics for dynamic scheduling of container port trucks,” IEEE Trans. Evol. Comput., vol. 29, no. 4, pp. 1371−1385, Aug. 2025.
    [31]
    Y. Liu, C. Gao, Z. Zhang, Y. Lu, S. Chen, M. Liang, and L. Tao, “Solving NP-hard problems with Physarum-based ant colony system,” IEEE/ACM Trans. Comput. Biol. Bioinf., vol. 14, no. 1, pp. 108−120, Jan.−Feb. 2017. doi: 10.1109/TCBB.2015.2462349
    [32]
    D. Angus, “Niching for population-based ant colony optimization,” in Proc. 2nd IEEE Int. Conf. e-Science and Grid Computing, Amsterdam, Netherlands, 2006, pp. 115.
    [33]
    X.-C. Han, H.-W. Ke, Y.-J. Gong, Y. Lin, W.-L. Liu, and J. Zhang, “Multimodal optimization of traveling salesman problem: A niching ant colony system,” in Proc. Genetic and Evolutionary Computation Conf. Companion, Kyoto, Japan, 2018, pp. 87−88.
    [34]
    P. Stodola, P. Otřísal, and K. Hasilová, “Adaptive ant colony optimization with node clustering applied to the travelling salesman problem,” Swarm Evol. Comput., vol. 70, Art. no. 101056, Apr. 2022.
    [35]
    I. D. I. D. Ariyasingha and T. G. I. Fernando, “Performance analysis of the multi-objective ant colony optimization algorithms for the traveling salesman problem,” Swarm Evol. Comput., vol. 23, pp. 11−26, Aug. 2015.
    [36]
    T. Huang, Y.-J. Gong, S. Kwong, H. Wang, and J. Zhang, “A niching memetic algorithm for multi-solution traveling salesman problem,” IEEE Trans. Evol. Comput., vol. 24, no. 3, pp. 508−522, Jun. 2020.
    [37]
    Y. Zhu, Y. Chen, and Z.-H. Fu, “Knowledge-guided two-stage memetic search for the pickup and delivery traveling salesman problem with FIFO loading,” Knowledge-Based Syst., vol. 242, Art. no. 108332, Apr. 2022. doi: 10.1016/j.knosys.2022.108332
    [38]
    S.-J. Jian and S.-Y. Hsieh, “A niching regression adaptive memetic algorithm for multimodal optimization of the Euclidean traveling salesman problem,” IEEE Trans. Evol. Comput., vol. 27, no. 5, pp. 1413−1426, Oct. 2023.
    [39]
    A. Hamza, A. H. Darwish, and O. Rihawi, “A new local search for the bees algorithm to optimize multiple traveling salesman problem,” Intell. Syst. Appl., vol. 18, Art. no. 200242, May 2023. doi: 10.2139/ssrn.4174344
    [40]
    D. Nuraiman, F. Ilahi, Y. Dewi, and E. A. Z. Hamidi, “A new hybrid method based on nearest neighbor algorithm and 2-opt algorithm for traveling salesman problem,” in Proc. 4th Int. Conf. Wireless and Telematics, Nusa Dua, Indonesia, 2018, pp. 1−4.
    [41]
    S. Chatterjee, C. Carrera, and L. A. Lynch, “Genetic algorithms and traveling salesman problems,” Eur. J. Oper. Res., vol. 93, no. 3, pp. 490−510, Sep. 1996. doi: 10.1016/0377-2217(95)00077-1
    [42]
    J. Wang, O. K. Ersoy, M. He, and F. Wang, “Multi-offspring genetic algorithm and its application to the traveling salesman problem,” Appl. Soft Comput., vol. 43, pp. 415−423, Jun. 2016. doi: 10.1016/j.asoc.2016.02.021
    [43]
    P. Zhang, J. Wang, Z. Tian, S. Sun, J. Li, and J. Yang, “A genetic algorithm with jumping gene and heuristic operators for traveling salesman problem,” Appl. Soft Comput., vol. 127, Art. no. 109339, Sep. 2022. doi: 10.1016/j.asoc.2022.109339
    [44]
    Y. Wang, “The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem,” Comput. Ind. Eng., vol. 70, pp. 124−133, Apr. 2014. doi: 10.1016/j.cie.2014.01.015
    [45]
    S. K. R. Kanna, K. Sivakumar, and N. Lingaraj, “Development of deer hunting linked earthworm optimization algorithm for solving large scale traveling salesman problem,” Knowledge-Based Syst., vol. 227, Art. no. 107199, Sep. 2021. doi: 10.1016/j.knosys.2021.107199
    [46]
    T. Huang, Y.-J. Gong, and J. Zhang, “Seeking multiple solutions of combinatorial optimization problems: A proof of principle study,” in Proc. IEEE Symp. Series on Computational Intelligence, Bangalore, India, 2018, pp. 1212−1218.
    [47]
    C. Yue, Y. Shen, J. Liang, K. Yu, M. Li, T. Ma, and H. Song, “Hierarchical genetic algorithm for the multi-solution traveling salesman problem,” IEEE Trans. Evol. Comput., vol. 30, no. 2, pp. 732−746, Apr. 2026. doi: 10.1109/tevc.2025.3565947/mm1
    [48]
    T. Huang, Z.-Q. Zhang, Y.-J. Gong, and J. Liu, “nLKH-ACS: A niching Lin-Kernighan-Helsgaun-based ant colony system for multisolution traveling salesman problems,” IEEE Trans. Evol. Comput., vol. 29, no. 6, pp. 2596−2610, Dec. 2025.
    [49]
    L. Ke, Q. Zhang, and R. Battiti, “MOEA/D-ACO: A multiobjective evolutionary algorithm using decomposition and AntColony,” IEEE Trans. Cybern., vol. 43, no. 6, pp. 1845−1859, Dec. 2013. doi: 10.1109/TSMCB.2012.2231860
    [50]
    X. Cai, Y. Li, Z. Fan, and Q. Zhang, “An external archive guided multiobjective evolutionary algorithm based on decomposition for combinatorial optimization,” IEEE Trans. Evol. Comput., vol. 19, no. 4, pp. 508−523, Aug. 2015.
    [51]
    R. Morante-González, A. D. López-Sánchez, J. Sánchez-Oro, and A. G. Hernández-Díaz, “The multiobjective traveling salesman−repairman problem with profits: Design and implementation of a variable neighborhood descent algorithm for a real scenario,” Int. Trans. Oper. Res., vol. 32, no. 1, pp. 221−243, Jan. 2025. doi: 10.1111/itor.13407
    [52]
    X. Zheng, B. Han, and Z. Ni, “Tourism route recommendation based on a multi-objective evolutionary algorithm using two-stage decomposition and Pareto layering,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 2, pp. 486−500, Feb. 2023. doi: 10.1109/JAS.2023.123219
    [53]
    Y. Nagata, “New EAX crossover for large TSP instances,” in Proc. 9th Int. Conf. Parallel Problem Solving from Nature, Reykjavik, Iceland, 2006, pp. 372−381.
    [54]
    Y. Nagata, “Fast EAX algorithm considering population diversity for traveling salesman problems,” in Proc. 3rd European Conf. Evolutionary Computation in Combinatorial Optimization, Budapest, Hungary, 2006, pp. 171−182.
    [55]
    Y. Nagata and S. Kobayashi, “A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem,” INFORMS J. Comput., vol. 25, no. 2, pp. 346−363, Apr. 2013. doi: 10.1287/ijoc.1120.0506
    [56]
    R. I. Bolaños, M. G. Echeverry, and J. W. Escobar, “A multiobjective non-dominated sorting genetic algorithm (NSGA-II) for the multiple traveling salesman problem,” Decis. Sci. Lett., vol. 4, no. 4, pp. 559−568, 2015. doi: 10.5267/j.dsl.2015.5.003
    [57]
    J. J. Grefenstette, R. Gopal, B. J. Rosmaita, and D. Van Gucht, “Genetic algorithms for the traveling salesman problem,” in Proc. 1st Int. Conf. Genetic Algorithms, Broadway Hillsdale, USA, 1985, pp. 160−168.
    [58]
    K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182−197, Apr. 2002.
    [59]
    Y. Liu, G. G. Yen, and D. Gong, “A multimodal multiobjective evolutionary algorithm using two-archive and recombination strategies,” IEEE Trans. Evol. Comput., vol. 23, no. 4, pp. 660−674, Aug. 2019.
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

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

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

    Figures(10)  / Tables(6)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (15) PDF downloads(1) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return