The complete program follows. You can also view it online in the YourDispatcherHome/examples/src/multitr.cpp file.
// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/multitr.cpp
//---------------------------------------------------------------------------
#include <ildispat/ilodispatcher.h>
ILOSTLBEGIN
///////////////////////////////////////////////////////////////////////////////
// Modeling
class RoutingModel {
IloEnv _env;
IloModel _mdl;
IloDispatcherGraph _graph;
IloDimension2 _distance;
IloDimension1 _weight;
IloVisitArray _unorderedVisitArray;
void addDimensions();
void loadGraphInformation (const char* arcFileName);
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; }
IloDispatcherGraph getGraph() const {return _graph;}
IloVisitArray getUnorderedVisitArray () const {return _unorderedVisitArray;}
};
RoutingModel::RoutingModel( IloEnv env,
int argc,
char* argv[]):
_env(env),
_mdl(env),
_graph(env),
_unorderedVisitArray(env){
addDimensions();
// Load dispatcher graph information from file .
// Add instance-specific features to network
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);
//create IloNodes and associate them to graph nodes
char * nodeFileName;
if(argc < 4) nodeFileName =
(char*) "../../../examples/data/vrp100/vrp100nodes.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/vrp100/vrp100vehicles.csv";
else vehiclesFileName = argv[5];
createVehicles(vehiclesFileName);
//create visits
char * visitsFileName;
if(argc < 7) visitsFileName =
(char*) "../../../examples/data/vrp100/vrp100visits.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_distance = IloGraphDistance (_graph);
_distance =IloDimension2 (_env, SP_distance, "distance");
_mdl.add(_distance);
}
// load network topology and travel costs from files.
// note that by default, all turns are allowed with no penalty.
void RoutingModel::loadGraphInformation (const char* arcFileName) {
_graph.createArcsFromFile (arcFileName);
_graph.loadArcDimensionDataFromFile (arcFileName, _distance);
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));
}
//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");
IloVehicle vehicle(first, last, name);
vehicle.setCost(250.0);
vehicle.setCost(_distance, 1.0);
vehicle.setCapacity(_weight, capacity);
last.getCumulVar(_distance).setUb(350);
_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");
IloNode node = IloNode::Find(_env, nodeName);
IloVisit visit(node, visitName);
visit.getTransitVar(_weight).setBounds(quantity, quantity);
_unorderedVisitArray.add(visit);
++it;
}
csvVisitReader.end();
}
///////////////////////////////////////////////////////////////////////////////
// Solving
class RoutingSolver {
IloEnv _env;
IloModel _mdl;
IloSolver _solver;
IloDispatcher _dispatcher;
IloRoutingSolution _solution;
IloGoal _instantiateCost;
IloGoal _restoreSolution;
IloVisitArray _orderedVisitArray;
public:
RoutingSolver(RoutingModel mdl);
~RoutingSolver() {}
void insertAllReturnVisits ();
void orderVisits (IloVisitArray visitArray,
IloDispatcherGraph graph);
bool insertCustomerVisits ();
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);
}
void RoutingSolver::insertAllReturnVisits () {
_solver.out() << "Inserting return visits" << endl;
IloNode depot = IloNode::Find(_env, "depot");
for (IloVehicleIterator vehIt(_mdl); vehIt.ok(); ++vehIt) {
IloVehicle vehicle = *vehIt;
for (IloInt i = 0; i < 2; i++) {
IloVisit visit(depot, "depot");
visit.setPenaltyCost(-0.1);
_mdl.add (visit);
IloGoal insert =
IloInsertVisit(_env, visit, vehicle, _solution, _instantiateCost);
if (!_solver.solve(insert)) {
_solver.out() << "Cannot insert new visit in solution" << endl;
_mdl.remove(visit);
}
else {
_solution.add(visit);
_solution.store(_solver);
}
}
}
}
void RoutingSolver::orderVisits(IloVisitArray unorderedVisitArray,
IloDispatcherGraph graph) {
IloModel tspModel(_env);
IloInt nbOfVisits = unorderedVisitArray.getSize();
IloVisit first(unorderedVisitArray[0].getNode(), "first");
IloVisit last(unorderedVisitArray[0].getNode(), "last");
IloVehicle vehicle(first, last, "TSP");
tspModel.add(vehicle);
IloDistance dist = IloGraphDistance (graph);
IloDimension2 dim(_env, dist, IloFalse);
vehicle.setCost(dim, 1.0);
tspModel.add(dim);
for (IloInt i = 1; i < nbOfVisits; i++)
tspModel.add(unorderedVisitArray[i]);
IloSolver solver(tspModel);
IloDispatcher dispatcher(solver);
IloGoal instCost = IloDichotomize(_env, dispatcher.getCostVar(), IloFalse);
solver.out() << "Producing insertion order" << endl;
solver.solve(IloNearestAdditionGenerate(_env) && instCost);
IloRoutingSolution rsolution(tspModel);
rsolution.store(solver);
IloNHood nhood = IloTwoOpt(_env);
IloMetaHeuristic improve = IloImprove(_env);
IloGoal move = IloSingleMove(_env, rsolution, nhood, improve, instCost);
while (solver.solve(move)) {
}
_orderedVisitArray = IloVisitArray (_env, nbOfVisits);
IloRoutingSolution::RouteIterator rit(rsolution, vehicle);
++rit;
_orderedVisitArray[0] = unorderedVisitArray[0];
for (IloInt k = 1; k < nbOfVisits; ++k, ++rit)
_orderedVisitArray[k] = *rit;
nhood.end();
solver.end();
rsolution.end();
}
bool RoutingSolver::insertCustomerVisits () {
_solver.out() << "Inserting customer visits" << endl;
for (IloInt i = 0; i < _orderedVisitArray.getSize(); i++) {
IloVisit visit = _orderedVisitArray[i];
_mdl.add(visit);
IloGoal insert = IloInsertVisit(_env, visit, _solution, _instantiateCost);
if (!_solver.solve(insert)) {
_solver.error() << "Could not generate an initial solution" << endl;
return IloFalse;
}
else {
_solution.add(visit);
_solution.store(_solver);
}
}
return IloTrue;
}
//Improve solution using nhood
void RoutingSolver::improveWithNhood() {
IloNHood nhood = IloRelocate(_env)
+ IloTwoOpt(_env)
+ IloOrOpt(_env)
+ IloCross(_env)
+ IloExchange(_env)
+ IloMakeUnperformed(_env)
+ IloMakePerformed(_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);
solver.insertAllReturnVisits();
solver.orderVisits(mdl.getUnorderedVisitArray(), mdl.getGraph());
if (solver.insertCustomerVisits()) {
solver.improveWithNhood();
solver.printInformation("***Solution after improvements with nhood***");
}
} catch(IloException& ex) {
cerr << "Error: " << ex << endl;
}
env.end();
return 0;
}
PREVIOUS
NEXT