/*

09/10/01

This is the default encoding of the delivery variant 
of the vehicle routing problem
with one base and a homogeneous fleet.

PRECONDITIONS:

1. ILOG Dispatcher 3.0;
2. Data file in the following format:

   *************************************   
   0  x_base y_base 0        earliest_start   latest_end    0
   1  x_1    y_1    demand_1 earliest_start_1 lateststart_1 service_time_1
   ...
   i  x_i    y_i    demand_i earliest_start_i lateststart_i service_time_i
   ...
   *************************************

   The base and customers each are described
   by seven numbers in a separate line, 
   in this order: (i) index (0 - for the base), 
   (ii and iii) x and y coordinates of the base 
   in the 2D right Cartesian reference frame;
   (iv) demand>=0 (0 for the base); (v) earliest start;
   (vi) latest end (for the base) and latest 
   start (for customers); and (vii) service time.

2. Output file;
3. Index of Method: 0 for Guided Local Search, 1 for Tabu Search.
4. Search Parameter: penalty factor for Guided Local Search, tabu 
   tenure for Tabu Search.
5. Index of Limit on Search: enter 0 if you want to set a limit
   on the number of moves, enter 1 if you want a limit on execution time.
6. Value of limit depending on what you enter as the 5th parameter.

POSTCONDITIONS:

1. The first solution generated by the savings heuristic and
   solution(s) improved by either guided local search or tabu search
   with a limit (either on the number of moves or on execution time).
   The information is stored in the specified output file.  
*/


#include <ildispat/ilodispatcher.h> 
#include <time.h> 
 
ILOSTLBEGIN 
 
IloNum TimeLimit, MoveLimit; 
 
IloNum PenaltyFactor; 
IloInt TabuTenure; 
IloBool TypeOfMethod;//0-GLS,1-Tabu; 
 
void Info(IloDispatcher dispatcher, ofstream& fout) { 
  IloSolver solver = dispatcher.getSolver(); 
  fout<< "===============" << endl 
	       << "Cost         : " << dispatcher.getTotalCost() << endl  
	       << "Number of vehicles used : "  
	       << dispatcher.getNbOfVehiclesUsed() << endl 
	       << "Solution     : " << endl 
	       << dispatcher << endl; 
} 
 
void improveWithGLS_TimeLimitVersion(IloDispatcher dispatcher, 
                                     IloRoutingSolution solution, 
                                     IloNHood nhood, 
                                     ofstream& fout) { 
	IloNumVar cost = dispatcher.getCostVar(); 
	IloEnv env = dispatcher.getEnv(); 
	IloGoal instantiateCost = IloDichotomize(env, cost, IloFalse); 
	IloRoutingSolution rsol = solution.makeClone(env); 
	IloRoutingSolution best = solution.makeClone(env); 
	IloDispatcherGLS dgls(env, PenaltyFactor); 
	IloSearchSelector sel = IloMinimizeVar(env,dgls.getPenalizedCostVar()); 
	IloGoal move = IloSingleMove(env, rsol, nhood, dgls, sel, instantiateCost); 
	move = move && IloStoreBestSolution(env, best); 
	IloSolver solver = dispatcher.getSolver(); 
	IloCouple(nhood, dgls); 
	clock_t tStart = clock()/CLK_TCK, time = tStart;  
 
	while (time <= tStart + TimeLimit) { 
		if (solver.solve(move)) { 
			fout << "Cost = "<<solver.getMin(cost) <<endl; 
		} 
		else { 
			fout <<" ----- "<<endl; 
			if (dgls.complete()) { 
				cout<<"exiting by break"<<endl; 
				break; 
			} 
		} 
		time = clock()/CLK_TCK; 
	} 
	IloDecouple(nhood, dgls); 
	IloGoal restoreSolution = IloRestoreSolution(env, best) && 
							  instantiateCost; 
	solver.solve(restoreSolution); 
	rsol.end(); 
	best.end(); 
} 
 
void improveWithGLS_MoveLimitVersion(IloDispatcher dispatcher, 
				     IloRoutingSolution solution, 
				     IloNHood nhood, 
				     ofstream& fout) { 
	IloNumVar cost = dispatcher.getCostVar(); 
	IloEnv env = dispatcher.getEnv(); 
	IloGoal instantiateCost = IloDichotomize(env, cost, IloFalse); 
	IloRoutingSolution rsol = solution.makeClone(env); 
	IloRoutingSolution best = solution.makeClone(env); 
	IloDispatcherGLS dgls(env, PenaltyFactor); 
	IloSearchSelector sel = IloMinimizeVar(env,dgls.getPenalizedCostVar()); 
	IloGoal move = IloSingleMove(env, rsol, nhood, dgls, sel, instantiateCost); 
	move = move && IloStoreBestSolution(env, best); 
	IloSolver solver = dispatcher.getSolver(); 
	IloCouple(nhood, dgls); 
 
	IloNum NbMoves=0; 
 	while (NbMoves<=MoveLimit) { 
		if (solver.solve(move)) { 
			fout << "Cost = "<<solver.getMin(cost) <<endl; 
		} 
		else { 
			fout <<" ----- "<<endl; 
			if (dgls.complete()) { 
				cout<<"exiting by break"<<endl; 
				break; 
			} 
		} 
		NbMoves = dispatcher.getNbOfMoves(); 
	} 
 
	IloDecouple(nhood, dgls); 
	IloGoal restoreSolution = IloRestoreSolution(env, best) && 
				  instantiateCost; 
	solver.solve(restoreSolution); 
	rsol.end(); 
	best.end(); 
} 
 
void improveWithTabu_TimeLimitVersion(IloDispatcher dispatcher, 
				      IloRoutingSolution solution, 
				      IloNHood nhood, 
				      ofstream& fout) { 
 
	IloNumVar cost = dispatcher.getCostVar(); 
	IloEnv env = dispatcher.getEnv(); 
	IloGoal instantiateCost = IloDichotomize(env, cost, IloFalse); 
	IloRoutingSolution rsol = solution.makeClone(env); 
	IloRoutingSolution best = solution.makeClone(env); 
	IloDispatcherTabuSearch dts(env, TabuTenure); 
 
	IloGoal move  = IloSingleMove(env, 
		                      rsol, 
				      nhood, 
				      dts, 
				      IloMinimizeVar(env, cost), 
				      instantiateCost); 
	move = move && IloStoreBestSolution(env,best); 
	IloSolver solver = dispatcher.getSolver(); 
 
	IloCouple(nhood, dts); 
	clock_t tStart = clock()/CLK_TCK, time = tStart;  
 
	IloInt Counter = 0; 
	while (time <= tStart + TimeLimit) {
	        //outputting information after every 5000 moves 
		if (Counter==5e3) { 
			Info(dispatcher, fout); 
			Counter=0; 
		}  
		if (solver.solve(move)) { 
			fout << "Cost = "<<solver.getMin(cost) <<endl; 
			Counter++; 
		} 
		else { 
			fout <<" ----- "<<endl; 
			if (dts.complete()) { 
				cout<<"exiting by break"<<endl; 
				break; 
			} 
		} 
		time = clock()/CLK_TCK; 
	} 
	IloDecouple(nhood, dts); 
	IloGoal restoreSolution = IloRestoreSolution(env, best) && 
				  instantiateCost; 
	solver.solve(restoreSolution); 
	rsol.end(); 
	best.end(); 
 
} 
 
void improveWithTabu_MoveLimitVersion(IloDispatcher dispatcher, 
				      IloRoutingSolution solution, 
				      IloNHood nhood, 
				      ofstream& fout) { 
 
	IloNumVar cost = dispatcher.getCostVar(); 
	IloEnv env = dispatcher.getEnv(); 
	IloGoal instantiateCost = IloDichotomize(env, cost, IloFalse); 
	IloRoutingSolution rsol = solution.makeClone(env); 
	IloRoutingSolution best = solution.makeClone(env); 
	IloDispatcherTabuSearch dts(env, TabuTenure); 
 
	IloGoal move  = IloSingleMove(env, 
		                      rsol, 
				      nhood, 
				      dts, 
				      IloMinimizeVar(env, cost), 
				      instantiateCost); 
	move = move && IloStoreBestSolution(env,best); 
	IloSolver solver = dispatcher.getSolver(); 
 
	IloNum NbMoves=0; 
 	while (NbMoves<=MoveLimit) { 
		if (solver.solve(move)) { 
			fout << "Cost = "<<solver.getMin(cost) <<endl; 
		} 
		else { 
			fout <<" ----- "<<endl; 
			if (dts.complete()) { 
				cout<<"exiting by break"<<endl; 
				break; 
			} 
		} 
		NbMoves = dispatcher.getNbOfMoves(); 
	} 
 
	IloGoal restoreSolution = IloRestoreSolution(env,best) && 
		                  instantiateCost; 
	solver.solve(restoreSolution); 
	rsol.end(); 
	best.end(); 
 
} 
 
int main(int argc, char* argv[]) { 
  IloEnv env; 
  try {

    //////////////////////////////////////////////////////////////////////
    //
    // Creating a model 
    //
    //////////////////////////////////////////////////////////////////////
    
    IloModel mdl(env); 
    IloDimension2 time(env, IloEuclidean, "Time"); 
    IloDimension2 length(env, IloEuclidean, "Length"); 
    IloDimension1 weight(env, "Weight"); 
    ifstream infile; 
	ofstream outfile; 
	TimeLimit = 0; 
	MoveLimit = 0; 
    char * problem; 
	char * output; 
    if (argc ==7) { 
		problem = argv[1]; 
		output  = argv[2]; 
		TypeOfMethod = atoi(argv[3]); 
		if (TypeOfMethod==0) PenaltyFactor = atof(argv[4]); 
		else TabuTenure = atoi(argv[4]); 
		if (atoi(argv[5])==1)  
		{ 
			TimeLimit=atoi(argv[6]); 
		} 
		else  
		{ 
			MoveLimit=atoi(argv[6]); 
		} 
 
	} 
    else { 
		env.out() <<"Usage: <file_name>.exe <datafile> <resfile>\n"; 
		env.out() <<"       TypeOfMethod <0-GLS,1-TS> SearchParam <penalty for GLS, tenure for TS>\n"; 
		env.out() <<"       Limit <0-move, 1-time> LimitValue <integer>\n"; 
		return 0; 
	} 
 
	char str[9]; 
	cout <<"Problem "<<problem<<" has been solved since "<<_strtime(str)<<endl; 
 
	infile.open(problem); 
	outfile.open(output, ios::out); 
 
    if (!infile) {  
      env.out() << "File not found or not specified: " << problem << endl; 
      env.end(); 
      return 0; 
    } 
    if (!outfile) {  
      env.out() << "Cannot open file for output: " << output << endl; 
      env.end(); 
      return 0; 
    } 

    /////////////////////////////////////////////////////////////////
    //
    // Setting the number of customers (i.e. visits) and trucks
    // as well as the capacity of a truck; and then reading data in
    //
    /////////////////////////////////////////////////////////////////

    IloInt nbOfVisits = 100, nbOfTrucks = 25;  
    IloNum capacity = 200; 
    IloNum depotX, depotY, openTime, closeTime, rubbish; 
    infile >> rubbish >> depotX  >> depotY >> rubbish >> openTime >> closeTime >> rubbish; 
 
	outfile<<"Solutions to "<<problem<<endl; 
	if (TypeOfMethod==0)  
		outfile<<"GLS penalty factor = "<<PenaltyFactor<<endl; 
	else  
		outfile<<"Tabu tenure = "<<TabuTenure<<endl; 
	outfile<<endl; 
	outfile<<"nbOfVisits = "<<nbOfVisits<<endl; 
	outfile<<"nbOfTrucks = "<<nbOfTrucks<<endl; 
	outfile<<"capacity = "<<capacity<<endl; 
	outfile<<"depotX = "<<depotX<<endl; 
	outfile<<"depotY = "<<depotY<<endl; 
	outfile<<"openTime = "<<openTime<<endl; 
	outfile<<"closeTime = "<<closeTime<<endl; 
 
    IloNode depot(env, depotX, depotY); 
    for (IloInt j = 0; j < nbOfTrucks; j++) { 
      IloVisit first(depot, "Depot"); 
      mdl.add(first.getCumulVar(time) >= openTime); 
      IloVisit last(depot, "Depot"); 
      mdl.add(last.getCumulVar(time) <= closeTime); 
      char name[16]; 
      sprintf(name, "Vehicle %d", j); 
      IloVehicle vehicle(first, last, name); 
      vehicle.setCost(length, 1.0); 
      vehicle.setCapacity(weight, capacity); 
      mdl.add(vehicle); 
    } 
    for (IloInt i = 0; i < nbOfVisits; i++) { 
      IloInt id; // visit identifier 
      IloNum x, y, quantity, minTime, maxTime, dropTime; 
      infile >> id >> x >> y >> quantity >> minTime >> maxTime >> dropTime; 
      IloNode customer(env, x, y); 
      char name[16]; 
      sprintf(name, "%d", id); 
      IloVisit visit(customer, name); 
      mdl.add(visit.getDelayVar(time) == dropTime); 
      mdl.add(visit.getTransitVar(weight) == quantity); 
      mdl.add(minTime <= visit.getCumulVar(time) <= maxTime); 
      mdl.add(visit);  
    } 
    infile.close(); 
    IloSolver solver(mdl); 
    IloDispatcher dispatcher(solver); 
    IloRoutingSolution solution(mdl); 

    ////////////////////////////////////////////////
    //
    // constructing the 1st solution with savings
    //
    ////////////////////////////////////////////////
  
    IloGoal instantiateCost = IloDichotomize(env,  
					     dispatcher.getCostVar(), 
					     IloFalse); 
    IloGoal restoreSolution = IloRestoreSolution(env, solution); 
    IloGoal goal = IloSavingsGenerate(env) && instantiateCost; 
    if (!solver.solve(goal)) { 
      solver.out() << "A first solution can't be constructed. Try to add more vehicles." << endl; 
      return 0; 
    } 
 
    ///////////////////////////////////////////
    //
    // outputting the first solution 
    //
    ///////////////////////////////////////////

    Info(dispatcher,outfile); 
 
    solution.store(solver); 

    ////////////////////////////////////////////////
    //
    // constructing the neighbourhood of a solution
    //
    ////////////////////////////////////////////////

    IloNHood nhood = IloTwoOpt(env) 
		   + IloOrOpt(env) 
		   + IloRelocate(env) 
		   + IloExchange(env) 
		   + IloCross(env); 
 
    ////////////////////////////////////////////////
    //
    // improving the first solution
    //
    ////////////////////////////////////////////////

    if (TypeOfMethod==0)  
    { 
      if (TimeLimit>0)  
      { 
	improveWithGLS_TimeLimitVersion(dispatcher,solution,nhood,outfile); 
      } 
      else  
      { 
	improveWithGLS_MoveLimitVersion(dispatcher,solution,nhood,outfile); 
      } 
    } 
    else  
    { 
      if (TimeLimit>0)  
      { 
        improveWithTabu_TimeLimitVersion(dispatcher,solution,nhood,outfile); 
      } 
      else 
      { 
	improveWithTabu_MoveLimitVersion(dispatcher,solution,nhood,outfile); 
      } 
    }

    ///////////////////////////////////////////
    //
    // outputting the improved solution 
    //
    ///////////////////////////////////////////

    Info(dispatcher,outfile); 

  } catch(IloException& ex) { 
    cerr << "Error: " << ex << endl; 
  }  
  env.end(); 
  return 0; 
}