After you have found a first solution, you create the neighborhoods you will use in the solution improvement phase. The central idea of the neighborhood is to define a set of solution changes, or deltas, that represent alternative moves that can be taken. Neighborhoods are classified in two groups: those that modify only one route are known as intra-route neighborhoods; those that make changes between routes are known as inter-route neighborhoods. Inter-route neighborhoods can sometimes be used to improve a single route and thus become--strictly speaking--intra-route neighborhoods themselves.

Add the following code after the comment //Create the neighborhoods

void RoutingSolver::improveWithNhood() {
  IloNHood nhood =  IloTwoOpt(_env)
                  + IloOrOpt(_env)
                  + IloRelocate(_env)
                  + IloCross(_env)
                  + IloExchange(_env);
  _solver.out() << "Improving solution" << endl;

Now, you use iterative improvement techniques to modify the first solution using the neighborhoods you just created. Local search uses search heuristics to guide how the alternative moves in a neighborhood are taken. The search is iterative in that it tries a series of moves in order to decrease the cost of the solution found.

In this lesson, Dispatcher uses the first accept search heuristic. First accept search takes the first legal cost decreasing move encountered. The search continues to take such moves until the neighborhood contains no legal cost-reducing moves. This point is usually termed a local minimum. The word local is used to signify that this point is not guaranteed--and, in fact, is not usually--a global minimum. This method accepts any legal improving move and so is not too expensive in terms of computational cost. Thus, it is preferred when the problem is very large or an optimized solution is required as quickly as possible.

Add the following code after the comment //Improve the solution

  IloGoal improve = IloSingleMove(_env,
                                  _solution,
                                  nhood,
                                  IloImprove(_env),
                                  _instantiateCost);
  while (_solver.solve(improve)) {
  }

You use the function IloSingleMove to return a goal that makes a single local move as defined by a neighborhood and a search heuristic. The first legal move reducing costs results. The goal scans the neighborhood nhood using _solution as the current solution. The function IloSingleMove will first see if it can make a legal, cost-decreasing move using the neighborhood IloTwoOpt. If it cannot, it tries IloOrOpt, and so on. The search heuristic IloImprove is used to filter moves by implementing a greedy search heuristic. It accepts only new routing plans that strictly decrease the cost and, thus, allows only improvements in the objective. The subgoal _instantiateCost is executed after the deltas from the neighborhood are applied to the current solution.

If a successful move can be found, the goal succeeds. The constrained variables are in the state corresponding to the application of the move. This new state is saved to _solution before the goal succeeds. If no successful move can be found, the goal fails, and _solution is left unchanged. You then use the _restoreSolution goal you created in the RoutingSolver constructor to restore this last solution.

Add the following code after the comment //Restore the last solution

    _solver.solve(_restoreSolution);
}