ScholarMate
English简体中文繁體中文
客服热线:400-1616-289
登录注册
期刊论文

Multi-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems

Zhou, Yangming; Xu, Wenqiang; Fu, Zhang-Hua; Zhou, MengChu*华东理工大学; 上海交通大学
IEEE Transactions on Intelligent Transportation Systems2022-9DOI: 10.1109/TITS.2022.3147924
58被引3阅读
引用收藏
分享

摘要

A coloring traveling salesman problem (CTSP) generalizes the well-known multiple traveling salesman problem, where colors are used to differentiate salesmen's the accessibility to individual cities to be visited. As a useful model for a variety of complex scheduling problems, CTSP is computationally challenging. In this paper, we propose a Multi-neighborhood Simulated Annealing-based Iterated Local Search (MSAILS) to solve it. Starting from an initial solution, it iterates through three sequential search procedures: a multi-neighborhood simulated annealing search to find a local optimum, a local search-enhanced edge assembly crossover to find nearby high-quality solutions around a local optimum, and a solution reconstruction procedure to move away from the current search region. Experimental results on two groups of 45 medium and large benchmark instances show that it significantly outperforms state-of-the-art algorithms. In particular, it is able to discover new upper bounds for 29 instances while matching 8 previous best-known upper bounds. Hence, this work greatly advances the field of CTSP.

学科与关键词

关键词
Urban areasColorTraveling salesman problemsSimulated annealingBiological cellsUpper boundRobotsMulti-neighborhood searchsimulated annealingiterated local searchcolored traveling salesman problem
相关
加载中…
  • Iterated two-phase local search for the colored traveling salesmen problem
    He, Pengfei; Hao, Jin-Kao*ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2021, 97: 104018.被引 14
  • Bi-Objective Colored Traveling Salesman Problems
    Xu, Xiangping; Li, Jun*; Zhou, MengChuIEEE Transactions on Intelligent Transportation Systems, 2022, 23(7): 6326-6336.被引 17
  • Precedence-Constrained Colored Traveling Salesman Problem: An Augmented Variable Neighborhood Search Approach
    Xu, Xiangping; Li, Jun*; Zhou, Mengchu; Yu, XinghuoIEEE Transactions on Cybernetics, 2022, 52(9): 9797-9808.被引 17
查看全部 →

发表信息

论文状态
公开发表
期刊
IEEE Transactions on Intelligent Transportation Systems
发表日期
2022-09
卷期
第 23 卷, 第 9 期
页码
16072-16082
DOI
10.1109/TITS.2022.3147924
语言
ENGLISH
期刊等级
1区
成果收录
SCIE
资助标注
Fundo Para o Desenvolvimento das Ciencias da Tecnologia (FDCT) [0047/2021/A1]; National Natural Science Foundation of China [61903144]; Shanghai Sailing Program [19YF1412400]; Macau Young Scholars Program [AM2020011]; Open Project of the Shenzhen Institute of Artificial Intelligence and Robotics for Society [AC01202005002]

作者

  • Z

    Zhou, Yangming (第一作者)

    shanghai jiao tong univ

  • X

    Xu, Wenqiang

    east china univ sci & technol

查看全部 4 位作者收起作者
  • F

    Fu, Zhang-Hua

    chinese univ hong kong

  • Z

    Zhou, MengChu (通讯)

登录解锁更多功能

  • 收藏这篇,随时在“我的 · 收藏”找回
  • 认领你的成果,生成推广素材
  • 关注作者获取最新成果
  • 加入项目组、协同写作
注册 / 登录

产品服务

  • 科研之友
  • 创新城
  • 科创云

服务支持

  • 帮助中心
  • 隐私政策
  • 服务条款

联系方式

在线客服:【】
客服热线:400-1616-289
电子邮箱:support@scholarmate.com

关注或下载科研之友

微信二维码
微信公众号
客户端下载二维码
下载客户端
科研成果科研人员科研机构科研动态爱瑞思软件

©2026 深圳市科研之友网络服务有限公司

公安备案图标粤公网安备 44030502000213
粤ICP备 16046710 号粤B2-20110417