solution.cpp

vrpsd -tabu搜索求解！！！！！！！！！！！！！！！！！！！！！！！

#include "Solution.h"

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

Problem* Solution::problem=0 ;

// Construct a solution and a pointer to initialized problem data.
Solution::Solution( Random* rnd, Control& control,  Problem* p ) :
   vector<int>(p->numberOfCustomers), rg(rnd), computedExpectedCost(false),
   control_(control), move(3,-1),
   allocatedCostToGoMatrix(false),   computedCostToGoMatrix(false)
{
  problem = p;
  useProxy = control_.usingProxy();
 }



// Create a random initial solution (sequence of customers, without thresholds).
void
Solution::initializeRandomSolution() {

  int n = problem->numberOfCustomers;
  int i=0, pick;
  int redo;          // 1 if city already extracted, 0 otherwise
  vector<int> flag(n);
 
  //flag initialization
  flag[0]=1; //the depot cannot be chosen
  for(i=1;i<n;i++) flag[i]=0;

  (*this)[0]=0; //the depot
  for(i=1;i<n;i++){
    do{//extract a new city
      pick= 1+ (int)(rg->next()*(n-1));
      //      cout << pick << endl;///////(int)((double)(n-1)*rand()/(RAND_MAX+1.0));
      if(flag[pick]==1) redo=1;     //already exctracted
      else {                        //store extracted
	(*this)[i]= pick;
	flag[pick]=1;
	redo=0;
      }
    }while(redo==1);
  }
  for(pick=0;pick<n;pick++){       //last city is deterministic 
    if(flag[pick]==0) (*this)[n-1]=pick;
  }
  computedCostToGoMatrix = false; 
}



//OrOpt operator which shift a string into another position of the solution
//according to the current move, and updates the expected cost value.
void
Solution::shift(){
  int i = move[0];
  int k = move[1];
  int j = move[2];
  int n = problem->numberOfCustomers ;

  if(i<0 || i>= n || i+k > n-2 || j< i+k+1 ){
    cout << "Solution::shift(): Error! Move out of range. Exit." << endl;
    return;
  }
 

  vector<int>::iterator first, last, result;

  //cout << "shift(): ";///////////

  //Create a temporary vector with the string to be shifted.
  vector<int> string(k,-1);
  first = begin()+i+1;
  last = first +k;
  result = string.begin();
  copy( first, last, result );

  //Shift backwards the customers after the string untill jth customer.
  first = begin()+i+k+1;
  last = first +j-i-k;
  result = begin()+i+1;
  copy( first, last, result );

  //printOn(cout);//////////////

  //Copy the string into the solution vector.
  first = string.begin();
  last = string.end();
  result = begin() +j-k+1;
  copy( first, last, result );

  //printOn(cout);//////////////

  //Update expectedCost and costToGoMatrix
  if(allocatedCostToGoMatrix == false){
    allocateCostToGoMatrix();          
    allocatedCostToGoMatrix = true;
  }
  expectedCost = computeExpectedCost(costToGoMatrix);
  computedExpectedCost = true;
  computedCostToGoMatrix = true;
}



//OrOpt operator which shift a string into another position of the solution
//according to the current move, without updating the expected cost value.
void
Solution::shiftTSP(){
  int i = move[0];
  int k = move[1];
  int j = move[2];
  int n = problem->numberOfCustomers ;

  if(i<0 || i>= n || i+k > n-2 || j< i+k+1 ){
    cout << "Solution::shift(): Error! Move out of range. Exit." << endl;
    return;
  }
 

  vector<int>::iterator first, last, result;

  //cout << "shift(): ";///////////

  //Create a temporary vector with the string to be shifted.
  vector<int> string(k,-1);
  first = begin()+i+1;
  last = first +k;
  result = string.begin();
  copy( first, last, result );

  //Shift backwards the customers after the string untill jth customer.
  first = begin()+i+k+1;
  last = first +j-i-k;
  result = begin()+i+1;
  copy( first, last, result );

  //printOn(cout);//////////////

  //Copy the string into the solution vector.
  first = string.begin();
  last = string.end();
  result = begin() +j-k+1;
  copy( first, last, result );

  computedCostToGoMatrix = false;
}


//Set the move value equal to the one given as input parameter.
void
Solution::setMove(const vector<int>& m){

  move[0] = m[0];
  move[1]= m[1];
  move[2] = m[2];

}

//Set the first move with fixed string length.
bool 
Solution::firstMove(int len){
  if(len < 0 || len > 3){
    cerr << "Solution::firstMove(int len) error: len must be in the interval [1,3], exit";
      exit(-1);
   }
  int n = problem->numberOfCustomers;
  move[0]= 0;
  move[1]=len;
  
  int j = 1+len +(int)(rg->next()*(n-len-1));//((double)(n-len-1)*rand()/(RAND_MAX + 1.0) );
  move[2]=j;
      
  return true;
}



//Set the next move with fixed string length.
bool 
Solution::nextMove(int len){
  if(len < 0 || len > 3){
    cerr << "Solution::nextMove(int len) error: len must be in the interval [1,3], exit";
      exit(-1);
   }
  int n = problem->numberOfCustomers;

  if (move[0] +1 >= n-len-1) return false;
  else{
    move[0]+= 1;
    move[1]=len;
    int i = move[0];
    int j = i+len+1 +(int)(rg->next()*(n-i-len-1));//( (double)(n-i-len-1)*rand()/(RAND_MAX + 1.0) );
    move[2]=j;
        
    return true;
  }
}

double
Solution::computeMoveValueTSP( const double currentLen ){
  control_.nrDeltaLen++;

  double value = currentLen;
  int n = problem->numberOfCustomers;
  int i = move[0];
  int k = move[1];
  int j = move[2];
  value += problem->distanceMatrix[ (*this)[i] ][ (*this)[(i+k+1)%n] ];
  value += problem->distanceMatrix[ (*this)[(i+k)%n] ][ (*this)[(j+1)%n] ];
  value += problem->distanceMatrix[ (*this)[j] ][ (*this)[(i+1)%n] ];

  value -= problem->distanceMatrix[ (*this)[i] ][ (*this)[(i+1)%n] ];
  value -= problem->distanceMatrix[ (*this)[(i+k)%n] ][ (*this)[(i+ k+ 1)%n] ];
  value -= problem->distanceMatrix[ (*this)[j] ][ (*this)[(j+1)%n] ];

  return value;
}
  

//Compute the value of the solution that would be obtained, if the move would be
//applied to the current solution. 
//The value returned is not exact, if the delta has been computed with the 
//proxy function (computeProxyDelta).
double
Solution::computeMoveValue(){
  control_.nrDeltaCost++;

  double value;
  if( computedCostToGoMatrix == false ){
    if( allocatedCostToGoMatrix == false ) {
      allocateCostToGoMatrix();
      allocatedCostToGoMatrix = true;
    }
    computeExpectedCost(costToGoMatrix);
    computedCostToGoMatrix = true;
  }

  if(useProxy == true) value = expectedCost + computeProxyDelta();
  else value = expectedCost + computeExactDelta();

  return value;
}


//Compute the length of the a priori solution.
double
Solution::computeTourLength(){
  control_.nrLen++;

  int n = problem->numberOfCustomers;
  double len = 0;
  for (int i =0; i<n; i++){
    len += problem->distanceMatrix[ (*this)[i] ][ (*this)[(i+1)%n] ];
  }
  return len;
}


//Compute the expected cost-to-go  and the thresholds,
//the  threshold vector must be given as an argument to the function
//and it must have numberOfCustomers -1 elements
double
Solution::computeExpectedCostAndThresholds(vector<int>& thresholds){
  control_.nrCost++;

  int  Q = problem->capacity;
  int n = problem->numberOfCustomers;
  bool foundThreshold;
  
  if(thresholds.capacity() != (unsigned int)n ) 
    cout << "Error: Solution.cpp: in method double Solution::computeExpectedCostAndThresholds(vector<int> thresholds): thresholds vector does not have numberOfCustomers elements!" << endl;

  //initialization of cost-to-go vectors from the last customer to the depot
  vector<double> 
    costToGo_jplus1(Q+1,problem->distanceMatrix[(*this)[n-1]][0]);
  thresholds[(*this)[n-1]]= 0;  
  //cout << n-1 <<" f()= "<<  costToGo_jplus1[0] << endl;//////////////

  double costRestock;
  double costNoRestock;
  vector<double> costToGo_j(Q+1);
  for(int j=n-2; j>0; j--){
    foundThreshold = false;
    costRestock = this->computeCostIfPreventiveRestock(j,j+1,costToGo_jplus1);
    //cout << j <<" h' " << costRestock << endl;//////////////
    
    
    for(int q=Q; q>=0; q--){
      //compute costToGo in case of proceeding to the next customer
      costNoRestock = this->computeCostIfProceed(q,j,j+1,costToGo_jplus1);
      //cout << j <<" h(" << q << ")= "<< costNoRestock ;//////////////
      
      //choose smaller cost btw preventiveRestock and Proceed, and set threshold
      if(costRestock < costNoRestock){
	if(!foundThreshold){
	  thresholds[(*this)[j]] = q + 1;
	  foundThreshold = true;
	}
	costToGo_j[q]= costRestock;
      }
      else 
	costToGo_j[q] = costNoRestock;
      //cout << " f(" << q << ")= "<<  costToGo_j[q] << endl;//////////////
    }
    
    if(!foundThreshold){
      thresholds[(*this)[j]] = 0;
      foundThreshold = true;
    }
    
    //store chosen cost vector in costToGo_jplus1   
    for(int q=Q; q>=0; q--)
      costToGo_jplus1[q] = costToGo_j[q];
  }  
  
  //j==0: costToGo from the depot on (last iteration)
  thresholds[0] = Q;
  costToGo_j[Q] = this->computeCostIfProceed(Q,0,1,costToGo_jplus1);
  //  cout << " costToGo_j[Q]= " << costToGo_j[Q] << endl;/////////////
  
  expectedCost= costToGo_j[Q]; 
  computedExpectedCost = true;
  return costToGo_j[Q]; 
}



//compute the expected cost-to-go 
double
Solution::computeExpectedCost(){
  control_.nrCost++;

  int  Q = problem->capacity;
  int n = problem->numberOfCustomers;

  //initialization of cost-to-go vectors from the last customer to the depot
  vector<double> 
    costToGo_jplus1(Q+1,problem->distanceMatrix[(*this)[n-1]][0]);
  //cout << n-1 <<" f()= "<<  costToGo_jplus1[0] << endl;//////////////

  double costRestock;
  double costNoRestock;
  vector<double> costToGo_j(Q+1);
  for(int j=n-2; j>0; j--){
    costRestock = this->computeCostIfPreventiveRestock(j,j+1,costToGo_jplus1);
    //cout << j <<" h' " << costRestock << endl;//////////////
    
    for(int q=Q; q>=0; q--){
      //compute costToGo in case of proceeding to the next customer
      costNoRestock = this->computeCostIfProceed(q,j,j+1,costToGo_jplus1);
      //cout << j <<" h(" << q << ")= "<< costNoRestock ;//////////////
      
      //choose smaller cost btw preventiveRestock and Proceed, and set threshold
      if(costRestock < costNoRestock)
	costToGo_j[q]= costRestock;
      else 
	costToGo_j[q] = costNoRestock;
      //cout << " f(" << q << ")= "<<  costToGo_j[q] << endl;//////////////
    }
    
    //store chosen cost vector in costToGo_jplus1   
    for(int q=Q; q>=0; q--)
      costToGo_jplus1[q] = costToGo_j[q];
  }  
  
  //j==0: costToGo from the depot on (last iteration)
  costToGo_j[Q] = this->computeCostIfProceed(Q,0,1,costToGo_jplus1);
  //cout << " costToGo_j[Q]= " << costToGo_j[Q] << endl;/////////////
  
  expectedCost= costToGo_j[Q]; 
  computedExpectedCost = true;
  return costToGo_j[Q]; 
}



//Compute the expected cost-to-go 
//storing the intermediate cost-to-gos in the costToGoMatrix.
double
Solution::computeExpectedCost( vector<vector<double> >& costToGoMatrix){
  control_.nrCost++;

  int  Q = problem->capacity;
  int n = problem->numberOfCustomers;
  

  //Initialization of cost-to-go vectors from the last customer to the depot.
  vector<double> 
    costToGo_jplus1(Q+1,problem->distanceMatrix[(*this)[n-1]][0]);
  for(int q=Q; q>=0; q--)
    costToGoMatrix[n-1][q] = costToGo_jplus1[q];
  //cout << n-1 <<" f()= "<<  costToGo_jplus1[0] << endl;//////////////

  double costRestock;
  double costNoRestock;
  vector<double> costToGo_j(Q+1);
  for(int j=n-2; j>0; j--){
    costRestock = computeCostIfPreventiveRestock(j,j+1,costToGo_jplus1);
    //cout << j <<" h' " << costRestock << endl;//////////////
     
    for(int q=Q; q>=0; q--){
      //compute costToGo in case of proceeding to the next customer
      costNoRestock = computeCostIfProceed(q,j,j+1,costToGo_jplus1);
      //cout << j <<" h(" << q << ")= "<< costNoRestock ;//////////////
      
      //choose smaller cost btw preventiveRestock and Proceed, and set threshold
      if(costRestock < costNoRestock)
	costToGo_j[q]= costRestock;
      else 
	costToGo_j[q] = costNoRestock;

      costToGoMatrix[j][q]= costToGo_j[q]; 
      //cout << " f(" << q << ")= "<<  costToGo_j[q] << endl;//////////////
    }
    
    
    //store chosen cost vector in costToGo_jplus1   
    for(int q=Q; q>=0; q--)
      costToGo_jplus1[q] = costToGo_j[q];
  }  
  
  //j==0: costToGo from the depot on (last iteration)
  costToGo_j[Q] = computeCostIfProceed(Q,0,1,costToGo_jplus1);
  //  cout << " costToGo_j[Q]= " << costToGo_j[Q] << endl;/////////////

  expectedCost= costToGo_j[Q]; //Solution member
  computedExpectedCost = true; //Solution member