oropttsp.cpp

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

#include "Problem.h"
#include "Solution.h"
#include "Control.h"
#include "Random.h"

/*
  orOptTSP.cpp
  Program with the implementation of the function orOpt(), which performs
  the Or opt local search for the TSP, on a VRPSD instance.
  The initial solution given in input is modified  if a solution with
  smaller expected cost is found.
  The local optimum is with respect to the tsp length.*/

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


void orOptTSP(Random* rnd, Control& control, Solution& initialSolution ){

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

  //Initialize current best solution.
  Solution currSol(rnd, control, pp);
  currSol.copySolution(initialSolution);
  double trueCostBest = currSol.computeExpectedCost();
  double currLen= currSol.computeTourLength();
  //cout << "currSol.expectedCost " << currSol.expectedCost << endl;//////
  //currSol.printOn(cout);/////	

  //Allocation for the best move.
  vector<int> bestMove(3,-1);


  //The lengths of the neighbour solution.
  double bestNeighborCost;
  double neighborCost;


  int stringLen = 3;
  int falseImprove = 0; //Number of consecutive moves that lead to a worsening solution.
  while(stringLen >= 1 && control.timeLeft() && falseImprove < 11){

    currSol.firstMove(stringLen);
    bestNeighborCost = currLen;

    do{//Evaluate the move, update best move, and generate new move.

      //Compute the neighbour cost by difference with the
      //current solution cost.
      neighborCost = currSol.computeMoveValueTSP(currLen);
      //cout << "neighbCost " << neighborCost << endl;/////

      //Update the  best move (with respect to tsp objective).
      if( neighborCost  < bestNeighborCost ){
	bestNeighborCost = neighborCost;
	bestMove = currSol.getMove();
      }

    }while( currSol.nextMove(stringLen) );

    //If an  improving move is found, update the solution.
    if( bestNeighborCost < currLen ){

      //Set the solution move equal to the best move.
      currSol.setMove(bestMove);

      //cout << "i " << bestMove[0] << " k " << bestMove[1] << " j " << bestMove[2] << endl;/////
      double currCost = currSol.computeExpectedCost() ;
      //Change the solution according to the "best" move, and re-compute the cost.
      currSol.shiftTSP();
      //      currSol.printOn(cout);/////
      currLen= currSol.computeTourLength();

      //cout << "orOptTSP(): currSol.expectedCost " << currSol.computeExpectedCost() << endl;////

      //If the new current solution is really the new best, update the initial solution.
      if ( currSol.computeExpectedCost() < trueCostBest ){
	initialSolution.copySolution(currSol);
	trueCostBest = currSol.expectedCost;
	control.setCurrentCost( trueCostBest );
      }

      //Check-Set number of false improvements.
      if(currSol.expectedCost > currCost) falseImprove ++;
      else falseImprove = 0;
     	
    }
    else //No best move has been found.
      stringLen --;
  }

  //cout << "orOptTSP(): currSol.expectedCost " << currSol.computeExpectedCost() << endl;////

}