#include<iostream>
#include<fstream>
#include<cstring>
#include<cmath>	
#include<math.h>
using namespace std;
#define  Rad_to_deg  57.29577951
#define	 Reapeat 10                   //大的循环次数
#define Q 100                        //客户数
#define M 50                     //班级总人数（初始种群个体数）
#define WS 20                      //差学生的数量
#define T 10                        //教师数量
#define GS 20                         //好学生数量
#define DEM 200                       //车辆最大载重



struct customer
{
	int number, x, y, demand, etime, ltime, stime;
	double angle;
	double distance;
	double btime, wtime;
	int pos;
	bool flag;
};
struct initialRoutes
{
	int count, best, worst;
	int routes[Q][Q], len[Q], remain[Q];
	double value, averagevalue[Q];
};

customer customer1[Q + 1], customer2[Q], customer3[Q];//customer1是原结构数组，customer2是按角度排序的结构数组，customer3是按照离配送中心的距离排序的结构数组
initialRoutes  initialRoutes0, initialRoutes1[Q], initialRoutes2[Q];

double distances[Q + 1][Q + 1];                       //距离矩阵
double  remain[Q];                     //里程，总时间，剩余货量  
int routes[Q][Q], len[Q], Pair[Q][2];                              //路径,子路径客户个数（包括前后两个0点），随机配对数组  

//读取文件
void readfile(void)
{
	using namespace std;
	ifstream inFile;
	inFile.open("r102.txt");
	if (!inFile.is_open())
	{
		cout << "could not open the file." << endl;
	}
	int count0 = 0;
	while (inFile.good())
	{

		inFile >> customer1[count0].number >> customer1[count0].x >> customer1[count0].y >> customer1[count0].demand >>
			customer1[count0].etime >> customer1[count0].ltime >> customer1[count0].stime;
		count0++;
	}
	inFile.close();
	for (int i = 1; i < Q + 1; i++)//计算角度
		customer1[i].angle = atan2((customer1[i].y - 50), (customer1[i].x - 40))*Rad_to_deg;
	for (int i = 1; i < Q + 1; i++)//计算距离
		customer1[i].distance = sqrt((customer1[i].y - 50)*(customer1[i].y - 50) + (customer1[i].x - 40)*(customer1[i].x - 40));
	for (int i = 1; i < Q + 1; i++)
		customer2[i] = customer1[i];
}

//根据角度升序排序的customer2
void sort_by_angle()
{
	for (int i = 1; i< Q + 1; i++)
		customer2[i - 1] = customer1[i];
	for (int i = 0; i < Q; i++)
	{
		for (int j = 1; j < Q - i; j++)
		{
			customer temp;
			if (customer2[j - 1].angle > customer2[j].angle)
			{
				temp = customer2[j];
				customer2[j] = customer2[j - 1];
				customer2[j - 1] = temp;
			}
		}
	}
}

//根据距离升序排序 customer3
void sort_by_distance()
{
	for (int i = 1; i < Q + 1; i++)
		customer3[i - 1] = customer1[i];
	for (int i = 0; i < Q; i++)
	{
		for (int j = 1; j < Q - i; j++)
		{
			customer temp;
			if (customer3[j - 1].distance > customer3[j].distance)
			{
				temp = customer3[j];
				customer3[j] = customer3[j - 1];
				customer3[j - 1] = temp;
			}
		}
	}
}

//计算距离矩阵
void calDistance(double distances[Q + 1][Q + 1])
{
	for (int i = 0; i < Q + 1; i++)
	{
		for (int j = 0; j < Q + 1; j++)
		{
			double deltaX = customer1[i].x - customer1[j].x;
			double deltaY = customer1[i].y - customer1[j].y;
			distances[i][j] = sqrt(deltaX * deltaX + deltaY * deltaY);
		}
	}
}

//求较大值  
double max(double a, double b)
{
	if (a > b)
		return a;
	else
		return b;
}

//重置全局变量  
void resetVariables()
{
	int i, j;
	for (i = 0; i < Q; i++) {
		customer1[i].btime = 0;
		customer1[i].wtime = 0;
		customer1[i].pos = 0;
		remain[i] = 200;
		len[i] = 0;
	}
	for (i = 0; i < Q; i++) {
		for (j = 0; j < Q; j++) {
			routes[i][j] = 0;
		}
	}
}

//找到扫描的第一个客户
int getFirCust(int i)
{
	int no;
	for (int j = 0; j < Q; j++)
	{
		if (customer3[i].number == customer2[j].number)
		{
			no = j;
			break;
		}
	}
	return no;
}

//计算到达客户j的时间  
double calArriveTime(int j, int i)
{
	double pBtime;
	if (i == 0)
		pBtime = 0;
	else
		pBtime = customer1[i].btime;
	return (pBtime + customer1[i].stime + distances[i][j] * 1);
}

//计算客户j的服务开始时间  
double calBtime(int j, int i)
{
	double arriveTime = calArriveTime(j, i);
	return max(arriveTime, customer1[j].etime);
}

//计算客户j的等待时间  
double calWtime(int j, int i)
{
	double arriveTime = calArriveTime(j, i);
	if (arriveTime >= customer1[j].etime)
		return 0;
	else
		return customer1[j].etime - arriveTime;
}

//验证是否满足time feasibility的充要条件  
bool meetTCondition(int u, int pos, int count, int len)
{
	double pf;//前推值
	int prev, next, ts;
	prev = routes[count][pos - 1];
	next = routes[count][pos];
	customer1[u].btime = calBtime(u, prev);
	if (customer1[u].btime > customer1[u].ltime)
		return false;
	else {
		if (next != 0)
		{
			pf = calBtime(next, u) - customer1[next].btime;
			if (customer1[next].btime + pf > customer1[next].ltime)
				return false;
			int r;
			for (r = pos + 1; r < len - 1; r++)
			{
				ts = routes[count][r];
				pf = max(0, pf - customer1[ts].wtime);
				if (customer1[ts].btime + pf > customer1[ts].ltime)
					return false;
			}
			if (customer1[routes[count][r - 1]].btime + pf + customer1[routes[count][r - 1]].stime + distances[routes[count][r - 1]][0] * 1 > customer1[0].ltime)
				return false;
		}
		else
		{
			if (customer1[u].btime + customer1[u].stime + distances[u][0] > customer1[0].ltime)
				return false;
		}
		return true;
	}
}

//在count路径上的插入客户no 
void insertCust(int count, int len1, int no)
{
	int i, ts;
	for (i = len1; i > customer1[no].pos; i--)
	{
		routes[count][i] = routes[count][i - 1];
	}
	routes[count][i] = no;
	for (; i < len1; i++) 
	{
		ts = routes[count][i];
		customer1[ts].wtime = calWtime(ts, routes[count][i - 1]);
		customer1[ts].btime = calBtime(ts, routes[count][i - 1]);
	}
	remain[count] -= customer1[no].demand;
	len[count]++;
	/*cout << "count:" << count << " len:" << len[count] << " routes:\n";
	for (int i = 0; i < 10; i++)
	cout << routes[count][i]<<" ";
	cout << "\n wtime:" << customer1[no].wtime << " btime:" << customer1[no].btime <<" etime:"<< customer1[no].etime<<" distance:"<<distances[0][no]<<endl;
	exit(0);*/
}

//初始化新子路径 
void initialNewRoute(int a, int count)
{
	int custNo = a;
	routes[count][0] = 0;
	routes[count][1] = 0;
	len[count] = 2;
	customer1[custNo].pos = 1;
	insertCust(count, len[count], custNo);
}

void vrptw(int a,int z)    //初始种群的产生
{
	int b,  flag1 = 0, flag2 = 0;
	b= a;
	int custNo;
	int count = 0;            //第 条子路径，
	initialNewRoute(customer2[b].number, count);
	b = (++b % Q);
	while (b != a)
	{
		
		flag1 = 0, flag2 = 0;
		custNo = customer2[b].number;
		for (int i = 1; i < len[count]; i++)
		{
			if (meetTCondition(custNo, i, count, len[count]) && remain[count] >= customer1[custNo].demand)
			{
				customer1[custNo].pos = i;
				insertCust(count, len[count], custNo);

				/*cout << "count:" << count << " len:" << len[count] << " routes:\n";
				for (int i = 0; i < 10; i++)
				cout << routes[count][i]<<" ";
				cout << "\n wtime:" << customer1[24].wtime << " btime:" << customer1[24].btime <<" stime"<<customer1[20].stime<<" etime:"<< customer1[24].etime<<" distance:"<<distances[0][24]<<endl;
				exit(0);*/

				flag1 = 1;
				b = (++b %Q);
				break;
			}
		}
		if (flag1)	continue;
		if (count != 0)
		{
			for (int i = 1; i < len[count - 1]; i++)
			{
				if (meetTCondition(custNo, i, count - 1, len[count - 1]) && remain[count - 1] >= customer1[custNo].demand)
				{
					customer1[custNo].pos = i;
					insertCust(count - 1, len[count - 1], custNo);
					flag2 = 1;
					b = (++b % Q);
					break;
				}
			}
		}
		if (flag2)	continue;
		count++;
		initialNewRoute(customer2[b].number, count);
		b = (++b % Q);

		
		//测试函数
		//cout << "\n";
		//for (int i = 0; i < 20; i++)
		//	cout << routes[1][i] << " ";
		/*for (int i = 1; i < 6; i++)
		{
		int j = routes[0][i];
		int k = routes[0][i - 1];
		cout <<"\n custom: "<<j<<" etime:" << customer1[j].etime << " ltime:" << customer1[j].ltime
		<< " btime:" << customer1[j].btime << " stime:" << customer1[j].stime << " wtime:"<<customer1[j].wtime
		<<" distance:" << distances[k][j] << endl;
		}
		cout<< "distance:" << distances[100][36] << endl;
		for (int i = 0; i < 20; i++)
		cout << routes[1][i] << " ";
		for (int i = 1; i < 6; i++)
		{
		int j = routes[1][i];
		int k = routes[1][i - 1];
		cout << "\n custom: " << j << " etime:" << customer1[j].etime << " ltime:" << customer1[j].ltime
		<< " btime:" << customer1[j].btime << " stime:" << customer1[j].stime << " wtime:" << customer1[j].wtime
		<< " distance:" << distances[k][j] << endl;
		}
		exit(0);*/

	}

	int m, n;
	double sum2 = 0;
	for (int i = 0; i <= count; i++)
	{
		double sum1 = 0;
		for (int j = 0; j < len[i]; j++)
		{
			initialRoutes1[z].routes[i][j] = routes[i][j];         //赋值routes
			m = routes[i][j];
			n = routes[i][j + 1];
			sum1 += distances[m][n];
		}
		initialRoutes1[z].averagevalue[i] = sum1 / (len[i] - 2);                 //赋值initialRoutes1[].averagevalue[]
		sum2 += sum1;
		initialRoutes1[z].len[i] = len[i];                        //赋值initialRoutes1[].len[]
	}
	initialRoutes1[z].value = sum2 + count;                        //赋值initialRoutes1[].value
	initialRoutes1[z].count = count;                               //赋值initialRoutes1[].count

	double min = 100000.0, max = 0.00001;
	int BEST, WORST;
	for (int i = 0; i <= count; i++)
	{
		if (initialRoutes1[z].averagevalue[i] < min)
		{
			min = initialRoutes1[z].averagevalue[i];
			BEST = i;
		}
		if (initialRoutes1[z].averagevalue[i] > max)
		{
			max = initialRoutes1[z].averagevalue[i];
			WORST = i;
		}
	}
	initialRoutes1[z].best = BEST;                             //赋值initialRoutes1[].best
	initialRoutes1[z].worst = WORST;                           //赋值initialRoutes1[].worst
}

//根据value对initialRoutes2升序排列
void sort_by_value()
{
	initialRoutes temp;
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < M - i - 1; j++)
		{
			if (initialRoutes2[j].value > initialRoutes2[j + 1].value)
			{
				temp = initialRoutes2[j];
				initialRoutes2[j] = initialRoutes2[j + 1];
				initialRoutes2[j + 1] = temp;
			}
		}
	}
}

//随机两两配对
void random_pair(int a, int b)
{
	for (int i = 0; i < Q; i++)                //将Pair[][]重置为零
		Pair[i][0] = Pair[i][1] = 0;
	int len = b - a + 1;
	int flag[Q] = { 0 };
	int rand1 = 0, row, col;
	for (int i = 0; i<len; i++)
	{
		rand1 = (rand() % len) + a;
		while (flag[rand1] == 1)
		{
			rand1 = (rand() % len) + a;
		}
		row = i / 2;
		col = i % 2;
		flag[rand1] = 1;
		Pair[row][col] = rand1;
	}
}

//找出x中的子路径替换y中种子路径后 y中重复的客户
void repeatCust(int x, int y, int *a)
{

	int bestnum = initialRoutes2[x].best, worstnum = initialRoutes2[y].worst;
	int num = 0;
	for (int i = 0; i < initialRoutes2[x].len[bestnum]; i++)
	{
		int flag = 0;
		for (int j = 0; j < initialRoutes2[y].len[worstnum]; j++)
			if (initialRoutes2[x].routes[bestnum][i] == initialRoutes2[y].routes[worstnum][j])
			{
				flag = 1;
				break;
			};
		if (!flag)
		{
			a[num] = initialRoutes2[x].routes[bestnum][i];
			num++;
		}
	}
}

//找出x中的子路径替换y中种子路径后 y中丢失的客户
void loseCust(int x, int y, int *a)
{
	int bestnum = initialRoutes2[x].best, worstnum = initialRoutes2[y].worst;
	int num = 0;
	for (int i = 0; i <initialRoutes2[y].len[worstnum]; i++)
	{
		int flag = 1;
		for (int j = 0; j < initialRoutes2[x].len[bestnum]; j++)
		{
			if (initialRoutes2[x].routes[bestnum][j] == initialRoutes2[y].routes[worstnum][i])
			{
				flag = 0;
				break;
			}
		}
		if (flag)
		{
			a[num] = initialRoutes2[y].routes[worstnum][i];
			num++;
		}
	}
}


//把最好子路径放进去initialRoutes0中
void replaceCount(int x, int y)
{
	int bestnum = initialRoutes2[x].best, worstnum = initialRoutes2[y].worst;
	for (int i = 0; i < Q; i++)
	{
		initialRoutes0.routes[worstnum][i] = initialRoutes2[x].routes[bestnum][i];
	}
	initialRoutes0.len[worstnum] = initialRoutes2[x].len[bestnum];      //更新被替换的子路径长度
}

//重置initialRoutes0
void resetInitialRoutes0()
{
	for (int i = 0; i < Q; i++)
	{
		for (int j = 0; j < Q; j++)
			initialRoutes0.routes[i][j] = 0;
		initialRoutes0.averagevalue[i] = 0;
		initialRoutes0.len[i] = 0;
	}
	initialRoutes0.count = 0;
	initialRoutes0.best = 0;
	initialRoutes0.worst = 0;
}

//除去initiaoRoutes0中重复的客户
void deleteCust(int * a)
{

	int count = (initialRoutes0.count + 1), ROW, COLUMN, flag;
	int worstnum = initialRoutes0.worst;
	/*if (repeat0 == 6 && repeat1 == 16)
	{
		int count = 0;
	for (int i = 0; i < 20; i++)
	{
		for (int j = 0; j < 15; j++)
		{
			if (initialRoutes0.routes[i][j] != 0)
				count++;
			cout << initialRoutes0.routes[i][j] << " "; }
		cout << "\n";
	}
	cout << "\n count:" << count;
	}*/
	for (int i = 0; a[i] != 0; i++)
	{
		/*if (repeat0 == 6 && repeat1 == 16)
			cout << initialRoutes0.best << endl;*/
		flag = 0;
		for (int row = 0; ;)
		{
			if (row == worstnum)
				row = (++row) % count;
			for (int column = 0; column < initialRoutes0.len[row]; column++)
			{
				if (a[i] == initialRoutes0.routes[row][column])
				{
					ROW = row;
					COLUMN = column;
					flag = 1;
					break;
				}
			}
			row = (++row) % count;
			if (flag)
				break;
		}
		for (int column = COLUMN; column < initialRoutes0.len[ROW] - 1; column++)
			initialRoutes0.routes[ROW][column] = initialRoutes0.routes[ROW][column + 1];
		initialRoutes0.len[ROW]--;
	}
	
	int nowcount = initialRoutes0.count;
	for (int i = 0; i <= initialRoutes0.count; i++)                 //检查并更新initial 0的子路径数量
	{
		if (initialRoutes0.routes[i][1] == 0)
			nowcount--;
	}
	if (nowcount < initialRoutes0.count)
	{
		int temp[Q][Q];
		for (int i = 0; i <= initialRoutes0.count; i++)
		{
			for (int j = 0; j < Q; j++)
			{ 
				temp[i][j] = initialRoutes0.routes[i][j];
				initialRoutes0.routes[i][j] = 0;
			}
		}
		int zz = 0;
		for (int i = 0; i <= initialRoutes0.count; i++)
		{
			if (temp[i][1] != 0)
			{
				for (int j = 0; j < Q; j++)
					initialRoutes0.routes[zz][j] = temp[i][j];
				zz++;
			}
		}
		initialRoutes0.count = nowcount;
	}
}


//更新已插入客户的wtime,btime
void renewTime()
{
	int m, n;
	for (int i = 0; i <= initialRoutes0.count; i++)
	{
		for (int j = 0; j < len[i] - 2; j++)
		{
			m = routes[i][j];
			n = routes[i][j + 1];
			customer1[n].btime = calBtime(n, m);
			customer1[n].wtime = calWtime(n, m);
		}
	}
}

//更新剩余容量-- remain[]
void renewRemain()
{
	for (int i = 0; i <= initialRoutes0.count; i++)
	{
		for (int j = 0; j < len[i]; j++)
			remain[i] -= customer1[routes[i][j]].demand;
	}
}

//把initialRoutes0.routes的值赋给 routes[][]
void renewRoutes()
{
	for (int i = 0; i <= initialRoutes0.count; i++)
	{
		for (int j = 0; j < Q; j++)
			routes[i][j] = initialRoutes0.routes[i][j];
	}
}

//更新initialRoutes0.len[]的值并赋给len[]
void renewLen()
{
	for (int i = 0; i <= initialRoutes0.count; i++)
	{
		int m = 2, j = 1;
		while (initialRoutes0.routes[i][j] != 0)
		{
			m++;
			j++;
		}
		len[i] = initialRoutes0.len[i] = m;
	}
}

//找出扫描到的第一个子路径
int find_first_route(int cust, int *a)
{
	
	int nextnum, ROW;
	int i = 0, j = 0, flag = 0;
	while (cust != customer2[i].number)
	{
		i = (++i) % Q;
	}
	nextnum = (++i) % Q;
	while (a[j] != 0)
	{
		if (a[j] == customer2[nextnum].number)
		{
			j = 0;
			nextnum = (++nextnum) % Q;
			continue;
		}
		j++;
	}
	//if (test1 == 2 && test2 == 10000)     //the problem is here
	//{ 
	//	cout << "nextnum" << nextnum << endl;
	//	int num1 = 0;
	//	for (int i = 0; i < 11; i++)
	//	{
	//		for (int j = 0; j <16; j++)
	//		{
	//			cout << initialRoutes0.routes[i][j] << " ";
	//			if (initialRoutes0.routes[i][j] != 0)
	//				num1 ++;
	//		}
	//		cout << "\n";
	//	}
	//	cout << "num:" << num1<< endl;
	//}
	for (int row = 0; row <= initialRoutes0.count; row++)
	{
		for (int column = 0; column < Q; column++)
		{
			if (customer2[nextnum].number == initialRoutes0.routes[row][column])
			{
				ROW = row;
				flag = 1;
				break;
			}
		}
		if (flag)
			break;
	}
	return ROW;
}

//计算子路径的长度
double calSinglevalue(int pos, int count, int cust)
{
	int m = 0, n = 0;
	double sum = 0;
	for (int i = 0; i < pos - 1; i++)
	{
		m = routes[count][i];
		n = routes[count][i + 1];
		sum += distances[m][n];
	}
	sum += distances[n][cust];
	sum += distances[cust][routes[count][pos]];
	for (int i = pos; i <initialRoutes0.len[count] - 1; i++)
	{
		m = routes[count][i];
		n = routes[count][i + 1];
		sum += distances[m][n];
	}
	return  sum;
}

//插入空闲客户
void insert_lose_cust(int  *a)
{	
	int b[Q] = { 0 };
	for (int i = 0; a[i] != 0; i++)
		b[i] = a[i];
	for (int i = 0; a[i] != 0; i++)
	{		
		double singlevalue[Q] = { 0 }, min = 99999.9;
		int pos1, poses[Q] = { 0 }, num = 0, NUM = 0, count;		
		count = find_first_route(a[i], b);		
		while (NUM < 3)
		{			
			/*if (count == initialRoutes0.worst)           //不用最优路径保存策略,且我也不知道initial 0.worst的值
			count = (++count) % (initialRoutes0.count + 1);*/
			for (int j = 1; j < len[count]; j++)       //要注意这里面判断的是routes[][]
			{
				if (meetTCondition(a[i], j, count, len[count]) && remain[count] >= customer1[a[i]].demand)
				{
					poses[num] = j;
					num++;
				}
			}
			if (num > 0)
				break;
			count = (++count) % (initialRoutes0.count + 1);
			NUM++;
		}
		if (num == 0)
		{
			initialRoutes0.count++;
			initialNewRoute(a[i], initialRoutes0.count);
		}
		else
		{
			for (int j = 0; poses[j] != 0; j++)
				singlevalue[j] = calSinglevalue(poses[j], count, a[i]);
			for (int j = 0; poses[j] != 0; j++)
			{
				if (singlevalue[j] < min)
				{
					min = singlevalue[j];
					pos1 = poses[j];
				}
			}
			customer1[a[i]].pos = pos1;
			insertCust(count, len[count], a[i]);
		}
	}
}

//计算个体目标函数值
double calValue(double * sum1)
{
	double sum = 0;
	int m, n;
	for (int i = 0; i <= initialRoutes0.count; i++)
	{
		for (int j = 0; j < len[i] - 1; j++)
		{
			m = routes[i][j];
			n = routes[i][j + 1];
			sum1[i] += distances[m][n];
			sum += distances[m][n];
		}
	}
	return sum;
}

//判断个体是否有所改善及是否替换,是否直接替换掉initialRoutes[y]
void compare_replace(int y)
{
	//输出函数
	/*int num = 0;
	for (int i = 0; i < 20; i++)
	{
	for (int j = 0; j < 15; j++)
	{
	cout << routes[i][j] << " ";
	if (routes[i][j] != 0)  num++;
	}
	cout << "\n";
	}cout << "num:" << num << endl;
	cout << initialRoutes0.count << endl;
	for (int i = 0; i < 20; i++)
	cout << len[i] << " "; exit(0);*/
	double min = 9999.9, max = 0.0001;
	int MAX, MIN;
	double sum1[Q] = { 0 };
	double value = calValue(sum1);
	if (value < initialRoutes2[y].value)
	{
		for (int a = 0; a < Q; a++)
		{
			for (int b = 0; b < Q; b++)
				initialRoutes2[y].routes[a][b] = 0;
		}
		for (int i = 0; i <= initialRoutes0.count; i++)
		{
			for (int j = 0; j < len[i]; j++)
			{
				initialRoutes2[y].routes[i][j] = routes[i][j];
			}
			initialRoutes2[y].len[i] = len[i];
			initialRoutes2[y].averagevalue[i] = sum1[i] / (len[i] - 2);
		}
		initialRoutes2[y].count = initialRoutes0.count;
		initialRoutes2[y].value = value;
		for (int i = 0; i <= initialRoutes0.count; i++)
		{
			if (initialRoutes2[y].averagevalue[i] < min)
			{
				min = initialRoutes2[y].averagevalue[i];
				MIN = i;
			}
			if (initialRoutes2[y].averagevalue[i] > max)
			{
				max = initialRoutes2[y].averagevalue[i];
				MAX = i;
			}
		}
		initialRoutes2[y].best = MIN;
		initialRoutes2[y].worst = MAX;
	}
}

//initialRoutes2中第x个个体的最好子路径代替第y个个体的最差子路径
void rePlace(int x, int y)
{
	

	int repeat[Q] = { 0 };
	int lose[Q] = { 0 };
	repeatCust(x, y, repeat);
	loseCust(x, y, lose);

	initialRoutes0 = initialRoutes2[y];     
	
	replaceCount(x, y);
	
	deleteCust(repeat);
	
	resetVariables();                                   //重置全局变量
	
	renewRoutes();                                     //routes[][]
	renewLen();                                        //len[]	
	renewTime();
	
	renewRemain();                                     //remain[]
	
	insert_lose_cust(lose);                          //这里改变的是len[]和routes[][]的值	
	compare_replace(y);

}


//教师间的相互学习
void teachersLearning()
{
	for (int i = 0; i < T; i++)
	{
		rePlace(Pair[i][0], Pair[i][1]);
		rePlace(Pair[i][1], Pair[i][0]);
	}
}

//交换选中的两条子路径
void ex_routes(int arr[][Q], int n, int one, int two, int point1, int point2)
{
	for (int i = 0; i <= point1; i++)
		arr[0][i] = initialRoutes0.routes[one][i];
	for (int i = 0; i <= point2; i++)
		arr[1][i] = initialRoutes0.routes[two][i];
	int m = point1 + 1; n = point2 + 1;
	for (int i = point2 + 1; i < initialRoutes0.len[two]; i++)
	{
		arr[0][m] = initialRoutes0.routes[two][i];
		m++;
	}
	for (int i = point1 + 1; i < initialRoutes0.len[one]; i++)
	{
		arr[1][n] = initialRoutes0.routes[one][i];
		n++;
	}
}

//判断载重量是否满足要求
int meet_weight(int arr[][Q], int m)
{
	int flag = 0;
	for (int i = 0; i<m; i++)
	{
		int j = 1;
		double demand = 0;
		while (arr[i][j] != 0)
		{
			int cus = arr[i][j];
			demand += customer1[cus].demand;
			j++;
		}
		if (demand > DEM)
			flag = 1;
		if (flag)
			break;
	}
	return flag;
}

//判断是否超时
int meet_time(int arr[][Q], int m)
{
	int flag = 0;
	for (int i = 0; i < m; i++)
	{
		int j = 1, sec = 0;
		while (arr[i][j] != 0)
		{
			int fir = arr[i][j - 1];
			sec = arr[i][j];
			customer1[sec].btime = calBtime(sec, fir);
			if (customer1[sec].btime>customer1[sec].ltime)
			{
				flag = 1;
				break;
			}
			j++;
		}
		if (sec != 0 && calBtime(0, sec) > customer1[0].ltime)
			flag = 1;
		if (flag)
			break;
	}
	return flag;
}

//判断是否距离更短
int be_shorter(int arr[][Q], int m, int one, int two)
{
	int subroutes[2] = { one,two };
	double alldistances[2] = { 0 };          //分别是交换后和交换前的距离
	int flag = 0;
	for (int i = 0; i < m; i++)
	{
		int j = 1, nex = 0;
		while (arr[i][j] != 0)
		{
			int fir = arr[i][j - 1];
			nex = arr[i][j];
			alldistances[0] += distances[fir][nex];
			j++;
		}
		alldistances[0] += distances[nex][0];
	}
	for (int i = 0; i < 2; i++)
	{
		int j = 1, nex = 0;
		while (initialRoutes0.routes[subroutes[i]][j] != 0)
		{
			int fir = initialRoutes0.routes[subroutes[i]][j - 1];
			nex = initialRoutes0.routes[subroutes[i]][j];
			alldistances[1] += distances[fir][nex];
			j++;
		}
		alldistances[1] += distances[nex][0];
	}
	if (alldistances[0] < alldistances[1])
		flag = 1;
	return flag;
}

//更新子路径
void renew_subroutes(int arr[][Q], int m, int one, int two)
{
	int rou[2] = { one,two };
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < Q; j++)
			initialRoutes0.routes[rou[i]][j] = 0;
	int last = initialRoutes0.count;

	if (arr[0][1] == 0 || arr[1][1] == 0)    //若出现全零行，更新initial 0的count
	{
		int unzero = (arr[0][1] != 0) ? 0 : 1;
		for (int i = 0; i < Q; i++)
		{
			initialRoutes0.routes[one][i] = arr[unzero][i];
			initialRoutes0.routes[two][i] = initialRoutes0.routes[last][i];
			initialRoutes0.routes[last][i] = 0;
		}
		initialRoutes0.len[last] = 0;
		initialRoutes0.count--;
	}
	else
	{
		for (int i = 0; i < m; i++)
		{
			int j = 1;
			while (arr[i][j] != 0)
			{
				initialRoutes0.routes[rou[i]][j] = arr[i][j];
				j++;
			}
		}
	}
	for (int i = 0; i < 2; i++)
	{
		int count = 2;
		int j = 1;
		while (initialRoutes0.routes[rou[i]][j] != 0)
		{
			count++;
			j++;
		}
		initialRoutes0.len[rou[i]] = count;
	}
	if (initialRoutes0.count < last)
		initialRoutes0.len[last] = 0;
}

//对教师a进行邻域搜索
void VNS(int a)
{
	initialRoutes0 = initialRoutes2[a];
	int bet = 0;
	for (int i = 0; i <= initialRoutes0.count; i++)
	{
		int better = 0;
		for (int j = 0; j <(initialRoutes0.len[i] - 1); j++)
		{
			int fir = initialRoutes0.routes[i][j];
			int sec = initialRoutes0.routes[i][j + 1];
			for (int k = i + 1; k <= initialRoutes0.count; k++)
			{

				for (int g = 0; g < (initialRoutes0.len[k] - 1); g++)
				{
					int thir = initialRoutes0.routes[k][g];
					int fort = initialRoutes0.routes[k][g + 1];
					if (fir == thir || sec == fort)
						continue;
					int exroutes[2][Q];
					for (int i = 0; i < 2; i++)
						for (int j = 0; j < Q; j++)
							exroutes[i][j] = 0;
					ex_routes(exroutes, 2, i, k, j, g);    //得出交换后的子路径	
					if (meet_weight(exroutes, 2))          //判断是否超重
						continue;
					if (meet_time(exroutes, 2))           //判断是否超时
						continue;
					if (!be_shorter(exroutes, 2, i, k))     //判断结果是否有所改善
						continue;
					renew_subroutes(exroutes, 2, i, k);     //更新initial 0子路径的count与len，包括了是否出现零行的情况          
					i = -1;
					bet = 1;                               //用来判断是否VNS后得到了更好解，从而接下来判断是否更新initialRoutes2[a]
					better = 1;
					break;
				}
				if (better)
					break;
			}
			if (better)
				break;
		}
	}
	if (bet)                            //赋值给initialRoutes[a],并更新各个参数
	{
		for (int i = 0; i <= initialRoutes2[a].count; i++)
		{
			for (int m = 0; m < Q; m++)                                   //routes[][]全部置零
				initialRoutes2[a].routes[i][m] = 0;
			initialRoutes2[a].len[i] = 0;                                //len[]全部置零
			initialRoutes2[a].averagevalue[i] = 0;                        //averagevalue置零
		}
		initialRoutes2[a].count = initialRoutes0.count;              //更新count
		double sum = 0, sum1[Q] = { 0 };
		int m, n;
		for (int i = 0; i <= initialRoutes2[a].count; i++)
		{
			initialRoutes2[a].len[i] = initialRoutes0.len[i];       //更新Len[]
			for (int j = 0; j < (initialRoutes2[a].len[i] - 1); j++)
			{
				initialRoutes2[a].routes[i][j] = initialRoutes0.routes[i][j];  //更新routes[][]
				m = initialRoutes0.routes[i][j];
				n = initialRoutes0.routes[i][j + 1];
				sum1[i] += distances[m][n];
				sum += distances[m][n];
			}
			initialRoutes2[a].averagevalue[i] = sum1[i] / (initialRoutes2[a].len[i] - 2);    //更新averagevalue[]
		}
		initialRoutes2[a].value = sum;                   //更新value
		double max = 0.0001, min = 100000;
		int MAX, MIN;
		for (int i = 0; i <= initialRoutes2[a].count; i++)
		{
			if (initialRoutes2[a].averagevalue[i] < min)
			{
				min = initialRoutes2[a].averagevalue[i];
				MIN = i;
			}
			if (initialRoutes2[a].averagevalue[i] > max)
			{
				max = initialRoutes2[a].averagevalue[i];
				MAX = i;
			}
		}
		initialRoutes2[a].best = MIN;                    //更新best与worst
		initialRoutes2[a].worst = MAX;
	}
}

//教学阶段的分组
void random_pair_ano(int a, int b)
{
	for (int i = 0; i < Q; i++)                //将Pair[][]重置为零
		Pair[i][0] = Pair[i][1] = 0;
	int len = b - a + 1;
	int flag[Q] = { 0 };
	int rand1, rand2;
	for (int i = 0; i<len; i++)
	{
		rand1 = rand() % T;
		rand2 = (rand() % len) + a;
		while (flag[rand2] == 1)
		{
			rand2 = (rand() % len) + a;
		}
		flag[rand2] = 1;
		Pair[i][0] = rand1;
		Pair[i][1] = rand2;
	}
}


//教学阶段
void teaching_phase()
{
	for (int i = 0; i < GS + WS; i++)
	{
		rePlace(Pair[i][0], Pair[i][1]);           //repeat1==16的时候出问题了
	}
}

//学生之间的相互学习
void studentsLearning()
{
	for (int i = 0; i < GS / 2; i++)
	{
		rePlace(Pair[i][0], Pair[i][1]);		
		rePlace(Pair[i][1], Pair[i][0]);
		
	}
}

/*
算法思路：
	产生初始种群
	教师间的相互学习
		对于两个相互学习的个体，分别选出它们的最好子路径和最差子路径，分别让最好的子路径替换最差子路径
	教师的自学--从第一条子路径的第一个客户开始往后插入
	教学
	学生的相互学习
*/
//主函数
int main()
{
	readfile();
	sort_by_angle();
	sort_by_distance();
	calDistance(distances);
	double bestcusts[Reapeat];            //储存最优解的数组
	for (int mn = 0; mn<Reapeat; mn++)
	{
		cout << mn << endl;
		int pq = getFirCust(mn);
		for (int m = 0; m <M; m++)		//初始种群的产生-用扫描法依次产生可行解
		{
			resetVariables();
			vrptw(pq,m);   
			pq = (pq+2) % Q;
		}

		for (int i = 0; i < M; i++)
			initialRoutes2[i] = initialRoutes1[i];         //先对initialRoute2[]赋值
		sort_by_value();		
		for (int repeat = 0; repeat<1000; repeat++)
		{
			random_pair(0, T - 1);                   //代表的是initialRoutes2中的第T-1的个体
			teachersLearning();                      //教师间的相互学习

			for (int i = 0; i <T; i++)				//教师的自学
				VNS(i);                             //对教师依次进行邻域搜索
			
			random_pair_ano(T, M - 1);
			teaching_phase();                       //教学阶段    			
			
			random_pair(T, M - WS - 1);
			studentsLearning();                     //学生相互学习阶段

			sort_by_value();                        //对initial2进行升序排序
		}
		bestcusts[mn] = initialRoutes2[0].value;     //输出本次最优解
	}
	
	//种群输出
	for (int i = 0; i < Reapeat; i++)
		cout<<bestcusts[i]<<endl;
	/*int num1[M] = { 0 };
	for (int k=0; k <10; k++)
	{
		int aa, bb;
		cout << "\n" << "  #" << k + 1 << endl;
		for (int i = 0; i < 11; i++)
		{
			for (int j = 0; j <16; j++)
			{
				aa = initialRoutes2[k].routes[i][j];
				bb = initialRoutes2[k].routes[i][j + 1];
					cout << initialRoutes2[k].routes[i][j] << " ";
				if (initialRoutes2[k].routes[i][j] != 0)
					num1[k] ++;
			}
			 cout << "--------len(" << i << "):" << initialRoutes2[k].len[i] << "\n";
			 cout << "\n";
		}
		 cout << "num:" << num1[k] << ";value:" << initialRoutes2[k].value << " ;count:" << initialRoutes2[k].count
			<< ";best:" << initialRoutes2[k].best << ";worest:" << initialRoutes2[k].worst << endl;
	}*/

	return 0;
}