In Dispatcher, side constraints such as capacity, time windows, and deadlines are implemented by associating one floating-point constrained variable per dimension with each visit. These cumulative variables represent the accumulation of the dimension from the beginning of the vehicle route to the visit. Constraints can then be placed on these variables. They can be accessed through the member function IloVisit::getCumulVar.

While the cumulative variable is accessed through the visit, it is also linked to a specific vehicle--the accumulation of a dimension, such as weight, is accumulated as one vehicle makes visits along its route.

For example, if a truck starts empty from the depot and performs 4 visits, where it collects goods of weight 4, 7, 8, and 3, respectively, the cumulative variable associated to the dimension weight at the fourth visit is equal to 4+7+8 = 19 (the cumulative variable corresponds to the quantity in the truck upon arrival at the visit). The constraint placed on this cumulative variable is that it must be always less than or equal to the capacity of the vehicle.

Dispatcher also uses transit variables to model side constraints. The transit variable associated with a visit is a floating-point constrained variable which represents the change in the cumulative variable between that visit and the following visit. It can be accessed through the member function IloVisit::getTransitVar.

Cumulative and transit variables for dimensions--instances of both IloDimension1 and IloDimension2--are defined by the path constraint. The path constraint is functionally equivalent to one constraint of the following form for dimension d, and each pair of visits v1 and v2:

mdl.add(IloIfThen(env,
                  v1.getNextVar()   == v2,
                  v2.getCumulVar(d) == v1.getCumulVar(d) + v1.getTransitVar(d)
                  ));

For instances of IloDimension2, such as time, the transit variable is defined as the sum of the delay variable, the wait variable, and the travel variable. For a visit v and a dimension d, the transit variables are maintained by the following rule:

v.getTransitVar(d) == v.getDelayVar(d) + v.getTravelVar(d) + v.getWaitVar(d);

The delay variable of v1, returned by v1.getDelayVar(d), is a floating-point constrained variable which represents the delay in terms of dimension d at visit v1. This is useful to represent the time needed to unload a truck. It can be accessed through the member function IloVisit::getDelayVar.

The wait variable of v1, returned by v1.getWaitVar(d), is a floating-point constrained variable which represents the additional quantity of dimension d consumed between v1 and its successor, over the time required to serve v1 and travel from v1 to its successor. In the case where d represents time, v1.getWaitVar(d) represents the waiting time. It can be accessed through the member function IloVisit::getWaitVar.

The travel variable of v1, returned by v1.getTravelVar(d), is a floating-point constrained variable which represents the quantity of dimension d taken by the vehicle serving v1 to get to v2. It can be accessed through the member function IloVisit::getTravelVar. The travel variable is maintained by the following rule:

mdl.add(IloIfThen(env,
                  v1.getNextVar()    == v2 && v1.getVehicleVar() == veh,
                  v1.getTravelVar(d) == v1.getDistanceTo(v2, d, veh)
                  / veh.getSpeed(d)
                  ));

In the previous code, v1.getVehicleVar().getSpeed(d) returns the speed of the vehicle associated with the vehicle performing v1.

Modeling visit quantity constraints

Visits have quantities, which can be expressed using IloDimension1 objects. These quantities, which can be weights, volumes, numbers of objects, and so on, represent the amount of a good picked up or dropped off by the vehicle. A visit can have more than one quantity associated with it. The quantity can be a positive or negative value or a variable. The demand for each visit must also be defined in terms of dimensions and constraints.

For example, to model a visit quantity, you first define the dimension quantity and then set a constraint on the transit variable associated with quantity using the member function IloVisit::getTransitVar. Using the member function setBounds is a bit more efficient in terms of memory and speed than using an equality or range constraint. However you might need to use a constraint if you want to give different values to the transit variable in different models or if you want to metapost the constraint. The following code shows how to define quantity (an IloDimension1) and how to express the quantity of goods related to visit:

IloEnv env;
IloModel mdl(env);
IloNode node(env);
IloDimension1 quantity(env);
mdl.add(weight);
IloVisit visit(node);
mdl.add(visit);
visit.getTransitVar(quantity).setBounds(12,12); // 12 items 

Modeling vehicle capacity constraints

Vehicles have capacity; they cannot hold more than a certain weight or a given number of pallets, for example. To express this idea, you define the dimension in which the capacity will be expressed, and you post a constraint on the variable that represents capacity.

For example, to model a vehicle capacity, you first define the dimension weight and then set a constraint on the dimension using the member function IloVehicle::setCapacity. The following code shows how to define weight (an IloDimension1) and how to express the capacity of a truck in terms of this intrinsic dimension.

IloEnv env;
IloModel mdl(env);
IloDimension1 weight(env);
mdl.add(weight);
IloVehicle vehicle(env);
vehicle.setCapacity(weight, 15000); // weight associated with vehicle
                                    // it has a capacity of 15000 kg

Capacity constraints correspond to constraints on the bounds of the cumulative variables. For example, the maximum load of a truck is handled internally by Dispatcher by setting bounds on all the cumulative variables associated with weight. The constraint placed on this cumulative variable is that it must be always less than or equal to the capacity of the vehicle.

Modeling time window constraints

Time windows occur in problems from many business sectors. For example, courier services have to pickup parcels after a certain time, but before another. Likewise, deliveries usually have to be made within a given time window--before one hour, but after another.

For example, to model a time window, you first define the dimension time and then set a constraint on the cumulative variable associated with time using the member function IloVisit::getCumulVar. To see how to implement a time window with one of these cumulative variables, assume that a dimension, node and visit have been defined already, like this:

IloEnv env;
IloModel mdl(env);
IloDimension2 time(env, IloEuclidean);
IloInt x=4, y=-5;
IloNode node(env, x, y);
IloVisit visit(node);
mdl.add(visit);

To define a time window between 10 and 14, use the following code:

mdl.add(visit.getCumulVar(time) >= 10);
mdl.add(visit.getCumulVar(time) <= 14);

You can also define a time window between 10 and 14 like this:

mdl.add(10 <= visit.getCumulVar(time) <= 14);

Not all time windows consist of a continuous block of time, of course. There are situations where the acceptable time window occurs in pieces. These are called disjoint time windows. Deliveries that can be made only between 7 and 9 in the morning or between 5 and 7 in the evening are an example of disjoint time windows.

To represent a disjoint time window, Dispatcher provides the IloDimensionWindows class. Using this class you can represent disjoint feasible periods of time. For example, to represent two disjoint time windows, the first starting at 8 and ending at 10 and the second starting at 14 and ending at 16, you could write:

IloDimensionWindows windows(env, time);
windows.setBounds(8, 16);
windows.setForbiddenInterval(10, 14);

You can then apply this window to a visit using the IloExecutionWindowsToVisitCon constraint:

mdl.add(IloExecutionWindowsToVisitCon(visit, windows));

Modeling service delays constraints

A delay is often encountered when performing a visit. This delay can be expressed in terms of distance (for example, to travel inside a large factory) or in terms of time (to unload the truck, for instance).

For example, to model a service delay, you first define the dimensions time and volume. You set a constraint on the transit variable associated with volume using the member function IloVisit::getTransitVar. You then set a constraint on the delay variable associated with time using the member function IloVisit::getDelayVar. The last line of code expresses that the time needed to unload the truck is equal to 0.5 units of time per unit of volume.

IloEnv env;
IloModel mdl(env);
IloDimension1 volume(env);
mdl.add(volume);
IloDimension2 time(env, IloEuclidean);
mdl.add(time);
IloNode node(env);
IloVisit visit(node);
mdl.add(visit);
mdl.add(visit.getTransitVar(volume) == 10);     // 10 m3
mdl.add(visit.getDelayVar(time) == .5*visit.getTransitVar(volume));
                                                // .5 minute / m3

Modeling deadline constraints

It may be useful to set deadlines on vehicles. For example, in some problems the vehicle must return to the depot before a certain time of the day.

For example, to model deadlines, you first define the dimension time. You also use the member functions IloVehicle::getFirstVisit and IloVehicle::getLastVisit together with IloVisit::getCumulVar.

IloEnv env;
IloModel mdl(env);
IloDimension2 time(env, IloEuclidean);
IloNode depot(env);
IloVisit first(depot);
IloVisit last(depot);
IloVehicle vehicle(first, last);
mdl.add(vehicle);
const IloNum timeDeadline = 17;

In the following code fragment, vehicle is constrained to start at 8:

mdl.add(first.getCumulVar(time) == 8);

and to come back before 17:

mdl.add(last.getCumulVar(time) <= timeDeadline);