Now you create the submodel that is used to order the customer visits so that they can be inserted into the first solution along with the return visits. This submodel is a version of a basic routing problem, the Traveling Salesperson Problem (TSP). The description of this problem is fairly simple: a set of locations are given, the goal is to build a closed route (closed in the sense that it ends where it begins) that goes through each of these locations exactly once, while minimizing the cost. Unlike a standard VRP, a TSP uses only one vehicle.

The TSP submodel takes the unordered array of customer visits from the VRP model and a single vehicle and finds a solution. You then iterate over the route of the vehicle and create the array of ordered visits. These ordered visits can then be inserted in the first solution of the VRP model. If you had just inserted the visits from the unordered visit array into the first solution, this would have likely resulted in a more costly first solution. Inserting the visits that have already been ordered into the first solution will create a lower cost first solution.

Here is the heuristic used in the submodel to create the ordered array of customer visits:

First, you define the orderVisits function to take two parameters: an instance of the unordered visit array and an instance of IloDispatcherGraph. Then, you create the submodel tspModel using an instance of IloModel. With Concert Technology, you can create more than one model in a given environment.

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

void RoutingSolver::orderVisits(IloVisitArray unorderedVisitArray,
                                IloDispatcherGraph graph) {
  IloModel tspModel(_env);

Next, you add the dimension and vehicle to the submodel. You create the first and last visits the vehicle will make--these two visits are to the same location, the first visit in the array of unordered customer visits. You create the vehicle and add it to the TSP submodel. Then you create the distance dimension using a distance function that is the shortest path in distance computed from the road network graph. You set the cost of the vehicle to be directly proportional to the distance dimension dim and add the dimension dim to the TSP submodel.

Add the following code after the comment
//Add the dimension and vehicle to the submodel

  IloInt nbOfVisits = unorderedVisitArray.getSize();
  IloVisit first(unorderedVisitArray[0].getNode(), "first");
  IloVisit last(unorderedVisitArray[0].getNode(), "last");
  IloVehicle vehicle(first, last, "TSP");
  tspModel.add(vehicle);
  IloDistance dist =  IloGraphDistance (graph);
  IloDimension2 dim(_env, dist, IloFalse);
  vehicle.setCost(dim, 1.0);
  tspModel.add(dim);
 

You add the visits to the TSP submodel by looping through unorderedVisitArray and adding each visit to the model. Since you are only concerned with generating an order based on location, you do not add any constraints on visit quantity.

Add the following code after the comment
//Add the customer visits to the submodel

  for (IloInt i = 1; i < nbOfVisits; i++)
    tspModel.add(unorderedVisitArray[i]);
 

As in a standard VRP, you create an instance of IloSolver, an instance of IloDispatcher, and a goal to instantiate cost.

Add the following code after the comment
//Create the solver, dispatcher, and cost goal in the submodel

  IloSolver solver(tspModel);
  IloDispatcher dispatcher(solver);
  IloGoal instCost = IloDichotomize(_env, dispatcher.getCostVar(), IloFalse);
  solver.out() << "Producing insertion order" << endl;

Add the following code after the comment
//Find the first solution in the submodel and store it

  solver.solve(IloNearestAdditionGenerate(_env) && instCost);
  IloRoutingSolution rsolution(tspModel);
  rsolution.store(solver);

Add the following code after the comment
//Improve the first solution in the submodel

  IloNHood nhood = IloTwoOpt(_env);
  IloMetaHeuristic improve = IloImprove(_env);
  IloGoal move = IloSingleMove(_env, rsolution, nhood, improve, instCost);
  while (solver.solve(move)) {
    }

Now, you create _orderedVisitArray, an instance of IloVisitArray. You iterate over the route of the vehicle, adding visits from the route to _orderedVisitArray.

Add the following code after the comment
//Create the array of ordered customer visits in the submodel

  _orderedVisitArray = IloVisitArray (_env, nbOfVisits);
  IloRoutingSolution::RouteIterator rit(rsolution, vehicle);
  ++rit;
  _orderedVisitArray[0] = unorderedVisitArray[0];
  for (IloInt k = 1; k < nbOfVisits; ++k, ++rit)
    _orderedVisitArray[k] = *rit;

Finally, you use the member functions IloNHood::end, IloSolver::end, and IloRoutingSolution::end to deallocate the memory used by these objects in the submodel.

Add the following code after the comment //End the objects in the submodel

  nhood.end();
  solver.end();
  rsolution.end();
}