farthestinsertion.cpp

随机需求VRP（VRPSD）

#include "Problem.h"
#include "Solution.h"

/*
  farthestInsertion.cpp
  Program with the implementation of the function farthestInsertion(), which 
  generates a vrpsd solution
  according to the farthest insertion heuristic.
  The solution to be built must be given in input.
*/

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

#include <cstdlib>

#ifndef DBLMAX
    #define DBLMAX 1E37
#endif


void farthestInsertion( Solution& solution ){

  //Read problem pointer from input solution.
  Problem* pp = solution.getProblem();
  int n = pp->numberOfCustomers;

  int s = 0; //The starting city MUST be 0, that is, the depot!
  int end1=0, end2=0, farthest=0, i, index, j;
  int  nextindex;
  double  maxdist, inscost, newcost;
  
  /* initialization */
  vector<int> cycle(n);
  vector<double> dist(n);

  for (i=0; i<n; i++)
    cycle[i] = -1;
  cycle[s] = 0; //the depot is the starting customer.

  /*	printf("\n");
	for (i=0; i<n; i++)
	for (j=0; j<n; j++) {
	
	printf(" %i %i %4.0f  ",i,j,w[i,j]);
	}
  */
  
  /* calcolo le distanze tra il nodo di partenza e tutti gli altri 
     in dist[i] c'e' sempre la distanza massima tra tra i nodi appartenenti al ciclo
     e il nodi i
  */

  double* ptr;
  double* w=(double *) malloc(n * n*sizeof(double));

  for(int i=0; i<n; i++)
    for (int j=0; j<n; j++)
      w[n*i+j] = pp->distanceMatrix[i][j];

  for (i=0, ptr=w+n*s ; i<n; i++, ptr++){
    dist[i] = *ptr;
    //cout << s << " " << i << " " << dist[i] << " " << w[s*n+i] << endl;// equivale al w /////////
  }
  
  
  /* main loop */
  
  for (i=0; i<n-1; i++) {
    maxdist = -DBLMAX;
    for (j=0; j<n; j++)
      if (cycle[j] == -1 && dist[j] > maxdist) {
	maxdist = dist[j];
	farthest = j;
	/*				printf("max %f %i \n",maxdist,j);*/
      }
    inscost = DBLMAX;
    index = s;
    for (j=0; j<=i; j++) {
      nextindex = cycle[index];
      newcost = *(w+index*n+farthest) +
	*(w+farthest*n+nextindex) - 
	*(w+index*n+nextindex);
      if (newcost < inscost) {
	inscost = newcost;
	end1 = index;
	end2 = nextindex;
      }
      index = nextindex;
    }
    cycle[farthest] = end2;
    cycle[end1] = farthest;
    
    /* printf("%i %i %i \n",farthest,end1,end2);
       printf("%f %f %f %f\n",inf,inscost,newcost,*tweight); */
    for (j=0, ptr=w+farthest*n; j<n; j++, ptr++)
      if (cycle[j] == -1 && *ptr < dist[j])
	{
	  /*			printf(" %i %i %4.10f  %4.10f  %4.10f\n",farthest,j,dist[j],*ptr);
				inserisco le nuove distanza tra il nodo e gli altri nodi 
				in modo da sapere quelli che si sono avvicinati (saranno sfavoriti
				dopo per  > maxdist */
	  dist[j] = *ptr;
	}
  }
  index = s;
  for (i=0; i<n; i++) {
    solution[i] = index;	
    index = cycle[index];
  }
  free(w);
  
}

void randomizedFarthestInsertion(Random* rnd, Solution& solution ){

  //Read problem pointer from input solution.
  Problem* pp = solution.getProblem();
  int n = pp->numberOfCustomers;

  int s = (int)(rnd->next() * n); 
  int end1=0, end2=0, farthest=0, i, index, j;
  int  nextindex;
  double  maxdist, inscost, newcost;
  
  /* initialization */
  vector<int> cycle(n);
  vector<double> dist(n);

  for (i=0; i<n; i++)
    cycle[i] = -1;
  cycle[s] = s; //the initial cycle is the trivial one.

  /*	printf("\n");
	for (i=0; i<n; i++)
	for (j=0; j<n; j++) {
	
	printf(" %i %i %4.0f  ",i,j,w[i,j]);
	}
  */
  
  /* calcolo le distanze tra il nodo di partenza e tutti gli altri 
     in dist[i] c'e' sempre la distanza massima tra tra i nodi appartenenti al ciclo
     e il nodi i
  */

  double* ptr;
  double* w=(double *) malloc(n * n*sizeof(double));

  for(int i=0; i<n; i++)
    for (int j=0; j<n; j++)
      w[n*i+j] = pp->distanceMatrix[i][j];

  for (i=0, ptr=w+n*s ; i<n; i++, ptr++){
    dist[i] = *ptr;
    //cout << s << " " << i << " " << dist[i] << " " << w[s*n+i] << endl;// equivale al w /////////
  }
  
  
  /* main loop */
  
  for (i=0; i<n-1; i++) {
    maxdist = -DBLMAX;
    for (j=0; j<n; j++)
      if (cycle[j] == -1 && dist[j] > maxdist) {
	maxdist = dist[j];
	farthest = j;
	/*				printf("max %f %i \n",maxdist,j);*/
      }
    inscost = DBLMAX;
    index = s;
    for (j=0; j<=i; j++) {
      nextindex = cycle[index];
      newcost = *(w+index*n+farthest) +
	*(w+farthest*n+nextindex) - 
	*(w+index*n+nextindex);
      if (newcost < inscost) {
	inscost = newcost;
	end1 = index;
	end2 = nextindex;
      }
      index = nextindex;
    }
    cycle[farthest] = end2;
    cycle[end1] = farthest;
    
    /* printf("%i %i %i \n",farthest,end1,end2);
       printf("%f %f %f %f\n",inf,inscost,newcost,*tweight); */
    for (j=0, ptr=w+farthest*n; j<n; j++, ptr++)
      if (cycle[j] == -1 && *ptr < dist[j])
	{
	  /*			printf(" %i %i %4.10f  %4.10f  %4.10f\n",farthest,j,dist[j],*ptr);
				inserisco le nuove distanza tra il nodo e gli altri nodi 
				in modo da sapere quelli che si sono avvicinati (saranno sfavoriti
				dopo per  > maxdist */
	  dist[j] = *ptr;
	}
  }
  index = 0; //The starting city MUST be 0, that is, the depot!
  for (i=0; i<n; i++) {
    solution[i] = index;	
    index = cycle[index];
  }
  free(w);
  
}