Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Pickup and Delivery with alternatives #968

Closed
GuyBenhaim opened this issue Dec 9, 2018 · 24 comments
Closed

Pickup and Delivery with alternatives #968

GuyBenhaim opened this issue Dec 9, 2018 · 24 comments
Assignees
Labels
Help Needed Modeling/Usage problem Lang: Python Python wrapper issue Solver: Routing Uses the Routing library and the original CP solver
Milestone

Comments

@GuyBenhaim
Copy link

GuyBenhaim commented Dec 9, 2018

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 GuyBenhaim changed the title Pickup and Delivery with options Pickup and Delivery with alternatives Dec 9, 2018
@GuyBenhaim
Copy link
Author

Any tips, please?

@Mizux
Copy link
Collaborator

Mizux commented Dec 14, 2018

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

@Mizux Mizux added Help Needed Modeling/Usage problem Lang: Python Python wrapper issue Solver: Routing Uses the Routing library and the original CP solver labels Dec 14, 2018
@GuyBenhaim
Copy link
Author

GuyBenhaim commented Dec 14, 2018

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
Copy link
Collaborator

Mizux commented Dec 14, 2018

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
Copy link
Author

Thanks!
Will check this.

@jmarca
Copy link
Contributor

jmarca commented Dec 14, 2018

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
Copy link
Contributor

jmarca commented Dec 15, 2018

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
Copy link
Collaborator

Mizux commented Dec 17, 2018

@jmarca thanks for the feedback !

@GuyBenhaim
Copy link
Author

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

@GuyBenhaim
Copy link
Author

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

@jmarca
Copy link
Contributor

jmarca commented Dec 17, 2018

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
Copy link
Contributor

jmarca commented Dec 17, 2018

@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
Copy link
Author

Thx,
Need to review the code to better understand.

@Mizux
Copy link
Collaborator

Mizux commented Dec 18, 2018

@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
Copy link
Contributor

jmarca commented Dec 18, 2018

@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 (

DisjunctionIndex AddDisjunction(const std::vector<int64>& indices,
) and it looks like that change was made in October maybe? Looking at the commits, I think it happened b027e57#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
Copy link
Contributor

jmarca commented Dec 19, 2018

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
Copy link
Author

Will check that, Thx.

@Mizux
Copy link
Collaborator

Mizux commented Dec 20, 2018

@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
Copy link
Author

GuyBenhaim commented Dec 20, 2018

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
Copy link
Collaborator

Mizux commented Dec 20, 2018

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

for PD policy follow (Notification: subscribe) #961

@Mizux Mizux added Solver: Routing Uses the Routing library and the original CP solver and removed Solver: Routing Uses the Routing library and the original CP solver labels Jan 10, 2019
@jmarca
Copy link
Contributor

jmarca commented Jan 17, 2019 via email

@abduakhatov
Copy link

abduakhatov commented Oct 14, 2019

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
Copy link
Author

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

@abduakhatov
Copy link

@GuyBenhaim Thanx for reply!
The latter one

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Help Needed Modeling/Usage problem Lang: Python Python wrapper issue Solver: Routing Uses the Routing library and the original CP solver
Projects
None yet
Development

No branches or pull requests

4 participants