vpr1.cpp

解VRPTW问题的模拟退火程序

// VPR1.cpp: implementation of the CVPR class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "VPR1.h"
#include "iomanip"


#include <ctime> 
using namespace std;
#define MAX 10000
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CVPR::CVPR()
{
	Relateness.resize(m_Count+1); 
	m_rand=new int[m_Count+1];
	for (int i=1;i<=m_Count;i++)
		m_rand[i]=0;
}


void CVPR::SetClient(UINT index,UINT next)
{
	m_Client[next].SetNext(m_Client[index].GetNext());
	m_Client[index].SetNext(next);
	m_Client[next].SetPrevious(index);
	m_Client[m_Client[next].GetNext()].SetPrevious(next);
}

void CVPR::SetVehicle(CVehicle &vehicle,UINT first,UINT vacuum)
{
	vehicle.SetVehicle(first,vacuum);
}





bool CVPR::Open(const CString str)
{
	CFile file(str,CFile::modeRead);
	return true;
}

bool CVPR::Feasible(list<CVehicle>::iterator plCur,UINT i,UINT u,UINT j,bool IsNewSolution)//检验指定位置是否可以插入
{
	if(IsNewSolution)
	{
	if(m_newClient[u].GetNeed()<=plCur->GetVacuum())//判断是否超重
	{   
		double newtime=m_newClient[i].GetTime_new()+m_newClient[i].GetServerTime()+WasteTime(i,u);
		newtime=newtime>m_newClient[u].GetTime_low()?newtime:m_newClient[u].GetTime_low();
		double k=m_newClient[i].GetTime_new();
		if(newtime<=m_newClient[u].GetTime_uper())                 //检验u的时间窗
		{
			//检验j及j后面客户的时间窗
			do
			{
				newtime+=m_newClient[u].GetServerTime()+WasteTime(u,j);
			    newtime=newtime>m_newClient[j].GetTime_low()?newtime:m_newClient[j].GetTime_low();
				u=j;
				j=m_newClient[j].GetNext();
			}while(newtime<=m_newClient[u].GetTime_uper() &&u) ;    
			if(!u&&newtime<=m_newClient[u].GetTime_uper())return 1;
			
		}
	}}
	else{
			if(m_Client[u].GetNeed()<=plCur->GetVacuum())//判断是否超重
	{   
		double newtime=m_Client[i].GetTime_new()+m_Client[i].GetServerTime()+WasteTime(i,u);
		newtime=newtime>m_Client[u].GetTime_low()?newtime:m_Client[u].GetTime_low();
		double k=m_Client[u].GetTime_new();
		if(newtime<=m_Client[u].GetTime_uper())                 //检验u的时间窗
		{
			//检验j及j后面客户的时间窗
			do
			{
				newtime+=m_Client[u].GetServerTime()+WasteTime(u,j);
				newtime=newtime>m_Client[j].GetTime_low()?newtime:m_Client[j].GetTime_low();
				u=j;
				j=m_Client[j].GetNext();
			}while(newtime<=m_Client[u].GetTime_uper() &&u) ;    
			if(!u&&newtime<=m_Client[u].GetTime_uper())return 1;
			
		}
	}
	}
	return 0;
	
	
}

bool CVPR::Find_InitialSolution(double mu,double alpha,double lambda)//构造初始解
{
	//检验是否有解
	if(!IsSolution())
    return 0;
    
	while(m_Client[0].GetNext())
	{		
		//============构造一条新路径===================//
		CVehicle v(m_capacity,0);
		m_Vehicle.push_back(v);
		list<CVehicle>::iterator plcur=m_Vehicle.end();           //记录第一个没有插入的客户
	    plcur--;
		bool  temp(1)  ;   //当前路径还能插入客户,值为0时不能或没有客户插入
 		while(temp&&m_Client[0].GetNext())
		{
            //定义相关变量
			UINT u,I(MAX),J;                                //u表示将被插入的客户,I和J结合表示u的插入位置
			double C2(-MAX) ;                               //决策变量
		
			//选择前的准备工作
			UINT restNext=m_Client[0].GetNext();
			m_Client[0].SetNext(plcur->GetFirst());        //将中心库加入路径
			
	        UINT k(restNext);                               //计算中的客户
			//==============选择当前被插入的客户=============//	
			while(k)
			{ 		
				UINT I1,J1;	                                  //I1,J1表示客户k的最佳插入位置
				double C1(MAX);
				UINT i(0),j(plcur->GetFirst());
		
				UINT temp1(1);                                               //辅助变量

				while(temp1)
				{
					if(Feasible(plcur,i,k,j))
						
					{
						double c1=CalD(i,k)+CalD(k,j)-mu*CalD(i,j);
                        if(c1<C1) 
						{
							I1=i;
							J1=j;
							C1=c1;
						} 
					}
					i=j;
					j=m_Client[i].GetNext();
					if(!i)temp1=0;
				}

				if(C1!=MAX)
				{    double c2=lambda*CalD(0,k)-C1;
					if(c2>C2)
					{
						I=I1;
						J=J1;
						u=k;
						C2=c2;
					}
				}
				k=m_Client[k].GetNext();
			}
			
			//==============选择当前被插入的客户结束=============//
			
			
				int pp=m_Client[0].GetNext();			//=============开始插入当前客户===========================//
            if(I!=MAX)//如果有合适的客户
			{
				//更新路径信息
				if(I==0)
				{
					plcur->SetFirst(u);
				}
				plcur->SetVacuum(plcur->GetVacuum()-m_Client[u].GetNeed());
				
				//从剩余客户链中删除要插入的客户
				UINT pre(m_Client[u].GetPrevious()),nxt(m_Client[u].GetNext());
				if(pre)m_Client[pre].SetNext(nxt);
				if(nxt)m_Client[nxt].SetPrevious(pre);
				
				//让中心库重新成为剩余键的第一个客户
				if(u==restNext)
				{
				   m_Client[0].SetNext(m_Client[u].GetNext());
				}
				else m_Client[0].SetNext(restNext);
				

                //将选出的客户插入到当前路径中去
                 if(J)m_Client[J].SetPrevious(u);
				 if(I)m_Client[I].SetNext(u);
				 m_Client[u].SetPrevious(I);
				 m_Client[u].SetNext(J);
				

				// 改插入新客户后,每个客户新的最早开始的时间
				while(u){
					double time=CalNewTime(u);
					m_Client[u].SetNewTime(time);
					u=m_Client[u].GetNext();
				}

				
			}
			else {temp=0;
			m_Client[0].SetNext(restNext);
			}
			//=============插入当前客户结束===========================//	
		}
	}
return 1;
}

bool CVPR::SimulatedAnnealing(double alpha,UINT m_max,UINT iter_max)
{
	srand(time(0));
	double tempture=m_Temperature;
	double tau=m_tau;
	if(!Find_InitialSolution(2,0.8,0.2))return 0;
	cout<<"初始解:"<<endl;
	OutPut();
		cout<<"客户   "<<"需求  "<<"服务时间  "<<"     时间窗   "
		<<"   新的开始时间 "<<" 前一个客户   "<<"后一个客户"<<endl;

	for (int i=0;i<=m_Count;i++)
	{
		cout<<i<<setw(8)<<m_Client[i].GetNeed()<<setw(8)<<m_Client[i].GetServerTime()<<setw(10)<<"["
			<<setw(3)<<m_Client[i].GetTime_low()<<setw(5)<<m_Client[i].GetTime_uper()<<"]"<<setw(12)
			<<m_Client[i].GetTime_new()<<setw(14)
			<<m_Client[i].GetPrevious()<<setw(12)<<m_Client[i].GetNext()<<endl;
	}
	while(tempture>=tau)
	{
		UINT iter_num=1;      //某固定温度下迭代计数器
		UINT m_num=1;          //某固定温度下目标函数值连续未改进次数计数器
		while(m_num<m_max&&iter_num<iter_max)
		{
			ExchangeSolution();
			double total1,total2 , delta;
			//移除模式
			double nn=log((m_tau/m_Temperature))/log(alpha);
			int n=nn-1;bool dis(0);
            if(tempture<m_Temperature*pow(alpha,n)||m_num>m_max-4)
			{
				dis=1;
			}
			CalTotalDistance(total1);       //计算改变前总路程
			GenerateNewSolution(m_num/5+1,dis);          //产生新解
			CalTotalDistance(total2);       //计算改变后的总路程  
            
			delta=total2-total1;
            double probli=exp(delta/tempture); //计算接收概率
			
			UINT recept(0);
			//判断是否接收新解
			if(m_newVehicle.size()>m_Vehicle.size())
			{
				
				UINT kk=rand()%1000;
				if(kk<100)
				{
					if(delta>0)
					{	
						                          // 根据系统时间设置随机数种子
                        int i = rand() % 1000;                     // 取得区间[0,1000)的整数
                        if(i<=1000*probli)recept=1;
					}
				}
				
			}
			else recept=1;
	
			//接收条件还要改哦:若路径减少了则一定要接收
			
			if(recept)                      //满足条件则接收新解
			{
				ExchangeSolution(FALSE);
				
				m_num=0;
			}
			else	m_num+=1;
			
			iter_num+=1;
		}
		if(m_num>m_max)break;
		tempture*=alpha;
	}
    cout<<"本程序得到的最优结果:"<<endl;
	OutPut();
	//计算并输出总路程
	double Totaldistance;
	ExchangeSolution();
	CalTotalDistance(Totaldistance);
	cout<<"路径总长:"<<Totaldistance<<endl;
	
	//计算并输出总时间
	double TotalTime;
	CalTotalTime(TotalTime);
 //   cout<<"耗费时间:"<<TotalTime<<endl;
	
	//输出时间安排
	return TRUE;
    
}

void CVPR:: Remove(UINT count,bool IsDis)
{
    
    if(IsDis)
	{
		list <CVehicle>::iterator p=m_newVehicle.begin(),p1=p;
		UINT i(m_Count);
		while(p1!=m_newVehicle.end())
		{
			UINT first(p1->GetFirst()),i1(0);
			while(first)
			{
				i1++;
				first=m_newClient[first].GetNext();
			}
			if(i>i1){i=i1;p=p1;}
			p1++;
		}
		if(i<m_Count/m_newVehicle.size())
		{
			m_newClient[0].SetNext(p->GetFirst());
			m_newVehicle.remove(*p);
			return;
		}
	}


    double MAX_TIME=Max_time();

	UINT First;          //指向被移除的客户所在路径的第一个客户
	for (int q=0;q<=m_Count;q++)
		Relateness[q]=0;
	UINT index;          //被移走的客户
	//  srand( (unsigned)time( NULL ) );

     index=rand()%m_Count+1; //随机产生第一个客户
  //   srand(m_rand[index]);
//	 m_rand[index]+=1;
//	  index=(rand()+index)%m_Count+1;
//	  m_rand[index]+=1;

	 // index=8;
//	cout<<"我们将移除第"<<index<<"个客户"<<endl;
    for(int i=1;i<=count;i++)
	{    
		//寻找将被移除客户所在路径的第一个客户
		UINT index1=index;
		while(m_newClient[index1].GetPrevious())
		{
			index1=m_newClient[index1].GetPrevious();
		}
		First=index1;   
		
		//寻找被移除客户所在路径
		list<CVehicle>::iterator	p=m_newVehicle.begin();
		while(p->GetFirst()!=First)
			p++;
		
		if(m_newClient[index].GetPrevious()==0)//若将移除的是某条路径的第一个客户
		{
			if(m_newClient[index].GetNext()==0)//如果即将移除的同时也是最后一个客户,则需删除这一路径
			{
			    const	CVehicle  v=*p;
				m_newVehicle.remove(v);
				p=m_newVehicle.begin();
			}
			else{ p->SetFirst(m_newClient[index].GetNext());
			      p->SetVacuum(p->GetVacuum()+m_newClient[index].GetNeed());
			}
			
		}
		else
		{
			p->SetVacuum(p->GetVacuum()+m_newClient[index].GetNeed());
		}
			UINT pre= m_newClient[index].GetPrevious();
			UINT nex=m_newClient[index].GetNext();
		if(pre)
			m_newClient[pre].SetNext(nex);
		if(nex)
		{
			m_newClient[nex].SetPrevious(pre);
			//更改时间窗
			UINT u=nex;
			while(u){
				double time=CalNewTime(u,TRUE);
				m_newClient[u].SetNewTime(time);
				u=m_newClient[u].GetNext();
				}

		}

		m_newClient[index].SetPrevious(0);
		UINT nextt(m_newClient[0].GetNext());
		m_newClient[index].SetNext(nextt);
		if(nextt)m_newClient[nextt].SetPrevious(index);
		m_newClient[0].SetNext(index);
		
		double max_relate(0);
		
       	list<CVehicle>::iterator pp=m_newVehicle.begin();