文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 人文社科 > 社会学 > 用模拟退火算法解旅行商问题
侵权投诉

用模拟退火算法解旅行商问题

建模

第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-),男,浙江嘉兴人,教授Λ主要研究方向为计算机图形学、图象处理、算法分析等Λ

第1页

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email