Pickup delivery Problem minumize extra distance per parcel

[lahiru madushanka]

Hi All

In Pickup delivery Problem Can anyone help me  with the constraint and how to use it in the model  for minimizing the additional distance traveled per parcel.  

Thanks

[lahiru madushanka]

Solved it by adding  a constraint. May be useful for someone in the future 

Note- DISTANCE_FACTOR_THRESHOLD  is an scalar >=1 

for request in data['pickups_deliveries']:
  pickup_index = manager.NodeToIndex(request[0])
  delivery_index = manager.NodeToIndex(request[1])

  max_distance_per_parcel = DISTANCE_FACTOR_THRESHOLD*data['distance_matrix'][pickup_index][delivery_index]

  routing.solver().Add(distance_dimension.CumulVar(delivery_index) - distance_dimension.CumulVar(pickup_index) < int(max_distance_per_parcel))

[blind.lin...@gmail.com]

Nice, thanks for sharing.

Similar to my answer to issue 1388
(https://github.com/google/or-tools/issues/1388) and what I wrote up
in my blog post here
https://activimetrics.com/blog/pdptw/multiple_alternatives/ (scoll
down to the heading "Limiting in-vehicle time")

A couple of points.

First, your solution doesn't do what I *thought* you were asking
about. I thought you wanted to actually minimize distance per parcel.

For example, suppose you have two items (or people) picked up from
depot A, with deliveries at B and C, and the vehicle has to return to
A. A perfect example is a shared vehicle service from an airport.

A ----- B -- C


Assume B and C are in roughly a straight line. Then a human
dispatcher would assign the route A-B-C-A. That is, make the delivery
at B, then the delivery at C, then return to A. But the solver would
see A-B-C-A as equivalent to A-C-B-A, that is, driving to C with both
items, delivering at C, then delivering at A.

If distance(A,C) + distance(C,B) <= factor*distance(A,B), then your
solution won't help this case. The solver will be free to pick either
routing.

I came up with an ugly hack to prefer the A-B-C-A route over A-C-B-A
using conditional constraints. I'm pretty sure I wrote it up before
either in the forum or in the github issues, but it is not very
elegant and doesn't deserve repeating. So I'm always on the lookout
for something better, and if you come up with a way to really minimize
time in vehicle for each item, please share.

Second point is that you have to be careful to allow for inactive
nodes if you are allowing nodes to be dropped. Specifically, if your
pickup and delivery pair are both dropped, then might be impossible for the
solver to satisfy the condition:

routing.solver().Add(
distance_dimension.CumulVar(delivery_index) - distance_dimension.CumulVar(pickup_index) < int(max_distance_per_parcel))

If delivery index and pickup index are both dropped, it is NOT the
case that the CumulVar is zero at those nodes. The solver does not
zero out the CumulVar at nodes that were in the solution but
subsequently were dropped from the solution. That is why in my blog
post I have the calls to "ActiveVar()", which is zero if the node is
not active.

(I think I wrote that blog post for V6-era OR Tools, so the API calls
have changed a bit).

Finally, you might want to look into the FIFO/LIFO constraints that
were added a while back for pickup and delivery problems. You might
be able to solve my A-B-C-A vs A-C-B-A problem by setting the FIFO
parameter, for example as used here
https://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/vrp_pickup_delivery_fifo.py.

Regards,
James

> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/07952f23-b2d8-4b8a-b450-3b8b751a6046n%40googlegroups.com.


--

James E. Marca
Activimetrics LLC