The complete program follows. You can also view it online in the file YourDispatcherHome/examples/src/technic1.cpp.
// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/technic1.cpp
//---------------------------------------------------------------------------
#include <ildispat/ilodispatcher.h>
ILOSTLBEGIN
/**
* This example shows the use of the visit-vehicle compatibility constraint.
* The constraint is defined using skill proficiency vectors, attached
* to both visits and vehicles.
*
*
*/
/**
* The SkillProfile class is used to model vector a skill proficiencies.
* it maps a level for each skill.
*/
class SkillProfile {
IloEnv _env;
IloInt _nbOfSkills;
IloInt* _skillLevels;
public:
SkillProfile(IloEnv env, IloInt nbOfSkills):
_env(env),
_nbOfSkills(nbOfSkills),
_skillLevels(0)
{
_skillLevels = new (env) IloInt [ nbOfSkills ];
for (IloInt s=0; s< _nbOfSkills; ++s) _skillLevels[s] = 0;
}
void setSkillLevel(IloInt skillIndex, IloInt level=1) {
_skillLevels[ skillIndex ] = level; }
/**
* Returns true if <code>other</code> is comparable with this
* and is greater.
*/
IloBool isGreaterThanOrEqual(const SkillProfile* other);
virtual void display(ILOSTD(ostream)& os) const {
os << "[";
for (IloInt s=0; s< _nbOfSkills; ++s) {
os << _skillLevels[s];
if ( s < _nbOfSkills-1) os << ", ";
}
os << "]";
}
};
inline ostream& operator<<(ostream& os, const SkillProfile& profile) {
profile.display(os); return os;
}
IloBool SkillProfile::isGreaterThanOrEqual(const SkillProfile* other) {
for(IloInt index = 0;
index < _nbOfSkills && other->_nbOfSkills; ++index) {
if ( _skillLevels[index] < other->_skillLevels[index] ) {
return IloFalse;
}
}
return IloTrue;
}
class RoutingModel {
IloEnv _env;
IloModel _mdl;
IloArray<SkillProfile*> _profiles;
IloInt _nbOfSkills;
const char* _nodePath;
const char* _technicianPath;
const char* _visitPath;
const char* _profilePath;
const char* _techProfilePath; // table binding profiles to tecnicians
const char* _visitProfilePath; // table binding profiles to visits
void createDimensions();
void createIloNodes(const char* nodePath);
void createSkillProfiles(const char* profilePath);
void setTechnicianSkillProfiles(const char* techProfilePath);
void setVisitSkillProfiles(const char* visitProfilePath);
void createTechnicians(const char* technicianPath);
void createVisits(const char* visitsPath);
void postCompatibility();
/**
* Lazy accessor to the profile table, with id as key.
* First, missing array slots are filled with zeroes.
* Then, if returned profile is null,
* a new profile is created, stored and returned.
*/
SkillProfile* getSkillProfile(IloInt profileId) {
if ( _profiles.getSize() <= profileId ) {
for (IloInt p= _profiles.getSize(); p <= profileId; ++p) {
_profiles.add( (SkillProfile*) 0);
}
}
SkillProfile* profile = _profiles[ profileId ] ;
if ( 0 == profile ) {
profile = new (_env) SkillProfile(_env, _nbOfSkills);
_profiles[ profileId ] = profile;
}
return profile;
}
public:
RoutingModel(IloEnv env);
~RoutingModel() {}
void parse(int argc, char** argv);
void createModel();
IloEnv getEnv() const { return _env; }
IloModel getModel() const { return _mdl; }
};
RoutingModel::RoutingModel(IloEnv env)
: _env(env),
_mdl(env),
_profiles(env),
_nbOfSkills(3),
_nodePath("../../../examples/data/technic1/nodes.csv"),
_technicianPath("../../../examples/data/technic1/technicians.csv"),
_visitPath("../../../examples/data/technic1/visits.csv"),
_profilePath("../../../examples/data/technic1/SkillProfiles.csv"),
_techProfilePath("../../../examples/data/technic1/techSkills.csv"),
_visitProfilePath("../../../examples/data/technic1/visitSkills.csv")
{ }
void RoutingModel::parse(int argc, char** argv) {
if ( argc > 1 ) _visitPath = argv[1];
if ( argc > 2 ) _technicianPath = argv[2];
if ( argc > 3 ) _visitProfilePath = argv[3];
if ( argc > 4 ) _techProfilePath = argv[4];
if ( argc > 5 ) _profilePath = argv[5];
if ( argc > 6 ) _nodePath = argv[6];
}
void RoutingModel::createModel() {
createDimensions();
createIloNodes(_nodePath);
createTechnicians(_technicianPath);
createVisits(_visitPath);
createSkillProfiles(_profilePath);
setTechnicianSkillProfiles(_techProfilePath);
setVisitSkillProfiles(_visitProfilePath);
postCompatibility();
}
// Create dimensions
void RoutingModel::createDimensions() {
IloDimension2 time(_env, IloEuclidean, "Time");
time.setKey("Time");
_mdl.add(time);
}
// Create IloNodes
void RoutingModel::createIloNodes(const char* nodePath) {
IloCsvReader csvNodeReader(_env, nodePath);
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::createTechnicians(const char* techPath) {
IloDimension2 time = IloDimension2::Find(_env, "Time");
IloCsvReader csvTechReader(_env, techPath);
char namebuf[128];
IloCsvReader::LineIterator it(csvTechReader);
for( ; it.ok(); ++it) {
IloCsvLine line = *it;
char * namefirst = line.getStringByHeader("first");
char * namelast = line.getStringByHeader("last");
char * name = line.getStringByHeader("name");
IloNum openTime = line.getFloatByHeader("open");
IloNum closeTime = line.getFloatByHeader("close");
IloNode node1 = IloNode::Find(_env, namefirst);
IloNode node2 = IloNode::Find(_env, namelast);
sprintf(namebuf, "start_%s", name);
IloVisit first(node1, namebuf);
_mdl.add( first.getCumulVar(time) >= openTime );
sprintf(namebuf, "end_%s", name);
IloVisit last(node2, namebuf);
_mdl.add( last.getCumulVar(time) <= closeTime );
IloVehicle technician(first, last, name);
technician.setCost(time, 1.0);
technician.setKey(name);
_mdl.add(technician);
}
csvTechReader.end();
}
// Create visits
void RoutingModel::createVisits(const char* visitsPath) {
IloDimension2 time = IloDimension2::Find(_env, "Time");
IloCsvReader csvVisitReader(_env, visitsPath);
IloCsvReader::LineIterator it(csvVisitReader);
for( ;it.ok(); ++it) {
IloCsvLine line = *it;
//read visit data from files
char * visitName = line.getStringByHeader("name");
char * nodeName = line.getStringByHeader("node");
IloNum minTime = line.getFloatByHeader("minTime");
IloNum maxTime = line.getFloatByHeader("maxTime");
IloNum serviceTime = line.getFloatByHeader("dropTime");
IloNode node = IloNode::Find(_env, nodeName);
IloVisit visit(node, visitName);
_mdl.add( visit.getDelayVar(time) == serviceTime );
_mdl.add( minTime <= visit.getCumulVar(time) <= maxTime);
visit.setPenaltyCost(10000);
visit.setKey(visitName);
_mdl.add(visit);
}
csvVisitReader.end();
}
void RoutingModel::createSkillProfiles(const char* profilePath) {
IloCsvReader skillProfileReader(_env, profilePath);
for( IloCsvReader::LineIterator it(skillProfileReader); it.ok(); ++it) {
IloCsvLine line = *it;
IloInt profileId = line.getIntByHeader("id");
IloInt skill1Level = line.getIntByHeader("Skill1Level");
IloInt skill2Level = line.getIntByHeader("Skill2Level");
IloInt skill3Level = line.getIntByHeader("Skill3Level");
SkillProfile* profile = getSkillProfile(profileId);
assert( 0 != profile );
profile->setSkillLevel(0, skill1Level);
profile->setSkillLevel(1, skill2Level);
profile->setSkillLevel(2, skill3Level);
}
skillProfileReader.end();
}
void RoutingModel::setTechnicianSkillProfiles(const char* techProfilePath) {
// now read the techProfilePath table.
IloCsvReader techProfileReader(_env, techProfilePath);
for (IloCsvReader::LineIterator tpit(techProfileReader); tpit.ok(); ++tpit) {
IloCsvLine line = *tpit;
const char* techName = line.getStringByHeader("name");
IloInt profileId = line.getIntByHeader("TechProfileId");
IloVehicle tech = IloVehicle::Find(_env, techName);
SkillProfile* profile = getSkillProfile(profileId);
if ( 0 != tech.getImpl() && 0 != profile ) {
tech.setObject( (IloAny)profile );
}
}
techProfileReader.end();
}
void RoutingModel::setVisitSkillProfiles(const char* visitProfilePath) {
// now read the techProfilePath table.
IloCsvReader visitProfileReader(_env, visitProfilePath);
for (IloCsvReader::LineIterator vpit(visitProfileReader); vpit.ok(); ++vpit) {
IloCsvLine line = *vpit;
const char* visitName = line.getStringByHeader("name");
IloInt profileId = line.getIntByHeader("VisitProfileId");
IloVisit visit = IloVisit::Find(_env, visitName);
SkillProfile* profile = getSkillProfile(profileId);
if ( 0 != visit.getImpl() && 0 != profile ) {
visit.setObject( (IloAny)profile );
}
}
visitProfileReader.end();
}
/**
* This predicate codes the compatibility relation between a visit and a
* technician. A visit is compatible with a technician if the
* visit profile is subsumed by the technician profile.
* To be defensive, a special case is also considered, when
* the visit has no profile, then all technicians are compatible.
*/
static IloBool AreSkillsCompatible(IloVisit visit, IloVehicle vehicle) {
SkillProfile* visitProfile = (SkillProfile*)visit.getObject();
SkillProfile* techProfile = (SkillProfile*)vehicle.getObject();
if ( 0 != visitProfile ) {
if ( 0 != techProfile ) {
return techProfile->isGreaterThanOrEqual(visitProfile);
} else {
return IloFalse;
}
} else {
return IloTrue;
}
}
void RoutingModel::postCompatibility() {
IloVisitVehicleCompat compat(_env, AreSkillsCompatible);
_mdl.add( IloCompatible(compat, "skill compatibility"));
}
// Solving
class RoutingSolver {
IloModel _mdl;
IloSolver _solver;
IloRoutingSolution _solution;
IloBool findFirstSolution(IloGoal goal);
void greedyImprove(IloNHood nhood, IloGoal subGoal);
void improve(IloGoal subgoal);
public:
RoutingSolver(RoutingModel mdl);
~RoutingSolver() {}
IloRoutingSolution getSolution() const { return _solution; }
void printInformation(const char* heading = 0) const;
void solve();
};
RoutingSolver::RoutingSolver(RoutingModel mdl)
: _mdl(mdl.getModel()), _solver(mdl.getModel()), _solution(mdl.getModel()) {}
// Solving : find first solution
IloBool RoutingSolver::findFirstSolution(IloGoal goal) {
if (!_solver.solve(goal)) {
_solver.error() << "Infeasible Routing Plan" << endl;
return IloFalse;
}
_solution.store(_solver);
return IloTrue;
}
// Improve solution using nhood
void RoutingSolver::greedyImprove(IloNHood nhood, IloGoal subGoal) {
_solver.out() << "Improving solution" << endl;
IloEnv env = _solver.getEnv();
nhood.reset();
IloGoal improve = IloSingleMove(env,
_solution,
nhood,
IloImprove(env),
subGoal);
while (_solver.solve(improve)) {}
}
// Improve solution
void RoutingSolver::improve(IloGoal subGoal) {
IloEnv env = _solver.getEnv();
IloNHood nhood =
IloMakePerformed(env)
+
IloTwoOpt(env)
+ IloOrOpt(env)
+ IloRelocate(env)
+ IloCross(env)
+ IloExchange(env);
greedyImprove(nhood, subGoal);
}
// Display Dispatcher information
void RoutingSolver::printInformation(const char* heading) const {
if ( 0 != heading ) {
_solver.out() << heading << endl;
}
IloDispatcher dispatcher(_solver);
_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::solve() {
IloDispatcher dispatcher(_solver);
IloEnv env = _solver.getEnv();
IloGoal instantiateCost =
IloDichotomize(env, dispatcher.getCostVar(), IloFalse);
IloGoal restoreSolution = IloRestoreSolution(env, _solution);
IloGoal goal =
IloInsertionGenerate(env) && instantiateCost ;
// Solving
if (findFirstSolution(goal)) {
_solver.out() << "First Solution with cost: "
<< _solution.getObjectiveValue() << endl;
improve(instantiateCost);
_solver.solve(restoreSolution && instantiateCost);
printInformation("***Improved Solution***");
}
}
///////////////////////////////////////////////////////////////////////////////
int main(int argc, char * argv[]) {
IloEnv env;
try {
RoutingModel mdl(env);
mdl.parse(argc, argv);
mdl.createModel();
RoutingSolver rsolver(mdl);
rsolver.solve();
} catch(IloException& ex) {
cerr << "Error: " << ex << endl;
}
env.end();
return 0;
}
PREVIOUS
NEXT