The complete program follows. You can also view it online in the YourDispatcherHome/examples/src/disjunct.cpp file.
// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/disjunct.cpp
//---------------------------------------------------------------------------
#include <ildispat/ilodispatcher.h>
ILOSTLBEGIN
///////////////////////////////////////////////////////////////////////////////
// Modeling
class RoutingModel {
IloEnv _env;
IloModel _mdl;
IloDispatcherGraph _graph;
IloDimension1 _weight;
IloDimension2 _time;
IloDimension2 _distance;
IloNHoodArray _swapArray;
void addDimensions();
void loadGraphInformation (const char * arcFileName,
const char* turnFileName);
void lastMinuteGraphChanges ();
void createIloNodes(const char * nodeFileName, const char* coordFileName);
void createVehicles(const char * vehicleFileName);
void createVisits(const char * visitsFileName);
public:
RoutingModel(IloEnv env, int argc, char* argv[]);
~RoutingModel() {}
IloEnv getEnv() const { return _env; }
IloModel getModel() const { return _mdl; }
IloNHoodArray getSwapArray() const {return _swapArray;}
IloVisit createAdditionalVisits (int argc, char* argv[]);
void removeVisit (IloVisit);
};
RoutingModel::RoutingModel( IloEnv env,
int argc,
char* argv[]):
_env(env), _mdl(env), _graph(env) {
addDimensions();
// Load dispatcher graph information and add instance-specific features.
char * arcFileName;
if(argc < 2) arcFileName =
(char*) "../../../examples/data/dispatcherGraphData/gridNetwork.csv";
else arcFileName = argv[1];
char * turnFileName;
if(argc < 3) turnFileName =
(char*) "../../../examples/data/dispatcherGraphData/turnData.csv";
else turnFileName = argv[2];
loadGraphInformation (arcFileName, turnFileName);
//create IloNodes and associate them to graph nodes
char * nodeFileName;
if(argc < 4) nodeFileName =
(char*) "../../../examples/data/vrp50/vrp50nodes.csv";
else nodeFileName = argv[3];
char * nodeCoordsFile;
if(argc < 5) nodeCoordsFile =
(char*) "../../../examples/data/dispatcherGraphData/coordTable.csv";
else nodeCoordsFile = argv[4];
createIloNodes(nodeFileName, nodeCoordsFile);
//create vehicles
char * vehiclesFileName;
if(argc < 6) vehiclesFileName =
(char*) "../../../examples/data/vrp50/vrp50vehicles.csv";
else vehiclesFileName = argv[5];
createVehicles(vehiclesFileName);
//create visits
char * visitsFileName;
if(argc < 7) visitsFileName =
(char*) "../../../examples/data/vrp50/vrp50visits.csv";
else visitsFileName = argv[6];
createVisits(visitsFileName);
}
// create distance functions for dimensions, add dimensions to model
void RoutingModel::addDimensions() {
_weight =IloDimension1 (_env, "weight");
_mdl.add(_weight);
IloDistance SP_time = IloGraphDistance (_graph);
_time =IloDimension2 (_env, SP_time, "time");
_mdl.add(_time);
IloDistance SP_distance = IloGraphDistance (_graph);
_distance =IloDimension2 (_env, SP_distance, "distance");
_mdl.add(_distance);
}
// load network topology and travel costs from files.
void RoutingModel::loadGraphInformation ( const char* arcFileName,
const char* turnFileName) {
_graph.createArcsFromFile (arcFileName);
_graph.loadArcDimensionDataFromFile (arcFileName, _time);
_graph.loadArcDimensionDataFromFile (arcFileName, _distance);
_graph.loadTurnDimensionDataFromFile(turnFileName, _time);
lastMinuteGraphChanges();
}
// Make modifications to network conditions based on latest information.
void RoutingModel::lastMinuteGraphChanges () {
_graph.forbidArcUse(_graph.getArcByEnds(2785-1, 2785));
_graph.forbidArcUse(_graph.getArcByEnds(2785+1, 2785));
_graph.forbidArcUse(_graph.getArcByEnds(2785-56, 2785));
_graph.setTurnPenalty(_graph.getArc(1323), _graph.getArc(1544), _time, 12);
}
//create IloNodes
void RoutingModel::createIloNodes(const char * nodeFileName,
const char* coordFileName) {
IloCsvReader csvNodeReader(_env, nodeFileName);
IloCsvReader::LineIterator it(csvNodeReader);
while(it.ok()) {
IloCsvLine line = *it;
char * name = line.getStringByHeader("name");
IloNode node(_env, line.getFloatByHeader("x"),
line.getFloatByHeader("y"), 0, name);
node.setKey(name);
_graph.associateByCoordsInFile (node, coordFileName);
++it;
}
csvNodeReader.end();
}
//create vehicles
void RoutingModel::createVehicles(const char * vehicleFileName) {
IloCsvReader csvVehicleReader(_env, vehicleFileName);
IloCsvReader::LineIterator it(csvVehicleReader);
while(it.ok()) {
IloCsvLine line = *it;
char * namefirst = line.getStringByHeader("first");
char * namelast = line.getStringByHeader("last");
char * name = line.getStringByHeader("name");
IloNum capacity = line.getFloatByHeader("capacity");
IloNode node1 = IloNode::Find(_env, namefirst);
IloNode node2 = IloNode::Find(_env, namelast);
IloVisit first(node1, "depot");
_mdl.add(first.getCumulVar(_weight) == 0);
IloVisit last(node2, "depot");
_mdl.add(last.getCumulVar(_distance) >= line.getFloatByHeader("open"));
_mdl.add(last.getCumulVar(_distance) <= line.getFloatByHeader("close"));
IloVehicle vehicle(first, last, name);
vehicle.setCapacity(_weight, capacity);
vehicle.setCost(_time, 1.0);
vehicle.setCost(_distance, 1.0);
_mdl.add(vehicle);
++it;
}
csvVehicleReader.end();
}
//create visits
void RoutingModel::createVisits( const char* visitsFileName) {
IloCsvReader csvVisitReader(_env, visitsFileName);
_swapArray = IloNHoodArray (_env, csvVisitReader.getNumberOfItems()/2);
IloInt i=0;
IloCsvReader::LineIterator it(csvVisitReader);
while(it.ok()){
IloCsvLine line1 = *it;
//read visit data from files
char * visitName1 = line1.getStringByHeader("name");
char * nodeName1 = line1.getStringByHeader("node");
IloNum quantity1 = line1.getFloatByHeader("quantity");
IloNum minTime1 = line1.getFloatByHeader("minTime");
IloNum maxTime1 = line1.getFloatByHeader("maxTime");
IloNode node1 = IloNode::Find(_env, nodeName1);
IloVisit visit1(node1, visitName1);
_mdl.add(visit1.getTransitVar(_weight) == quantity1);
visit1.setPenaltyCost(20);
_mdl.add(minTime1 <= visit1.getCumulVar(_time) <= maxTime1);
_mdl.add(visit1);
++it;
IloCsvLine line2 = *it;
char * visitName2 = line2.getStringByHeader("name");
char * nodeName2 = line2.getStringByHeader("node");
IloNum quantity2 = line2.getFloatByHeader("quantity");
IloNum minTime2 = line2.getFloatByHeader("minTime");
IloNum maxTime2 = line2.getFloatByHeader("maxTime");
IloNode node2 = IloNode::Find(_env, nodeName2);
IloVisit visit2(node2, visitName2);
_mdl.add(visit2.getTransitVar(_weight) == quantity2);
visit2.setPenaltyCost(10);
_mdl.add(minTime2 <= visit2.getCumulVar(_time) <= maxTime2);
_mdl.add(visit2);
++it;
_mdl.add(visit1.unperformed() + visit2.unperformed() == 1);
IloVisitArray visits(_env, 2);
visits[0] = visit1; visits[1] = visit2;
_swapArray[i] = IloSwapPerform(_env, visits);
++i;
}
csvVisitReader.end();
}
// Modify problem set-up by adding a new visit.
// Associate new visit to graph node.
IloVisit RoutingModel::createAdditionalVisits (int argc, char * argv[]) {
char * nodeCoordsFile;
if(argc < 5) nodeCoordsFile =
(char*) "../../../examples/data/dispatcherGraphData/coordTable.csv";
else nodeCoordsFile = argv[4];
IloNode customer(_env, 43, 63);
_graph.associateByCoordsInFile (customer, nodeCoordsFile);
IloVisit visit(customer, "Extra visit");
_mdl.add(visit.getDelayVar(_time) == 10);
_mdl.add(visit.getTransitVar(_weight) == 12);
_mdl.add(70 <= visit.getCumulVar(_time) <= 120);
_mdl.add(visit);
return visit;
}
void RoutingModel::removeVisit (IloVisit visit) {
_mdl.remove(visit);
}
///////////////////////////////////////////////////////////////////////////////
// Solving
class RoutingSolver {
IloEnv _env;
IloModel _mdl;
IloSolver _solver;
IloDispatcher _dispatcher;
IloRoutingSolution _solution;
IloGoal _instantiateCost;
IloGoal _generalGoal;
IloGoal _restoreSolution;
public:
RoutingSolver(RoutingModel mdl);
~RoutingSolver() {}
IloBool findFirstSolution ();
void improveWithNhood (IloNHoodArray swap);
IloBool addNewVisit (IloVisit visit);
IloBool removeVisitAndResolve (IloVisit visit);
void printInformation(const char* =0) const;
};
RoutingSolver::RoutingSolver(RoutingModel mdl):
_env(mdl.getEnv()),
_mdl(mdl.getModel()),
_solver(mdl.getModel()),
_dispatcher(_solver),
_solution(mdl.getModel()){
_instantiateCost =
IloDichotomize(_env, _dispatcher.getCostVar(), IloFalse);
_generalGoal = IloSavingsGenerate(_env) && _instantiateCost;
_restoreSolution = IloRestoreSolution(_env, _solution);
}
// Solving : find first solution
IloBool RoutingSolver::findFirstSolution() {
if (!_solver.solve(_generalGoal)) {
_solver.error() << "Infeasible Routing Plan" << endl;
return IloFalse;
}
_solution.store(_solver);
return IloTrue;
}
//Improve solution using nhood
void RoutingSolver::improveWithNhood(IloNHoodArray swap) {
IloNHoodArray nhoodArray(_env, 6);
nhoodArray[0] = IloTwoOpt(_env);
nhoodArray[1] = IloOrOpt(_env);
nhoodArray[2] = IloConcatenate(_env, swap);
nhoodArray[3] = IloExchange(_env);
nhoodArray[4] = IloRelocate(_env);
nhoodArray[5] = IloCross(_env);
IloNHood nhood = IloConcatenate(_env, nhoodArray);
_solver.out() << "Improving solution" << endl;
IloGoal improve = IloSingleMove(_env,
_solution,
nhood,
IloImprove(_env),
_instantiateCost);
while (_solver.solve(improve)) {
}
_solver.solve(_restoreSolution);
}
IloBool RoutingSolver::addNewVisit (IloVisit visit) {
IloGoal insert = IloInsertVisit(_env, visit, _solution, _instantiateCost);
if (!_solver.solve(insert)) {
_solver.out() << "Cannot insert new visit in solution" << endl;
return IloFalse;
}
_solution.add(visit);
_solution.store(_solver);
return IloTrue;
}
IloBool RoutingSolver::removeVisitAndResolve (IloVisit visit) {
_solution.remove(visit);
if (_solver.solve(_restoreSolution))
return IloTrue;
else return IloFalse;
}
// Display Dispatcher information
void RoutingSolver::printInformation(const char* heading) const {
if(heading)
_solver.out()<<heading<<endl;
_solver.printInformation();
_dispatcher.printInformation();
_solver.out() << "===============" << endl
<< "Cost : " << _dispatcher.getTotalCost() << endl
<< "Number of vehicles used : "
<< _dispatcher.getNumberOfVehiclesUsed() << endl
<< "Solution : " << endl
<< _dispatcher << endl;
}
///////////////////////////////////////////////////////////////////////////////
int main(int argc, char * argv[]) {
IloEnv env;
try {
RoutingModel mdl(env, argc, argv);
RoutingSolver solver(mdl);
if (solver.findFirstSolution()) {
solver.printInformation("***First Solution***");
solver.improveWithNhood(mdl.getSwapArray());
solver.printInformation("***Solution after improvements with nhood***");
IloVisit visit = mdl.createAdditionalVisits (argc, argv);
if (solver.addNewVisit (visit)) {
solver.printInformation("***Solution including new visit***");
mdl.removeVisit(visit);
if (solver.removeVisitAndResolve (visit)) {
solver.printInformation("***Solution after removing visit***");
}
}
}
} catch(IloException& ex) {
cerr << "Error: " << ex << endl;
}
env.end();
return 0;
}
PREVIOUS
NEXT