IBM ILOG Dispatcher User's Manual > Transportation Industry Solutions > Adding Vehicle Breaks > Complete Program

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;
}