vpr1.cpp

解VRPTW问题的模拟退火程序

			// 计算被删除客户所在路径客户的相关度
		while(pp!=m_newVehicle.end())
		{
			UINT indexx=pp->GetFirst();

			while(indexx)
			{
				double relate;
				if(pp!=p)relate=1/(WasteTime(indexx,index)/MAX_TIME);
				else  relate=1/(WasteTime(indexx,index)/MAX_TIME+1);
				Relateness[indexx]+=relate;
				if(max_relate<Relateness[indexx])
				{
					max_relate=Relateness[indexx];
					index=indexx;
				}
				indexx=m_newClient[indexx].GetNext();
			}
			pp++;
		}		
	}


}

void CVPR::OutPut(bool IsNewSolution)//输出解
{
	if(IsNewSolution)
	{
	list<CVehicle>::iterator v=m_newVehicle.begin();
	while(v!=m_newVehicle.end())
	{
		cout<<"容量"<<m_capacity-v->GetVacuum()<<"    ";
		int out=v->GetFirst();
		cout<<0<<"    ";
		while(out)
		{
			cout<<out<<"    ";
			out=m_newClient[out].GetNext();
		}
		cout<<0<<"    "<<endl;
		v++;
	}
	}
	else{
	list<CVehicle>::iterator v=m_Vehicle.begin();
	while(v!=m_Vehicle.end())
	{
		int out=v->GetFirst();
		cout<<0<<"    ";
		while(out)
		{
			cout<<out<<"    ";
			out=m_Client[out].GetNext();
		}
		cout<<0<<"    "<<endl;
		v++;
	}
	}
}

CVPR::~CVPR()
{
	delete[] distance_data;
    delete[]m_rand;

}

double CVPR::CalD(UINT i, UINT j)
{
	UINT I,J;
	if(i==j)return 0.0;
	I=i<j?i:j;
	J=i<j?j:i;
	
	UINT index=(2*m_Count-I+1)*I/2+J-I-1;
	return distance_data[index];
	
}

double CVPR::CalNewTime(UINT index,bool IsNewSolution)    //计算新的服务时间
{
	if(IsNewSolution)
	{
		double uperTime=m_newClient[index].GetTime_low();
		UINT index1=m_newClient[index].GetPrevious();
		double NewTime=m_newClient[index1].GetTime_new()+m_newClient[index1].GetServerTime()+
			WasteTime(index,index1);
		return uperTime>NewTime?uperTime:NewTime;
	}
	else{
		
		double uperTime=m_Client[index].GetTime_low();
		UINT index1=m_Client[index].GetPrevious();
		double NewTime=m_Client[index1].GetTime_new()+m_Client[index1].GetServerTime()+
			WasteTime(index,index1);
		return uperTime>NewTime?uperTime:NewTime;
	}
	
}

double CVPR::WasteTime(UINT i, UINT j)
{
	return CalD(i,j)/m_speed;
}

void CVPR::CalTotalDistance(double & distance)//以新路径为标准
{
	distance=0;
    list<CVehicle>::iterator p1=m_newVehicle.begin();
	while(p1!=m_newVehicle.end())
	{
		//加上中心库到第一个客户的距离
		UINT index=p1->GetFirst();		
		distance+=CalD(0,index);

		while(index)
		{
			distance+=CalD(index,m_newClient[index].GetNext());
			index=m_newClient[index].GetNext();
		}
		p1++;
	}
	
}

void CVPR::CalTotalTime(double &time)
{
	list<CVehicle>::iterator p=m_Vehicle.begin();
	while(p!=m_Vehicle.end())
	{
		double e,l;
		e=m_Client[0].GetTime_low();
		l=m_Client[0].GetTime_uper();
		UINT index(0),index1(p->GetFirst());
		do
		{
			index=index1;
			index1=m_Client[index1].GetNext();
		}while(index1);
		double e1,l1;
		do
		{
			e1=m_Client[index].GetTime_low();
			l1=m_Client[index].GetTime_uper();
			e-=WasteTime(index,index1)+m_Client[index].GetServerTime();
			l-=WasteTime(index,index1)+m_Client[index].GetServerTime();
			e=e>e1?e:e1;
			l=l>l1?l1:l;
		    index1=index;
			index=m_Client[index].GetPrevious();
		}while(index1);
		cout<<"最佳出发时间:"<<l;
		index1=p->GetFirst(),index=0;
	     do
		{
			l+=m_Client[index1].GetServerTime()+WasteTime(index,index1);
			cout<<setw(8)<<l;
			index=index1;
			index1=m_Client[index].GetNext();
		}while(index);
		cout<<endl;
		p++;
	}
	
}

void CVPR::ExchangeSolution(bool findnew)
{
	
	if(findnew){
		//准备新解的路径
		list<CVehicle>::iterator p1=m_Vehicle.begin();
		m_newVehicle.clear();
		while(p1!=m_Vehicle.end())
		{
			CVehicle vehi(*p1);	
			m_newVehicle.push_back(vehi);
			p1++;
		}
		
		//准备新解的客户
		vector<CClient>::iterator p2=m_Client.begin();
		m_newClient.clear();
		while(p2!=m_Client.end())
		{
			CClient cli(*p2);
			m_newClient.push_back(cli);
			p2++;
		}
	}
	else{
		list<CVehicle>::iterator p1=m_newVehicle.begin();
		m_Vehicle.clear();
		while(p1!=m_newVehicle.end())
		{
			CVehicle vehi(*p1);
			m_Vehicle.push_back(vehi);
			p1++;
		}
		
		vector<CClient>::iterator p2=m_newClient.begin();
		int	i=0;
		while(p2!=m_newClient.end())
		{
			m_Client[i].SetPrevious(p2->GetPrevious());
			m_Client[i].SetNewTime(p2->GetTime_new());
			m_Client[i].SetNext(p2->GetNext());
			i++;
			p2++;
		}
	}
}

void CVPR::GenerateNewSolution(UINT count,bool dis)
{
	Remove(count,dis);
/*	cout<<"移走一些客户后的路径"<<endl;
	OutPut(TRUE);
	cout<<"移走一些客户后的客户状态"<<endl;
	cout<<"客户   "<<"需求  "<<"服务时间  "<<"     时间窗   "
		<<"   新的开始时间 "<<" 前一个客户   "<<"后一个客户"<<endl;

	for (int i=0;i<=m_Count;i++)
	{
		cout<<i<<setw(8)<<m_newClient[i].GetNeed()<<setw(8)<<m_newClient[i].GetServerTime()<<setw(10)<<"["
			<<setw(3)<<m_newClient[i].GetTime_low()<<setw(5)<<m_newClient[i].GetTime_uper()<<"]"<<setw(12)
			<<m_newClient[i].GetTime_new()<<setw(14)
			<<m_newClient[i].GetPrevious()<<setw(12)<<m_newClient[i].GetNext()<<endl;
	}*/
	ReInsert();
/*	cout<<"改进后的解"<<endl;
	OutPut(TRUE);
	cout<<"新解中客户的状态"<<endl;
	cout<<"客户   "<<"需求  "<<"服务时间  "<<"     时间窗   "
		<<"   新的开始时间 "<<" 前一个客户   "<<"后一个客户"<<endl;
	for (i=0;i<=m_Count;i++)
	{
		cout<<i<<setw(8)<<m_newClient[i].GetNeed()<<setw(8)<<m_newClient[i].GetServerTime()<<setw(10)<<"["
			<<setw(3)<<m_newClient[i].GetTime_low()<<setw(5)<<m_newClient[i].GetTime_uper()<<"]"<<setw(12)
						<<m_newClient[i].GetTime_new()<<setw(14)
			<<m_newClient[i].GetPrevious()<<setw(12)<<m_newClient[i].GetNext()<<endl;
	}*/
}

BOOL CVPR::ReInsert()
{
	//对每个还未插入客户计算一次
	UINT index=m_newClient[0].GetNext();
	while(index)
	{
   	    UINT I(0),J(0),Index(m_newClient[0].GetNext());
		double Increase(MAX);
		while(index)
		{	
		    UINT I1(0),J1(0);
			double Increase1(MAX);
			//对每条路径计算一次
			list<CVehicle>::iterator p=m_newVehicle.begin();
			while(p!=m_newVehicle.end())
			{
				int i(0);
				int j=p->GetFirst();
				double increase1(MAX);
				do
				{
					if(Feasible(p,i,index,j,TRUE)){
						double increase=CalD(i,index)+CalD(index,j)-CalD(i,j);
						if(increase<Increase1)
						{
							I1=i;
							J1=j;
							Increase1=increase;
						}
					}
					i=j;
					j=m_newClient[j].GetNext();
				}while(i);
				p++;	
			}
			
			if(Increase>Increase1)
			{
				I=I1;
				J=J1;
				Increase=Increase1;
				Index=index;
			}
			index=m_newClient[index].GetNext();
		}
		list<CVehicle>::iterator p=m_newVehicle.begin();	//p用来指向插入的路径
		//从未插入的客户链中删除待插客户
		UINT pre=m_newClient[Index].GetPrevious();
		UINT nex=m_newClient[Index].GetNext();
		m_newClient[pre].SetNext(nex);
		if(nex)
			m_newClient[nex].SetPrevious(pre);
		//将客户插入
		if(I==0)
		{
			if(J==0){//没找到合适的插入位置,则构造新路径,插入
				CVehicle v(m_capacity-m_newClient[Index].GetNeed(),0);
				m_newVehicle.push_back(v);
				m_newClient[Index].SetNext(0);
				m_newClient[Index].SetPrevious(0);
				p=m_newVehicle.end();
				p--;
				p->SetFirst(Index);
			}
			else{
				
				while(p->GetFirst()!=J)
					p++;
				p->SetFirst(Index);	
				p->SetVacuum(p->GetVacuum()-m_newClient[Index].GetNeed());
			}
		}
		else{
			UINT first=I;
			while(m_newClient[first].GetPrevious())
				first=m_newClient[first].GetPrevious();
			while(p->GetFirst()!=first)
				p++;
			p->SetVacuum(p->GetVacuum()-m_newClient[Index].GetNeed());
		}
		if(I)m_newClient[I].SetNext(Index);
		if(J)m_newClient[J].SetPrevious(Index);
		
		m_newClient[Index].SetNext(J);
		m_newClient[Index].SetPrevious(I);
		
		// 改插入新客户后,每个客户新的最早开始的时间
		UINT u=Index;
		while(u){
			double time=CalNewTime(u,TRUE);
			m_newClient[u].SetNewTime(time);
			u=m_newClient[u].GetNext();
		}

/*			cout<<"客户   "<<"需求  "<<"服务时间  "<<"     时间窗   "
		<<"   新的开始时间 "<<" 前一个客户   "<<"后一个客户"<<endl;
	for (int i=0;i<=m_Count;i++)
	{
		cout<<i<<setw(8)<<m_newClient[i].GetNeed()<<setw(8)<<m_newClient[i].GetServerTime()<<setw(10)<<"["
			<<setw(3)<<m_newClient[i].GetTime_low()<<setw(5)<<m_newClient[i].GetTime_uper()<<"]"<<setw(12)
			<<m_newClient[i].GetTime_new()<<setw(14)
			<<m_newClient[i].GetPrevious()<<setw(12)<<m_newClient[i].GetNext()<<endl;
	}*/
		index=m_newClient[0].GetNext();
	}
return TRUE;
}

double CVPR::Max_time()
{
	double max_time(-MAX);
	for (int i=0;i<m_Count;i++)
		for(int j=0;j<m_Count;j++)
		{
			double time=WasteTime(i,j);
           if(max_time<time)
			   max_time=time;
		}

	return max_time;

}

CVPR::CVPR(double temperature,  double tau,

    double speed,       //汽车速度
	UINT capacity,      //汽车容量
	UINT count,        //客户数
	vector<CClient> client,  //客户需求信息
	double   *        distance_data //客户距离信息
	)
{
	this->m_Temperature=temperature;
	this->m_tau=tau;
	this->m_speed=speed;
	this->m_capacity=capacity;
	this->m_Count=count;
	this->m_Client=client;

    this->distance_data=distance_data;
	Relateness.resize(m_Count+1); 
		m_rand=new int[m_Count+1];
	for (int i=1;i<=m_Count;i++)
		m_rand[i]=0;
}

BOOL CVPR::IsSolution()
{
	vector<CClient>::iterator p=m_Client.begin();
	bool temp(1);
	for(int i=1;i<=m_Count;i++)
	{
       double newtime=m_Client[0].GetTime_new()+WasteTime(0,i);
	   if(newtime>m_Client[i].GetTime_uper())
	   {temp=0;break;}


	}
    return temp;
}