建模
第16卷第1期2005年3月
中国计量学院学报
JournalofChinaJiliangUniversity
Vol.16No.1Mar.2005
【文章编号】 100421540(2005)0120066206
用模拟退火算法解旅行商问题
孙燮华
(中国计量学院信息工程学院,浙江杭州310018)
【摘 要】 对解旅行商问题的模拟退火算法作了改进,增加了产生新解的函数,修改了原算法计算旅行回路总长度的代价函数,并用混沌随机序列替代不适宜的随机函数Λ从而用TurboC实现了改进算法Λ实验表明,改进算法对于解旅行商问题是实用的Λ【关键词】 旅行商问题;模拟退火算法;解法
【中图分类号】 TP301.6 【文献标识码】 A
Solvingtravelingsalesmanproblembysimulatedannealingalgorithm
SUNXie2hua
(CollegeofInformationEngineering,ChinaJiliangUniversity,Hangzhou310018,China)
Abstract:Thispaperimprovesthesimulatedannealingalgorithmforsolvingtravelingsalesmanproblem(TSP).WeaddadifferentmethodforproducingnewsolutionsofTSP,andrevisethecorrespondingfunc2tionforcomputingthelength.UsingTurboC,wecompletetheprogramforsolvingTSP.Runningthepro2.gramindicatestheimprovedalgorithmisuseful
Keywords:travelingsalesmanproblem;simulatedannealingalgorithm;solution
旅行商问题,也称为货郎担问题Λ问题简述如下Λ
旅行商问题(TravelingSalesmanProblem,简称TSP)已知n个城市之间的相互距离Ζ现有一个推销员必须遍访这n个城市,并且每个城市只能访问一次,最后必须返回出发城市Ζ如何安排这些城市的访问顺序,使旅行线路的总长度最短Ζ若
【收稿日期】 2004211211
对于城市V={s1,s2,s3,…,sn}的一个访问顺序为
T=(t1,t2,t3,…,tn),其中ti∈V(i=1,2,…,n).
约定tn+1=t1,则旅行商问题的数学模型为
n
minL=
∑d(t,t
i
i=1
i+1
),
这里dtiti+1为城市ti与ti+1之间的距离Ζ
旅行商问题是一个典型的组合优化问题,并
【作者简介】 孙燮华(1945-),男,浙江嘉兴人,教授Λ主要研究方向为计算机图形学、图象处理、算法分析等Λ
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入会员!获取文档下载券 用模拟退火算法求解旅行商问题 用模拟退火...
拟退火算法的形成原理、算法步骤和求解旅行商问题,重...
2005 【 文章编号】 1004-1540( 2005) 01-0066-06 用模拟退火算法解旅行商问题孙燮华 ( 中国计量学院 信息工程学院 , 浙江 杭州 310018) 【摘要】 对解旅行...
13 I 基于模拟退火算法的旅行商问题求解光信息科学与技术 指导教师 董铸祥 张明强 摘要: 易于描述却难以处理的 NP 难题, 其可能的路径 摘要 旅行商问题是组合...
维普资讯 http://www.cqvip.com 曲 晓丽 等 : 行商 问题 的一种 模拟 退火算 法求解 旅 旅行商问题的一种模拟退火算法求解 曲晓丽 . 潘 昊 , 向斌 ....
旅行商问题的一种模拟退火算法求解_理学_高等教育_教育专区。算法软件技术 曲晓丽等 : 旅行商问题的一种模拟退火算法求解 旅行商问题的一种模拟退火算法求解曲...
模拟退火与蚁群混合并行算法解旅行商问题_专业资料。求解TSP问题的智能优化算法主要包括蚁群算法和模拟退火算法等,这些算法求解TSP问题的速度比传统的精确求解算法有...
基于模拟退火算法的旅行商问题的实现_专业资料。旅行商问题TSP是一类典型的NP完全问题.围绕着这个问题有各种不同的求解方法,已有的算法例如动态规划法、分支限界法...
基于模拟退火算法的旅行商问题的实现摘 要: 主要介绍了模拟退火算法的原理以及应用,并且将遗传算法应用于解决旅行商问题。关键词:模拟退火算法 中图分类号: 旅行商...
求解旅行商问题的模拟退火算法_理学_高等教育_教育专区。旅行商问题借助matlab的讲义,很不错的!第17 卷第 3 期 2003 年 06 月 华 ( 自然科学版) 东船舶...
热门文档