IBM ILOG Dispatcher User's Manual > The Basics > Minimizing the Number of Vehicles > Solve

Solve

INDEX Gray bullet PREVIOUS NEXT

Because the standard approach to vehicle routing problems described in Lesson 3 Solving a Vehicle Routing Problem can be inefficient when tackling the problem of minimizing the number of vehicles used to solve a VRP, this lesson presents another method, based on the use of instances of IloRoutingSolution and dynamic insertion of visits.

Here is a short description of the proposed heuristic:

  1. Find a first solution.
  2. Save the current solution in _solution, an instance of IloRoutingSolution.
  3. Improve the first solution using neighborhoods.
  4. Close any empty vehicles so that they cannot take part in any solution.
  5. Let v be the non-empty vehicle with the fewest visits. Empty v by constraining the visits assigned to it so that they must be performed by some other vehicle, disabling v, and finding a new solution. (There will always be a solution if the visits have a finite penalty cost and can therefore be unperformed.)
  6. Improve the new solution, minimizing its cost.
  7. If there are no unperformed visits, go to 2.
  8. If there are unperformed visits, enable v, and restore solution.
  9. The solution with the minimal number of vehicles is solution.

As in Chapter 3, Solving a Vehicle Routing Problem, you create the RoutingSolver class, which is used to solve the vehicle routing problem.

© Copyright IBM Corp. 1987, 2009. Legal terms. PREVIOUS NEXT