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

Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search

Geng, Xiutang*; Chen, Zhihua; Yang, Wei; Shi, Deqian; Zhao, Kai华中科技大学
APPLIED SOFT COMPUTING2011-6DOI: 10.1016/j.asoc.2011.01.039
158被引3阅读
引用收藏
分享

摘要

The traveling salesman problem (TSP) is a classical problem in discrete or combinatorial optimization and belongs to the NP-complete classes, which means that it may be require an infeasible processing time to be solved by an exhaustive search method, and therefore less expensive heuristics in respect to the processing time are commonly used in order to obtain satisfactory solutions in short running time. This paper proposes an effective local search algorithm based on simulated annealing and greedy search techniques to solve the TSP. In order to obtain more accuracy solutions, the proposed algorithm based on the standard simulated annealing algorithm adopts the combination of three kinds of mutations with different probabilities during its search. Then greedy search technique is used to speed up the convergence rate of the proposed algorithm. Finally, parameters such as cool coefficient of the temperature, the times of greedy search, and the times of compulsive accept and the probability of accept a new solution, are adaptive according to the size of the TSP instances. As a result, experimental results show that the proposed algorithm provides better compromise between CPU time and accuracy among some recent algorithms for the TSP.

学科与关键词

关键词
Simulated annealingGreedy searchTraveling salesman problemAdaptiveCombinatorial optimizationHeuristic
相关
加载中…
  • An Effective Simulated Annealing Algorithm for Solving the Traveling Salesman Problem
    Wang, Zicheng; Geng, Xiutang; Shao, Zehui*Journal of Computational and Theoretical Nanoscience, 2009, 6(7): 1680-1686.被引 27
  • An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem
    Du, Pengzhen*; Liu, Ning; Zhang, Haofeng; Lu, JianfengJOURNAL OF ADVANCED TRANSPORTATION, 2021, 2021: 6642009.被引 11
  • A Novel Sparrow Search Algorithm for the Traveling Salesman Problem
    Wu, Changyou*; Fu, Xisong; Pei, Junke; Dong, ZhiguiIEEE Access, 2021, 9: 153456-153471.被引 49
查看全部 →

发表信息

论文状态
公开发表
期刊
APPLIED SOFT COMPUTING
发表日期
2011-06
卷期
第 11 卷, 第 4 期
页码
3680-3689
DOI
10.1016/j.asoc.2011.01.039
语言
ENGLISH
成果收录
SCIE
资助标注
National Natural Science Foundation of China [60803113, 60373089, 60674106, 60533010]; National High Technology Research and Development Program of China [2009AA012413]

作者

  • G

    Geng, Xiutang (通讯) (第一作者)

  • C

    Chen, Zhihua

    huazhong univ sci & technol

查看全部 5 位作者收起作者
  • Y

    Yang, Wei

  • S

    Shi, Deqian

  • Z

    Zhao, Kai

登录解锁更多功能

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

产品服务

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

服务支持

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

联系方式

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

关注或下载科研之友

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

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

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