The complete program follows. You can also view it online in the file YourDispatcherHome/examples/src/breaks.cpp
.
// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/breaks.cpp
//---------------------------------------------------------------------------
#include <ildispat/ilodispatcher.h>
ILOSTLBEGIN
///////////////////////////////////////////////////////////////////////////////
// Modeling
class RoutingModel {
IloEnv _env;
IloModel _mdl;
void createDimensions();
void createNodes(char* nodeFileName);
void createVehicles(char* vehicleFileName);
void createVisits(char* visitsFileName);
void createVehicleBreaks(char* vehcileBreaksFileName);
void createBreaksRelation(char* breaksRelationFileName);
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) {
createDimensions();
char* nodeFileName;
if ( argc < 4 )
nodeFileName = (char *) "../../../examples/data/break/nodes.csv";
else
nodeFileName = argv[3];
createNodes(nodeFileName);
char* vehiclesFileName;
if ( argc < 2 )
vehiclesFileName = (char *) "../../../examples/data/break/vehicles.csv";
else
vehiclesFileName = argv[1];
createVehicles(vehiclesFileName);
char* visitsFileName;
if ( argc < 3 )
visitsFileName = (char *) "../../../examples/data/break/visits.csv";
else
visitsFileName = argv[2];
createVisits(visitsFileName);
char* vehicleBreaksFileName;
if ( argc < 5 )
vehicleBreaksFileName = (char *) "../../../examples/data/break/vehicleBreaks.csv";
else
vehicleBreaksFileName = argv[4];
createVehicleBreaks(vehicleBreaksFileName);
char* breaksRelationFileName;
if ( argc < 6 )
breaksRelationFileName = (char *) "../../../examples/data/break/breaksRelation.csv";
else
breaksRelationFileName = argv[5];
createBreaksRelation(breaksRelationFileName);
}
// Create dimensions
void RoutingModel::createDimensions() {
IloDimension2 time(_env, IloEuclidean, "Time");
time.setKey("Time");
_mdl.add(time);
IloDimension2 length(_env, IloEuclidean, IloFalse, "Length");
length.setKey("Length");
_mdl.add(length);
IloDimension1 weight(_env, "Weight");
weight.setKey("Weight");
_mdl.add(weight);
}
// Create nodes
void RoutingModel::createNodes(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(char* vehicleFileName) {
IloDimension1 weight = IloDimension1::Find(_env, "Weight");
IloDimension2 time = IloDimension2::Find(_env, "Time");
IloDimension2 length = IloDimension2::Find(_env, "Length");
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(length, 1.0);
vehicle.setSpeed(time, 30.0);
vehicle.setCapacity(weight, capacity);
vehicle.setKey(name);
_mdl.add(vehicle);
++it;
}
csvVehicleReader.end();
}
// Create visits
void RoutingModel::createVisits(char* visitsFileName) {
IloDimension1 weight = IloDimension1::Find(_env, "Weight");
IloDimension2 time = IloDimension2::Find(_env, "Time");
IloCsvReader csvVisitReader(_env,visitsFileName);
IloCsvReader::LineIterator it(csvVisitReader);
while ( it.ok() ) {
IloCsvLine line = *it;
//read visit data from files
char* pickupVisitName = line.getStringByHeader("pickup");
char* pickupNodeName = line.getStringByHeader("pickupNode");
char* deliveryVisitName = line.getStringByHeader("delivery");
char* deliveryNodeName = line.getStringByHeader("deliveryNode");
IloNum quantity = line.getFloatByHeader("quantity");
IloNum pickupMinTime = line.getFloatByHeader("pickupMinTime");
IloNum pickupMaxTime = line.getFloatByHeader("pickupMaxTime");
IloNum deliveryMinTime = line.getFloatByHeader("deliveryMinTime");
IloNum deliveryMaxTime = line.getFloatByHeader("deliveryMaxTime");
IloNum dropTime = line.getFloatByHeader("dropTime");
IloNum pickupTime = line.getFloatByHeader("pickupTime");
IloNode pickupNode = IloNode::Find(_env, pickupNodeName);
IloNode deliveryNode = IloNode::Find(_env, deliveryNodeName);
//create and add pickup and delivery visits
IloVisit pickup(pickupNode, pickupVisitName);
_mdl.add(pickup.getDelayVar(time) == pickupTime);
_mdl.add(pickup.getTransitVar(weight) == quantity);
_mdl.add(pickupMinTime <= pickup.getCumulVar(time) <= pickupMaxTime);
_mdl.add(pickup);
IloVisit delivery(deliveryNode, deliveryVisitName);
_mdl.add(delivery.getDelayVar(time) == dropTime);
_mdl.add(delivery.getTransitVar(weight) == -quantity);
_mdl.add(deliveryMinTime <= delivery.getCumulVar(time) <= deliveryMaxTime);
_mdl.add(delivery);
//add pickup and delivery order constraint
_mdl.add(IloOrderedVisitPair(_env, pickup, delivery));
++it;
}
csvVisitReader.end();
}
//create vehicle breaks
void RoutingModel::createVehicleBreaks(char* vehicleBreaksFileName) {
IloDimension2 time = IloDimension2::Find(_env, "Time");
IloCsvReader csvVehicleBreaksReader(_env, vehicleBreaksFileName);
IloCsvReader::LineIterator it(csvVehicleBreaksReader);
while ( it.ok() ) {
IloCsvLine line = *it;
char* vehicleName = line.getStringByHeader("vehicle");
char* breakName = line.getStringByHeader("breakName");
IloNum startLB = line.getFloatByHeader("startLB");
IloNum startUB = line.getFloatByHeader("startUB");
IloNum durationLB = line.getFloatByHeader("durationLB");
IloNum durationUB = line.getFloatByHeader("durationUB");
IloInt nbDays = line.getIntByHeader("nbDays");
IloVehicle vehicle = IloVehicle::Find(_env, vehicleName);
for ( IloInt i = 0; i < nbDays; i++ ) {
char name[100];
IloNumVar breakStart(_env,(i * 24) + startLB, (i * 24) + startUB);
IloNumVar breakDuration(_env, durationLB, durationUB);
sprintf(name,"%s-day%ld",breakName,i + 1);
IloVehicleBreakCon breaks(vehicle, time, breakStart, breakDuration, name);
breaks.setKey(name);
_mdl.add(breaks);
}
++it;
}
csvVehicleBreaksReader.end();
}
//add breaks constraints
void RoutingModel::createBreaksRelation(char* breaksRelationFileName) {
IloCsvReader csvBreaksRelationReader(_env, breaksRelationFileName);
IloCsvReader::LineIterator it(csvBreaksRelationReader);
while ( it.ok() ) {
IloCsvLine line = *it;
char* break1 = line.getStringByHeader("break1");
char* break2 = line.getStringByHeader("break2");
IloNum totalDuration = line.getFloatByHeader("totalDuration");
char* constraint = line.getStringByHeader("constraint");
IloNumVar breakDuration(_env);
IloVehicleBreakCon vehicleBreakCon1 = IloVehicleBreakCon::Find(_env, break1);
if ( strlen(break2) != 0 ) {
IloVehicleBreakCon vehicleBreakCon2 = IloVehicleBreakCon::Find(_env, break2);
_mdl.add(breakDuration == vehicleBreakCon1.getDurationVar()
+ vehicleBreakCon2.getDurationVar());
}
else {
_mdl.add(breakDuration == vehicleBreakCon1.getStartVar()
+ vehicleBreakCon1.getDurationVar());
}
if ( strcmp(constraint,"equal") == 0 )
_mdl.add(breakDuration == totalDuration);
if ( strcmp(constraint,"at least") == 0 )
_mdl.add(breakDuration >= totalDuration);
if ( strcmp(constraint,"at most") == 0 )
_mdl.add(breakDuration <= totalDuration);
++it;
}
csvBreaksRelationReader.end();
}
///////////////////////////////////////////////////////////////////////////////
// Solving
class RoutingSolver {
IloModel _mdl;
IloEnv _env;
IloSolver _solver;
IloRoutingSolution _solution;
IloRoutingSolution _breaks;
IloBool findFirstSolution(IloGoal goal);
void greedyImprove(IloNHood nhood, IloGoal subGoal);
void improve(IloGoal subgoal);
void addBreaks();
public:
RoutingSolver(RoutingModel mdl);
~RoutingSolver() {
}
IloRoutingSolution getSolution() const {
return _solution;
}
void printInformation() const;
void solve();
};
RoutingSolver::RoutingSolver(RoutingModel mdl):_mdl(mdl.getModel()),
_env(mdl.getEnv()),
_solver(mdl.getModel()),
_solution(mdl.getModel()),
_breaks(mdl.getEnv()) {
}
// Solving : find first solution
IloBool RoutingSolver::findFirstSolution(IloGoal goal) {
if ( !_solver.solve(goal) ) {
_solver.error() << "Infeasible Routing Plan" << endl;
return IloFalse;
}
IloDispatcher dispatcher(_solver);
_solver.out() << dispatcher.getTotalCost() << endl;
_solution.store(_solver);
_breaks.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) )
_breaks.store(_solver);
}
// Improve solution
void RoutingSolver::improve(IloGoal subGoal) {
IloNHood nhood = IloTwoOpt(_env)
+ IloOrOpt(_env)
+ IloRelocate(_env)
+ IloCross(_env)
+ IloExchange(_env);
greedyImprove(nhood,subGoal);
}
//add breaks to _breaks routing solution
void RoutingSolver::addBreaks() {
IloVehicleBreakConIterator it(_mdl);
while ( it.ok() ) {
_breaks.add(*it);
++it;
}
}
// Display Dispatcher information
void RoutingSolver::printInformation() const {
IloDispatcher dispatcher(_solver);
_solver.printInformation();
dispatcher.printInformation();
_solver.out() << "===============" << endl
<< "Cost : " << dispatcher.getTotalCost() << endl
<< "Number of vehicles used : " << dispatcher.getNumberOfVehiclesUsed() << endl
<< "Solution : " << endl
<< IloVerbose(dispatcher) << endl;
}
// Solving
void RoutingSolver::solve() {
IloDispatcher dispatcher(_solver);
//add breaks to _breaks routing solution
addBreaks();
// Subgoals
//The IloInstantiateVehicleBreaks goal uses a precision of 1 minutes
//and treats all vehicles independently in the instantiation of vehicle breaks
IloGoal instantiateBreaks = IloLimitSearch(_env,
IloInstantiateVehicleBreaks(_env, 1.0/60.0, IloTrue),
IloFailLimit(_env, 100));
IloGoal instantiateCost = IloDichotomize(_env,
dispatcher.getCostVar(),
IloFalse);
IloGoal subGoal = instantiateBreaks && instantiateCost;
IloGoal goal = IloSavingsGenerate(_env, instantiateBreaks) && instantiateCost;
IloGoal restoreSolution = IloRestoreSolution(_env, _solution) && IloRestoreSolution(_env, _breaks);
// Solving
if ( findFirstSolution(goal) ) {
improve(subGoal);
_solver.solve(restoreSolution);
}
}
///////////////////////////////////////////////////////////////////////////////
int main(int argc,char* argv[]) {
IloEnv env;
try {
RoutingModel mdl(env,argc,argv);
RoutingSolver solver(mdl);
solver.solve();
solver.printInformation();
}
catch ( IloException& ex ) {
cerr << "Error: " << ex << endl;
}
env.end();
return 0;
}