saoropt.cpp

随机需求VRP（VRPSD）

#include <cfloat>
#include <cmath>
#include "Problem.h"
#include "Solution.h"
#include "fairSAControl.h"
#include "Random.h"

/*
  orOpt.cpp
  Program with the implementation of the function orOpt(), which performs
  the Or opt local search for the VRPSD.
  The initial solution given in input is modified if a better solution is found,
  otherwise it is left unchanged.
*/

#include <fstream.h>
#include <iostream.h>
using namespace std;


inline bool SAcriterion(Random* rg, double delta, float Temp)
{
  //cout<<delta<<" "<<(exp((double)(-delta)/Temp))<<endl;
  return (rg->next() < (exp((double)(-delta)/Temp)));
}


void SAorOpt(Random* rnd, fairSAControl& control, Solution& initialSolution ){

  //Read problem pointer from input solution.
  Problem* pp = initialSolution.getProblem();

  float iniTemp = 0;
  int idleLength = 0, LengthIter = 0, iter=0;
  double worst_in_length = 0;
  double best_in_length = DBL_MAX;
  bool improved_in_length = false;
  float Temp;
  double delta = DBL_MAX;
  control.setSAOrOptParameters();

  //Initialize current best solution.
  Solution currSol(rnd, control, pp);
  currSol.copySolution(initialSolution);

  //Allocation for the best move.
  vector<int> bestMove(3,-1);
  double currFitness;
  //The cost of the true best solution.
  double globalBestFitness = currSol.computeExpectedCost();
  
  //The possibly approximated costs of the neighbour solution.
  double neighborCost;

#ifdef DEBUG
  currSol.printOn(cout);
  cout << "initial cost: " << currSol.expectedCost << endl;
#endif
  int neighborhoodSize = (pp->numberOfCustomers-3)
    + (pp->numberOfCustomers-2)
    + (pp->numberOfCustomers-1);
   
  //int TempLength = (int)control.rateTempLength;
  int TempLength = (int)(neighborhoodSize * control.rateTempLength);
 
  int stringLen = 3;
  int numSamp = 0;
  double recordDelta = 0;
  currSol.firstMove(stringLen);
  currFitness = currSol.expectedCost;
  while (stringLen>=1)
    {
      do 
	{
	  recordDelta += fabs(currSol.computeMoveValue() - currFitness);
	  //cout<< currSol.computeMoveValue() - currFitness<<endl;
	  numSamp++;
	} while (currSol.nextMove(stringLen));
      stringLen--;
    }
  //cout<<(float)recordDelta/numSamp<<endl;
  iniTemp = control.initTempFactor*(float)recordDelta/numSamp;
  Temp = iniTemp;
  
  stringLen = 3;
  
  while(control.timeLeft() ){

    if (LengthIter > TempLength)
      {
	Temp = control.alfa * Temp;
	LengthIter = 0;
	if (improved_in_length)
	  idleLength=0;
	else
	  idleLength++;
	improved_in_length = false;
      }
    if (idleLength > control.idle_length_reheating)
      {
	Temp = Temp + iniTemp;
	idleLength = 0;  
	worst_in_length = 0;
	best_in_length = DBL_MAX;
      }    
    LengthIter++;
    iter++;

    

currFitness = currSol.expectedCost;
    //bestNeighborCost = DBL_MAX;

#ifdef DEBUG 
    (*tempFile) <<iter<<"\t"<<Temp<<"\t"<<currFitness<<endl;
#endif
    //  cout << "firstMove("<<stringLen<< ") "<<endl;
    // << currSol.move[0] 
    // << " " << currSol.move[1] << " " << currSol.move[2]<< endl;//////////
    if (!currSol.nextMove(stringLen))
      {
	if (stringLen>1)
	  {
	    stringLen--;
	    currSol.firstMove(stringLen);
	  }
	else
	  {
	    stringLen=3;
	    currSol.firstMove(stringLen);
	  }
      }
    neighborCost = currSol.computeMoveValue();
    //If an (possibly approximated) improving move is found, update the solution.
    delta = neighborCost - currFitness;
    if (delta <= 0)
      {

	currSol.setMove(currSol.getMove());
	  currSol.shift();
	  //	cout<<"+"<<endl;
	  if ( currSol.expectedCost < globalBestFitness ){
	    initialSolution.copySolution(currSol);
	    globalBestFitness = currSol.expectedCost;
	    control.setCurrentCost( globalBestFitness );
	    stringLen=3;
	  }
	  if (neighborCost > worst_in_length)
	    {
	      worst_in_length = neighborCost;
	      best_in_length = neighborCost;
	    }
	  if (neighborCost < best_in_length)
	    {
	      best_in_length = neighborCost;
	      improved_in_length = true;
	    }
      }
    else if (SAcriterion(rnd,delta,Temp))
	  {
	    //cout<<"accepted\n";
	    currSol.setMove(currSol.getMove());
	    currSol.shift();
	    stringLen=3;
	    if ( currSol.expectedCost < globalBestFitness ){
	      initialSolution.copySolution(currSol);
	      globalBestFitness = currSol.expectedCost;
	      control.setCurrentCost( globalBestFitness );
	      stringLen=3;
	    }
	    //cout<<"*"<<endl;
	  }
	/*else 
	  {
	  if (stringLen > 1)
	  stringLen--;
	  else
	  stringLen = 3;
	  //cout<<"-"<<endl;
	  }*/
  
  }    //------------end main loop--------

#ifdef DEBUG
  delete tempFile;
#endif  
  //cout <<"orOpt(): final solution " <<endl;//////////////
  //  initialSolution.copySolution(currSol);
  // cout <<"true best: " << initialSolution.expectedCost<< endl;//////////////
  //initialSolution.printOn(cout);//////////////	
  
}