psovrp.cpp

一个求解车辆路径问题的粒子群算法的源码

// PsoVrp.cpp: implementation of the CPsoVrp class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "VRP.h"
#include "PsoVrp.h"
#include "math.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CPsoVrp::CPsoVrp()
{

}
double CPsoVrp::abs(double s)
{
	if (s>0) 
		return s;
	else
		return -s;
}
void CPsoVrp::reserial(CPsoVrp::Node *PNode)
{
	int i,j,count;
	double data;

	for(i=1;i<=TASK;i++)
	{
		data=PNode->Xr[i];
		count=1;
		for(j=1;j<=TASK;j++)
		{
			if(PNode->Xv[i]==PNode->Xv[j]&&data-PNode->Xr[j]>=0.000001)
				count++;
			if(PNode->Xv[i]==PNode->Xv[j]&&(abs(data-PNode->Xr[j])<0.000001)&&i>j)
				count++;
		}
		PNode->iXr[i]=count;
	}
    
	return;
}
double CPsoVrp::Eval(CPsoVrp::PNODE *PNode)
{
	int i,j,k,step;
	double dist[VECHI+1];
	double weight[VECHI+1];
	double All_weight,All_dist;
	double prex,prey;


label1:
	reserial(PNode);

	for(i=1;i<=VECHI;i++)
	{
		dist[i]=0;
	    weight[i]=0;
	}

	for(i=1;i<=VECHI;i++)
	{
		step=1;
		prex=GPNode.x[0];
		prey=GPNode.y[0];
		 
		do
		{
		  for(j=1;j<=TASK;j++)
			if(PNode->Xv[j]==i&&PNode->iXr[j]==step)
				break;
		  if(j<=TASK)
			//找到车辆i的step次任务点j
		  {
		    dist[i]+=sqrt((GPNode.x[j]-prex)*(GPNode.x[j]-prex)+(GPNode.y[j]-prey)*(GPNode.y[j]-prey));
		    prex=GPNode.x[j];
		    prey=GPNode.y[j];
            weight[i]+=GPNode.weight[j];
		  }
		  step=step+1;
		}while(j<=TASK);
        dist[i]+=sqrt((prex-GPNode.x[0])*(prex-GPNode.x[0])+(prey-GPNode.y[0])*(prey-GPNode.y[0]));
	}
	 All_weight=0;
	 for(i=1;i<=VECHI;i++)
		 All_weight+=weight[i];
	 All_dist=0;
	 for(i=1;i<=VECHI;i++)
		 All_dist+=dist[i];
   PNode->value=All_dist;
   for(i=1;i<=VECHI;i++)
	   if(weight[i]>1.0)
	   {
		   do{
			   j=rand()%VECHI+1;
		   }while(j==i);
		   do{
			   k=rand()%TASK+1;
		   }while(PNode->Xv[k]!=i);
		   PNode->Xv[k]=j;
		   goto label1;
	   }

   return PNode->value;
}

void CPsoVrp::initialize()
{
  int i,j;
  for(i=0;i<PopSize;i++)
	{
		for(j=1;j<=TASK;j++)
		{
			VNode[i].Node.Xv[j]=rand()%VECHI+1;
			VNode[i].Node.Xr[j]=rand()%TASK+1;
            VNode[i].Node.Vv[j]=rand()%VECHI+1;
            VNode[i].Node.Vr[j]=(rand()%10>5)?rand()%TASK:(-(rand()%TASK));
		}
        Eval(&VNode[i].Node);
  }
  for(i=0;i<PopSize;i++)
  {
	  VNode[i].LocalNode=VNode[i].Node;
  }
  //生成局部最小
  j=0;
  double minvalue=MAX;
  for(i=0;i<PopSize;i++)
  {
	  if(VNode[i].Node.value<minvalue)
	  {
		  minvalue=VNode[i].Node.value;
		  j=i;
	  }
  }
  GBest=VNode[j].Node;
  //全局最小值 
}

void CPsoVrp::localbest(int Pos)
{
	if(VNode[Pos].Node.value<VNode[Pos].LocalNode.value)
		VNode[Pos].LocalNode=VNode[Pos].Node;
}

void CPsoVrp::globalbest(int Pos)
{
	if(VNode[Pos].Node.value<GBest.value)
		GBest=VNode[Pos].Node;
}

void CPsoVrp::comput_Pso(int Pos)
{
	int i;
	double c1=0.729,r1=1.49445,r2=1.49445;
	double s;
	for(i=1;i<TASK;i++)
	{
		VNode[Pos].Node.Vv[i]=(int)(c1*VNode[i].Node.Vv[i]+r1*(VNode[Pos].LocalNode.Vv[i]-VNode[Pos].Node.Vv[i])+r2*(GBest.Vv[i]-VNode[Pos].Node.Vv[i]));
		if(VNode[Pos].Node.Vv[i]>MaxVSpeed)
		  VNode[Pos].Node.Vv[i]=MaxVSpeed;
        if(VNode[Pos].Node.Vv[i]<-MaxVSpeed)
		  VNode[Pos].Node.Vv[i]=-MaxVSpeed;
		
		VNode[Pos].Node.Vr[i]=c1*VNode[i].Node.Vr[i]+r1*(VNode[Pos].LocalNode.Vr[i]-VNode[Pos].Node.Vr[i])+r2*(GBest.Vr[i]-VNode[Pos].Node.Vr[i]);
		if(VNode[Pos].Node.Vr[i]>MaxRSpeed)
		  VNode[Pos].Node.Vr[i]=MaxRSpeed;
        if(VNode[Pos].Node.Vr[i]<-MaxRSpeed)
		  VNode[Pos].Node.Vr[i]=-MaxRSpeed;
	}
    
	for(i=1;i<TASK;i++)
	{
        s=VNode[Pos].Node.Xv[i]+VNode[Pos].Node.Vv[i];
		VNode[Pos].Node.Xv[i]=s>(int)s?(int)s+1:(int)s;

      	if(VNode[Pos].Node.Xv[i]>VECHI)
		  VNode[Pos].Node.Xv[i]=VECHI;
		if(VNode[Pos].Node.Xv[i]<1)
		  VNode[Pos].Node.Xv[i]=1;
        VNode[Pos].Node.Xr[i]=VNode[Pos].Node.Xr[i]+VNode[Pos].Node.Vr[i];
	}
	Eval(&VNode[Pos].Node);
}

double CPsoVrp::Vrp_Pso()
{
	int Step,i;
	initialize();
	for(Step=0;Step<20;Step++)
	{
		for(i=0;i<PopSize;i++)
		{
			comput_Pso(i);
			localbest(i);
			globalbest(i);
		}
	}

	return GBest.value;

}
CPsoVrp::~CPsoVrp()
{

}