/* 
 
09/10/01 
 
This is an encoding of the job shop problem 
reformulated as an instance of the vehicle routing problem. 
A machine is a vehicle, an operation is a visit. 
 
Here we have known vehicle-visit assignments,  
visits sequences for different vehicles (these 
correspond to jobs), no distances between 
customers. The only dimension we use here is time. 
We construct a first solution with the savings heuristic. 
 
Then the maximal time of return to base among all the vehicles 
should be minimised because this corresponds to makespan. 
 
To do so we set a deadline equal to the maximal 
return to base time in the first solution and locally 
improve it. 
 
PRECONDITIONS: 
 
1. ILOG Dispatcher 3.0; 
2. Data file in the following format. 
   The first line contains two numbers: number of jobs 
   and number of machines. The subsequent lines 
   (one for each job) contain m pairs of numbers, 
   where m is the number of operations in a job. 
   Each pair consists of the number of machine 
   required by an operation and the duration of this 
   operation. 
3. Output file; 
4. Method index (enter 0 for guided local search, 1 for tabu search); 
5. Method parameter (penalty factor for guided local search, tabu tenure for tabu search); 
6. Type of limit on search (0 - limit on the number of moves, 1 - on execution time); 
7. Limit value depending on 6. 
 
POSTCONDITIONS: 
 
1. The first solution and an improved solution 
   obtained by local search stored in the specified output file 
   in the default Dispatcher 3.0 format. 
*/ 
 
 
#include <ildispat/ilodispatcher.h> 
#include <time.h> 
 
ILOSTLBEGIN 
 
IloNum TimeLimit; 
IloNum MoveLimit; 
const IloInt MaxSize = 400; 
IloNum PenaltyFactor; 
IloInt TabuTenure; 
IloBool TypeOfMethod;//0-GLS,1-Tabu; 
 
void Info(IloDispatcher dispatcher, ofstream& outfile) { 
  IloSolver solver = dispatcher.getSolver(); 
  outfile<< "===============" << 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) { 
		//outpitting solutions 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 { 
    IloModel mdl(env); 
    IloDimension2 time(env, IloEuclidean, "Time"); 
    IloDimension2 length(env, IloEuclidean, "Length"); 
    IloDimension1 weight(env, "Weight"); 
    ifstream infile; 
    ofstream outfile; 
    char * problem; 
    char * output; 
	 
    /*Upper bounds:  
      Thompson6x6 -> 165; 
      Apes7x6 -> 183; 
      Lawrence 10x5 -> 2306; 
      Adams 10x10 -> 6363; 
      Lawrence 15x10 -> 6067; 
      Lawrence 15x15 -> 9084; 
    */ 
 
    IloInt UpperBound = 183; 
 
 
    ////////////////////////////////////////////////////// 
    // 
    // Reading in data 
    // 
    ////////////////////////////////////////////////////// 
 
 
    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() << endl; 
		env.out() <<"Usage: <filename>.exe <datafile_name> <resfile_name>\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"; 
		exit(1); 
	} 
 
    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; 
    } 
 
    IloInt nbOfVisits, nbOfTrucks, nbOfJobs; 
    infile>>nbOfJobs; 
    infile>>nbOfTrucks; 
    nbOfVisits = nbOfJobs*nbOfTrucks; 
 
    IloInt* resourceNumbers; 
    resourceNumbers = new IloInt[MaxSize]; 
    IloInt* durations; 
    durations = new IloInt[MaxSize]; 
    for (int i=0;i<MaxSize;i++) { 
      	resourceNumbers[i] = 0; 
       	durations[i] = 0; 
    } 
 
    IloInt index=0; 
    for (i=0;i<nbOfJobs;i++) { 
       for (int j=0;j<nbOfTrucks;j++) { 
       		infile>>resourceNumbers[index]; 
       		infile>>durations[index]; 
	        index++; 
       } 
    } 
 
    /////////////////////////////////////////////////////// 
    // 
    // Specifying parameters and constraints of the model 
    // 
    /////////////////////////////////////////////////////// 
 
    IloNum capacity = 200; 
    IloNum dropTime = 1; 
    IloNum depotX=0, depotY=0, openTime=0, closeTime=IloInfinity; 
 
    outfile<<"Solutions to "<<problem<<endl; 
    if (TypeOfMethod==0)  
     	outfile<<"GLS penalty factor = "<<PenaltyFactor<<endl; 
     else  
       	outfile<<"Tabu tenure = "<<TabuTenure<<endl; 
    outfile<<endl; 
 
    IloVehicleArray vehicles(env,nbOfTrucks); 
    IloVisitArray visits(env,nbOfTrucks*nbOfJobs); 
    IloNumVar deadline(env,0,IloInfinity,ILOINT); 
 
    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(time, 1.0); 
	  vehicles[j]=vehicle; 
      mdl.add(vehicle); 
    } 
 
    for (i = 0; i < nbOfTrucks*nbOfJobs; i++) { 
     	IloInt id=i;  
       	IloNum x=0, y=0; 

	IloNode customer(env, x, y); 
	char name[16]; 
       	sprintf(name, "%d", id); 
       	IloVisit visit(customer, name); 
       	mdl.add(visit.getDelayVar(time) == durations[i]); 
       	visits[i] = visit; 
       	mdl.add(visit);  
    } 
     
    //Imposing vehicle-visit constraints 
    for (i=0;i<nbOfTrucks*nbOfJobs; i++) { 
      	mdl.add(visits[i].getVehicleVar()==vehicles[resourceNumbers[i]]); 
    } 
 
    //Imposing precedence constraints 
    for (i=0;i<nbOfJobs;i++) { 
      	for (j=0;j<nbOfTrucks-1; j++) { 
     		IloInt index = i*nbOfTrucks+j; 
       		mdl.add(visits[index].getCumulVar(time)+durations[index]<= 
      			visits[index+1].getCumulVar(time)); 
	} 
    } 
 
    //Imposing a deadline 
    for (i=0;i<nbOfJobs;i++) { 
      	index = i*nbOfTrucks+nbOfTrucks-1; 
       	mdl.add(visits[index].getCumulVar(time)+durations[index]<=deadline); 
    } 
	
    mdl.add(deadline<=UpperBound); 
    IloInt sum = 0; 
    for (i=0;i<nbOfJobs*nbOfTrucks;i++) { 
       	sum += durations[i]; 
    } 
 
    infile.close(); 
    IloSolver solver(mdl); 
 
    /////////////////////////////////////////////////// 
    // 
    // Constructing a first solution using savings 
    // 
    /////////////////////////////////////////////////// 
 
    IloDispatcher dispatcher(solver); 
    IloRoutingSolution solution(mdl); 
    IloGoal instantiateCost = IloDichotomize(env,  
					     dispatcher.getCostVar(), 
					     IloFalse); 
    IloGoal restoreSolution = IloRestoreSolution(env, solution); 
    IloGoal goal = IloSavingsGenerate(env) && instantiateCost; 
 
    if (!solver.solve(goal)) { 
       	solver.out() << "Couldn't generate first solution. Try changing the makespan's upper bound"; 
        return 0; 
    } 
 
    // output the first solution 
    Info(dispatcher,outfile); 
 
    //////////////////////////////////////////// 
    // 
    // Creating the neighbourhood of a solution 
    // 
    //////////////////////////////////////////// 
 
    solution.store(solver); 
    IloNHood nhood = IloTwoOpt(env)  
		   + IloOrOpt(env)  
		   + IloRelocate(env) 
		   + IloExchange(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); 
       	} 
    } 
 
    Info(dispatcher,outfile); 
  } catch(IloException& ex) { 
    cerr << "Error: " << ex << endl; 
  }  
  env.end(); 
  return 0; 
}