Solve

IBM ILOG Dispatcher User's Manual > The Basics > IBM ILOG Dispatcher Concepts > Solve

Solve

Dispatcher uses a two-phase approach for solving routing problems. The first phase consists of generating a solution that satisfies the problem. In phase two, you improve this first solution using local search.

Solving a routing problem can be translated into the simple question: "Who does what?" In the case of the routing problem, this question can be answered by giving the list of visits performed by each vehicle. This is a routing plan, which can be represented and accessed in several ways:

through an instance of the class IloModel, which contains all the objects of the routing plan, such as visits and vehicles;
through an instance of the class IloDispatcher, to access or modify the values of the model's variables during or after a search;
through an instance of the class IloRoutingSolution, to access the routing plan resulting from a search and stored in a solution.

To allow dynamic problem solving, optimization in Dispatcher is based on first generating a solution, and then improving it using local search methods. As its name implies, local search acts by locally modifying a given solution to decrease the cost using neighborhoods. The central idea of a neighborhood is to define a set of solution changes that represent alternative moves that can be taken. In the case of vehicle routing, this translates into modifying the next-variables of some visit variables.

To achieve this in Dispatcher, a double representation of the problem is used. A passive representation based on instances of IloRoutingSolution, depicting the last valid solution encountered, is associated with each decision variable in the problem--the next-vars, prev-vars and performed-vars. The saved values of the passive representation can be accessed through member functions such as IloRoutingSolution::getNext(IloVisit), IloRoutingSolution::getPrev(IloVisit) and IloRoutingSolution::isPerformed(IloVisit).

An active representation of the problem is used to search for a new, modified solution using neighborhoods.

Thus, the process for solving a problem using Dispatcher is:

Generate, create, or input a first solution.
Store the first solution in an instance of IloRoutingSolution.
Generate a new, modified, solution using a neighborhood.
Set the decision variables affected by the move operator to their new values.
Set the remaining decision variables to their saved values.
Propagate the constraints.
If the propagation fails, the new solution is refused. Otherwise, the solution is accepted and the decision variables of the new solution are saved.
The domains of variables are restored to their initial values on backtracking.

Generating a first solution

In a normal Dispatcher application, you would generate a first solution using one of Dispatcher's predefined first solution generation functions. For more information, see Chapter 3, Solving a Vehicle Routing Problem and ïtò^ A Predefined First Solution Heuristics. You could also load a first solution from a file or write your own first solution generation method. For more information, see Chapter 17, Developing Your Own First Solution Heuristics.

To demonstrate the concepts involved in local search, imagine that you have a simple routing problem with one vehicle, one depot, and three customer visits.

IloEnv env;
IloModel mdl(env);
IloNode depot(env, 0.0, 0.0);
IloNode n1(env, 1.0, 1.0);
IloNode n2(env, 1.0, 0.0);
IloNode n3(env, 0.0, 1.0);
IloVisit visit1(n1, "Visit 1");
IloVisit visit2(n2, "Visit 2");
IloVisit visit3(n3, "Visit 3");
mdl.add(visit1);
mdl.add(visit2);
mdl.add(visit3);
IloVisit first(depot, "Start"), last(depot, "End");
IloVehicle w(first, last);
mdl.add(w);

You set the cost of the vehicle to be proportional to the distance traveled length.

IloDimension2 length(env, IloEuclidean);
w.setCost(length, 1);

You input a first solution where the vehicle starts at the depot, makes visit 1, then visit 2, then visit 3, and finally returns to the depot. The cost of this routing plan would be 4.83 (). The following figure shows this routing plan.

Figure 1.1 First Routing Solution Created from Scratch

Improving the solution using local search

You then use local search to modify the next-variables of some variables and search for a routing plan with a lower cost. To do this, you use Dispatcher's predefined neighborhoods and search heuristics to guide how the alternative moves in a neighborhood are taken. For more information, see Chapter 3, Solving a Vehicle Routing Problem and ïtò^ B Predefined Neighborhoods.

The improved solution has a cost of 4. The following figure shows this routing plan.

Figure 1.2 Solution Improved with Local Search

PREVIOUS NEXT