TSP问题数学模型的问题解法

1、途程建构法（Tour Construction Procedures）

从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：

2）节省法（Clark and Wright Saving）：以服务每一个纯哗节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。

3）插入法（Insertion procedures）：如插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。

2、途程改善法（Tour Improvement Procedure）

先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：

1）K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代路径中K条节线，并计算其成本尘裤穗（或距离），如果成本降低（距离减少），则取代之，派卜直到无法改善为止，K通常为2或3。

2）Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性。

3、合成启发法（Composite Procedure）

1）起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。 　 2）起始解求解+3-Opt：以途程建构法建立一个起始的解，再用3-Opt的方式改善途程，直到不能改善为止。

蚂蚁算法实现tsp。其中city是n行2列的矩阵，表示n个城市的经纬模旦度，iter_max是最大循环次数，其穗洞余是蚂蚁算法的参数。

function [Shortest_Route,Shortest_Length]=anttsp(city,iter_max,m,Alpha,Beta,Rho,Q)

n=size(city,1)

d=zeros(n,n)

d=squareform(pdist(city))

Eta=1./d

Tau=ones(n,n)

Tabu=zeros(m,n)

nC=1

R_best=zeros(iter_max,n)

L_best=inf.*ones(iter_max,1)

while nC<猜码枯=iter_max

route=[]

for i=1:ceil(m/n)

route=[route,randperm(n)]

end

Tabu(:,1)=(route(1,1:m))'

for j=2:n

for i=1:m

visited=Tabu(i,1:(j-1))

J=zeros(1,(n-j+1))

P=J

Jc=1

for k=1:n

if isempty(find(visited==k, 1))

J(Jc)=k

Jc=Jc+1

end

end

for k=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta)

end

P=P/(sum(P))

Pcum=cumsum(P)

Select=find(Pcum>=rand)

if isempty(Select)%是不是一定能保证Select不为空

Tabu(i,j)=round(1+(n-1)*rand)

else

next_visit=J(Select(1))

Tabu(i,j)=next_visit

end

end

end

if nC>=2

Tabu(1,:)=R_best(nC-1,:)

end

L=zeros(m,1)

for i=1:m

R=Tabu(i,:)

for j=1:(n-1)

L(i)=L(i)+d(R(j),R(j+1))

end

L(i)=L(i)+d(R(1),R(n))

end

L_best(nC)=min(L)

pos=find(L==L_best(nC))

R_best(nC,:)=Tabu(pos(1),:)

nC=nC+1

Delta_Tau=zeros(n,n)

for i=1:m

for j=1:(n-1)

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i)

end

Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i)

end

Tau=(1-Rho).*Tau+Delta_Tau

Tabu=zeros(m,n)

end

Pos=find(L_best==min(L_best))

Shortest_Route=R_best(Pos(1),:)

Shortest_Length=L_best(Pos(1))

end

该程序试图对具有31个城市的VRP进行求解，已知的最优解为784.1，我用该程序只能优化到810左右，返茄应该是陷入局部最优，但我不知问题出在什么地方。请用过蚁群算法的高手指教。

蚁群算法的matlab源码，同时请指出为何不能优化漏庆察到已知的最好解

%

%

%the procedure of ant colony algorithm for VRP

%

%%%%%%%%%%%

%initialize the parameters of ant colony algorithms

load data.txt

d=data(:,2:3)

g=data(:,4)

m=31% 蚂蚁数

alpha=1

belta=4% 决定tao和miu重要性的参数

lmda=0

rou=0.9%衰减系数

q0=0.95

% 概率

tao0=1/(31*841.04)%初始信息素

Q=1% 蚂蚁循环一周所释放的信息素

defined_phrm=15.0 % initial pheromone level value

QV=100 % 车辆容量

vehicle_best=round(sum(g)/QV)+1%所完成任务所需的最少车数

V=40

% 计算两点的距离

for i=1:32

for j=1:32

dist(i,j)=sqrt((d(i,1)-d(j,1))^2+(d(i,2)-d(j,2))^2)

end

end

%给tao miu赋初值

for i=1:32

for j=1:32

if i~=j

%s(i,j)=dist(i,1)+dist(1,j)-dist(i,j)

tao(i,j)=defined_phrm

miu(i,j)=1/dist(i,j)

end

end

end

for k=1:32

for k=1:32

deltao(i,j)=0

end

end

best_cost=10000

for n_gen=1:50

print_head(n_gen)

for i=1:m

%best_solution=[]

print_head2(i)

sumload=0

cur_pos(i)=1

rn=randperm(32)

n=1

nn=1

part_sol(nn)=1

%cost(n_gen,i)=0.0

n_sol=0 % 由蚂蚁产生的路径数量

M_vehicle=500

t=0 %最佳路径数组的元素数为0

while sumload<=QV

for k=1:length(rn)

if sumload+g(rn(k))<=QV

gama(cur_pos(i),rn(k))=(sumload+g(rn(k)))/QV

A(n)=rn(k)

n=n+1

end

end

fid=fopen('out_customer.txt','a+')

fprintf(fid,'%s %i\t','the current position is:',cur_pos(i))

fprintf(fid,'\n%s','the possible customer set is:')

fprintf(fid,'\t%i\n',A)

fprintf(fid,'差辩------------------------------\n')

fclose(fid)

p=compute_prob(A,cur_pos(i),tao,miu,alpha,belta,gama,lmda,i)

maxp=1e-8

na=length(A)

for j=1:na

if p(j)>maxp

maxp=p(j)

index_max=j

end

end

old_pos=cur_pos(i)

if rand(1)<q0

cur_pos(i)=A(index_max)

else

krnd=randperm(na)

cur_pos(i)=A(krnd(1))

bbb=[old_pos cur_pos(i)]

ccc=[1 1]

if bbb==ccc

cur_pos(i)=A(krnd(2))

end

end

tao(old_pos,cur_pos(i))=taolocalupdate(tao(old_pos,cur_pos(i)),rou,tao0)%对所经弧进行局部更新

sumload=sumload+g(cur_pos(i))

nn=nn+1

part_sol(nn)=cur_pos(i)

temp_load=sumload

if cur_pos(i)~=1

rn=setdiff(rn,cur_pos(i))

n=1

A=[]

end

if cur_pos(i)==1 % 如果当前点为车场,将当前路径中的已访问用户去掉后,开始产生新路径

if setdiff(part_sol,1)~=[]

n_sol=n_sol+1 % 表示产生的路径数,n_sol=1,2,3,..5,6...,超过5条对其费用加上车辆的派遣费用

fid=fopen('out_solution.txt','a+')

fprintf(fid,'%s%i%s','NO.',n_sol,'条路径是:')

fprintf(fid,'%i ',part_sol)

fprintf(fid,'\n')

fprintf(fid,'%s','当前的用户需求量是:')

fprintf(fid,'%i\n',temp_load)

fprintf(fid,'------------------------------\n')

fclose(fid)

% 对所得路径进行路径内3-opt优化

final_sol=exchange(part_sol)

for nt=1:length(final_sol)% 将所有产生的路径传给一个数组

temp(t+nt)=final_sol(nt)

end

t=t+length(final_sol)-1

sumload=0

final_sol=setdiff(final_sol,1)

rn=setdiff(rn,final_sol)

part_sol=[]

final_sol=[]

nn=1

part_sol(nn)=cur_pos(i)

A=[]

n=1

end

end

if setdiff(rn,1)==[]% 产生最后一条终点不为1的路径

n_sol=n_sol+1

nl=length(part_sol)

part_sol(nl+1)=1%将路径的最后1位补1

% 对所得路径进行路径内3-opt优化

final_sol=exchange(part_sol)

for nt=1:length(final_sol)% 将所有产生的路径传给一个数组

temp(t+nt)=final_sol(nt)

end

cost(n_gen,i)=cost_sol(temp,dist)+M_vehicle*(n_sol-vehicle_best) %计算由蚂蚁i产生的路径总长度

for ki=1:length(temp)-1

deltao(temp(ki),temp(ki+1))=deltao(temp(ki),temp(ki+1))+Q/cost(n_gen,i)

end

if cost(n_gen,i)<best_cost

best_cost=cost(n_gen,i)

old_cost=best_cost

best_gen=n_gen % 产生最小费用的代数

best_ant=i%产生最小费用的蚂蚁

best_solution=temp

end

if i==m %如果所有蚂蚁均完成一次循环，，则用最佳费用所对应的路径对弧进行整体更新

for ii=1:32

for jj=1:32

tao(ii,jj)=(1-rou)*tao(ii,jj)

end

end

for kk=1:length(best_solution)-1

tao(best_solution(kk),best_solution(kk+1))=tao(best_solution(kk),best_solution(kk+1))+deltao(best_solution(kk),best_solution(kk+1))

end

end

fid=fopen('out_solution.txt','a+')

fprintf(fid,'%s%i%s','NO.',n_sol,'路径是:')

fprintf(fid,'%i ',part_sol)

fprintf(fid,'\n')

fprintf(fid,'%s %i\n','当前的用户需求量是:',temp_load)

fprintf(fid,'%s %f\n','总费用是:',cost(n_gen,i))

fprintf(fid,'------------------------------\n')

fprintf(fid,'%s\n','最终路径是:')

fprintf(fid,'%i-',temp)

fprintf(fid,'\n')

fclose(fid)

temp=[]

break

end

end

end

end

我现在也在研究它,希望能共同进步.建义可以看一下段海滨的关于蚁群算法的书.讲的不错,李士勇的也可以,还有一本我在图书馆见过,记不得名字了.

---