Or-tools: Pickup and Delivery with alternatives

[GuyBenhaim]

I hope this is not too tricky.
If we have two alternative pickup points A and A' and two alternative drop points B and B'. We can pick from either A or A' and drop at either B or B'. We probably need a disjunction for A and A' and separately for B and B'.

How to create a pickup and drop condition in this case?
Can we combine (A and A') and (B and B') and use one condition?
Or must we have four conditions: A and B, A and B', A' and B, A' and B' ?
(this will become 9 if we also have alternatives A'' and B'')

[GuyBenhaim]

Any tips, please?

[Mizux]

Did you try to play with ActiveVar() ?

A = routing.NodeToIndex("A")
Ap = routing.NodeToIndex("A'")
B = routing.NodeToIndex("B")
Bp = routing.NodeToIndex("B'")

# Same vehicle
routing.solver().Add(
  routing.ActiveVar(A) * routing.VehicleVar(A) + routing.ActiveVar(Ap) * routing.VehicleVar(Ap)
 == 
  routing.ActiveVar(B) * routing.VehicleVar(B) + routing.ActiveVar(Bp) * routing.VehicleVar(Bp)
)

# precedence `time([A,A']) < time([B,B'])`
routing.solver().Add(
  routing.ActiveVar(A) * dim.CumulVar(A) + routing.ActiveVar(Ap) * dim.CumulVar(Ap)
 <= 
  routing.ActiveVar(B) * dim.CumulVar(B) + routing.ActiveVar(Bp) * dim.CumulVar(Bp)
)

with a disjunction only one A or Apshould be active so it may works...
EDIT: remove typo

[GuyBenhaim]

I may need some homework to fully understand this.
still

Can the first term relate only to A and B, and not Ap and Bp? (I suspect B_Index is typo)

constraintActive = routing.ActiveVar(routing.NodeToIndex(A)) *
routing.ActiveVar(routing.NodeToIndex(B_index))

Principally, if we also have A'' and B'' the conditions grow linearly:

# Same vehicle
routing.solver().Add(
routing.ActiveVar(A) * routing.VehicleVar(A) + routing.ActiveVar(Ap) * routing.VehicleVar(Ap) +
routing.ActiveVar(App) * routing.VehicleVar(App)
routing.ActiveVar(B) * routing.VehicleVar(B) + routing.ActiveVar(Bp) * routing.VehicleVar(Bp) +
routing.ActiveVar(Bpp) * routing.VehicleVar(Bpp)
)

# precedence time([A,A']) < time([B,B'])
routing.solver().Add(
routing.ActiveVar(A) * dim.CumulVar(A) + routing.ActiveVar(Ap) * dim.CumulVar(Ap) + routing.ActiveVar(App) * dim.CumulVar(App)
<=
routing.ActiveVar(B) * dim.CumulVar(B) + routing.ActiveVar(Bp) * dim.CumulVar(Bp) +

routing.ActiveVar(Bpp) * dim.CumulVar(Bpp)
)

[Mizux]

yup, that's the point since add_disjunction guaranty only ONE node active or none (and you pay the penalty)

sorry for the first two line copy/paste from other examples don't need these lines at all...

[GuyBenhaim]

Thanks!
Will check this.

[jmarca]

would it also work to use max rather than active var? Something like (in python):

# loop over each "group" of pickup alternatess and delivery alternates
# let "all_pickups" be list of alternate pickups, and 
#      "all_deliver" be list of alternate deliveries
routing.AddDisjunction(all_pickups, penalty)
routing.AddDisjunction(all_deliver, penalty)

pickup_vehicles = [ routing.VehicleVar(routing.NodeToIndex(i)) for i in all_pickups ]
deliver_vehicles = [ routing.VehicleVar(routing.NodeToIndex(i)) for i in all_deliver ]
# values are -1 for inactive, or positive for active
# same vehicle requirement across alternatives
solver.AddConstraint(solver.Max(pickup_vehicles) == solver.Max(deliver_vehicles))

# similar approach to force pickup before delivery
pickup_times  = [ time_dimension.CumulVar(routing.NodeToIndex(i)) for i in all_pickups ]
deliver_times = [ time_dimension.CumulVar(routing.NodeToIndex(i)) for i in all_deliver ]
# deliver *after* pickup
solver.AddConstraint(
                solver.Max(pickup_times) <= solver.Max(deliver_times))

Haven't tested that but is seems okay to me.

One issue I can't see how to solve cleanly is calling the routing.AddPickupAndDelivery() call. It seems in the forthcoming version 7, we will be able to do

pickup_disjunction_index = routing.AddDisjunction(all_pickups, penalty)
deliver_disjunction_index = routing.AddDisjunction(all_deliver, penalty)
# ...
routing.AddPickupAndDeliverySets(pickup_disjunction_index, deliver_disjunction_index)

But... as of 6.10, the AddDisjunction call returns void, and the API call AddPickupAndDeliverySets doesn't exist.

[jmarca]

Actually, what I suggested won't work. I just ran some tests on a simple case and learned by doing...

My assumption was that if a node is not active its CumulVar is zero. This is not the case. Rather it is set to the range of the variable (so if it is a time window, it is the time window). Calling Max on that time window gives the max of the time window (I think).

Further, playing with an auxiliary dimension that starts and zero and increments in order, what I discovered is that (apparently) if a node is in the solution and then rotated out in favor of another valid alternative, it still keeps its earlier CumulVar values, rather than resetting to zero (or to the min/max of the preset range, if any). So even with a non-ranged variable, the constraints that I wrote above will not be valid, as the solver.Max(...) expression might be picking up values from inactive nodes.

[Mizux]

@jmarca thanks for the feedback !

[GuyBenhaim]

Thanks, James.
Could come handy in other cases ...

[GuyBenhaim]

How do I prevent visiting a certain Node A, something like this:
routing.solver().Add(routing.ActiveVar(NodeA) == 0)
?

[jmarca]

Following up on my earlier comment, here is what works for me (code updated to fix bugs pointed out by @Mizux):

# assuming pd_pairs is a minimal set, and I have other data structures to store alternatives
for pair in  pd_pairs.values():
    # these solver-indices are not needed anymore
    # pickup_index  = routing.NodeToIndex(pair[0])
    # deliver_index = routing.NodeToIndex(pair[1])

    # add pickup disjunction
    all_pickups = [ routing.NodeToIndex(pi) for pi in alternatives[pair[0]] ]
    # pdi is placeholder until v7.x comes out
    pdi = routing.AddDisjunction(all_pickups, penalty)

    # add deliver disjunction
    all_deliver = [ routing.NodeToIndex(di) for di in alternatives[pair[1]] ]
    ddi = routing.AddDisjunction(all_deliver, penalty)

    pickup_vehicles = [ routing.VehicleVar(i) for i in all_pickups ]
    deliver_vehicles = [ routing.VehicleVar(i) for i in all_deliver ]

    pickup_active = [ routing.ActiveVar(i) for i in all_pickups ]
    deliver_active = [ routing.ActiveVar(i) for i in all_deliver ]

    # same vehicle requirement across alternatives
    # haven't thoroughly tested that this works without *_active...works for 2 veh
    solver.AddConstraint(solver.Max(pickup_vehicles) == solver.Max(deliver_vehicles))

    # timing constraints
    pickup_times  = [ time_dimension.CumulVar(i) for i in all_pickups ]

    deliver_times = [ time_dimension.CumulVar(i) for i in all_deliver ]

    pickup_cross_active = [p*a for (p, a) in zip(pickup_times,pickup_active)]
    deliver_cross_active = [d*a for (d, a) in zip(deliver_times,deliver_active)]

    # deliver *after* pickup
    solver.AddConstraint(
        solver.Max(pickup_cross_active) <= solver.Max(deliver_cross_active))

    # AND, only allow max of 1 hour over travel time from A to B
    # need to do nested loop here, because travel times are unique for all OD pairs
    for o in all_pickups:
        # need node ref here for travel time lookup
        o_node = routing.IndexToNode(o)
        pickup_cross_active_time = routing.ActiveVar(o) * time_dimension.CumulVar(o)
        for d in all_deliver:
            # need node ref here for travel time lookup
            d_node = routing.IndexToNode(d)
            # here I multiply by both active and origin, active at
            # destination.  Perhaps should just make a
            # conditional...need to test to see impact on runtime
            deliver_cross_active_time = routing.ActiveVar(o) * routing.ActiveVar(d) * time_dimension.CumulVar(d)
            # travel limit is command line option, typically one hour,
            # meaning the item is allowed to be in vehicle no more
            # than one hour over the base travel time from origin to
            # destination.  Think passengers getting upset about
            # picking up other passengers
            travel_time = lookup_fn[o_node][d_node] + travel_limit

            # deliver earlier than pickup time + allowed travel time
            # if not active, 0 <= 0 + travel time, so satisfied
            solver.AddConstraint(
                deliver_cross_active_time <= pickup_cross_active_time + travel_time)


    # routing.AddPickupAndDeliverySets(pickup_disjunction_index, deliver_disjunction_index)
    # this API call isn't available until version 7+

    routing.AddPickupAndDelivery(pair[0],pair[1])
    # not sure if necessary to do a loop for all combinations of alternatives

I ran this a "bunch of times" and manually inspected the output. Did not see any violations of pickups after deliveries, etc. I have not yet automated the checking yet, and I have so far only run with one vehicle (well, multiple vehicles are in problem, but only one is used in the solution because I have only <30 or so items to pickup and deliver during testing). I'll finish up and write this up as a blog post or something.

Typical output looks like:

The Objective Value is 79
Route 0:
   18:: --depot--   Load(0) Time(0:00:00, 0:00:00) 
-> 20:: --depot--   Load(0) Time(1 day, 18:00:00, 1 day, 18:01:00) 
-> 21:: --depot--   Load(0) Time(2 days, 18:00:00, 2 days, 18:01:00) 
->  8:: [0, 6, 8]                Load(0) Time(3 days, 8:14:39, 3 days, 15:56:51) 
->  2:: [2, 14, 16]                Load(1) Time(3 days, 8:33:52, 3 days, 16:16:04) 
->  15:: [2, 14, 16] -- [5, 15, 17] Load(2) Time(3 days, 8:50:46, 3 days, 16:32:58) 
->  1:: [1, 10, 12]                Load(1) Time(3 days, 9:01:07, 3 days, 16:43:19) 
->  4:: [1, 10, 12] -- [4, 11, 13] Load(2) Time(3 days, 9:18:47, 3 days, 17:00:59) 
->  9:: [0, 6, 8] -- [3, 7, 9] Load(1) Time(3 days, 9:38:58, 3 days, 17:21:10) 
-> 22:: --depot--   Load(0) Time(3 days, 18:00:00, 3 days, 18:01:00) 
-> 23:: --depot--   Load(0) Time(4 days, 18:00:00, 4 days, 18:01:00) 
-> 24:: --depot--   Load(0) Time(5 days, 18:00:00, 5 days, 18:01:00) 
-> 19:: --depot--   Load(0) Time(6 days, 23:59:00, 7 days, 0:00:00) 
->  EndRoute 0. 

Route 1: Empty 

[jmarca]

@GuyBenhaim, I think if you want to prevent a node from being visited, the most efficient thing is to just drop it from the problem entirely, right? But otherwise I think you're proposed constraint will work.

[GuyBenhaim]

Thx,
Need to review the code to better understand.

[Mizux]

@jmarca You code seems ok, except one part IMHO, you use alternative[pickup_index] since alternative is your data structure you should use pair[0] as index same for deliver_index.

Also after you use AddDisjunction(all_pickups ... which means all_pickups contains a list of Index (i.e. solver referential) and later routing.NodeToIndex(i)) for i in all_pickups which means all_pickups this time contains NodeIndex (i.e. your referential).

note: I'll try soon to write a Pickup & Delivery example (without multi P and D however)...

[jmarca]

@Mizux I think you mean my code...and I see what you mean about alternative[pickup_index] being incorrect. It works here because the index and the node happen to be the same integer, but yes, a bug that will bite me later. I'll fix it in a little bit just in case someone else comes to this issue and "copy-pastes" my code sample.

Also, it appears the API has changed on the AddDisjunction call, at some point, and I failed to change with it! I see in master branch the call is with indices (https://github.com/google/or-tools/blob/75876db06929f48cdde9c4fa93fbadb7f19a6354/ortools/constraint_solver/routing.h#L539) and it looks like that change was made in October maybe? Looking at the commits, I think it happened https://github.com/google/or-tools/commit/b027e57e95e2f70d17c28d6f6319e57dcbbd46b2#diff-72f6d61ab9adc4958dc30b74a014986fR539. Good, that was annoying...The old way was void AddDisjunction(const std::vector<NodeIndex>& nodes, int64 penalty, int64 max_cardinality); (NodeIndex---is it a node, or an index?) and then had internal calls to node_to_index_[node] inside the routing.cc code.

Update: fixed my code above.

[jmarca]

And relevant to your earlier question @GuyBenhaim, I also did a similar thing to get FIFO constraints working too with alternative origins/destinations. Just multiply everything by the value of ActiveVar, and use solver.Max to get the "actual" value.

[GuyBenhaim]

Will check that, Thx.

[Mizux]

@jmarca Index is internal indices used by the solver. NodeIndex is the indices you usually use for your data structure. All API of routing (methods, callback, solution assignment etc..) takes/returns Index.

• So you must use (in v6.10.X) routing.NodetoIndex(your_node_index) to convert from you data to solver solver and IndexToNode() form solver to your data structure.
  -AddDisjunction() API was a mistake since it use NodeIndex in its API...

v7.0 (currrent master branch):

• RoutingModel::nodeToIndex() have been replaced/moved to the IndexManager() class
• AddDisjuntion() now take Index to be consistent

[GuyBenhaim]

Admin:
Were the C# examples adapted for V7.0, and demonstrate the updated registration of CallBacks, IndexManager, Etc.?

Does it support built-in FIFO/LIFO?

Happy Holidays!

    *
   /\
  //\\*
*//||\\
   ||

[Mizux]

master is v7.0-beta so all examples on master already use v7.0 API...

for PD policy follow (Notification: subscribe) #961

[jmarca]

On Wed, Jan 16, 2019 at 03:19:31AM -0800, Guy wrote:

Closed #968.

--
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub:
https://github.com/google/or-tools/issues/968#event-2077121334

I wrote up the tricky bits of my solution to this on my website:
https://activimetrics.com/blog/pdptw/multiple_alternatives/

(And if it is considered bad form to post that link here, please delete this post.)

James

[abduakhatov]

Following up on my earlier comment, here is what works for me (code updated to fix bugs pointed out by @Mizux):

# assuming pd_pairs is a minimal set, and I have other data structures to store alternatives
for pair in  pd_pairs.values():
    # these solver-indices are not needed anymore
    # pickup_index  = routing.NodeToIndex(pair[0])
    # deliver_index = routing.NodeToIndex(pair[1])

    # add pickup disjunction
    all_pickups = [ routing.NodeToIndex(pi) for pi in alternatives[pair[0]] ]
    # pdi is placeholder until v7.x comes out
    pdi = routing.AddDisjunction(all_pickups, penalty)

    # add deliver disjunction
    all_deliver = [ routing.NodeToIndex(di) for di in alternatives[pair[1]] ]
    ddi = routing.AddDisjunction(all_deliver, penalty)

    pickup_vehicles = [ routing.VehicleVar(i) for i in all_pickups ]
    deliver_vehicles = [ routing.VehicleVar(i) for i in all_deliver ]

    pickup_active = [ routing.ActiveVar(i) for i in all_pickups ]
    deliver_active = [ routing.ActiveVar(i) for i in all_deliver ]

    # same vehicle requirement across alternatives
    # haven't thoroughly tested that this works without *_active...works for 2 veh
    solver.AddConstraint(solver.Max(pickup_vehicles) == solver.Max(deliver_vehicles))

    # timing constraints
    pickup_times  = [ time_dimension.CumulVar(i) for i in all_pickups ]

    deliver_times = [ time_dimension.CumulVar(i) for i in all_deliver ]

    pickup_cross_active = [p*a for (p, a) in zip(pickup_times,pickup_active)]
    deliver_cross_active = [d*a for (d, a) in zip(deliver_times,deliver_active)]

    # deliver *after* pickup
    solver.AddConstraint(
        solver.Max(pickup_cross_active) <= solver.Max(deliver_cross_active))

    # AND, only allow max of 1 hour over travel time from A to B
    # need to do nested loop here, because travel times are unique for all OD pairs
    for o in all_pickups:
        # need node ref here for travel time lookup
        o_node = routing.IndexToNode(o)
        pickup_cross_active_time = routing.ActiveVar(o) * time_dimension.CumulVar(o)
        for d in all_deliver:
            # need node ref here for travel time lookup
            d_node = routing.IndexToNode(d)
            # here I multiply by both active and origin, active at
            # destination.  Perhaps should just make a
            # conditional...need to test to see impact on runtime
            deliver_cross_active_time = routing.ActiveVar(o) * routing.ActiveVar(d) * time_dimension.CumulVar(d)
            # travel limit is command line option, typically one hour,
            # meaning the item is allowed to be in vehicle no more
            # than one hour over the base travel time from origin to
            # destination.  Think passengers getting upset about
            # picking up other passengers
            travel_time = lookup_fn[o_node][d_node] + travel_limit

            # deliver earlier than pickup time + allowed travel time
            # if not active, 0 <= 0 + travel time, so satisfied
            solver.AddConstraint(
                deliver_cross_active_time <= pickup_cross_active_time + travel_time)


    # routing.AddPickupAndDeliverySets(pickup_disjunction_index, deliver_disjunction_index)
    # this API call isn't available until version 7+

    routing.AddPickupAndDelivery(pair[0],pair[1])
    # not sure if necessary to do a loop for all combinations of alternatives

I ran this a "bunch of times" and manually inspected the output. Did not see any violations of pickups after deliveries, etc. I have not yet automated the checking yet, _and_ I have so far only run with one vehicle (well, multiple vehicles are in problem, but only one is used in the solution because I have only <30 or so items to pickup and deliver during testing). I'll finish up and write this up as a blog post or something.

Typical output looks like:

The Objective Value is 79
Route 0:
   18:: --depot--   Load(0) Time(0:00:00, 0:00:00) 
-> 20:: --depot--   Load(0) Time(1 day, 18:00:00, 1 day, 18:01:00) 
-> 21:: --depot--   Load(0) Time(2 days, 18:00:00, 2 days, 18:01:00) 
->  8:: [0, 6, 8]                Load(0) Time(3 days, 8:14:39, 3 days, 15:56:51) 
->  2:: [2, 14, 16]                Load(1) Time(3 days, 8:33:52, 3 days, 16:16:04) 
->  15:: [2, 14, 16] -- [5, 15, 17] Load(2) Time(3 days, 8:50:46, 3 days, 16:32:58) 
->  1:: [1, 10, 12]                Load(1) Time(3 days, 9:01:07, 3 days, 16:43:19) 
->  4:: [1, 10, 12] -- [4, 11, 13] Load(2) Time(3 days, 9:18:47, 3 days, 17:00:59) 
->  9:: [0, 6, 8] -- [3, 7, 9] Load(1) Time(3 days, 9:38:58, 3 days, 17:21:10) 
-> 22:: --depot--   Load(0) Time(3 days, 18:00:00, 3 days, 18:01:00) 
-> 23:: --depot--   Load(0) Time(4 days, 18:00:00, 4 days, 18:01:00) 
-> 24:: --depot--   Load(0) Time(5 days, 18:00:00, 5 days, 18:01:00) 
-> 19:: --depot--   Load(0) Time(6 days, 23:59:00, 7 days, 0:00:00) 
->  EndRoute 0. 

Route 1: Empty 

with VRPTW.py sample, I have following:

A = manager.NodeToIndex(1)
    Ap = manager.NodeToIndex(13)
    B = manager.NodeToIndex(12)
    Bp = manager.NodeToIndex(6)
    routing.AddDisjunction([A, Ap], 1000)
    routing.AddDisjunction([B, Bp], 1000)
    # Same vehicle
    routing.solver().AddConstraint(
        routing.solver().Max([routing.VehicleVar(A) ,routing.VehicleVar(Ap)])
        ==
        routing.solver().Max([routing.VehicleVar(B), routing.VehicleVar(Bp)])
    )

    # precedence `time([A,A']) < time([B,B'])`
    routing.solver().AddConstraint(
        routing.solver().Max([routing.ActiveVar(A) * time_dimension.CumulVar(A), routing.ActiveVar(Ap) * time_dimension.CumulVar(Ap)])
        <=
        routing.solver().Max([routing.ActiveVar(B) * time_dimension.CumulVar(B), routing.ActiveVar(Bp) * time_dimension.CumulVar(Bp)])
    )
    routing.AddPickupAndDelivery(12, 6)

I set different values to penalty, still none of the alternative points returned in result:

Solving
Route for vehicle 0:
0 Time(0,0) -> 11 Time(10,10) -> 15 Time(13,13) -> 0 Time(22,22)
Time of the route: 22min

Route for vehicle 1:
0 Time(0,0) -> 9 Time(2,3) -> 14 Time(7,8) -> 16 Time(11,11) -> 0 Time(18,18)
Time of the route: 18min

Route for vehicle 2:
0 Time(0,0) -> 7 Time(2,4) -> 4 Time(10,13) -> 3 Time(16,16) -> 0 Time(24,24)
Time of the route: 24min

Route for vehicle 3:
0 Time(0,0) -> 5 Time(3,3) -> 8 Time(5,5) -> 2 Time(10,10) -> 10 Time(14,14) -> 0 Time(20,20)
Time of the route: 20min

Total time of all routes: 84min

One more interesting note, when PARALLEL_CHEAPEST_INSERTION is used, the program finishes without solving. LOG:

WARNING: Logging before InitGoogleLogging() is written to STDERR
I1014 19:42:39.059523 3940 search.cc:254] Start search (memory used = 33.98 MB)
I1014 19:42:39.059654 3940 search.cc:254] Root node processed (time = 0 ms, constraints = 160, memory used = 33.98 MB)
I1014 19:42:39.060621 3940 search.cc:254] Finished search tree (time = 1 ms, branches = 136, failures = 73, memory used = 33.98 MB)
I1014 19:42:39.060660 3940 search.cc:254] End search (time = 1 ms, branches = 136, failures = 73, memory used = 33.98 MB, speed = 136000 branches/s)

I think it is more related to @Mizux`s code at the begining

[GuyBenhaim]

Hi,
This is for FIFO or for alternative Pick and Drops?

[abduakhatov]

@GuyBenhaim Thanx for reply!
The latter one