mip_tsp.m

利用lindoapi借口在matlab中调用lindoapi中的函数

function [x_t,x_d,n]=MIP_TSP(distance,time)
%--------------------------------混合整数规划求最优解


n=length(distance);
for i=1:n
    distance(i,i)=90000;
    time(i,i)=90000;
    for j=i+1:n
        distance(i,j)=distance(j,i);
        time(i,j)=time(j,i);
    end
end
%这个是按照matlab的列进行操作的
C_d=[];
C_t=[];
for i=1:n
    C_d=[C_d,distance(:,i)'];
    C_t=[C_t,time(:,i)'];
end
for i=1:n-1
    C_d=[C_d,0];
    C_t=[C_t,0];
end

Alu=zeros(n*2,n*n+(n-1));
Ard=zeros((n-1)^2-(n-1),(n-1));
%前N行
for i=1:n
    for j=i*n-n+1:i*n
        Alu(i,j)=1;
    end
end

%再N行
j=1;
for i=n+1:2*n
        Alu(i,j)=1;
        k=j;
        while(k<=n*n-n)
            k=k+n;
            Alu(i,k)=1;
        end
        j=j+1;
end

%以下部分实现下半部分的约束
Ard=zeros((n-1)^2-(n-1),n*n+(n-1));
i=1;
while(i<=(n-1)^2-(n-1))
    for j=2:n
        k=2;
        if k==j
            k=k+1;
        end
        while (k<=n & k~=j)
              Ard(i,(k-1)*n+j)=n;
              Ard(i,n^2+j-1)=1;
              Ard(i,n^2+k-1)=-1;
              k=k+1;
              if k==j
                  k=k+1;
              end
              i=i+1;
        end
    end
end

A=[Alu;Ard];
b=ones(2*n,1);
bb=(n-1)*ones((n-1)^2-(n-1),1);
b=[b;bb];

vtype='';
%u=[];
%l=[];
for i=1:n^2;
    vtype=[vtype,'B'];
    %u=[u,1]
    %l=[l,0]
end
for i=1:n-1
    vtype=[vtype,'C'];
    %u=[u,inf]
    %l=[l,0]
end

csense='';
for i=1:2*n
    csense=[csense,'E'];
end
for i=1:(n-1)^2-(n-1)
    csense=[csense,'L'];
end

[x_t,y_t,s_t,dj_t,obj_t,solstat_t] = LMsolvem(A,b,C_t,csense,[],[],vtype);
[x_d,y_d,s_d,dj_d,obj_d,solstat_d] = LMsolvem(A,b,C_d,csense,[],[],vtype);
total_d=C_t*x_d;
total_t=obj_t;

disp('时间路线测量用时：');
disp(total_t);
disp('距离路线测量用时：')
disp(total_d);