Closed Jylanthas closed 4 years ago
I would say:
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:
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@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)
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 "arccost" 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
@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](https://gist.github.com/Jylanthas/a9878ace7445ffc6f0b7246ff90eac53#file-pdptw_max_dur_issue-py-L296-L310)
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](https://gist.github.com/Jylanthas/a9878ace7445ffc6f0b7246ff90eac53#file-pdptw_max_dur_issue-py-L81). 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
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
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!
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...
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! ;)
@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/
@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.
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)
...
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 internallycumulVar(loc_a ) <= cumlVar(loc_B)
# my bad thinking it was done by the previous methodvehicle(loc_A) == vehicle(loc_B)
constrainte.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 I am facing the same problem @Jylanthas faced.
@Jylanthas comment "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."
I am using this constraint for running 2 staged optimization. routing.solver().Add(routing.VehicleVar(routing.NodeToIndex(1)) == routing.VehicleVar(routing.NodeToIndex(2)))
After getting infeasible and trying PARALLEL_CHEAPEST_INSERTION, it worked for some cases and is very inconsistent.
In some cases, it gives infeasible in 2sec without searching till the timelimit=30sec. routing.status() is 2.
What I am trying to do is this:
It maybe inconsistent? [168, 150, 208, 204, 142, 1, 218, 58] these are locations served by the same vehicle after optimizing.
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). when I add same vehicle constraint for (168, 150), I get Infeasible in 2sec. I am not increasing the number of locations. I am using the same problem, optimizing it, taking solution and adding same vehicle constraint, reoptimizing, and it is failing.
@270ajay thanks for picking this back up. I'm still very curious though I had to move on to other things and never fully got it to work.
@Mizux I would be happy to run further tests with your guidance. The gist I posted is a good repro. I can re-explain if you'd like. Perhaps we're not understanding some fundamental limitation of local search related to local optima? My main confusion (and it seems also for @270ajay ) is that search terminates early (or never begins, possibly due to infeasible initial solution) with plenty of time remaining and plenty of solution permutations/swaps yet to investigate.
AFAIK the open source FSS (First Solution Strategy) is not good at back tracking so sometime it just can't find any solution.
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 https://github.com/google/or-tools/issues/847#issue-359410845 Thank you!
@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 ...
@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 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:
https://github.com/google/or-tools/blob/48134ce46d0d62b713f62626eb697507408172ec/ortools/constraint_solver/java/constraint_solver.i#L957
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));
}
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
result
expect
plan_dur
<=max_dur
, in the console print, whereplan_dur = dropoff_at - pickup_at
as retrieved fromassignment.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