📄 vrptwtest.cpp
字号:
最优解进行全局更新
****************************************/
void add_best_global_update()
{
int j;
for (j=0;j<MAX_ROUTE_LEN-1;j++)
if ((bestant.tour[j]!=0)||(bestant.tour[j+1]!=0))
{
detatau[bestant.tour[j]][bestant.tour[j+1]]+=(Q/bestant.len);
detatau[bestant.tour[j+1]][bestant.tour[j]]+=(Q/bestant.len);
}
}
/***************************************
全局更新规则 (加入最大最小蚂蚁思想)
****************************************/
void global_update_rule()
{
int i,j;
int goodantcount=ANT_NUM/2;//精英蚂蚁数目取ANT_NUM/2
for (i=0;i<CITY_NUM;i++)
for (j=0;j<CITY_NUM;j++)
{
tau[i][j]=(1.0-rou)*tau[i][j]+rou*detatau[i][j];
if(tau[i][j]>maxtau)
{
maxtau=1/(2*(1-rou)*L)+goodantcount/L;
tau[i][j]=maxtau;
}
else
tau[i][j]=mintau;
}
}
/***************************************
打印各路径的情况
****************************************/
void tour_output()
{
int j,k;
for (k=0;k<ANT_NUM;k++)
{
printf("\n第%2d只蚂蚁所走的路线: ",k);
outfile<<"\n第"<<k<<"只蚂蚁所走的路线为：";
for (j=0;j<MAX_ROUTE_LEN;j++)
{
printf("%3d",ant[k].tour[j]);
outfile<<setw(3)<<ant[k].tour[j];
}
printf("\n 该蚂蚁走的总路径长度为:%7.3f",ant[k].len);
printf(" 所用总的车辆数为:%2d\n",ant[k].carnum);// ant[k].tflag=%4d\n",ant[k].carnum,ant[k].tflag);
outfile<<"\n该蚂蚁走的总路径长度为:"<<ant[k].len;
outfile<<setw(5)<<" 所用总的车辆数为:"<<ant[k].carnum<<endl;
}
}
/*************************************
局部优化
*************************************/
void local_optimize()
{
int vehicle,num;
int n,i,j,k,r;
int route[MAX_ROUTE_LEN],temptour[CITY_NUM];
double bestlen,sublen,templen;
struct SUB_ROUTE *subtour;
srand(time(NULL));
subtour=new SUB_ROUTE[CITY_NUM];
for (i=0;i<MAX_ROUTE_LEN;i++)
route[i]=bestant.tour[i];//把蚂蚁找到的最优的路径放到route[i]
bestlen=bestant.len;//calc_length(bestant.tour);计算出最优的路径
for (i=0;i<bestant.carnum;i++)
{
subtour[i].cities=0;
subtour[i].partsum=0;
subtour[i].partlen=0;
}
vehicle=-1;
for(n=0;n<MAX_ROUTE_LEN-1;n++)
{
if ((route[n]==0)&&(route[n+1]==0)) break;
else
{
if (route[n]==0)
{
k=0;
vehicle++;
}
subtour[vehicle].partsum=subtour[vehicle].partsum+g[route[n]]; //一条路径中的一个子路径的一辆车的载重量如0 6 7 2 0 8 5 0 3 1 0 0 0 0 0中0 6 7 2 0是一个子路径
subtour[vehicle].tour[k]=route[n]; k++;//vehicle纪录着最好的蚂蚁找到的最优的路径所用到的车辆数
subtour[vehicle].cities++; //cities是子路径中的城市数，包含一个配送中心0 6 7 2 0 中就有4个城市
}
}
for (k=0;k<bestant.carnum;k++)//vnum是找到的最优路径中 vnum=bestant.carnum
{
j=subtour[k].cities; //在本题目中找到的最优路径中的第一个子路径中0 6 7 2 0 中有4个城市
subtour[k].tour[j]=0;
if (j<MAX_ROUTE_LEN-1)
subtour[k].tour[j+1]=0;
subtour[k].partlen=calc_sublen(subtour[k].tour);//计算一个子路径的长度
}
for (k=0;k<bestant.carnum;k++)
{
printf("\n");
printf("第%d条子路径所经过的城市为：",k);
outfile<<"第"<<k<<"条子路径经过的城市为：";
for (i=0;i<=subtour[k].cities;i++)
{
printf("%3d",subtour[k].tour[i]);
outfile<<setw(3)<<subtour[k].tour[i];
}
printf(" 经过的城市数：%5d",subtour[k].cities);
outfile<<setw(3)<<" 经过的城市数:"<<subtour[k].cities<<endl;
}
printf("\n");
outfile<<endl;
//子路径内部执行交换变异
for (k=0;k<bestant.carnum;k++)
{
for (i=0;i<=subtour[k].cities;i++) //subtour[k].cities纪录着最优路径中一条子路径的城市的个数如0 6 7 2 0 中有4个城市
temptour[i]=subtour[k].tour[i];
for (int i2=0;i2<subtour[k].cities;i2++)
{
int tp;
tp=temptour[i2+1];
for(j=0;j<subtour[k+1].cities;j++)
{
if(subtour[k+1].tour[j]==0)
break;
else
temptour[i2+1]=subtour[k+1].tour[j];
subtour[k+1].tour[j]=tp;
}
if (templen<subtour[k].partlen)//subtour[k].partlen是纪录那个子路径的长度如0 6 7 2 0这个子路径的长度是305。
{
//如果变异后的子路径长度小于开始的者段子路径则将变异后的子路径替代先前的子路径
for (i=0;i<subtour[k].cities;i++)
subtour[k].tour[i]=temptour[i];//进行优化后的该子路径的各个点的代替
subtour[k].partlen=templen;//该子路径的长度也要进行相应的变化
}
}
}
//组合改进后的子路径
num=0;
for (k=0;k<bestant.carnum;k++)
{
for (i=0;i<subtour[k].cities;i++)
{
route[num]=subtour[k].tour[i]; //把进行变异后的各条子路径上的点一并放入一个数组中route[num]中
num=num+1;
}
}
printf("\n");
outfile<<endl;
for (i=0;i<MAX_ROUTE_LEN;i++)
bestant.tour[i]=route[i]; //把变异后的子路径放入最好的蚂蚁选择的路径中
bestant.len=calc_length(bestant.tour);
printf("best_tour:\n");
for (i=0;i<MAX_ROUTE_LEN;i++)
{
printf("%3d",bestant.tour[i]);
outfile<<setw(3)<<bestant.tour[i];
}
printf("\n best_length:%f\n",bestant.len);
outfile<<"\n best_length:"<<bestant.len<<endl;
finish_time=clock();
duration=(double)(finish_time-start_time)/CLOCKS_PER_SEC;
printf( "time used:%f seconds\n", duration );
outfile<<"time used:"<<duration <<"seconds\n";
delete []subtour;
return;
}
/***************************************
求最好的路径
****************************************/
void calc_best_route()
{
int i,k;
for (k=0;k<ANT_NUM;k++)
if ((ant[k].len<bestant.len))//{ (ant[k].tflag==1)&& } ant[k].tflag==1纪录哪只蚂蚁找到了最好的路径（总路径长度最短）从tour_output()打印中可看出当k=3和7时ant[k].tflag==1
{//主函数中已经定义max_len=(MAX_ROUTE_LEN-1)*max_dist();和bestant.len=max_len;计算出来是3000.0000000000
bestant.len=ant[k].len;
bestant.carnum=ant[k].carnum;
for (i=0;i<MAX_ROUTE_LEN;i++) bestant.tour[i]=ant[k].tour[i];
best_gen=gen;//纪录找到该路径时的迭代次数
best_num=k;//纪录第几只蚂蚁是找到最好路径的蚂蚁
}
printf("\n");
printf("the best tour:\n");
outfile<<"\nthe best tour:\n";
for (i=0;i<MAX_ROUTE_LEN;i++)
{
printf("%3d",bestant.tour[i]);
outfile<<setw(5)<<bestant.tour[i];
}
printf("\n");
outfile<<endl;
bestant.len=calc_length(bestant.tour);
//printf(" best_gen=%d,best_num=%d\n",best_gen,best_num);
printf(" car_num=%d,best_len=%f\n",bestant.carnum,bestant.len);
outfile<<setw(3)<<" car_num="<<bestant.carnum<<" best_len="<<bestant.len;
L=bestant.len;
time_case(bestant.tour);//判断路径是否满足时间窗约束
finish_time=clock();
duration=(double)(finish_time-start_time)/CLOCKS_PER_SEC;////测量一个事件持续的时间
printf( "time used:%f seconds\n", duration );
printf("\n");
outfile<<" time used:"<<duration <<"seconds\n\n";
}
/*************************************
主函数
**************************************/
int main()
{
int i,j,k,ri,choice,first_node;
int finish,flag,temp_flag;
double per[CITY_NUM],pbest,pi;
double sumneed,temp_sumneed,atime,temp_atime,min_time,j_time;
//产生随机数
time_t timer;
time(&timer);
unsigned long seed=timer;
seed=seed%56000;
srand(time(NULL));
/*初始化参数*/
alpha=1;
beta=3;
rou=0.5;
Q=100;
outfile.open("result.txt",ios::out);
outfile<<"\n ----------------------------------------------------- "<<endl;
outfile<<"-----------------------2008年04级信工韩红轲毕业设计--------------------------"<<endl;
outfile<<"------------------------<<蚁群算法解决带时间窗的车辆调度问题>>------------------"<<endl;
max_len=(MAX_ROUTE_LEN-1)*max_dist();
tau0=Q/max_len;
//outfile<<"tau0="<<tau0;
printf("TAU0=%f\n",tau0);
outfile<<"tau0="<<tau0<<endl;
init_need();//生成各任务点的需求量
order_endtime();
calc_dist(); //求各任务间的距离矩阵
init_tau_by_value(tau0); //初始化tau0(tau为边上的信息素轨迹强度)
ant=new ROUTE[ANT_NUM];
for(i=0;i<MAX_ROUTE_LEN;i++) bestant.tour[i]=0;//把各个点开始都在禁忌表中置为0
bestant.len=max_len;
for (gen=0;gen<TIMES;gen++)//限制跌代的次数最大跌代数为TIMES
{
printf("第%d次迭代\n\n",gen);
printf("蚂蚁所寻找到的路径各个边上的具体信息为: \n ");
outfile<<"第"<<gen<<"次迭带"<<endl<<endl;
outfile<<"蚂蚁所寻找到的路径各个边上的具体信息为: \n\n";
clear_global_update();// detatau[i][j]=0.0;//detatau[i][j]是指蚂蚁k在本次循环中留在边（i，j）上的信息素
init_uniform(); //蚂蚁均匀分布在各任务点上
for(k=0;k<ANT_NUM;k++) //限制蚂蚁的数目
{
first_node=ant[k].tour[1];// first_node是整型的，是存放第k只蚂蚁在开始均匀分布的结点上的编号
sumneed=g[first_node];//第first_node个点的货物需求量存入sumneed中
if (D[0][first_node]/50<TW[first_node][0])//如果第first_node个节点到配货中心的时间早于该点要求的最早时间
atime=TW[first_node][0]+T[first_node];//则从配货中心到达第一个点的完成时间=时间窗开始时间+服务时间
else
atime=D[0][first_node]/50+T[first_node];//否则从配货中心到达第一个点的完成时间=到达时间+服务时间
init_tabu(); //初始化禁忌表全为0 tabu[]中1表示禁止走到那个任务点，0表示允许
tabu[first_node]=1; //把放入子路径中的节点的编号置入禁忌表中为禁忌 1
ant[k].tflag=1;
for (i=1;i<MAX_ROUTE_LEN-1;i++)
{
finish=1;
for (j=1;j<CITY_NUM;j++)
if (tabu[j]==0) //第k只蚂蚁还未遍历城市j
{
finish=0; //finish=0说明还未遍历完所有任务点
break;
}
if (finish==1)
{
ant[k].tour[i+1]=0; //路径结束尾部赋0
break; //若遍历完所有任务点，跳出循环
}
else
{
ri=ant[k].tour[i]; //ri是纪录第k只蚂蚁走到第i个点时该点的标号（可能就是i）
flag=0;
pbest=0;
for (j=1;j<CITY_NUM;j++) //从城市中选出全部符合条件并且选择概率最高的点choice为下一个节点
{
//j=ordertime[n].num;
per[j]=0;
temp_sumneed=sumneed+g[j];//temp_sumneed是临时纪录车走过的点的需求总量，sumneed是走到第一个点的需求量，g[j]是要的寻找要走那个点时的需求量
temp_atime=atime+D[ri][j]/50;//temp_atime是临时纪录到达该点时的时间
if ((tabu[j]==0)&&(temp_sumneed<=CONTENT))//如果禁忌表中该点未被标记并且此时车的载重量没有超过车的最大载重量
{
if ((temp_atime>=TW[j][0])&&(temp_atime<=TW[j][1]))//如果此时这个计算的临时到达时间正好在该点的时间窗口内则计算选择下一点的选择概率
{
yita[ri][j]=1.0/D[ri][j];
u[ri][j]=D[ri][0]+D[0][j]-D[ri][j];//考虑了任务点与配货中心间的距离而引入的变量称为节约值，u[ri][j]越大收益越大，而选择j的概率越大
w[ri][j]=1.0/(TW[j][1]-TW[j][0]);//w[ri][j]是纪录节点j的时间窗的倒数，可以使算法更倾向于那些短时间窗的客户
per[j]=pow(tau[ri][j],alpha)*pow(yita[ri][j],beta)*pow(u[ri][j],1)*pow(w[ri][j],1);
//tau[ri][j]是边（ri，j）上信息素轨迹强度，alpha表示轨迹信息素的相对重要性
//yita[ri][j]是边（ri，j）上的能见度：yita[ri][j]=1.0/D[ri][j];（取距离的倒数），beta表示能见度的相对重要性
if (per[j]>pbest)
{
choice=j; //j为下一个移向的结点
pbest=per[j];
flag=1; //说明找到了下一个移向的结点
}
}
}
}// end for (j=1;j<CITY_NUM;j++) //从城市中选出全部符合条件并且选择概率最高的点choice为下一个节点
if (flag==0) //说明严格按时间窗未找到可以移向的下一个结点
{
temp_flag=0;
min_time=8;
for (j=1;j<CITY_NUM;j++)
{
temp_sumneed=sumneed+g[j]; //计算出临时的车载重量
temp_atime=atime+D[ri][j]/50; //计算出到达此点j的时间
if ((tabu[j]==0)&&(temp_sumneed<=CONTENT))//如果j点未被走过并且车载没有超重
{
if (temp_atime<TW[j][0])// &&(temp_atime>TW[j][1]) )//到达该点的时间早于该点的时间窗的最早时间
j_time=TW[j][0]-temp_atime;
else//因为走到此步的都是没有严格按照时间窗到达的所以else后是超过时间窗的点大到达时间
j_time=temp_atime-TW[j][1];
if (j_time<min_time)//求出到达该点的时间与该点设置的时间窗的差与自己设置的min_time比较
{
min_time=j_time;
choice=j;
temp_flag=1;
}
}
}// for (j=1;j<CITY_NUM;j++)
if (temp_flag==1)//如果到达时间与时间窗的差值<min_time时
{
flag=1;
ant[k].tflag=0;
}
}
if (flag==1) //找到存在满足车载容量和时间窗的要求的任务点还未服务
{
ant[k].tour[i+1]=choice;//把选择的下一个节点放入第k只蚂蚁的子路径中
tabu[choice]=1; //把刚才选择的这个点的标号在禁忌表中置为1表示已经走过不能在走
sumneed=sumneed+g[choice]; //把车载当前的载重量计算出来
atime=atime+D[ri][choice]/50+T[choice];//把要到达的这个点并且完成任务时的时间计算出来=上一个点的完成时间+路上走的时间+服务时间
}
else
{
ant[k].tour[i+1]=0; //找不到下一个满足条件的节点，则车辆需要返回中心点此时在该节点后边加一个0表示返回中心
sumneed=g[0];
atime=0;
} //match else
}
} //match FOR(i=2;i<MAX_ROUTE_LEN;i++)
while (i<MAX_ROUTE_LEN-1)
{
i++;
ant[k].tour[i]=0;
}
ant[k].len=calc_length(ant[k].tour);
ant[k].carnum=calc_vehicle(ant[k].tour);
// ant[k].tflag=time_case(ant[k].tour);
} // match ant
tour_output(); //打印各个子路径的情况
calc_best_route();//在只是考虑时间关系的情况下找出最优路径,在此函数中调用函数 time_case(bestant.tour) 判断路径是否满足时间窗约束
maxtau=1/(2*(1-rou)*L); //信息素最大值
mintau=maxtau/20; //信息素最小值
//信息素更新
add_global_update();//进行各个边上的信息素的全局更新并且加入惩罚函数（对于不严格满足时间窗的点进行信息素的调正）
add_best_global_update(); //对符合时间窗的最优解进行信息素的全局更新
global_update_rule(); //按公式计算tau[i][j]=(1.0-rou)*tau[i][j]+rou*detatau[i][j]信息素
}
printf("\nafter local optimization,the best route:\n");
outfile<<"after local optimization,the best route:\n";
local_optimize();
delete []ant;
finish_time=clock();
duration=(double)(finish_time-start_time)/CLOCKS_PER_SEC;
printf( "time used:%f seconds\n", duration );
outfile<<"time used:"<< duration<<" seconds";
return(0);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -