The goal that builds the route for a given vehicle is the central goal of the search. Given the addition heuristic approach described in the preceding section, the goal iteratively chooses visits and tests to see if the selected visit can extend the current partial route.

Visits are chosen in order to minimize the cost increase of the current partial route. This is done by iterating on the possible successors of the last visit of the current partial route. The heuristic selects the cheapest visit that is not a first or a last visit and the vehicle variable that contains the current vehicle.

IloVisit ChooseCheapestVisit(IloDispatcher dispatcher,
                             IloVehicle vehicle,
                             IloVisit visit) {
  IloInt vehIndex = dispatcher.getIndex(vehicle);
  IlcIntVar nextVar = dispatcher.getNextVar(visit);
  IloVisit bestVisit;
  IloNum bestCost = IloInfinity;
  for (IlcIntExpIterator iter(nextVar); iter.ok(); ++iter) {
    IloVisit v = dispatcher.getVisit(*iter);
    IloNum cost = dispatcher.getCost(visit, v, vehicle);
    IlcIntVar vehicleVar = dispatcher.getVehicleVar(v);
    if (cost < bestCost
        && !v.isFirstVisit()
        && !v.isLastVisit()
        && vehicleVar.isInDomain(vehIndex)) {
      bestVisit = v;
      bestCost = cost;
    }
  }
  return bestVisit;
}

An internal search tests if the visit can extend the current partial route by checking if the route can be closed with the addition of the newly selected visit. The goal used for this search constrains the selected visit to directly follow the last visit of the current route, using IloDispatcher::setNext(IloVisit, IloVisit), and closes the route using IloGenerateRoute(IloSolver, IloVehicle). Note that it is better to limit the search when closing the route to avoid spending too much time proving that the route cannot be closed.

ILCGOAL3(AddArcTestGoal,
         IloVisit&, visit1,
         IloVisit&, visit2,
         IloVehicle&, vehicle) {
  IloSolver solver =  getSolver();
  IloDispatcher dispatcher(solver);
  dispatcher.setNext(visit1, visit2);
  return IloLimitSearch(solver,
                        IloGenerateRoute(solver, vehicle),
                        IloFailLimit(solver, 100));
}

If the selected visit can extend the route, it is constrained to do so, using IloDispatcher::setNext(IloVisit, IloVisit), and becomes the new last visit of the current partial route. The iteration ends when no more visits can be found to extend the partial route.

Here is the code for generating a route:

ILCGOAL1(Ilc_VehicleGenerateSolution, IloVehicle, vehicle) {
  IloSolver solver = getSolver();
  IloDispatcher dispatcher(solver);
  IloVisit visit1 = vehicle.getFirstVisit();
  IloVisit visit2 = ChooseCheapestVisit(dispatcher, vehicle, visit1);
  IlcGoal testGoal = AddArcTestGoal(solver, visit1, visit2, vehicle);
  while (visit2.getImpl() != 0) {
    if (solver.solve(testGoal, IloTrue)) {
      dispatcher.setNext(visit1, visit2);
      visit1 = visit2;
    } else {
      solver.add(dispatcher.getNextVar(visit1) != dispatcher.getIndex(visit2));
    }
    visit2 = ChooseCheapestVisit(dispatcher, vehicle, visit1);
  }
  solver.solve(IloGenerateRoute(solver, vehicle));
  return 0;
}