📄 vrp遗传算法25个点的3.cpp
字号:
//此程序运行出来有重复服务的客户点，且有的客户点被丢失...........
//运行结果不知道是什么类型，反正不对，交叉函数需要重写.....
#include<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<dos.h>
#include<conio.h>
#define car_client_num 25 //25个客户，数组中最大下标为24
#define car_num 25 //一个配送中心25辆车，数组中最大下标为24
#define M 150 // 种群大小
#define V 1.0 //汽车速度
#define GEN 100 //最大遗传代数
#define pm 0.02
#define pc 0.5
#define CONST 3000.0 //足够大的数
/*附加数据：
ET=0,912,825,65,727,15,621,170,255,534,357,448,652,30,567,384,475,99,179,278,10,914,812,732,65,169;
LT=1236,967,870,146,782,67,702,225,324,605,410,505,721,92,620,429,528,148,254,345,73,965,883,777,144,224;
t=0,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90;
g=10,30,10,10,10,20,20,20,10,10,10,20,30,10,40,40,20,20,10,10,20,20,10,10,40;*/
struct car //配送中心汽车
{
//int x,y; //坐标
double cost,g; //成本、容量
}car_data={0.0,200.0};
struct car_client
{
//int x,y; //横纵坐标
double g,t; //需求量和需要时间
}car_client_data[car_client_num]={{10.0,90.0},{30.0,90.0},{10.0,90.0},{10.0,90.0},{10.0,90.0},
{20.0,90.0},{20.0,90.0},{20.0,90.0},{10.0,90.0},{10.0,90.0},
{10.0,90.0},{20.0,90.0},{30.0,90.0},{10.0,90.0},{40.0,90.0},
{40.0,90.0},{20.0,90.0},{20.0,90.0},{10.0,90.0},{10.0,90.0},
{20.0,90.0},{20.0,90.0},{10.0,90.0},{10.0,90.0},{40.0,90.0}};
int car[car_num]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}; //选定和没选定车辆的数组
double distance[car_client_num+1][car_client_num+1]={{0.0,18.6815,20.6155,16.1245,18.1108,15.1327,19.0,16.0,18.1108,20.0998,16.7631,19.6469,38.0789,30.8058,39.3573,36.0555,40.3113,33.3017,35.3553,39.0512,10.0,10.198,12.1665,13.0,15.0,15.1327},
{18.6815,0.0,2.0,3.60555,3.0,4.24264,5.09902,5.38516,7.0,7.28011,10.198,10.0499,26.2488,24.0416,28.6007,27.7308,30.2324,27.8927,30.8058,32.311,23.4307,21.9317,23.3452,21.4009,26.9072,25.6125},
{20.6155,2.0,0.0,5.0,3.60555,5.83095,5.09902,6.40312,7.28011,7.0,10.7703,10.0499,25.0,23.5372,27.4591,26.9258,29.1548,27.4591,30.4138,31.6228,25.0,23.4307,24.7588,22.6716,28.2843,26.9072},
{16.1245,3.60555,5.0,0.0,2.0,1.0,3.60555,2.0,4.47214,5.65685,7.0,7.61577,25.4951,21.9317,27.5862,26.0768,29.0689,25.632,28.4605,30.4138,20.0,18.4391,19.799,17.8045,23.3452,22.0227},
{18.1108,3.0,3.60555,2.0,0.0,3.0,2.23607,2.82843,4.0,4.47214,7.28011,7.07107,24.0416,21.1896,26.2488,25.0599,27.8029,25.0,27.8927,29.5466,21.6333,20.0,21.2603,19.105,24.7588,23.3452},
{15.1327,4.24264,5.83095,1.0,3.0,0.0,4.47214,2.23607,5.0,6.40312,7.07107,8.06226,26.2488,22.3607,28.2843,26.6271,29.7321,26,28.7924,30.8869,19.2094,17.6918,19.105,17.2047,22.6716,21.4009},
{19,5.09902,5.09902,3.60555,2.23607,4.47214,0.0,3.0,2.23067,2.23067,5.83095,5.0,21.9317,18.9737,24.0832,22.8254,25.6125,22.8035,25.7099,27.313,21.4709,19.7231,20.8087,18.4391,24.2074,22.6716},
{16,5.38516,6.40312,2.0,2.82843,2.23607,3.0,0.0,2.82843,4.47214,5.0,5.83095,24.2074,20.1246,26.1725,24.4131,27.5862,23.7697,26.5707,28.6531,18.868,17.2047,18.4391,16.2788,21.9317,20.5183},
{18.1108,7.0,7.28011,4.47214,4.0,5.0,2.23607,2.82843,0.0,2.0,3.60555,3.16228,21.4009,17.4642,23.3452,21.6333,24.7588,21.1896,24.0416,25.9422,19.6977,17.8885,18.868,16.4012,22.2036,20.6155},
{20.0998,7.28011,7.0,5.65685,4.47214,6.40312,2.23607,4.47214,2.0,0.0,5.0,3.16228,19.8494,16.7631,21.9317,20.5913,23.4307,20.6155,23.5372,25.0799,21.5407,19.6977,20.5913,18.0278,23.8537,22.2036},
{16.7631,10.1980,10.7703,7.0,7.28011,7.07107,5.83095,5.0,3.60555,5.0,0.0,3.0,21.4709,15.8114,23.0217,20.5183,24.2074,19.2354,21.9317,24.4131,16.7631,14.8661,15.6525,13.0384,18.868,17.2047},
{19.6469,10.0499,10.0499,7.61577,7.07107,8.06226,5.0,5.83095,3.16228,3.16228,3.0,0.0,18.868,14.3178,20.6155,18.6011,21.9317,18.0278,20.8806,22.8254,19.6469,17.72,18.3848,15.6525,21.4709,19.7231},
{38.0789,26.2488,25.0,25.4951,24.0416,26.2488,21.9317,24.2074,21.4009,19.8494,21.4709,18.868,0.0,10.4403,3.0,7.07107,5,12.2066,14.1421,11.1803,35.3553,33.3766,33.1361,3.1496,35.0,33.0},
{30.8058,24.0416,23.5372,21.9317,21.1896,22.3607,18.9737,20.1246,17.4642,16.7631,15.8114,14.3178,10.4403,0.0,10,5.38516,10.198,4.0,7.0,8.60233,26.2488,24.3516,23.7697,20.8806,25.1794,23.1948},
{39.3573,28.6007,27.4591,27.5862,26.2488,28.2843,24.0832,26.1725,23.3452,21.7317,23.0217,20.6155,3.0,10.0,0.0,5.38516,2.0,10.7703,12.2066,8.60233,35.9026,33.9559,33.541,30.5941,35.1283,33.1361},
{36.0555,27.7308,26.9258,26.0768,25.0599,26.6271,22.8254,24.4131,21.6333,20.5913,20.5183,18.6011,7.07107,5.38516,5.38516,0.0,5.0,5.38516,7.07107,5.0,31.6228,29.7321,29.1204,26.2488,30.4188,28.4429},
{40.3113,30.2324,29.1548,29.6089,27.8029,29.7321,25.6125,27.5862,24.7588,23.4307,24.2074,21.9317,5,10.198,2,5,0,10.198,11.1803,7.07107,36.4005,34.4819,33.9559,31.0483,35.3553,33.3766},
{33.3017,27.8927,27.4591,25.632,25.0,26.0,22.8035,23.7697,21.1896,20.6155,19.2354,18.0278,12.2066,4.0,10.7703,5.38516,10.198,0.0,3.0,5.83095,27.7308,25.9422,25.0799,22.3607,25.9615,24.0416},
{35.3553,30.8058,30.4138,28.4605,27.8927,28.7924,25.7099,26.5707,24.0416,23.5372,21.9317,20.8806,14.1421,7.0,12.2066,7.07107,11.1803,3.0,0.0,5.0,29.1548,27.4591,26.4197,23.8537,26.9258, 25.0799},
{39.0512,32.311,31.6228,30.4138,29.5466,30.8869,27.313,28.6531,25.9422,25.0799,24.4131,22.8254,11.1803,8.60233,8.60233,5.0,7.07107,5.83095,5.0,0.0,33.541,31.7648,30.8707,28.178,31.6228,29.7321},
{10.0,23.4307,25.0,20.0,21.6333,19.2094,21.4709,18.868,19.6977,21.5407,16.7631,19.6469,35.3553,26.2488,35.9026,31.6228,36.4005,27.7308,29.1548,33.541,0.0,2.0,2.82843,5.38516,5.0,5.38516},
{10.198,21.9317,23.4307,18.4391,20.0,17.6918,19.7231,17.2047,17.8885,19.6977,14.8661,17.72,33.3766,24.3516,33.9559,29.7321,34.4819,25.9422,27.4591,31.7648,2.0,0.0,2,3.60555,5.38516,5.0},
{12.1655,23.3452,24.7588,19.799,21.2603,19.105,20.8087,18.4391,18.868,20.5913,15.6525,18.3848,33.1361,23.7697,33.541,29.1204,33.9559,25.0799,26.4197,30.8707,2.82843,2.0,0.0,3.0,3.60555,3.0},
{13.0,21.4009,22.6716,17.8045,19.105,17.2047,18.4391,16.2788,16.4012,18.0278,13.0384,15.6525,30.1496,20.8806,30.5941,26.2488,31.0483,22.3607,23.8537,28.178,5.38516,3.60555,3.0,0.0,5.83095,4.24264},
{15.0,26.9072,28.2843,23.3452,24.7588,22.6716,24.2074,21.9317,22.2036,23.8537,18.838,21.4709,35.0,25.1794,35.1283,30.4138,35.3553,25.9615,26.9258,31.6228,5.0,5.38516,3.60555,5.83095,0.0,2.0},
{15.1327,25.6125,26.9072,22.0227,23.3452,21.4009,22.6716,20.5183,20.6155,22.2036,17.2047,19.7231,33.0,23.1948,33.1361,28.4429,33.3766,24.0416,25.0799,29.7321,5.38516,5.0,3.0,4.24264,2.0,0.0}};
int road[M][car_num][car_client_num];//用来保存每辆车的客户点，以利于后面排序用
int popinitialize[M][car_client_num],popnew[M][car_client_num]; //新旧染色体数组
int temp[car_client_num],i,j; //临时存储数组
//int initial[M][car_client_num]; //用来产生初始染色体的数组
int generation; //世代值
//double pay1[M],pay2[M]; //惩罚值
double p[M],q[M]; //选择概率数组,及累计概率数组
double sum_f; //目标函数植
double w[M][car_client_num+1]; //存储到达每个客户的时间及到达中心的时间
double ET[car_client_num+1]={0,912,825,65,727,15,621,170,255,534,357,448,652,30,
567,384,475,99,179,278,10,914,812,732,65,169}; //最早到达时间
double LT[car_client_num+1]={1236,967,870,146,782,67,702,225,324,605,410,
505,721,92,620,429,528,148,254,345,73,965,883,777,144,224}; //最晚到达时间
//double fun[M];
int aa,a,d,m,n;
double arrive_t[car_client_num]; //到达每个客户的时间
int kt[car_num],sign[car_client_num]; //分别存储每条路线上的客户数和每条染色体上的客户服务情况
double sum_r[car_num]={0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,
0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0};//存放每条路线的距离值
double sum_s; //存放每条染色体满足约束条件的距离值
int y=0;
double best_f[GEN];int best[GEN][car_client_num];
struct individual
{
double value;
double fitness; //适应度
}population[M];
double max(double na,double nb)
{
if(na>=nb)return na;
else return nb;
}
double min(double a,double b)
{
if(a<=b)return a;
else return b;
}
void initialize() //定义初始解 产生初始染色体 此处问题解决了
{
int i,j,k;
int num[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25};
int rn[car_client_num];
//int popinitialize[M][car_client_num];
srand((unsigned)time(NULL));
for(k=0;k<M;k++)
{
for(i=0;i<car_client_num;i++)
{
rn[i]=rand()%car_client_num;
for(j=0;j<i;j++)
{
if(rn[i]==rn[j]){i--;break;}
}
}
for(j=0;j<car_client_num;j++)
{
popinitialize[k][j]=num[rn[j]];
//cout<<popinitialize[k][j]<<" ";
}
// cout<<endl;
}
}
double roads(int i) //包含每条路径的距离和到达每个客户的到达时间 应该OK的
{
int flag=1;
sum_s=0.0;
aa=0;a=0;
int index=0;
for(int c=0;c<car_num;c++)
kt[c]=0;
for(int j=0;j<car_client_num;j++)
sign[j]=0;
double sum_r[car_num]={0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,
0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0};
double sum[car_num]={0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,
0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0};//每条路的需求量之和
while(flag==1)
{
flag=0;
for(int j=0;j<car_client_num;j++)
{
if(kt[a]==0)
{
if(sign[j]==0&&distance[0][popinitialize[i][j]]<=LT[popinitialize[i][j]]&&
sum[a]+car_client_data[popinitialize[i][j]-1].g<=car_data.g)
{
road[i][a][kt[a]]=popinitialize[i][j];
sign[j]=1;kt[a]++;sum[a]+=car_client_data[popinitialize[i][j]-1].g;
if(distance[0][popinitialize[i][j]]>ET[popinitialize[i][j]])
arrive_t[road[i][a][kt[a]]-1]=distance[0][popinitialize[i][j]];
else arrive_t[road[i][a][kt[a]]-1]=ET[popinitialize[i][j]];
}
}
else if(sign[j]==0&&(distance[road[i][a][kt[a]]][popinitialize[i][j]]+
arrive_t[road[i][a][kt[a]]-1]+car_client_data[road[i][a][kt[a]]-1].t)<=LT[popinitialize[i][j]]&&
sum[a]+car_client_data[popinitialize[i][j]-1].g<=car_data.g) //这句也没运行
{
road[i][a][kt[a]]=popinitialize[i][j];
sign[j]=1;kt[a]++;sum[a]+=car_client_data[popinitialize[i][j]-1].g;
if(distance[0][popinitialize[i][j]]>ET[popinitialize[i][j]])
arrive_t[road[i][a][kt[a]]-1]=distance[0][popinitialize[i][j]];
else arrive_t[road[i][a][kt[a]]-1]=ET[popinitialize[i][j]];
}
}
for(j=0;j<car_client_num;j++)
if(sign[j]==0)
{flag=1;break;}
a++;
}
aa=a;
//cout<<aa<<endl;
index=0;
for(a=0;a<aa;a++)
{
for(j=index,d=0;j<(index+kt[a]),d<kt[a];j++,d++)
popinitialize[i][j]=road[i][a][d];
//cout<<road[i][a][d]<<" ";
//cout<<endl;
index+=kt[a];
}
/*for(j=0;j<car_client_num;j++)
cout<<popinitialize[i][j]<<" ";
cout<<endl;*/
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -