IBM ILOG Dispatcher User's Manual > The Basics > Solving a Vehicle Routing Problem > Complete Program

The complete VRP program follows. You can also view it online in the YourDispatcherHome/examples/src/vrp.cpp file.

// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/vrp.cpp
//---------------------------------------------------------------------------

#include <ildispat/ilodispatcher.h>

ILOSTLBEGIN
///////////////////////////////////////////////////////////////////////////////
// Modeling

class RoutingModel {
  IloEnv              _env;
  IloModel            _mdl;
  IloDimension2       _time;
  IloDimension2       _distance;
  IloDimension1       _weight;

  void addDimensions();
  void createIloNodes(const char* nodeFileName);
  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; }
};

RoutingModel::RoutingModel( IloEnv env,
                            int argc,
                            char* argv[]):
  _env(env), _mdl(env) {
  addDimensions();

  //create IloNodes
  char * nodeFileName;
  if(argc < 2)  nodeFileName =
       (char*) "../../../examples/data/vrp20/vrp20nodes.csv";
  else          nodeFileName = argv[1];
  createIloNodes(nodeFileName);

  //create vehicles
  char * vehiclesFileName;
  if(argc < 3)  vehiclesFileName =
       (char*) "../../../examples/data/vrp20/vrp20vehicles.csv";
  else          vehiclesFileName = argv[2];
  createVehicles(vehiclesFileName);

  //create visits
  char * visitsFileName;
  if(argc < 4)  visitsFileName =
       (char*)  "../../../examples/data/vrp20/vrp20visits.csv";
  else          visitsFileName = argv[3];
  createVisits(visitsFileName);
}

// create distance functions for dimensions, add dimensions to model
void RoutingModel::addDimensions() {

  _weight =IloDimension1 (_env, "weight");
  _mdl.add(_weight);

  _time  =IloDimension2 (_env, IloEuclidean, "time");
  _mdl.add(_time);

  _distance =IloDimension2 (_env, IloEuclidean, "distance");
  _mdl.add(_distance);
}

//create IloNodes
void RoutingModel::createIloNodes(const 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(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);
    _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(_distance, 1.0);

    vehicle.setCapacity(_weight, capacity);

    _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");
    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);

    ++it;
  }
  csvVisitReader.end();
}

///////////////////////////////////////////////////////////////////////////////
// Solving
class RoutingSolver {
  IloEnv              _env;
  IloModel            _mdl;
  IloSolver           _solver;
  IloDispatcher       _dispatcher;
  IloRoutingSolution  _solution;
  IloGoal             _instantiateCost;
  IloGoal             _restoreSolution;
  IloGoal             _goal;

public:
  RoutingSolver(RoutingModel mdl);
  ~RoutingSolver() {}
  IloBool findFirstSolution();
  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);

    _goal = IloSavingsGenerate(_env) && _instantiateCost;
  }

// Solving : find first solution
IloBool RoutingSolver::findFirstSolution() {
  if (!_solver.solve(_goal)) {
    _solver.error() << "Infeasible Routing Plan" << endl;
    return IloFalse;
  }

  _solution.store(_solver);
  return IloTrue;
}

//Improve solution using nhood
void RoutingSolver::improveWithNhood() {
  IloNHood nhood =  IloTwoOpt(_env)
                  + IloOrOpt(_env)
                  + IloRelocate(_env)
                  + IloCross(_env)
                  + IloExchange(_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);
    if (solver.findFirstSolution()) {
      solver.printInformation("***First Solution***");
      solver.improveWithNhood();
      solver.printInformation("***Improved Solution***");
    }
  } catch(IloException& ex) {
    cerr << "Error: " << ex << endl;
  }
  env.end();
  return 0;
}