Exploring Disjunctions in OR Tools 2019-06-19

A series of questions on the Google OR Tools mailing list recently led me to question what was really going on with the use of disjunctions. The original poster was kind enough to share his original code with me, but it was in C#. So I took the time to convert the code to python and test out various things. The result surprised me a bit, but I think I understand better how disjunctions work. This post will first present the original problem, then my solution, and then finally explore the interesting issues that came up while using disjunctions.

The question: How to exclusively use one of two vehicles

The original question posted was how one might use exactly one out of two possible vehicles. For example, suppose the dispatcher has a choice between running a truck, or a truck with a trailer. The trailer increases capacity, but adds to the cost of running the vehicle (slower travel times, higher operating costs). The goal is to set up a solver run that accounts for the costs and benefits of both styles of vehicle, and then chooses the best solution. Another example might be using a driver and a helper on a single vehicle, like some delivery firms do around the holidays. The extra person will speed up service times, but will add significantly to the cost per hour of operating the truck.

Typically in a solver run, the solver is allowed to use any number of the vehicles, with no restrictions on the various combinations of vehicles used. In this case, a truck can be run with or without a trailer, but not both.

Pick one or the other truck type

The two different truck types have different capacities and travel costs. The “combo” truck (combination truck and trailer) has a higher capacity (say 3 instead of 1) and a higher per-mile cost (say 10 instead of 1). In order to facilitate testing different combinations, I set these values on the command line using Python’s argparse facility.

# args.vehicles === number of vehicles
# args.combo_capacity === the capacity of the combo truck+trailer
# args.single_capacity === the capacity of the single truck
# args.combo_cost === the cost of the combo truck+trailer
# args.single_cost === the cost of the single truck
data['vehicle_capacities'] = list(
    chain.from_iterable([args.combo_capacity,
                            args.single_capacity]
                           for _ in range(0,args.vehicles))
)
 
data['vehicle_costs'] = list(
    chain.from_iterable([args.combo_cost,
                            args.single_cost]
                           for _ in range(0,args.vehicles))
)

Alternately, you can skip all the command line arguments and just do something like the following, simulating the use of two trucks:

data['vehicle_capacities'] = [3, 1, 3, 1]
data['vehicle_costs'] = [10, 1, 10, 1]

The different costs are realized in the solver by using a per-vehicle arc cost evaluator callback.

def vehicle_distance_callback(data, vehicle, manager, from_index, to_index):
    """Returns the distance between the two nodes for a vehicle."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]*data['vehicle_costs'][vehicle]
 
# then later...
# use per-vehicle arc cost evaluators
 
vehicle_transits = [
    routing.RegisterTransitCallback(
        partial(vehicle_distance_callback, data, v, manager)
    ) for v in range(0,num_veh)]
 
vehicle_costs = [
    routing.SetArcCostEvaluatorOfVehicle(
        t,v
    ) for (t,v) in zip(vehicle_transits,
                       range(0,num_veh))]

This isn’t a “distance” metric, so much as a cost per mile metric. Since I want the solver to minimize the cost of the solution, this is okay. All else being equal, the high capacity vehicles are more expensive to use to travel between any two locations. However, they can visit more nodes, so in theory they should be chosen in cases in which single unit trucks leave nodes unserved.

The code for excluding one or the other of a pair of vehicles originally relied on the trusty counting dimension idea. I wrote that up in other blog posts, most recently in its own post. The counting dimension is created as follows:

But after using it for a while, I realized that I could get the same utility by just using the travel cost dimension, which I already had in my code.

The travel cost dimension can be used to pick one or the other of the two vehicle options as follows:

# create travel cost dimension dependent on vehicle type
routing.AddDimensionWithVehicleTransits(
    vehicle_transits,
    0,      # no slack
    300000, # some really large time
    True,
    "Cost")
cost_dimension = routing.GetDimensionOrDie("Cost")

The dimension is fairly standard, except it uses a per-vehicle transit function to determine the value of the dimension at each node. The dimension accumuilates the travel cost as the vehicle moves from node to node. A vehicle that is not used travels from the starting depot to a dummy ending node that is also at the depot, and so it does not have any accumulated cost. A single truck will accumulate a lower cost with each node it visits than a combo unit, because the transit functions are specific to each vehicle.

This dimension is used as follows to set up the A-or-B type constraint.

# set constraints such that truck, truck and trailer cannot both be used
for veh_pair in range(0, num_veh//2):
    # buggy dead reckoning, but truck-trailer is first, truck single unit second
    combo = veh_pair*2
    single = veh_pair*2 + 1
    if args.cumulative_constraint:
        index_combo = routing.End(combo)
        index_single = routing.End(single)
 
        end_time_combo = cost_dimension.CumulVar(index_combo)
        end_time_single = cost_dimension.CumulVar(index_single)
 
        combo_on = end_time_combo > 0
        single_on = end_time_single > 0
 
        # constrain solver to prevent both being on
        # truth table:
        #
        #   combo_on     single_on   multiply  descr
        #     0             0           0      both unused; okay
        #     1             0           0      combo on only; okay
        #     0             1           0      single on only; okay
        #     1             1           1      both on; prevent
        #
        solver.Add(combo_on * single_on == 0)

The accumulated travel cost at the final node (routing.End(i)) will be zero if the vehicle is not used, and will be greater than zero if the vehicle is used. This state is captured for the two types of vehicles in the variables combo_on and single_on. I want to prevent the case in which both the combo_on and single_on are true. The “truth table” in the comment in the code block above shows the four cases. The first three are okay—both off, or just one on. The last case is what I want to prevent. Therefore the final line in the code block adds the constraint that the multiplying combo_on and single_on must be equal to zero.

The test case is pretty simple. It uses the following travel matrix and demand:

data['distance_matrix'] = [
        [0, 3, 3, 3, 3, 3],
        [3, 0, 1, 1, 1, 1],
        [3, 1, 0, 1, 1, 1],
        [3, 1, 1, 0, 1, 1],
        [3, 1, 1, 1, 0, 1],
        [3, 1, 1, 1, 1, 0]
]
data['demands'] = [0, 1, 1, 1, 1, 1 ]

In short, there are 5 locations that need service, each with a demand of 1. The service locations are all one unit of distance away from each other, and three units away from the depot. So for a truck without a trailer, one service call will cost 6 (depot to node is 3, node to depot is 3, cost multiplier of truck is 1). For a truck with a trailer, one service call will cost 60 (6 times the combo cost multiplier of 10). But a combo unit can serve three nodes, while a truck can serve just one.

To illustrate the use of the one-or-the-other constraint, first this is the model run without the constraint, just to see what happens:

python disjunction_fail.py  -v 2 --combo_cost 10
The Objective Value is 92
Truck 0 travel time
     combo: 0
     single: 6
Truck 1 travel time
     combo: 80
     single: 6

This is not what I want, but it shows what happens when the exclusion constraint is not on. In this result, the second truck (Truck 1) is used both in its combo state as well as in its single state.

With the constraint turned on with the appropriate flag, the following result is obtained.

python disjunction_fail.py  -v 2 --combo_cost 10 --cumulative_constraint
The Objective Value is 150
Truck 0 travel time
     combo: 80
     single: 0
Truck 1 travel time
     combo: 70
     single: 0

Obviously this is much more expensive than the previous solution, but it doesn’t violate the constraint that each truck can only be used in a single configuration. The solver chose to use both trucks with trailers. The first truck visits 3 nodes, and the second visits 2.

Adding disjunctions

The problem is that for more demand nodes, the solver must be able to drop nodes. To illustrate this case, I created the --seven command line flag that creates a larger sized demand matrix with eleven demands (it used to have seven, but I increased that without changing the name of the flag…). In order to drop nodes, the code must add disjunctions. I also created a command line option to turn on disjunctions, and to assign a specific cost for the disjunction penalty.

# optional disjunctions, depending on command line args
if args.single_disjunctions:
    print('single node disjunction penalty is',args.singlepenalty)
    disjunctions = [routing.AddDisjunction([manager.NodeToIndex(i)],args.singlepenalty)
                    for i in range(1,len(data['demands']))]

Running the solver with --seven and disjunctions gives:

python disjunction_fail.py  -v 2 --combo_cost 10 --cumulative_constraint -t 10 --seven -d --singlepenalty 1000
single node disjunction penalty is 1000
added 11 disjunctions, one per node
The Objective Value is 5160
Truck 0 travel time
     combo: 80
     single: 0
Truck 1 travel time
     combo: 80
     single: 0

This is the best the solver can do. Both vehicles are running in combo mode, six demands are served, and five are dropped at a cost of 1000 each.

So far so good.

Expect the unexpected

What I did next was to play around with the disjunction penalty when applied to the five node demand case. With disjunction penalty of 1, all nodes are dropped, as the cheapest way to serve one node costs at least 6.

python disjunction_fail.py  -v 2 --combo_cost 10 --cumulative_constraint -t 10  -d --singlepenalty 1
single node disjunction penalty is 1
added 5 disjunctions, one per node
The Objective Value is 5
Truck 0 travel time
     combo: 0
     single: 0
Truck 1 travel time
     combo: 0
     single: 0

If the disjunction penalty is set to 7, then it is cheaper to send a single unit truck out to perform a pickup than it is to drop those nodes, so only three nodes are dropped:

python disjunction_fail.py  -v 2 --combo_cost 10 --cumulative_constraint -t 10  -d --singlepenalty 7
single node disjunction penalty is 7
added 5 disjunctions, one per node
The Objective Value is 33
Truck 0 travel time
     combo: 0
     single: 6
Truck 1 travel time
     combo: 0
     single: 6

(Here is where things start to get weird.)

We know from above that if all five nodes are served using the truck and trailer combo, the total objective cost is 150 (70 for one combo unit serving two customers, 80 for the other serving three). So in theory, if the penalty of dropping a node is boosted high enough, the solver should notice and shift over to using combo trucks to serve all the nodes. But that is not what happens.

python disjunction_fail.py  -v 2 --combo_cost 10 --cumulative_constraint -t 10  -d --singlepenalty 47
single node disjunction penalty is 47
added 5 disjunctions, one per node
The Objective Value is 153
Truck 0 travel time
     combo: 0
     single: 6
Truck 1 travel time
     combo: 0
     single: 6

In other words, the solver chooses a solution that costs 153 and drops three nodes, even though it could serve all nodes for a cost of 150. Continuing to raise the disjunction cost to 60 gives the same “two single units” result. Bumping it up to 63 gives:

python disjunction_fail.py  -v 2 --combo_cost 10 --cumulative_constraint -t 10  -d --singlepenalty 63
single node disjunction penalty is 63
added 5 disjunctions, one per node
The Objective Value is 149
Truck 0 travel time
     combo: 80
     single: 0
Truck 1 travel time
     combo: 0
     single: 6

And finally, bumping the penalty to 64 produces the two-combo unit solution and a cost of 150.

Similar results were obtained with the larger numbers of vehicles in the –seven case. This puzzled me for a long time. It appeared the solver was getting stuck in a bad solution, and I couldn’t figure out how to get it to bump out of that stuck solution. I created some interesting hacks that sort of worked but didn’t really in all cases. They’re still in the code, but sort of pointless as they didn’t fix the problem.

Guided Local Search to the rescue

So the ultimate fix was to turn on “guided local search”.

if args.guided_local:
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

This option requires a time limit, but I’m used to using time limits as pickup and delivery problems (the usual thing I’m trying to solve) rarely converge. This option appears to make the solver bounce out of local minima and try different branches.

First, without the guided local search on, and with a disjunction penalty of 60, the solver gives the following solution:

python disjunction_fail.py  -v 2 --combo_cost 10 --cumulative_constraint -t 10  -d --singlepenalty 60
single node disjunction penalty is 60
added 5 disjunctions, one per node
The Objective Value is 192
Truck 0 travel time
     combo: 0
     single: 6
Truck 1 travel time
     combo: 0
     single: 6

With the option turned on, it gives this:

python disjunction_fail.py  -v 2 --combo_cost 10 --cumulative_constraint -t 10  -d --singlepenalty 60 --guided_local
single node disjunction penalty is 60
added 5 disjunctions, one per node
The Objective Value is 146
Truck 0 travel time
     combo: 80
     single: 0
Truck 1 travel time
     combo: 0
     single: 6

This solution of 146 is cheaper than serving all nodes (which we know costs 150). So serving 3 nodes with a combo truck, one node with a single truck, and dropping one node is the best solution. The solver is no longer getting stuck in suboptimal results.

Show the code

The complete code for this, along with several false starts and interesting but unsuccessful trial solutions is available on github at https://github.com/jmarca/disjunction_tests. The python code is in the file disjunction_fail.py.