10.5. Multi-depots and vehicles

Some instances have different depots. This is not a problem for the RL. You can have as many depots as you want (within the limit of an int). These depots can be starting, ending or starting and ending depots. Each problem in the RL is modelled with routes: each route starts at a depot, finishes at a depot and is serviced by one vehicle. The auxiliary graph used internally is constructed in such a way that every vehicle has its own starting and ending depots.

Each route and vehicle are in a one to one correspondence in the RL. They are represented by VehicleVar() variables and divided among several VehicleClasses.

10.5.1. Problems with multi-depots

You can find the source code in the file chap13/rl_auxiliary_graph.cc.

We only consider problems where the starting and ending depots are known for each vehicle. If you have to deal with a problem where this is not the case, there exists a bunch of modeling tricks where you can add fictive nodes.

To create the RoutingModel with multi-depots, simply pass to the constructor an std::vector<std::pair<RoutingModel::NodexIndex, RoutingModel::NodexIndex> > with the list of pairs of starting and ending depots in the original graph, one pair for each vehicle. The index of the pairs in the std::vector corresponds to the index of the vehicles.

Let’s implement the code for the instance used in the sub-section The auxiliary graph3.

In this example, we take four vehicles/routes:

• route 0: starts at 1 and ends at 4
• route 1: starts at 3 and ends at 4
• route 2: starts at 3 and ends at 7
• route 3: starts at 4 and ends at 7

Here is the code:

std::vector<std::pair<RoutingModel::NodeIndex,
                               RoutingModel::NodeIndex> > depots(4);
depots[0] = std::make_pair(1,4);
depots[1] = std::make_pair(3,4);
depots[2] = std::make_pair(3,7);
depots[3] = std::make_pair(4,7);

RoutingModel VRP(9, 4, depots);

The number of vehicles (4) and the length of the std::vector with the pairs of depots (depots.length()) must be equal[1].

[1]	If not, you trigger an assert().

10.5.2. Multi-depots in practice

There are several restrictions on the depots and practical facts about the RL model that are worth mentioning.

All vehicles are not necessarily used in a solution but if a vehicle is used it respects its starting and ending depots. When a vehicle is not used, the NextVar() variable corresponding to the starting depot of this vehicle points to the ending depot of this vehicle, i.e. if you have:

int vehicle = ...;
IntVar * start_var = routing.NextVar(routing.Start(vehicle)).
Assignment * solution = routing.Solve(...);

and the vehicle vehicle is not used in this solution, then

routing.IsEnd(solution.Value(start_var));

returns true[2].

The method IsVehicleUsed() of the RoutingModel class tests exactly this.

[2]	Remember that there are no NextVar() variables for end depots.

As mentioned earlier, a depot cannot be a transit node: you can only start, finish or start and finish a tour at a depot.

Warning

A depot cannot be a transit node.

10.5.3. The VehicleVar() variables

In the RL, there is a one to one correspondence between vehicles and routes. You probably noticed that we interchangeably used the terms route and vehicle in this manual. When you declare v vehicles/routes in your model, the RL solver creates a model with v vehicles/routes numbered from 0 to vehicles() - 1. These vehicles/routes are divided in different VehicleClasses (see next sub-section).

The VehicleVar(int64 i) method returns the IntVar* corresponding to the node with int64 index i: this variable indicates which vehicle services node i, i.e. if node i is serviced by vehicle vehicle_number in a solution (with the same abuse of notation as before):

VehicleVar(i) == vehicle_number.

You can grab all VehicleVar() variables at once with:

const std::vector<IntVar*>& VehicleVars() const;

For a vehicle vehicle_number, the following two conditions are satisfied:

routing.VehicleVar(routing.Start(vehicle_number)) == vehicle_number

and

routing.VehicleVar(routing.End(vehicle_number)) == vehicle_number.

On the same route, all nodes are serviced by the same vehicle, i.e.:

If NextVar(i) == j then VehicleVar(i) == VehicleVar(j)

If a node i is not active, i.e. not serviced by a vehicle, VehicleVar(i) is set to -1 but don’t rely on this to test if a node is active or not. Each node i has a corresponding BoolVar that indicates if the node is active or not. ActiveVar(i) returns (a pointer to) this variable. Internally, the real criterion used is to test if NextVar(i) points to itself or not. i.e. a node i is active if

NextVar(i) != i

and inactive if

NextVar(i) == i.

Depots are always active and thus can not be part of a Disjunction. This is worth remembering:

Warning

Depots are always active and thus can not be part of a Disjunction.

10.5.4. VehicleClasses

For efficiency reasons, vehicles/routes are divided in several VehicleClasses depending on the starting and ending depot(s) and the cost to use the vehicle/route[3]. The VehicleClass is a simple struct based on these three parameters. Its constructor method signature is:

VehicleClass(RoutingModel::NodeIndex start_node,
             RoutingModel::NodeIndex end_node,
             const int64 cost);

This struct provides an bool Equal(const VehicleClass& vehicle1, const VehicleClass& vehicle2) method to compare two VehicleClasses. The following method returns all the different VehicleClasses used in the model:

void GetVehicleClasses(std::vector<VehicleClass>* vehicle_classes)
                                                              const;

[3]	This cost can be set by SetRouteFixedCost(int64 cost) if all vehicles have the same cost or SetVehicleFixedCost(int vehicle, int64 cost) to set individual costs.