oropt.cpp

随机需求VRP（VRPSD）

#include "Problem.h"
#include "Solution.h"
#include "Control.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;


void orOpt(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);

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

  //The cost of the true best solution.
  double trueCostBest = currSol.computeExpectedCost();

  //The possibly approximated costs of the neighbour solution.
  double bestNeighborCost;
  double neighborCost;

#ifdef DEBUG
  currSol.printOn(cout);
  cout << "initial cost: " << currSol.expectedCost << endl;
#endif

  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 = currSol.expectedCost;

    //#ifdef DEBUG
    //    cout << "firstMove("<<stringLen<< ") "<< currSol.move[0] 
    //	 << " " << currSol.move[1] << " " << currSol.move[2]<< endl;
    //#endif

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

      //Compute the neighbour cost by difference (possibly approximated) with the
      //current solution cost.
      neighborCost = currSol.computeMoveValue();

      //Update the (possibly approximated) best move.
      if( neighborCost  < bestNeighborCost ){
	bestNeighborCost = neighborCost;
	bestMove = currSol.getMove();
      }

    }while( currSol.nextMove(stringLen) );

    //If an (possibly approximated) improving move is found, update the solution.
    double currCost = currSol.expectedCost;
    if( bestNeighborCost < currCost){

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

      //Change the solution according to the "best" move, and re-compute the cost.
      currSol.shift();
      //Check-Set number of false improvements.
      if(currSol.expectedCost > currCost) falseImprove ++;
      else falseImprove = 0;

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


#ifdef DEBUG
      cout <<"new \"best\": " << currSol.expectedCost<< endl;//////////////
      currSol.printOn(cout);
#endif
	
    }
    else //No best move has been found.
      stringLen --;
  }


  //  cout <<"orOpt(): final solution " <<endl;//////
  //initialSolution.copySolution(currSol);////////
  //cout <<"true best: " << initialSolution.expectedCost<< endl;///////
  //cout <<"currSol: " << currSol.expectedCost<< endl;///////
  //initialSolution.printOn(cout);//////////


}