模拟退火算法求解TSP问题的MATLAB程序清单

用模拟退火算法求TSP问题的程序清单

中国各省会城市地理位置(经纬度).xls

城市 经度 纬度

北京 116.24 39.55

天津 117.12 39.02

郑州 114.3 34.46

太原 112.33 37.54

昆明 102.42 25.04 呼和浩特 111.41 40.48 长沙 112.59 28.12 武汉 114.17 30.35 重庆 106.54 29.59 兰州 103.51 36.04 福州 119.18 26.05 上海 121.27 31.14

广州 113.14 23.08

南宁 108.19 22.48

包头 110 40.58 长春 125.19 43.54 哈尔滨 126.36 45.44 深圳 114.3 22.62 香港 115.12 21.23 银川 106.16 38.27 石家庄 114.3 38.02 南京 118.46 32.03

南昌 115.55 28.4

沈阳 123.25 41.48

西安 108.57 34.17 济南 117 36.4 成都 104.04 30.4 西宁 101.48 36.38 合肥 117.17 31.52

海口 110.2 20.2

贵阳 106.42 26.35 杭州 120.1 30.16 台北 121.3 25.03

拉萨 91.08 29.39

澳门 115.07 21.33

地球半径R=6400千米;高度h=10千米。

(1)TSP——模拟退火主函数

function [Lujing,Changdu]=TSP_moni_tuihuo(R,d,dili_weizhi) T0=20000; Tf=1; err=1; Tol=1e-5; L=10000; alpha=0.95;

m=size(dili_weizhi,1); sequence=1:m; x0=sequence;

L0=Length_Route(R,d,dili_weizhi,x0); SEQUENCE=[]; while (T0>Tf) for i=1:L

x1=suiji_duihuan(sequence);

L1=Length_Route(R,d,dili_weizhi,x1); if L1

err=L1-L0;

gailv_accept=exp(-err/T0); if gailv_accept>rand x0=x1; L0=L1; end end

if abs(err)

SEQUENCE=[SEQUENCE;x0,L0]; T0=alpha*T0; end

Lujing=x0;Changdu=L0; for j=1:m

duiyingguanxi(x0(j)); end figure(1);

p=qiuji_touying(R,d,dili_weizhi); for j=1:m

p1(j,:)=p(x0(j),:);

end

p1=[p1;p1(1,1:2)];

plot(p1(:,1),p1(:,2),'*-');

(2)对换函数

function y=suiji_duihuan(sequence) L=length(sequence); suiji=rand(1,L); a=min(suiji); b=max(suiji);

a_index=find(suiji==a); b_index=find(suiji==b); c=find(sequence==a_index); d=find(sequence==b_index); t=sequence(c);

sequence(c)=sequence(d); sequence(d)=t; y=sequence; y;

(3)求路径长度函数

function y=Length_Route(R,d,dili_weizhi,sequence) city_distance=chengshi_juli(R,d,dili_weizhi); [m,n]=size(city_distance); sum=0; for i=1:m-1

sum=sum+city_distance(sequence(i),sequence(i+1)); end

sum=sum+city_distance(sequence(m),sequence(1)); y=sum;

(4)求城市距离函数

function y=chengshi_juli(R,d,dili_weizhi)

[m,n]=size(dili_weizhi);%m is the number of cities in China dili_weizhi=pi/180*dili_weizhi; city_distance=zeros(m); zuobiao=zeros(m,3); for i=1:m

zuobiao(i,1)=(R+d)*cos(dili_weizhi(i,2))*cos(dili_weizhi(i,1)); zuobiao(i,2)=(R+d)*cos(dili_weizhi(i,2))*sin(dili_weizhi(i,1)); zuobiao(i,3)=(R+d)*sin(dili_weizhi(i,2)); end for i=1:m for j=i+1:m

R0=R+d;

dot_ji=sum(zuobiao(i,:).*zuobiao(j,:)); city_distance(i,j)=R0*acos(dot_ji/(R0^2)); end end

city_distance=city_distance'+city_distance; y=city_distance; y;

(5)球极投影函数

function y=qiuji_touying(R,d,dili_weizhi)

[m,n]=size(dili_weizhi);%m is the number of cities in China dili_weizhi=pi/180*dili_weizhi; city_distance=zeros(m); zuobiao=zeros(m,3); for i=1:m

zuobiao(i,1)=(R+d)*cos(dili_weizhi(i,2))*cos(dili_weizhi(i,1)); zuobiao(i,2)=(R+d)*cos(dili_weizhi(i,2))*sin(dili_weizhi(i,1)); zuobiao(i,3)=(R+d)*sin(dili_weizhi(i,2)); end

qiuji_zuobiao=zeros(m,2); for i=1:m

qiuji_zuobiao(i,1)=(R+d)*zuobiao(i,1)/(R+d-zuobiao(i,3)); qiuji_zuobiao(i,2)=(R+d)*zuobiao(i,2)/(R+d-zuobiao(i,3)); end

y=qiuji_zuobiao/100;

(6)对应关系函数

function y=duiyingguanxi(s) switch s case 1

disp('北京') case 2

disp('天津') case 3 disp('郑州') case 4 disp('太原') case 5

disp('昆明') case 6

disp('呼和浩特') case 7

disp('长沙') case 8

disp('武汉') case 9 disp('重庆') case 10 disp('兰州') case 11 disp('福州') case 12 disp('上海') case 13 disp('广州') case 14 disp('南宁') case 15 disp('包头') case 16 disp('长春') case 17

disp('哈尔滨') case 18 disp('深圳') case 19 disp('香港') case 20

disp(' 银川') case 21

disp('石家庄') case 22 disp('南京') case 23 disp('南昌') case 24

disp('沈阳') case 25 disp('西安') case 26 disp('济南') case 27 disp('成都') case 28 disp('西宁') case 29 disp('合肥') case 30

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4