The complete VRP program follows. You can also view it online in the YourDispatcherHome/examples/src/vrp.cpp
file.
// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/vrp.cpp
//---------------------------------------------------------------------------
#include <ildispat/ilodispatcher.h>
ILOSTLBEGIN
///////////////////////////////////////////////////////////////////////////////
// Modeling
class RoutingModel {
IloEnv _env;
IloModel _mdl;
IloDimension2 _time;
IloDimension2 _distance;
IloDimension1 _weight;
void addDimensions();
void createIloNodes(const char* nodeFileName);
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; }
};
RoutingModel::RoutingModel( IloEnv env,
int argc,
char* argv[]):
_env(env), _mdl(env) {
addDimensions();
//create IloNodes
char * nodeFileName;
if(argc < 2) nodeFileName =
(char*) "../../../examples/data/vrp20/vrp20nodes.csv";
else nodeFileName = argv[1];
createIloNodes(nodeFileName);
//create vehicles
char * vehiclesFileName;
if(argc < 3) vehiclesFileName =
(char*) "../../../examples/data/vrp20/vrp20vehicles.csv";
else vehiclesFileName = argv[2];
createVehicles(vehiclesFileName);
//create visits
char * visitsFileName;
if(argc < 4) visitsFileName =
(char*) "../../../examples/data/vrp20/vrp20visits.csv";
else visitsFileName = argv[3];
createVisits(visitsFileName);
}
// create distance functions for dimensions, add dimensions to model
void RoutingModel::addDimensions() {
_weight =IloDimension1 (_env, "weight");
_mdl.add(_weight);
_time =IloDimension2 (_env, IloEuclidean, "time");
_mdl.add(_time);
_distance =IloDimension2 (_env, IloEuclidean, "distance");
_mdl.add(_distance);
}
//create IloNodes
void RoutingModel::createIloNodes(const char* nodeFileName) {
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);
++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);
_mdl.add(first.getCumulVar(_time) >= line.getFloatByHeader("open"));
IloVisit last(node2, "depot");
_mdl.add(last.getCumulVar(_time) <= line.getFloatByHeader("close"));
IloVehicle vehicle(first, last, name);
vehicle.setCost(_distance, 1.0);
vehicle.setCapacity(_weight, capacity);
_mdl.add(vehicle);
++it;
}
csvVehicleReader.end();
}
//create visits
void RoutingModel::createVisits(const char* visitsFileName) {
IloCsvReader csvVisitReader(_env, visitsFileName);
IloCsvReader::LineIterator it(csvVisitReader);
while(it.ok()){
IloCsvLine line = *it;
//read visit data from files
char * visitName = line.getStringByHeader("name");
char * nodeName = line.getStringByHeader("node");
IloNum quantity = line.getFloatByHeader("quantity");
IloNum minTime = line.getFloatByHeader("minTime");
IloNum maxTime = line.getFloatByHeader("maxTime");
IloNum dropTime = line.getFloatByHeader("dropTime");
IloNode node = IloNode::Find(_env, nodeName);
IloVisit visit(node, visitName);
_mdl.add(visit.getDelayVar(_time) == dropTime);
_mdl.add(visit.getTransitVar(_weight) == quantity);
_mdl.add(minTime <= visit.getCumulVar(_time) <= maxTime);
_mdl.add(visit);
++it;
}
csvVisitReader.end();
}
///////////////////////////////////////////////////////////////////////////////
// Solving
class RoutingSolver {
IloEnv _env;
IloModel _mdl;
IloSolver _solver;
IloDispatcher _dispatcher;
IloRoutingSolution _solution;
IloGoal _instantiateCost;
IloGoal _restoreSolution;
IloGoal _goal;
public:
RoutingSolver(RoutingModel mdl);
~RoutingSolver() {}
IloBool findFirstSolution();
void improveWithNhood();
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);
_restoreSolution = IloRestoreSolution(_env, _solution);
_goal = IloSavingsGenerate(_env) && _instantiateCost;
}
// Solving : find first solution
IloBool RoutingSolver::findFirstSolution() {
if (!_solver.solve(_goal)) {
_solver.error() << "Infeasible Routing Plan" << endl;
return IloFalse;
}
_solution.store(_solver);
return IloTrue;
}
//Improve solution using nhood
void RoutingSolver::improveWithNhood() {
IloNHood nhood = IloTwoOpt(_env)
+ IloOrOpt(_env)
+ IloRelocate(_env)
+ IloCross(_env)
+ IloExchange(_env);
_solver.out() << "Improving solution" << endl;
IloGoal improve = IloSingleMove(_env,
_solution,
nhood,
IloImprove(_env),
_instantiateCost);
while (_solver.solve(improve)) {
}
_solver.solve(_restoreSolution);
}
// 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();
solver.printInformation("***Improved Solution***");
}
} catch(IloException& ex) {
cerr << "Error: " << ex << endl;
}
env.end();
return 0;
}