1049 Words

Reading time 5 min

0 google-or-tools 3 freight 2 vehicle types 21 code

Counting Dimension

For many applications of Google’s OR Tools routing library, I find a counting dimension to be quite useful. I’ve talked about it before, but this post focused just on the counting dimension.

How to set up a counting dimension

OR Tools uses dimensions, and the first time I started using it I found the concept a little bit strange. In a nutshell, the basic idea is that a dimension is something that changes due to visiting a node, or due to the transit between two nodes, or both. For example, consider time. Time increases when a vehicle travels from A to B, and it also increases when the vehicle is at B loading or unloading items. Thus a time dimension will have a value that is dependent on both the origin and the destination node (the transit time between nodes), and on the properties of the node itself (how long the “service time” at the node is). Another dimension that is often used is distance, which only depends on transit between nodes. Another common dimension is the vehicle load, something that increases or decreases only at the nodes, not based on the transits between nodes.

A counting dimension is like a vehicle load dimension, in that it only depends on the node being visited. However, it is even simpler. Instead of requiring some vector of per-node demands, a counting dimension simply increases by 1 with each node visited. The code to create a counting dimension is as follows:

count_dimension_name = 'count'
# assume some variable num_nodes holds the total number of nodes
routing.AddConstantDimension(
    1, # increment by one every time
    num_nodes+1,  # make sure the return to depot node can be counted
    True,  # set count to zero
    count_dimension_name)
count_dimension = routing.GetDimensionOrDie(count_dimension_name)

Using the counting dimension

I have already shown a few examples of using the counting dimension in this blog. I will repeat them here, slightly edited to focus on the idea of a counting dimension only.

Precedence constraints

First, in my post on sequence constraints, I used a counting dimension to make sure that some node A comes before another node B. You can do this with the following constraint:

# for some pair of indices A and B
A_index = manager.NodeToIndex(A);
B_index = manager.NodeToIndex(B);
# make sure same vehicle
solver.Add(routing.VehicleVar(A_index) ==
           routing.VehicleVar(B_index)
solver.Add(count_dimension.CumulVar(A_index) <=
           count_dimension.CumulVar(B_index))

Notice that the same vehicle constraint is required. All dimensions are vehicle specific. It is possible for some dimensions (time for example) to be roughly equivalent for each vehicle. A count is not like that, however. It makes no sense to compare the count of node A with the count of node B if they aren’t served by the same vehicle.

FIFO constraints

I worked out another example post on first in, first out requirements. In that post, I called the counting dimension “FIFO” rather than count, but it does the same thing. Again, presuming that the same vehicle visits A and B, the count dimension can be used to make sure that the items picked up from A are dropped of before the items from B (first in, first out). The following code demonstrates the use of the count dimension, and also how conditional constraints are used. For more details, see the original post.

# same vehicle condition: if true, A and B are both served by same vehicle
vehicle_condition = routing.VehicleVar(picku_a_index) ==
                    routing.VehicleVar(picku_b_index)

# pickup time condition: if true, A is picked up before B
early_condition = count_dimension.CumulVar(picku_a_index) <=
                  count_dimension.CumulVar(picku_b_index)

# poor man's AND.  True * True = True (1), all else equals False (0)
combined_conditions = vehicle_condition * early_condition

# require that delivery of A happens before delivery of B
deliv_constraint = count_dimension.CumulVar(deliv_a_index) <=
                   count_dimension.CumulVar(deliv_b_index)

expression = solver.ConditionalExpression(
    combined_conditions,
    deliv_constraint,
    1)

solver.AddConstraint(
    expression >= 1
)

A “fair” distribution of loads

Another question that comes up fairly often on the mailing list is how to balance work across a fleet of vehicles. Suppose you have a fleet of 5 vehicles and 50 pickups, but each vehicle has a capacity of 50. The solver will happily try to fit all 50 pickups into a single vehicle, and then will add other vehicles to serve the few demands that cannot be met by the first vehicle. This results in a skewed distribution of loads across vehicles.

Using a counting dimension, one can try to achieve a more even distribution of jobs across vehicles. In this case, with 50 jobs and 5 vehicles, you would want each vehicle to serve about 10 jobs each. You can set this upper bound in the definition of the counting dimension.

num_vehicles = 5
num_nodes = 50
...
count_dimension_name = 'count'
# assume some variable num_nodes holds the total number of nodes
routing.AddConstantDimension(
    1, # increment by one every time
    num_nodes // num_vehicles + 1,  # max value forces equivalent # of jobs
    True,  # set count to zero
    count_dimension_name)
count_dimension = routing.GetDimensionOrDie(count_dimension_name)

Now it might be the case that it is impossible to serve exactly 10 or whatever. Floordiv (the // operator) rounds down, so that;s why I added one above as a safety valve. Alternately, you can use math.ceil instead of the floordiv operator.

Make every vehicle do something

The previous fair distribution approach works to make sure that loads are balanced, but another goal might be to make sure that every vehicle is used at least once. In that case, you can borrow a trick from time windows to try to force a soft lower bound:

count_dimension = routing.GetDimensionOrDie(count_dimension_name)
... then later, constrain vehicle end node ...
for veh in range(0, num_veh):
    index_end = routing.End(veh)
    count_dimension.SetCumulVarSoftLowerBound(index_end,
                                              2,
                                              100000)

The constant dimension will increment by one with every node visited, including the vehicle end node. This means that if a vehicle visits no “real” pickup points, then it will have a count of 1 at the end node. By setting a soft constraint that the end node should have a lower bound of 2, that means the solver will try its best to make sure every vehicle visits one node. If it can’t do that, it will pay the penalty.

Of course I haven’t tried that last one by itself, although I have used the approach in combination with other things. It should work, but if it doesn’t email me with a fix.