The complete program follows. You can also view it online in the YourDispatcherHome/examples/src/minvehcl.cpp file.
// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/minvehcl.cpp
//---------------------------------------------------------------------------
#include <ildispat/ilodispatcher.h>
ILOSTLBEGIN
///////////////////////////////////////////////////////////////////////////////
// Modeling
class RoutingModel {
IloEnv _env;
IloModel _mdl;
IloDispatcherGraph _graph;
IloDimension2 _time;
IloDimension1 _weight;
void addDimensions();
void loadGraphInformation (char* arcFileName, char* turnFileName);
void lastMinuteGraphChanges ();
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; }
};
// 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);
}
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 < 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/vrp200/vrp200nodes.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/vrp200/vrp200vehicles.csv";
else vehiclesFileName = argv[5];
createVehicles(vehiclesFileName);
// Create visits
char * visitsFileName;
if(argc < 7) visitsFileName =
(char*) "../../../examples/data/vrp200/vrp200visits.csv";
else visitsFileName = argv[6];
createVisits(visitsFileName);
}
// Load network topology and travel costs from files.
void RoutingModel::loadGraphInformation ( char* arcFileName,
char* turnFileName) {
_graph.createArcsFromFile (arcFileName);
_graph.loadArcDimensionDataFromFile (arcFileName, _time);
_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(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");
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(_time, 1.0);
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);
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);
visit.setPenaltyCost(1000);
++it;
}
csvVisitReader.end();
}
///////////////////////////////////////////////////////////////////////////////
// Solving
class RoutingSolver {
IloEnv _env;
IloModel _mdl;
IloSolver _solver;
IloDispatcher _dispatcher;
IloRoutingSolution _solution;
IloGoal _instantiateCost;
IloGoal _generateGoal;
IloGoal _restoreSolution;
IloVehicle getShortestRoute ();
public:
RoutingSolver(RoutingModel mdl);
~RoutingSolver() {}
IloBool findFirstSolution ();
void improveWithNhood ();
void closeEmptyVehicles ();
void reduceActiveVehicles ();
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);
_generateGoal = IloSavingsGenerate(_env) && _instantiateCost;
_restoreSolution = IloRestoreSolution(_env, _solution);
}
// Solving : find first solution
IloBool RoutingSolver::findFirstSolution() {
if (!_solver.solve(_generateGoal)) {
_solver.error() << "Infeasible Routing Plan" << endl;
return IloFalse;
}
_solution.store(_solver);
return IloTrue;
}
//Improve solution using nhood
void RoutingSolver::improveWithNhood() {
IloNHood nhood = (IloRelocate(_env) + IloExchange(_env) + IloCross(_env))
+ (IloTwoOpt(_env) + IloOrOpt(_env))
+ (IloMakePerformed(_env)
+ IloMakeUnperformed(_env)
+ IloSwapPerform(_env));
_solver.out() << "Improving solution" << endl;
IloGoal improve = IloSingleMove(_env,
_solution,
nhood,
IloImprove(_env),
_instantiateCost);
while (_solver.solve(improve)) {
}
_solver.solve(_restoreSolution);
}
void RoutingSolver::closeEmptyVehicles() {
for (IloIterator<IloVehicle> iter(_env); iter.ok(); ++iter) {
IloVehicle vehicle = *iter;
IloInt size = _solution.getRouteSize(vehicle);
if (size == 0) {
_mdl.add(vehicle.getFirstVisit().getNextVar() == vehicle.getLastVisit());
}
}
}
IloVehicle RoutingSolver::getShortestRoute() {
IloInt bestSize = 1000000;
IloVehicle bestVehicle;
for (IloIterator<IloVehicle> iter(_env); iter.ok(); ++iter) {
IloVehicle vehicle = *iter;
IloInt size = _solution.getRouteSize(vehicle);
if (size < bestSize && size != 0) {
bestSize = size;
bestVehicle = vehicle;
}
}
return bestVehicle;
}
void RoutingSolver::reduceActiveVehicles () {
IloVehicle vehicle = getShortestRoute();
IloRoutingSolution solCopy(_env);
IloBool vehicleClosed = IloTrue;
IloGoal sync = IloRestoreSolution(_env, _solution)
&& IloStoreSolution(_env, _solution);
while (vehicleClosed && vehicle.getImpl()) {
solCopy.copy(_solution);
_solver.out() << "Emptying " << vehicle.getName() << " ..." << endl;
IloAnd andCt(_env);
_mdl.add(andCt);
for (IloRoutingSolution::RouteIterator iter(solCopy, vehicle);
iter.ok();
++iter) {
IloVisit visit = *iter;
if (!visit.isFirstVisit() && !visit.isLastVisit()) {
andCt.add(vehicle != visit.getVehicleVar());
_solution.remove(visit);
_solver.solve(sync);
IloGoal insert = IloInsertVisit(_env, visit, _solution);
_solver.solve(insert);
_solution.add(visit);
_solution.store(_solver);
}
}
improveWithNhood();
if (_solution.getNumberOfUnperformedVisits() == 0
&& _solution.getRouteSize(vehicle) == 0) {
_mdl.add(vehicle.getFirstVisit().getNextVar()
== vehicle.getLastVisit());
vehicle = getShortestRoute();
}
else {
_mdl.remove(andCt);
_solution.copy(solCopy);
vehicleClosed = IloFalse;
}
}
_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("***Solution after improvements with nhood***");
solver.closeEmptyVehicles();
solver.reduceActiveVehicles();
solver.printInformation("***Solution after reducing active vehicles***");
}
} catch(IloException& ex) {
cerr << "Error: " << ex << endl;
}
env.end();
return 0;
}
PREVIOUS
NEXT