constraint on max travel time not enforced, CVRPTW, pickup/delivery, IntExpr, CumulVar

[Jylanthas]

I'm not sure whether my expectations are unreasonable or if I've stumbled upon a bug. I've configured a CVRPTW with pickup and delivery precedence constraints. I would like to place a maximum allowable travel time (pickup to dropoff) constraint per individual customer, where the max travel time is a constant = some_coefficient *direct_travel_time(pickup_node, dropoff_node) . The idea being "riders should not endure more than 1.3x their direct path driving time". I've added a reproducible stripped-down gist. Let me know if this is not easy to work with. Thanks a bunch in advance.

https://gist.github.com/Jylanthas/a9878ace7445ffc6f0b7246ff90eac53

constraint excerpt from gist

min_dur = int(travel_time_callback(index, delivery_index)) # direct travel
max_dur = int(1.3 * min_dur) # some allowable duration beyond direct travel
# precedence constraint, also bounding max travel time between nodes of same customer
dur_expr = time_dim.CumulVar(index) + max_dur <= time_dim.CumulVar(delivery_index)
dur_expr.SetRange(min_dur, max_dur) # I have also tried ranging the expression itself
solver.Add(dur_expr)

result

# download https://gist.github.com/Jylanthas/a9878ace7445ffc6f0b7246ff90eac53
python pdptw_max_dur_issue.py

customer            route      pickup_node     dropoff_node        pickup_at       dropoff_at         plan_dur          min_dur          max_dur  plan_pickup_range  plan_dropoff_range  plan_min_poss_dur  
       1                9                1                2             2103             3266             1163             1041             1353       2103..2266       3266..3640             1000  
       2                9                3                4              894             3260             2366              773             1006        894..1057       3260..3482             2203  
       3                9                5                6             1647             3263             1616             1380             1794       1647..1810       3263..3617             1453  
       4                9                7                8             1173             3111             1938              943             1226       1173..1336       3111..3274             1775  
       5                9                9               10             1351             3176             1825             1184             1539       1351..1514       3176..3339             1662  
       6                9               11               12             1907             2963             1056             1026             1334       1907..2070       2963..3126              893  
       7                7               13               14             1632             2983             1351             1350             1755       1632..2205       2983..3556              778  
       8                7               15               16             1631             2982             1351             1350             1755       1631..1800       2982..3555             1182  

expect plan_dur <= max_dur, in the console print, where plan_dur = dropoff_at - pickup_at as retrieved from assignment.Value(time_dimension.CumulVar(respective pickup or dropoff node index))

ortools (5.1.4045)
pip 1.5.6
python 2.7
Mac Sierra 10.12.5

[Mizux]

I would say:

• try to use last ortools version 5.1.4045 is old and can contains some bugs
• I think you have a bug here:
  https://gist.github.com/Jylanthas/a9878ace7445ffc6f0b7246ff90eac53#file-pdptw_max_dur_issue-py-L105 (you use dur_constraint instead of dur_expr, and use min_dur instead of max_dur IMHO)
  My proposal (not tested):

      if delivery_index > 0:
        solver.Add(routing.VehicleVar(index) == routing.VehicleVar(delivery_index)) # 1)
        solver.Add(time_dimension.CumulVar(index) <= time_dimension.CumulVar(delivery_index)) # 2)
        min_dur = int(travel_time_callback(index, delivery_index))
        max_dur = int(max_dur_mult * min_dur)
        dur_expr = time_dimension.CumulVar(delivery_index) - time_dimension.CumulVar(index)
        solver.Add(dur_expr <= max_dur) # 3)
        routing.AddPickupAndDelivery(i, dropoffs[i])
        print dur_constraint

i.e. what you want:

1. vehicle which does the pickup is the same which does the delivery i.e. same vehicle constraint
2. time to pickup must be before time to delivery i.e. node precedence constraint
3. the difference delivery_time - pickup_time (i.e. the duration to perform the delivery) must not exceed max_dur aka "1.3 * min_dur" i.e. max duration constraint

[Jylanthas]

@Mizux Thank you. No dice, though I've made an interesting finding.

If I give the solver an easy way out by ensuring there are as many vehicles available as customers and that vehicle capacity is 1, such that each customer must be served alone, a solution is found incredibly fast. This indicates to me that the time constraints I'm imposing are not in fact unsatisfiable. In the original case where each vehicle has enough capacity for all customers, the solver is getting stuck iterating the entire search space with 2 vehicles rather than investigating solution candidates using more vehicles.

I understand convergence speed is highly affected by the initial solution, and maybe my failing case gets stuck in local optima, but I've let this thing run for quite a long time on such a small data set. Are there any search parameter flags you recommend tweaking that might help it jump out of local optima to investigate candidates using more vehicles, or ways I can log and see whether the entire search space has indeed been exhausted, maybe via search monitor?

python pdptw_max_dur_issue.py --capacity 1 --max_dur_mult 2.5 --search_time_limit 5000
solution exists
cust (pnode..dnode)    route    pickup_at..dropoff_at    cnstr_pickup    cnstr_dropoff    plan_dur    cnstr_dur    plan_pickup_range    plan_dropoff_range    plan_min_poss_dur
                 1 1..2        7               1040..2623       487..2287       2623..4423        1583   1041..2603           1040..2287            2623..4423                  336
                 2 3..4        9                774..2623       678..2478       2623..4423        1849    773..1934            774..2478            2623..4410                  145
                 3 5..6        4               1383..2764        23..1823       2623..4423        1381   1380..3450           1383..1823            2764..4423                  941
                 4 7..8        8                963..2623       537..2337       2623..4423        1660    943..2357            963..2337            2623..4423                  286
                5 9..10        6               1141..2623         0..1800       2623..4423        1482   1184..2960           1141..1800            2623..4423                  823
               6 11..12        5               1213..2623       704..2504       2623..4423        1410   1026..2567           1213..2504            2623..4423                  119
               7 13..14        2               1511..2862       823..2623       2623..4423        1351   1350..3376           1511..2623            2862..4423                  239
               8 15..16        3               1511..2862         0..1800       2623..4423        1351   1350..3376           1511..1800            2862..4423                 1062


python pdptw_max_dur_issue.py --capacity 10 --max_dur_mult 2.5 --search_time_limit 5000
solution not found

particularly odd. why does adding one seat make the problem intractable?

python pdptw_max_dur_issue.py --vehicles 3 --capacity 4 --max_dur_mult 2.5 --search_time_limit 10000
solution not found

python pdptw_max_dur_issue.py --vehicles 3 --capacity 3 --max_dur_mult 2.5 --search_time_limit 10000
solution exists

I've updated gist with your suggestions, and added a couple options to make testing easier

if delivery_index > 0:
        solver.Add(routing.VehicleVar(index) == routing.VehicleVar(delivery_index))
        solver.Add(time_dimension.CumulVar(index) <= time_dimension.CumulVar(delivery_index))
        min_dur = int(travel_time_callback(index, delivery_index))
        max_dur = int(max_dur_mult * min_dur)
        dur_expr = time_dimension.CumulVar(delivery_index) - time_dimension.CumulVar(index)
        solver.Add(dur_expr <= max_dur)
        routing.AddPickupAndDelivery(i, dropoffs[i])

updated to ortools (6.7.4973)

[Mizux]

my 2 cents,

• For pickup delivery problem you should use PARALLEL_CHEAPEST_INSERTION as first solution strategy
  cf. https://github.com/google/or-tools/blob/master/ortools/constraint_solver/routing.cc#L4246

• You can try to use GlobalSpan cost to force solver to use several vehicles
  cf https://developers.google.com/optimization/routing/vrp#global_span for an example (should work with a "time" dimension too)

• concerning your "arc_cost" function bind on CreateCustomTimeCallback.Duration() this method always recompute the distance. Should be better to create a matrix of time in _init_ then return in constant time the result in the callback. look at my example here

[Jylanthas]

@Mizux thanks for the pointers.

• PARALLEL_CHEAPEST_INSERTION added
  No problems here

• time_dimension.SetGlobalSpanCostCoefficient added
  Only affects assignment.ObjectiveValue, but not reflected in time time_dimension.CumulVar values

  How is it possible vehicle and time vars remain unchanged despite a massive difference in output total duration?

python pdptw_max_dur_issue.py --vehicles 8 --capacity 3 --max_dur_mult # no glob span cost coef
Total duration of all routes: 4200
3 vehicles used

python pdptw_max_dur_issue.py --vehicles 8 --capacity 3 --glob_span_cost_coef 1000 --max_dur_mult 2.5
Total duration of all routes: 1729200
3 vehicles used
solution durations and pickup/dropoff times unchanged compared to no glob span cost

• convert arc_cost function to constant time added
  In fact I do precompute in production, though I've gone ahead and updated this test case anyways.

  Unimportant to the main issue, memoization/caching might be a better option if there are cases where an acceptable solution can be found without inspecting ever node pair.

Final observation. There are failing cases which terminate FASTER than the search time limit. If I understand local search, it will run exhaustively until time limit or feasible solution is reached. Since, intuitively, adding more vehicle capacity should not preclude a solution, yet the solver failing prior to time limit, it has either exhausted every solution candidate (unlikely), or determined according to another criteria to terminate search.

python pdptw_issue3.py --vehicles 3 --capacity 3 --max_dur_mult 2.5 --search_time_limit 10000
solution exists

python pdptw_issue3.py --vehicles 3 --capacity 4 --max_dur_mult 2.5 --search_time_limit 10000
solution not found # 10s limit, 1s elapsed, only difference is MORE vehicle capacity

[Mizux]

Hi,

Concerning objective value:
routing.SetArcCostEvaluatorOfAllVehicles(arc_cost_callback) this will create the "default" cost for an edge and a solution is the sum of all edges vehicles will travel (note: you can grep transit_cost if i remember well).
Which is equivalent to only sum the cumul_var of end node for each vehicles.
In your case you use the time between nodes in my example I use the distance between nodes as default cost...
Thus the solver try to always minimize the objective "value".

Now when you create a dimension "Foo" and set a globalSpan coefficient k != 0
val = k * max{end} - min{start} # cf doc on GlobalSpan formula
This val is added to the objectif "value" function so now the solver has incentive to reduce this val (i think by default all dimensions have 0 as global span coefficient)

e.g. In your case supposing you have set cumul var to zero in your time dimension i.e. min vehicle start is 0:
1,729,200 - 4,200 /score of the SetArcCost/ = 1,725,000 = 1,725 * 1000 /your coef glob_span_cost_coef/
so the max cumul end should be 1725s ?

Maybe your "total duration of all routes" is the objective value which is not anymore equivalent to the sum of all end cumul_var of the time dimension ;)

note: you can add severals dim to objective i.e. non zero coeff to differents dimensions, in this case coefs weight the different incentives (or how to compare time cost, to distance cost, to order number cost etc...).
note 2: you can also add lot of other "cost" to the objective function
e.g. a fixed cost for each vehicle used

[bertop89]

Hi,

Did anybody found a way to limit the max travel time per vehicle? I tried some of the things posted in this issue but couldn't make it work. Thanks!

[Mizux]

Did anybody found a way to limit the max travel time per vehicle?

Off topic.. Just create a "Time" Dimension and set the vehicle capacity to max travel time
you can look at examples/python/cvrptw.py for how to create a Time dimension...

[bertop89]

Thanks @Mizux , what I meant was to limit the maximum time distance traveled per vehicle. For example, say I want to restrict to traveling 12 hours, if I add this the way you told me then I get a:

~/.local/lib/python3.6/site-packages/ortools/constraint_solver/pywrapcp.py in SetRange(self, l, u)
   1337 
   1338     def SetRange(self, l: 'int64', u: 'int64') -> "void":
-> 1339         return _pywrapcp.IntExpr_SetRange(self, l, u)
   1340 
   1341     def SetValue(self, v: 'int64') -> "void":

Exception: CP Solver fail

when I try to add a destination with a time window starting after 12h. Did I understood this correctly? Sorry for the off topic, should I create a new issue? Thanks again! ;)

[Jylanthas]

@bertop89 Not to step on toes but definitely create a new issue :)

It will depend on whether your max travel time (e.g. 12 hours) applies to ALL vehicles, or if individual vehicles may have different values. Which is your goal?

As far as your error, paste all of your code. if it's large use https://gist.github.com/

[Jylanthas]

@Mizux While we're back here, regarding the original issue, all of your suggestions were certainly improvements. I now understand glob span cost coef related to the objective value. I've found, however, many situations where the search terminates so quickly that I can only conclude the initial solution for local search was not satisfiable. Using a previous example:

python pdptw_issue3.py --vehicles 3 --capacity 3 --max_dur_mult 2.5 --search_time_limit 10000
solution exists

python pdptw_issue3.py --vehicles 3 --capacity 4 --max_dur_mult 2.5 --search_time_limit 10000
solution not found # in spite of MORE vehicle capacity, returns immediately, prior to 10000

My guess is that, in the latter execution, 2 customers begin on a vehicle which cannot satisfy time constraints.

• Is an initial solution that satisfies all constraints a prerequisite to starting local search (if it does not satisfy, will it terminate early)?
• How can I inspect the initial solution to verify whether it is satisfiable or not?

[Mizux]

Inspect don't know yet.

But at least you can enable some log using:

search_parameters.log_search = True

e.g. if I hack cvrp.py

$ examples/python/cvrp.py
WARNING: Logging before InitGoogleLogging() is written to STDERR
I0619 13:58:50.682148 116024 search.cc:241] Start search (memory used = 22.41 MB)
I0619 13:58:50.682247 116024 search.cc:241] Root node processed (time = 0 ms, constraints = 89, memory used = 22.41 MB)
I0619 13:58:50.682484 116024 search.cc:241] Solution #0 (7032, time = 0 ms, branches = 34, failures = 0, depth = 33, memory used = 22.41 MB)
I0619 13:58:50.682811 116024 search.cc:241] Solution #1 (6872, objective maximum = 7032, time = 0 ms, branches = 37, failures = 2, depth = 33, neighbors = 282, filtered neighbors = 1, accepted neighbors = 1, memory used = 22.41 MB)
I0619 13:58:50.684059 116024 search.cc:241] Finished search tree (time = 1 ms, branches = 73, failures = 38, neighbors = 1190, filtered neighbors = 1, accepted neigbors = 1, memory used = 22.41 MB)
I0619 13:58:50.684094 116024 search.cc:241] End search (time = 1 ms, branches = 73, failures = 38, memory used = 22.41 MB, speed = 73000 branches/s)
...

[Mizux]

Initial search is mandatory for starting local search.
Did you still use "PARALLEL_CHEAPEST_INSERTION" ?

For writing a Pickup&Delivery you need three statements

• addPickupDelivery(loc_A, loc_B) # solver use this as hint internally
• add the precedence constraint cumulVar(loc_a ) <= cumlVar(loc_B) # my bad thinking it was done by the previous method
• add the vehicle(loc_A) == vehicle(loc_B) constraint

e.g. supposing there is a "distance" dimension (also work with "time/duration" dimension if any).

routing.AddPickupAndDelivery(routing.NodeToIndex(1),routing.NodeToIndex( 2))
routing.solver().Add(routing.CumulVar(routing.NodeToIndex(1), "distance") <= routing.CumulVar(routing.NodeToIndex(2), "distance"))
routing.solver().Add(routing.VehicleVar(routing.NodeToIndex(1)) == routing.VehicleVar(routing.NodeToIndex(2)))

src: https://github.com/google/or-tools/blob/master/examples/cpp/pdptw.cc#L268

[Mizux]

AFAIK the open source FSS (First Solution Strategy) is not good at back tracking so sometime it just can't find any solution.

• You can try different FSS e.g. PATH_CHEAPEST_ARC is slower but can find solution sometime see Indexes seem to be off when comparing cumulvars #813 (comment)
• Try to make some node optional (e.g. using penalty) to be sure to find a solution then hope the LNS will improve the solution by finding a better route
• Wait for the backport to github of the new routing implementation by the end of the year (however will break few routing API but get significant performance increase)

[270ajay]

No problem! @Jylanthas
Using AddSoftSameVehicleConstraint can also help get feasible solution. However, this method is also inconsistent. It does not give optimal solution (i.e., constraint is violated) even if you put huge penalty cost and even when there is a solution.

@Mizux if you know another way to force same vehicle to visit node/set of nodes, please let me know. I have opened an issue for that #847 (comment) Thank you!

[Mizux]

@270ajay

Reoptimizing, I am able to get feasible solution when I add same vehicle constraint for pair (150, 208), (208, 204), (204, 142), (142, 1), (1, 218), (218, 58).

How did you model these constraints ? Did you use ActiveVar() ?
e.g. in python for 208, 204

constraintActive = routing.ActiveVar(routing.NodeToIndex(208)) * routing.ActiveVar(routing.NodeToIndex(204))
routing.solver().Add(
  constraintActive * routing.VehicleVar(routing.NodeToIndex(208)) == 
  constraintActive * routing.VehicleVar(routing.NodeToIndex(204)))

since solver will add node one by one during the first strategy ("greedy algorithm") step, if you don't use ActiveVar() the solver can block and return "unfeasible" quickly ...

[JacobenVosloo]

@Mizux and @Jylanthas

Any idea how to do this from one of the previous suggestions

dur_expr = time_dimension.CumulVar(delivery_index) - time_dimension.CumulVar(index)
solver.Add(dur_expr <= max_dur)

In java?

If I try to subtract one IntVar from the other I get this error

The operator - is undefined for the argument type(s)com.google.ortools.constraintsolver.IntVar, com.google.ortools.constraintsolver.IntVar

I also logged this on StackOverflow
https://stackoverflow.com/questions/62514537/how-to-create-intexpr-from-multiple-intexpr-in-java-using-or-tools-same-as-in

What I am trying to achieve is to ensure that the total duration (i.e on duty time of driver) is not exceeding a time limit.... since there can be a significant waiting time at the first depot node, due to time windows, I cant simply constrain the time dimension to the allowed on duty time as the slack will exceed the total allowed time.

That is why I wanted to add the following condition

for (int i = 0; i < data.vehicleNumber; ++i) {
     solver.addConstraint(solver.makeLessOrEqual(timeDimension.cumulVar(routing.end(i))-timeDimension.cumulVar(routing.start(i)), onDutyTimeLimit));
 }

[Mizux]

@Mizux and @Jylanthas

Any idea how to do this from one of the previous suggestions

dur_expr = time_dimension.CumulVar(delivery_index) - time_dimension.CumulVar(index)
solver.Add(dur_expr <= max_dur)

In java?

If I try to subtract one IntVar from the other I get this error

The operator - is undefined for the argument type(s)com.google.ortools.constraintsolver.IntVar, com.google.ortools.constraintsolver.IntVar

I also logged this on StackOverflow https://stackoverflow.com/questions/62514537/how-to-create-intexpr-from-multiple-intexpr-in-java-using-or-tools-same-as-in

What I am trying to achieve is to ensure that the total duration (i.e on duty time of driver) is not exceeding a time limit.... since there can be a significant waiting time at the first depot node, due to time windows, I cant simply constrain the time dimension to the allowed on duty time as the slack will exceed the total allowed time.

That is why I wanted to add the following condition

for (int i = 0; i < data.vehicleNumber; ++i) {
     solver.addConstraint(solver.makeLessOrEqual(timeDimension.cumulVar(routing.end(i))-timeDimension.cumulVar(routing.start(i)), onDutyTimeLimit));
 }

since Java do not provide operator overload (i.e. override operator -) you must use this:

or-tools/ortools/constraint_solver/java/constraint_solver.i

Line 957 in 48134ce

%rename (makeDifference) Solver::MakeDifference;

for (int i = 0; i < data.vehicleNumber; ++i) {
      solver.addConstraint(
          solver.makeLessOrEqual(
              solver.makeDifference(
                  timeDimension.cumulVar(routing.end(i)),
                  timeDimension.cumulVar(routing.start(i))),
              onDutyTimeLimit));
  }