VRP求解matlab程序.doc

(完整版)VRP求解matlab程序% % the procedure of ant colony algorithm for VRP % % % % % % % % % initialize the parameters of ant colony algorithms city=1 145 215 02 151 264 11003 159 261 7004 130 254 8005 128 252 14006 163 247 21007 146 246 4008 161 242 8009 142 239 10010 163 236 50011 148 232 60012 128 231 120013 156 217 130014 129 214 130015 146 208 30016 164 208 90017 141 206 210018 147 193 100019 164 193 90020 129 189 250021 155 185 180022 139 182 700；d=city（：,2:3)；x=d（:,1)；y=d（：,2)；g=city（:，4）； m=10； % 蚂蚁数 mm=max(size（city）;alpha=1; belta=3； 决定tao和miu重要性的参数 lmda=0; rou=0。4; 衰减系数 q0=0.95; 概率 tao0=1/(10*400.04);%初始信息素 Q=2；% 蚂蚁循环一周所释放的信息素 defined_phrm=1.0； % initial pheromone level value QV=6000; % 车辆容量 vehicle_best=round（sum（g)/QV）+1； 所完成任务所需的最少车数 V=40; maxitime=100; best_cost=zeros(1，maxitime); 最好解cost=zeros（maxitime,m)；best_tour=； optcost=inf;opttour=； maxtt=inf; 计算两点的距离 for i=1:mm; for j=1:mm； 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：mm； for j=1:mm; if i=j; s（i，j）=dist（i，1)+dist(1，j）-dist（i,j)； %节约值tao（i,j）=defined_phrm； %defined_phrm=15.0 miu（i，j)=1/dist(i,j); end； end; end； 置deltao（i,j）为0for k=1：mm; for k=1:mm； deltao（i,j)=0; end; end； %开始迭代 for Nc=1：maxitime迭代次数 temp=; for i=1：m m(10）为蚂蚁数tt=inf； costt=0；sumload=0; cur_pos(i）=1； %从车场出发rn=setdiff（randperm(mm）,1）; n=1；A（n) nn=1; part_sol（nn）=1； 部分路径的第一步n_sol=0; 蚂蚁产生的路径数量 M_vehicle=500; %是最大车辆数吗t=0； 最佳路径数组的元素数为0 hh=1； while hh=0 %hh为length（rn)while sumloadQV for k=1:length（rn) if sumload+g(rn(k）=QV gama(cur_pos(i），rn(k）)=（sumload+g（rn（k）)）/QV; gama越来越大，sumload是个定值A(n）=rn(k)； %选择重量适合的点n=n+1； %记录重量适合的点数end； end; na=length（A）；if na=0 breakelse在满足容量的点中计算概率，选择概率大的一点 for j=1：nap(j）=10(tao（cur_pos(i)，A（j)）alpha（miu（cur_pos(i）,A（j)belta； %p=compute_prob(A,cur_pos（i),tao,miu，alpha,belta，gama，lmda,i); %？endsump=sum（p）；p=p/sump；maxp=1e8; for j=1：na if p（j)maxp maxp=p（j）； index_max=j; end； end； for j=1:naif rand=q0&randtao(cur_pos（i)，old_pos） tao(cur_pos(i）,old_pos)=tao（old_pos，cur_pos(i）)；else tao(old_pos,cur_pos(i)）=tao（cur_pos（i),old_pos);endtao（old_pos，cur_pos（i）)=(1-rou)*tao（old_pos,cur_pos（i）)+ rouQ； maxtao=10/(1-rou)*Q/200;mintao=maxtao/200； if tao（old_pos，cur_pos(i)）maxtao tao(old_pos，cur_pos（i）=maxtao; end if tao(old_pos,cur_pos（i)mintao tao（old_pos，cur_pos(i)）=mintao; end nn=nn+1； nn记录容量和概率都满足的点part_sol（nn）=cur_pos(i); %part_sol为支路sumload=sumload+g（cur_pos（i）);temp_load=sumload; %temp_load结束时放出的货物总量rn=setdiff(rn,cur_pos(i); fid=fopen(out_customer.txt,a+)； fprintf(fid,%s %itn，the current position is:，cur_pos(i)）; fprintf(fid，%sn，the 容量满足的 customer set is:); fprintf(fid，nt%in,A); fprintf（fid，-n）; fclose(fid); na=；index_max=0;n=1； A=;endend%while sumloadmaxtao tao（i，j)=maxtao； end if tao(i，j）mintao tao（i，j）=mintao; end if i=j tao(i，j）=0; end endend fid=fopen（out2_solution。txt，a+); fprintf（fid,s%i%s,NO.，n_sol,路径是:）; fprintf（fid,i ，part_sol）； fprintf（fid,n）； fprintf（fid，%s %in，当前的用户需求量是：，temp_load）; fprintf（fid,s %fn,总费用是：，tt）; fprintf（fid,-n）; fprintf(fid,n）; fclose（fid);tt=0；end Nc的结束 optcost,opt_Nc=min(best_cost） opttour fid=fopen(out3_solution.txt，a+）;fprintf(fid，s fn,总费用是：，optcost）； fprintf（fid，-n); fprintf(fid，sn,最终路径是:）； fprintf(fid，%i-，opttour)； fprintf（fid,n）; fclose（fid）； %作图%plot（best_cost);figure plot(x(opttour(1）)，y(opttour(1),o）;hold onfor i=1:mmplot（x（i)，y(i)，*）；hold onendhold on for j=1：length（opttour）1line(x(opttour（j)）, x(opttour(j+1)）, y(opttour（j)）, y（opttour(j+1)）;hold on endhold offxlabel(x coordinate);ylabel（y coordinate）;title(Opttour in MaxITime iterations）;