The solving section of this example introduces metaheuristics. In previous lessons, heuristics terminated when no cost-reducing move could be found at a local minimum. Metaheuristics allow the search to continue by allowing neighborhood moves that degrade the current solution and allow the search to move from the current position. This degradation must be carefully controlled, however, to prevent the search from moving to very poor solutions. This control is provided by various types of metaheuristics. The type used in this lesson is based on guided local search (GLS).

Guided local search works by making a series of greedy searches, each to a local minimum. However, it reduces a different cost function from the original. If the original cost function is represented by c, then guided local search attempts to reduce the cost c+wp, where p is a penalty term that is adjusted every time a local minimum is reached, and w is a constant. So, in essence, guided local search tries to minimize a combination of the true cost and a penalty term. The weighting constant w is an important search parameter that determines how important the penalty term is with respect to the true cost.

Guided local search is constructed so that the penalty term is higher when the search moves to solutions that resemble previous ones. This is done by recording certain arcs as "bad" each time a local minimum is reached. When these arcs appear in a solution, the penalty term is increased. Guided local search determines which arcs are bad based upon the cost of the arc in the solution and how often that arc has previously appeared at local minima.

The first step in the solving section is to create the RoutingSolver function.

The function improveWithFastGLS uses the metaheuristic IloDispatcherGLS to get out of the local minimum solution to find a better one.

Two new functions appear in the class RoutingSolver for this lesson: modifyFilterLevelAndRestore and restoreSolution.

Add the following code after the comment
//Modify filter level and restore solution.

void RoutingSolver::modifyFilterLevelAndRestore() {
  _dispatcher.setFilterLevel(IlcMedium);
  IloNum cost = _solution.getObjectiveValue();
  _solver.solve(_restoreSolution
      && IloSetMax(_env, _dispatcher.getCostVar(), cost));
  _dispatcher.setFilterLevel(IlcLow);
}

This function changes the filter level of the propagation before restoring the solution. IlcMedium is the highest level of propagation, and takes considerably longer than IlcLow. This function is called to have better propagation of the cumul variables and to have a better display of the solution.

This function is called by main to restore the solution after modifyGraphArcCost has been called to modify the original arc cost data.

The next function, improveWithFastGLS, uses the metaheuristic IloDispatcherGLS to get out of the local minimum solution to find a better one.

IloDispatcherGLS tries to penalize "bad" arcs--arcs with a high cost. However, if an arc has been penalized a number of times, the importance of cost reduces. This is due to the fact that if an arc has been penalized a large number of times and is still in the solution, there may be no better arc with which to replace it and it is probably best to start looking elsewhere to place penalties.

The functions IloCouple and IloDecouple connect and disconnect a neighborhood to a metaheuristic. The neighborhood must be coupled to an instance of IloDispatcherGLS, otherwise an exception is thrown.

Locate the following code after the comment //The display paths function.

void RoutingSolver::displayPaths(IloDispatcherGraph graph) {
  _env.out() << "Paths" << endl;
  for (IloIterator<IloVehicle> iter1(_env); iter1.ok(); ++iter1) {
    IloVehicle vehicle = *iter1;
    IloVisit visit1 = vehicle.getFirstVisit();
    for (IloDispatcher::RouteIterator iter2(_dispatcher, vehicle);
         iter2.ok();
         ++iter2) {
      IloVisit visit2 = *iter2;
      if (visit1 != visit2) {
        _env.out() << visit1.getName() << " {"
                  <<  graph.getLocation(visit1.getStartNode())
                                  .getIndex();
        for (IloDispatcherGraph::PathIterator iter3(graph,
                                                    visit1.getEndNode(),
                                                    visit2.getStartNode(),
                                                    vehicle);
             iter3.ok();
             ++iter3) {
          _env.out() << " -> " << (*iter3).getIndex();
        }
        _env.out() << "} -> ";
        visit1 = visit2;
      }
    }
    _env.out() << vehicle.getLastVisit().getName() << endl;
  }
  _env.out() << endl;
}

The function displayPaths is used to display the route of each vehicle following the actual paths on the road network. An instance of IloIterator<IloVehicle> is used to iterate over the vehicles, and an instance of IloDispatcher::RouteIterator is used to iterate over the visits of each vehicle. IloDispatcherGraph::PathIterator is used to iterate over the nodes present on the shortest path between visits.

Finally, main calls these functions.

Add the following code after the comment //Add the main function

int main(int argc, char * argv[]) {
  IloEnv env;
  try {
    RoutingModel mdl(env, argc, argv);
    RoutingSolver solver(mdl);
    if (solver.findFirstSolution()) {
      solver.printInformation();
      solver.improveWithNHood(250);
      solver.modifyFilterLevelAndRestore();
      solver.printInformation();
      solver.displayPaths(mdl.getGraph());
      mdl.modifyGraphArcCost();
      solver.restoreSolution();
      solver.improveWithNHood(50);
      solver.modifyFilterLevelAndRestore();
      solver.printInformation();
      solver.displayPaths(mdl.getGraph());
    }
  } catch(IloException& ex) {
    cerr << "Error: " << ex << endl;
  }
  env.end();
  return 0;
}

Note that three sets of results are displayed: a set before and a set after the first modifyFilterLevelAndRestore function is called to change the propagation to IlcMedium, and one set after modifyGraphArcCost is called, increasing the cost of certain arcs.

First Solution Information

The first solution phase, before improveWithNHood(250) and modifyFilterLevelAndRestore have been called, finds a solution using 3 vehicles with a cost of 8100.14 units:

8100.14
Number of fails               : 218
Number of choice points       : 1048
Number of variables           : 1550
Number of constraints         : 197
Reversible stack (bytes)      : 132684
Solver heap (bytes)           : 715840
Solver global heap (bytes)    : 83476
And stack (bytes)             : 20124
Or stack (bytes)              : 44244
Search Stack (bytes)          : 4044
Constraint queue (bytes)      : 11160
Total memory used (bytes)     : 1011572
Elapsed time since creation   : 1.602
Number of nodes               : 52
Number of visits              : 55
Number of vehicles            : 5
Number of dimensions          : 3
Number of accepted moves      : 0
===============
Cost         : 8100.14
Number of vehicles used : 3

Improved Solution Information

The first solution is improved with improveWithNHood(250) and modifyFilterLevelAndRestore:

Improving solution
Improving with first-accept GLS
---
Cost = 7781.68
Cost = 7712.67
Cost = 7616.17
Cost = 7592.99
---

The solution improvement phase continues lowering the cost until it finds a solution using 3 vehicles with a cost of 7413.03 units:

---
Cost = 7546.96
Cost = 7546.96
---

Number of fails               : 0
Number of choice points       : 0
Number of variables           : 2086
Number of constraints         : 601
Reversible stack (bytes)      : 221124
Solver heap (bytes)           : 1636420
Solver global heap (bytes)    : 99556
And stack (bytes)             : 20124
Or stack (bytes)              : 44244
Search Stack (bytes)          : 4044
Constraint queue (bytes)      : 18172
Total memory used (bytes)     : 2043684
Elapsed time since creation   : 0.13
Number of nodes               : 52
Number of visits              : 55
Number of vehicles            : 5
Number of dimensions          : 3
Number of accepted moves      : 193
===============
Cost         : 7413.03
Number of vehicles used : 3

Solution Information with Modified Arc Costs

Now the problem is solved a second time. The cost is modified with modifyGraphArcCost and then reoptimized with improveWithNHood(50). Note that the modified cost is large until the solution is improved.

Modified cost: 8311.26
Improving solution
Improving with first-accept GLS
---
Cost = 7506.89
Cost = 7482.83
---

This solution improvement phase continues lowering the cost until it finds a solution using 3 vehicles with a cost of 7459.55 units:

Cost = 7626.4

Number of fails               : 0
Number of choice points       : 0
Number of variables           : 2086
Number of constraints         : 601
Reversible stack (bytes)      : 221124
Solver heap (bytes)           : 1636420
Solver global heap (bytes)    : 99556
And stack (bytes)             : 20124
Or stack (bytes)              : 44244
Search Stack (bytes)          : 4044
Constraint queue (bytes)      : 18172
Total memory used (bytes)     : 2043684
Elapsed time since creation   : 0.12
Number of nodes               : 52
Number of visits              : 55
Number of vehicles            : 5
Number of dimensions          : 3
Number of accepted moves      : 230
===============
Cost         : 7459.55
Number of vehicles used : 3