📄 vrptwtest.cpp
字号:
#include<stdio.h>
#include<stdlib.h>
//#include<iostream.h>
#include<fstream.h>
#include<math.h>
#include<time.h>
//#include<cstdlib>
#include<iomanip.h>
#include<assert.h>
//using namespace std;
#define CITY_NUM 9 //车场+任务数
#define MAX_ROUTE_LEN 16// 路径中的最多结点个数
#define ANT_NUM 8 //蚂蚁数量
//#define ANT_NUM 1 //蚂蚁数量
#define CONTENT 8.0 //车载容量
//#define CONTENT 100000.0 //车载容量
double w[9][9];//车载利用率
double u[9][9];//节省量
#define TIMES 5
ofstream outfile;
double atime1;
struct ROUTE
{
int tour[MAX_ROUTE_LEN];
double len;
int carnum;
int tflag;
};
struct SUB_ROUTE
{
int tour[CITY_NUM];
double partlen;
double partsum;
int cities;
};
struct NEEDPOINT
{
double starttime;
double endtime;
int num;
} ordertime[CITY_NUM]; //该结构体是包含最晚时间和第几个城市即那一个城市的最晚时间
struct ROUTE *ant,bestant,testour;
double g[CITY_NUM]={0,2,1.5,4.5,3,1.5,4,2.5,3}; //各个城市的需求量
double D[CITY_NUM][CITY_NUM]={{0,40,60,75,90,200,100,160,80},{40,0,65,40,100,50,75,110,100},
{60,65,0,75,100,100,75,75,75},{75,40,75,0,100,50,90,90,150},{90,100,100,100,0,100,75,75,100},
{200,50,100,50,100,0,70,90,75},{100,75,75,90,75,70,0,70,100},{160,110,75,90,75,90,70,0,100},
{80,100,75,150,100,75,100,100,0}}; //各个城市之间的距离
double TW[CITY_NUM][2]={{0,0},{1,4},{4,6},{1,2},{4,7},{3,5},{2,5},{5,8},{1.5,4}};//各个城市点的开始时间和结束时间TW[CITY_NUM][0]是各个最早时间TW[CITY_NUM][1]是最迟到时间
//double TW[CITY_NUM][2]={{0,1000000},{0,1000000},{0,1000000},{0,1000000},{0,1000000},{0,1000000},{0,1000000},{0,1000000},{0,1000000}};//各个城市点的开始时间和结束时间TW[CITY_NUM][0]是各个最早时间TW[CITY_NUM][1]是最迟到时间
//设置时间窗为[0，1000000]很大则该问题就变成为不带时间窗的车辆调度问题即（VRP问题）
double T[CITY_NUM]={0,1,2,1,2,2,2.5,3,0.8};//各个点上的服务时间（可能包括卸货时间和工作人员休息时间等）
int tabu[CITY_NUM];
double tau[CITY_NUM][CITY_NUM],yita[CITY_NUM][CITY_NUM],detatau[CITY_NUM][CITY_NUM];
double max_len,min_need;
double alpha,beta,rou,Q,tau0,q0;
double maxtau,mintau,L;
int best_gen,best_num,gen;
clock_t start_time, finish_time;
int hflag=0;
double duration; //测量一个事件持续的时间
//double dist(int i,int j);
void calc_dist();
double max_dist();
void initneed();
double calc_length(int *tour);
void init_tau_by_value(double value);
void init_uniform();
void clear_global_update();
void global_update_rule();
void init_tau_by_value(double value);
void init_uniform();
void clear_global_update();
void global_update_rule();
/*************************************
求任务之间的距离矩阵
*************************************/
void calc_dist()
{
int i,j;
int m=0;
printf("各个任务之间的距离矩阵D[I][J]:");
outfile<<"\n各个任务之间的距离矩阵D[I][J]:"<<endl;
for (i=0;i<CITY_NUM;i++)
{
for (j=0;j<CITY_NUM;j++)
{
if (m%9==0)
printf("\n");
outfile<<setw(5)<<D[i][j];
printf("%7.1f", D[i][j]);
m++;
}
printf("\n");
outfile<<"\n";
}
}
/**********************************
产生各货场的需求量并找到最小的需求
**********************************/
void init_need()
{
int i,temp;
min_need=g[1];
printf("各个点的需求量g[i]为:");
outfile<<"各个点的需求量g[i]为:\n";
for (i=0;i<CITY_NUM;i++)
{
if (i%9==0) printf("\n");
if ((i>0)&&(g[i]<min_need))
{
min_need=g[i];
temp=i;
}
printf("%5.1f",g[i]);
}
printf("\n其中最小的需求量是第%d点，需求量是%f\n",temp,min_need);
for(i=0;i<CITY_NUM;i++)
{
outfile<<setw(8)<<g[i];
}
outfile<<"\n其中最小的需求量是第"<<temp<<"点，需求量是"<<min_need;
}
/**************************************
按从小到大的顺序将各货场的关门时间排序
**************************************/
void order_endtime()
{
int i,j,k;
struct NEEDPOINT temp;
for (k=0;k<CITY_NUM;k++)
{
ordertime[k].starttime=TW[k][0];
ordertime[k].endtime=TW[k][1]; //TW[k][1]是第k个城市点的最晚时间
ordertime[k].num=k; //第k个城市
//double TW[CITY_NUM][2]={{0,0},{1,4},{4,6},{1,2},{4,7},{3,5.5},{2,5},{5,8},{1.5,4}};//各个城市点的开始时间和结束时间TW[CITY_NUM][0]是各个最早时间TW[CITY_NUM][1]是最迟到时间
}
for (j=1;j<CITY_NUM;j++) //对各个城市点的最晚时间进行排序
for (i=0;i<CITY_NUM-j;i++)
if (ordertime[i].endtime>ordertime[i+1].endtime)
{
temp=ordertime[i];
ordertime[i]=ordertime[i+1];
ordertime[i+1]=temp;
}
printf("按时间窗最晚时间从小到大排序各个点的编号为：");//the sorted end time case);
outfile<<"\n\n按时间窗最晚时间从小到大排序各个点的编号为："<<endl;
for (i=0;i<CITY_NUM;i++) //输出按最晚时间从早到晚排序后的各个城市点的序号
{
if (i%25==0) printf("\n");
printf("%8d",ordertime[i].num);
// printf("->时间窗后边沿%1.1f\n",ordertime[i].endtime);
}
printf("\n");
for (i=0;i<CITY_NUM;i++)
{
outfile<<setw(7)<<ordertime[i].num;
}
outfile<<endl;
for (i=0;i<CITY_NUM;i++) //输出各个排序后各个城市点对应的最晚时间
{
if (i%9==0) printf("\n");
printf("[%1.1f,%1.1f]",ordertime[i].starttime,ordertime[i].endtime);
//printf("%1.1f ",ordertime[i].endtime);
}
for (i=0;i<CITY_NUM;i++)
{
outfile<<setw(3.5)<<"["<<ordertime[i].starttime<<","<<ordertime[i].endtime<<"]";
}
}
/*************************************
计算两任务之间的最大距离
*************************************/
double max_dist()
{
int i,j;
double max_dist=0.0;
for (i=0;i<CITY_NUM;i++)
for (j=0;j<CITY_NUM;j++)
if (D[i][j]>max_dist)
max_dist=D[i][j];
return max_dist;
}
/*************************************
求子路径长度
*************************************/
double calc_sublen(int *route)
{
int n,i,j;
double len=0.0;
for(n=0;n<MAX_ROUTE_LEN-1;n++)
{
i=route[n];
j=route[n+1];
len+=D[i][j];
if (j==0) break;//route[]中存放的是计算出的子路径的编号eg：route[n]={0 3 1 5 0 8 4 0 6 7 0 2 0 0 0}当出现第二个0时为一条子路径
}
return(len);
}
/*************************************
求各子路径长度之和
*************************************/
double calc_length(int *route)
{
int n,i,j;
double len=0.0;
//for(int k=0;k<ANT_NUM;k++)
//{
// printf("第%d只蚂蚁寻找的路径为：\n",k);
// outfile<<"第"<<k<<"只蚂蚁寻找的路径各段距离为:"<<endl;
for(n=0;n<MAX_ROUTE_LEN-1;n++)
{
i=route[n]; //route[]中存放的是计算出的子路径的编号eg：route[n]={0 3 1 5 0 8 4 0 6 7 2 0 0 0}
j=route[n+1];
len+=D[i][j];//
if (i==j) break; //当i和j均为0时则该子路径结束
printf("%d->%d length：%1.1f ",i,j,D[i][j]);
outfile<<i<<"->"<<j<<" length:"<<D[i][j];
outfile<<setw(3);
}
printf("该车所走路径长度为：%1.1f\n\n",len);
outfile<<"\n该车所走路径长度为:"<<len<<endl<<endl;
//}
return(len);
}
/***************************************
求所用车辆数
***************************************/
int calc_vehicle(int *route)
{
int vehicle=0;
int n,i,j;
for(n=0;n<MAX_ROUTE_LEN-1;n++)
{
i=route[n];
j=route[n+1];
if ((i==0)&&(j!=0)) vehicle++;
}
return (vehicle);
}
/***************************************
判断路径是否满足时间窗约束
***************************************/
int time_case(int *route)
{
int n,tflag,i,j;
double atime;
atime=0;tflag=1;
outfile<<"\n找到的最好路径中到达的各个时间值分别为：\n";
for (n=0;n<MAX_ROUTE_LEN-1;n++)
{
i=route[n];
j=route[n+1];
atime=atime+T[i]+D[i][j]/50;
atime1=atime;
printf("从第%d点-第%d点,到达j点并完成任务时的时间为atime(计算方法atime=atime+T[i]+D[i][j]/50)%4.1f\n",i,j,atime);
outfile<<i<<"->"<<j<<" overtime:"<<atime<<endl;
if (j==0)
atime=0;
else
if (atime<(TW[j][0])||(atime>TW[j][1]))//到达时间不在时间窗内
{
hflag=1;
tflag=0; //0,表示不满足
printf("不符合时间窗的点=%d->%d(但通过计算惩罚值可以接受的点)\n",i,j);
outfile<<"不符合时间窗的点"<<i<<"->"<<j<<" 但该点是通过计算惩罚值可以接受的点"<<endl;
}
if (i==j) break;
}
return(tflag);
}
/***************************************
蚂蚁随机分布在各任务上
****************************************/
void init_random()
{
int k,rand1;
for(k=0;k<ANT_NUM;k++)
{
ant[k].tour[0]=0;
rand1=rand()%(CITY_NUM-1)+1;
ant[k].tour[1]=rand1;
}
}
/*****************************************
蚂蚁均匀分布在城市上
******************************************/
void init_uniform()
{
int k,may[CITY_NUM],num,i,j;
num=0;
for (i=1;i<CITY_NUM;i++) //挑选出满足时间窗的节点编号并纪录满足时间窗的节点数目
if ((D[0][i]/50>=TW[i][0])&&(D[0][i]/50<=TW[i][1]))//车辆到达时间正好在i点的时间窗中
{ //如果从配货中心到各个点的时间（距离除以速度D[0][i]/50）大于该点所允许的最早时间（TW[i][0]）或者小于该点的最晚时间（TW[i][1]）
may[num]=i;//符合上述要求的点的编号纪录到一个数组may[CITY_NUM]中
num=num+1;//纪录符合条件的点的个数
}
j=0;
for(k=0;k<ANT_NUM;k++) //把所有的蚂蚁都放在中心，然后把满足时间窗的蚂蚁放入下一个节点
{
ant[k].tour[0]=0;//所有蚂蚁一开始都在中心（tour[0]是纪录子路径编号的数组，其中的0是子路径第几个节点），0代表陪送中心编号0
j=k%num;
ant[k].tour[1]=may[j];//把符合时间条件的点的标号放入第k只蚂蚁的第一个要走的节点中
}
}
/*****************************************
初始化禁忌表
******************************************/
void init_tabu()
{
int j;
tabu[0]=1; //1表示禁止走到那个任务点，0表示允许
for (j=1;j<CITY_NUM;j++)
tabu[j]=0;
}
/**************************************
初始化tau(边上的信息素)
***************************************/
void init_tau_by_value(double value)
{
int i,j;
for (i=0;i<CITY_NUM;i++)
for (j=0;j<CITY_NUM;j++)
tau[i][j]=value;
}
/***************************************
清除全局更新轨迹量
****************************************/
void clear_global_update()
{
int i,j;
for (i=0;i<CITY_NUM;i++)
for (j=0;j<CITY_NUM;j++)
detatau[i][j]=0.0;//detatau[i][j]是指蚂蚁k在本次循环中留在边（i，j）上的信息素
}
/***************************************
进行全局更新（所有蚂蚁都找到一条子路径后进行的更新，第k只蚂蚁找到的路径各个边上的信息素均为(Q/ant[k].len)）
****************************************/
void add_global_update()
{
int k,j;
for (k=0;k<ANT_NUM;k++)
for (j=0;j<MAX_ROUTE_LEN-1;j++)
if ((ant[k].tour[j]!=0)||(ant[k].tour[j+1]!=0))//当第k只蚂蚁走过的点或下一个点不是中心时
{
if(hflag==0)
{
detatau[ant[k].tour[j]][ant[k].tour[j+1]]+=(Q/ant[k].len); //第k只蚂蚁在本次子路径中边（j->j+1）上的信息素
detatau[ant[k].tour[j+1]][ant[k].tour[j]]+=(Q/ant[k].len); //第k只蚂蚁在本次子路径回路上边（j+1->j）上的信息素
}
else // if (atime<(TW[j][0])||(atime>TW[j][1]))/
{
detatau[ant[k].tour[j]][ant[k].tour[j+1]]+=(Q/ant[k].len);
if(atime1<(TW[j][0]))//如果实际到达时间atime1比时间窗的最早时间早则信息素=信息素*（1-实际到达时间与时间窗边沿的差/时间窗）
detatau[ant[k].tour[j]][ant[k].tour[j+1]]=detatau[ant[k].tour[j]][ant[k].tour[j+1]]*( 1-( TW[j][0]-atime1 )/( TW[j][1]-TW[j][0] ) );
//早于时间窗前沿
else
detatau[ant[k].tour[j]][ant[k].tour[j+1]]=detatau[ant[k].tour[j]][ant[k].tour[j+1]]*( 1-(atime1 -TW[j][1] )/( TW[j][1]-TW[j][0] ) );
//晚于时间窗后沿
}
}
else
detatau[ant[k].tour[j]][ant[k].tour[j+1]]=0; //否则第k只蚂蚁在本次子路径中边（j->j+1）上的信息素为0
}
/***************************************
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -