The complete program follows. You can also view it online in the file YourDispatcherHome/examples/src/carp.cpp.
// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/carp.cpp
//---------------------------------------------------------------------------
#include <ildispat/ilodispatcher.h>
ILOSTLBEGIN
///////////////////////////////////////////////////////////////////////////////
// Modeling
class RoutingModel {
IloEnv _env;
IloModel _mdl;
IloDispatcherGraph _graph;
IloDimension2 _time;
IloDimension2 _distance;
IloDimension1 _weight;
void addDimensions();
void loadGraphInformation (char* arcFileName);
void CreateIloNodes(char* nodeFileName, char* coordFileName);
void CreateVehicles(char* vehicleFileName);
void CreateVisits(char* visitsFileName);
public:
RoutingModel(IloEnv env, int argc, char* argv[]);
~RoutingModel() {}
IloEnv getEnv() const { return _env; }
IloModel getModel() const { return _mdl; }
void modifyGraphArcCost();
IloDispatcherGraph getGraph() const { return _graph; }
};
RoutingModel::RoutingModel( IloEnv env,
int argc,
char* argv[]):
_env(env), _mdl(env), _graph(env) {
addDimensions();
// load dispatcher graph information from file and add instance-specific features
char * arcFileName;
if(argc < 5) arcFileName = (char *) "../../../examples/data/dispatcherGraphData/gridNetwork.csv";
else arcFileName = argv[4];
loadGraphInformation (arcFileName);
//create IloNodes
char * nodeFileName;
if(argc < 4) nodeFileName = (char *) "../../../examples/data/carp/nodes.csv";
else nodeFileName = argv[3];
char * nodeCoordsFile;
if(argc < 6) nodeCoordsFile = (char *) "../../../examples/data/carp/coordTable.csv";
else nodeCoordsFile = argv[5];
CreateIloNodes(nodeFileName, nodeCoordsFile);
//create vehicles
char * vehiclesFileName;
if(argc < 2) vehiclesFileName = (char *) "../../../examples/data/carp/vehicles.csv";
else vehiclesFileName = argv[1];
CreateVehicles(vehiclesFileName);
//create visits
char * visitsFileName;
if(argc < 3) visitsFileName = (char *) "../../../examples/data/carp/visits.csv";
else visitsFileName = argv[2];
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 (char* arcFileName) {
_graph.createArcsFromFile (arcFileName);
_graph.loadArcDimensionDataFromFile (arcFileName, _time);
_graph.loadArcDimensionDataFromFile (arcFileName, _distance);
}
//create IloNodes
void RoutingModel::CreateIloNodes(char* nodeFileName, 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(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");
IloNum costRatio = line.getFloatByHeader("costRatio");
IloNode node1 = IloNode::Find(_env, namefirst);
IloNode node2 = IloNode::Find(_env, namelast);
IloVisit first(node1, "depot");
_mdl.add(first.getCumulVar(_distance) == 0);
_mdl.add(first.getCumulVar(_time) == 0);
IloVisit last(node2, "depot");
IloVehicle vehicle(first, last, name);
vehicle.setCost(_time, 100 * costRatio);
vehicle.setCost(_distance, 100 * (1- costRatio));
vehicle.setCapacity(_weight, capacity);
_mdl.add(vehicle);
++it;
}
csvVehicleReader.end();
}
//create visits
void RoutingModel::CreateVisits(char* visitsFileName) {
IloCsvReader csvVisitReader(_env, visitsFileName);
IloCsvReader::LineIterator it(csvVisitReader);
char c = 's';
while(it.ok()){
IloCsvLine line = *it;
//read visit data from files
char * visitName = line.getStringByHeader("name");
char * nodeName1 = line.getStringByHeader("nodeName1");
char * nodeName2 = line.getStringByHeader("nodeName2");
IloInt symmetric = line.getIntByHeader("symmetric");
IloNum quantity = line.getFloatByHeader("quantity");
IloNum timeValue = line.getFloatByHeader("time");
IloNum distanceValue = line.getFloatByHeader("distance");
IloNode node1 = IloNode::Find(_env, nodeName1);
IloNode node2 = IloNode::Find(_env, nodeName2);
IloVisit visit1(node1, node2, visitName);
_mdl.add(visit1.getTransitVar(_weight) == quantity);
_mdl.add(visit1.getDelayVar(_time) == timeValue );
_mdl.add(visit1.getDelayVar(_distance) == distanceValue );
_mdl.add(visit1);
if(symmetric) {
visit1.setPenaltyCost(0);
char visitName2[16];
sprintf(visitName2, "%s%c", visitName, c);
IloVisit visit2(node2, node1, visitName2);
_mdl.add(visit2.getTransitVar(_weight) == quantity);
_mdl.add(visit2.getDelayVar(_time) == timeValue );
_mdl.add(visit2.getDelayVar(_distance) == distanceValue );
visit2.setPenaltyCost(0);
_mdl.add(visit2);
_mdl.add(visit1.performed() + visit2.performed() == 1);
}
++it;
}
csvVisitReader.end();
}
// Modify problem set-up by modifying the cost of un arc in the graph
void RoutingModel::modifyGraphArcCost() {
IloDispatcherGraph::Arc arc1 = _graph.getArc(3916); //Arc from 1043 to 987
IloDispatcherGraph::Arc arc2 = _graph.getArc(4134); //Arc from 1043 to 1042
IloDispatcherGraph::Arc arc3 = _graph.getArc(4136); //Arc from 1043 to 1044
IloDispatcherGraph::Arc arc4 = _graph.getArc(4137); //Arc from 1043 to 1099
_graph.setArcCost(arc1, _time, 10);
_graph.setArcCost(arc2, _time, 10);
_graph.setArcCost(arc3, _time, 10);
_graph.setArcCost(arc4, _time, 10);
}
///////////////////////////////////////////////////////////////////////////////
// Solving
class RoutingSolver {
IloModel _mdl;
IloSolver _solver;
IloRoutingSolution _solution;
IloEnv _env;
IloDispatcher _dispatcher;
IloGoal _instantiateCost;
IloGoal _restoreSolution;
IloGoal _goal;
void greedyImprove(IloNHood nhood, IloGoal subGoal);
void improve(IloGoal subgoal);
void improveWithFastGLS(IloNHood nhood, IloInt nbOfIter, IloGoal subgoal);
public:
RoutingSolver(RoutingModel mdl);
~RoutingSolver() {}
IloRoutingSolution getSolution() const { return _solution; }
void printInformation() const;
IloBool findFirstSolution();
void improveWithNHood(IloInt nbIter);
void modifyFilterLevelAndRestore();
void restoreSolution();
void displayPaths(IloDispatcherGraph graph);
};
RoutingSolver::RoutingSolver(RoutingModel mdl):
_mdl(mdl.getModel()),
_solver(mdl.getModel()),
_solution(mdl.getModel()),
_env(mdl.getEnv()),
_dispatcher(_solver) {
_instantiateCost = IloGoal (IloDichotomize(_env, _dispatcher.getCostVar(), IloFalse));
_restoreSolution = IloGoal(IloRestoreSolution(_env, _solution));
_goal = IloGoal(IloSavingsGenerate(_env) && _instantiateCost);
}
// Solving : find first solution
IloBool RoutingSolver::findFirstSolution() {
if (!_solver.solve(_goal)) {
_solver.error() << "Infeasible Routing Plan" << endl;
return IloFalse;
}
_solver.out() << _dispatcher.getTotalCost() << endl;
_solution.store(_solver);
return IloTrue;
}
// Improve solution using nhood
void RoutingSolver::greedyImprove(IloNHood nhood, IloGoal subGoal) {
_solver.out() << "Improving solution" << endl;
nhood.reset();
IloGoal improve = IloSingleMove(_env,
_solution,
nhood,
IloImprove(_env),
subGoal);
while (_solver.solve(improve)) {}
}
// Modify dispatcher filter level and resolve
void RoutingSolver::modifyFilterLevelAndRestore() {
_dispatcher.setFilterLevel(IlcMedium);
IloNum cost = _solution.getObjectiveValue();
_solver.solve(_restoreSolution
&& IloSetMax(_env, _dispatcher.getCostVar(), cost));
_dispatcher.setFilterLevel(IlcLow);
}
// Modify graph arc cost and resolve
void RoutingSolver::restoreSolution() {
_solver.solve(_restoreSolution && _instantiateCost);
_solution.store(_solver);
_solver.out() << "Modified cost: " << _dispatcher.getTotalCost() << endl;
}
void RoutingSolver::improveWithFastGLS(IloNHood nhood,
IloInt nbOfIter,
IloGoal instantiateCost) {
nhood.reset();
_solver.out() << "Improving with first-accept GLS" << endl;
IloRoutingSolution rsol = _solution.makeClone(_env);
IloRoutingSolution best = _solution.makeClone(_env);
IloDispatcherGLS dgls(_env, 0.2);
IloGoal move = IloSingleMove(_env, rsol, nhood, dgls, instantiateCost);
move = move && IloStoreBestSolution(_env, best);
IloNumVar costVar = _dispatcher.getCostVar();
IloCouple(nhood, dgls);
for (IloInt i = 0; i < nbOfIter; i++) {
if (_solver.solve(move)) {
_solver.out() << "Cost = " << _solver.getMax(costVar) << endl;
} else {
_solver.out() << "---" << endl;
if (dgls.complete()) break;
}
}
_solver.out() << endl;
IloDecouple(nhood, dgls);
IloGoal restoreSolution = IloRestoreSolution(_env, best) && instantiateCost;
_solver.solve(restoreSolution);
_solution.store(_solver);
rsol.end();
best.end();
dgls.end();
}
// Display Dispatcher information
void RoutingSolver::printInformation() const {
_solver.printInformation();
_dispatcher.printInformation();
_solver.out() << "===============" << endl
<< "Cost : " << _dispatcher.getTotalCost() << endl
<< "Number of vehicles used : "
<< _dispatcher.getNumberOfVehiclesUsed() << endl
<< "Solution : " << endl
<< _dispatcher << endl;
}
// Solving
void RoutingSolver::improveWithNHood(IloInt nbIter) {
IloNHood nhood = IloTwoOpt(_env)
+ IloOrOpt(_env)
+ IloRelocate(_env)
+ IloExchange(_env)
+ IloCross(_env)
+ IloSwapPerform(_env);
greedyImprove(nhood, _instantiateCost);
improveWithFastGLS(nhood, nbIter, _instantiateCost);
}
void RoutingSolver::displayPaths(IloDispatcherGraph graph) {
_env.out() << "Paths" << endl;
for (IloIterator<IloVehicle> iter1(_env); iter1.ok(); ++iter1) {
IloVehicle vehicle = *iter1;
IloVisit visit1 = vehicle.getFirstVisit();
for (IloDispatcher::RouteIterator iter2(_dispatcher, vehicle);
iter2.ok();
++iter2) {
IloVisit visit2 = *iter2;
if (visit1 != visit2) {
_env.out() << visit1.getName() << " {"
<< graph.getLocation(visit1.getStartNode())
.getIndex();
for (IloDispatcherGraph::PathIterator iter3(graph,
visit1.getEndNode(),
visit2.getStartNode(),
vehicle);
iter3.ok();
++iter3) {
_env.out() << " -> " << (*iter3).getIndex();
}
_env.out() << "} -> ";
visit1 = visit2;
}
}
_env.out() << vehicle.getLastVisit().getName() << endl;
}
_env.out() << endl;
}
///////////////////////////////////////////////////////////////////////////////
int main(int argc, char * argv[]) {
IloEnv env;
try {
RoutingModel mdl(env, argc, argv);
RoutingSolver solver(mdl);
if (solver.findFirstSolution()) {
solver.printInformation();
solver.improveWithNHood(250);
solver.modifyFilterLevelAndRestore();
solver.printInformation();
solver.displayPaths(mdl.getGraph());
mdl.modifyGraphArcCost();
solver.restoreSolution();
solver.improveWithNHood(50);
solver.modifyFilterLevelAndRestore();
solver.printInformation();
solver.displayPaths(mdl.getGraph());
}
} catch(IloException& ex) {
cerr << "Error: " << ex << endl;
}
env.end();
return 0;
}
PREVIOUS
NEXT