Forcing all pickup before any delivery

[Vinh Đặng]

Dear all

I am referring to the example: https://developers.google.com/optimization/routing/pickup_delivery

Can I force all the vehicles to go pickups first, then go to deliveries, i.e. I don't want a route like:

pickup1 -> pickup2 -> delivery1 -> pickup3 -> delivery3 -> delivery2

Many thanks

----------------------------------
Best Regards
 
Vinh Dang

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

Yes it is possible, but it is more complicated than you might think at
first.

But the complicated cases only show up in the real world, so maybe you
are just looking to solve a toy problem. In that case the easiest way
is to just require that some cumulative dimension (time, distance,
node count, etc) is lower at all pickup nodes than at all deliver
nodes.

```
for p in pickups:
pidx = manager.NodeToIndex(p)
pt = time.CumulVar(pidx)
for d in delivers:
didx = manager.NodeToIndex(d)
dt = time.CumulVar(didx)
routing.solver().Add(pt < dt)
```

Of course, that is going to fail in interesting ways because the
cumulvar for a node is a function of the vehicle, so you also have to
check that the same vehicle is visiting both nodes. Which probably
means digging through the documentation for examples of applying
conditional constraints, or else maybe this boolean logic hack will
work


```
for p in pickups:
pidx = manager.NodeToIndex(p)
pt = time.CumulVar(pidx)
for d in delivers:
didx = manager.NodeToIndex(d)
dt = time.CumulVar(didx)
sameveh = routing.VehicleVar(pidx) == routing.VehicleVar(didx)
routing.solver().Add(sameveh * pt <= sameveh * dt)
```

But this solution is rarely useful in practice. Instead, what I find
I want to do is keep picking up items until the vehicle is full, then
unload until the vehicle is empty, then repeat. This gets complicated
fast, and the devil is in the details of your particular problem.

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/CAJKBSe4LwFsNZJGoZH%3Dj-pMCKp7yG9uf%2B0e-rq3CRsFQHuww4w%40mail.gmail.com.

--

James E. Marca
Activimetrics LLC

[Mizux Seiha]

What about adding this kind of constraint "after visiting a delivery node, you can only visit a delivery node OR a vehicle's end node"

Something like this:

```
N = all_deliveries_index + all_vehicle_end_indexes

for all delivery nodes d:

  id = manager.NodeToIndex(d)

   routing.NextVar(id).SetValues(N)

```

[Vinh Đặng]

Many thanks James and Mizux

I will try your suggestions

----------------------------------
Best Regards
 
Vinh Dang

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/fe9ee3fb-1664-4ca0-893d-328f8cae8390n%40googlegroups.com.

[hannes]

Alternatively to James' suggestion you could also define a dimension that counts how many deliveries are currently on the tour.

So delivery_counter_callback(x, y) = 1 if is_delivery(y) else 0.

Since pickups should be served before all deliveries, set the delivery_counter_dimension.CumulVar(x) = 0 for all x in pickups.

[Kazi Ahsan]

Hai Mizuk,

Our scenario is very similar to this thread and I am following your answer "after visiting a delivery node, you can only visit a delivery node OR a vehicle's end node" 

Pickup 1 -> pickup 2 -> delivery 1 -> pickup 3 -> delivery 2 -> delivery 3

After putting the below restrictions

delivery 1 -> next possible nodes (delivery 1, delivery 2, delivery 3)
delivery 2 -> next possible nodes (delivery 1, delivery 2, delivery 3)
delivery 3 -> next possible nodes (delivery 1, delivery 2, delivery 3)

I assume the route will look more similar to below

Pickup 1 -> pickup 2 -> pickup 3 ->  delivery 1 -> delivery 2 -> delivery 3 -> stop.

Can we make the route where the vehicle will be starting to do more pick-ups after finishing the delivery, similar to below?

pickup1 -> pickup2 -> pickup3 -> delivery1 -> delivery2 -> delivery3 -> pickup 4 ->  pickup 5 ->  pickup 6 ->  delivery4 -> delivery5 -> pickup 6 -> stop. 

Kazi

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

The way I've done this in the past is to set conditional constraints.

My use case was pickup as much as the solver wanted or to max capacity, but once drop-off started the vehicle should drop off until empty, then it could go back to pickups. The application was with human passengers, and people tend to get angry if they see more passengers getting picked up and they're still waiting for their drop off.

What I did was to set a conditional constraint, with the condition being the load. When at a delivery node, the transition to a pickup node is not allowed only if the load on arrival at the pickup node is zero.

I don't have that project's code handy on this laptop...it was that long ago...but I am sure I cut and paste how I did it to this mailing list so you should search.

James

On Mon, Sep 05, 2022 at 10:15:07PM -0700, Kazi Ahsan wrote:

Hai Mizuk,

Our scenario is very similar to this thread and I am following your answer "after visiting a delivery node, you can only visit a delivery node OR a vehicle's end node"

Pickup 1 -> pickup 2 -> delivery 1 -> pickup 3 -> delivery 2 -> delivery 3

After putting the below restrictions

delivery 1 -> next possible nodes (delivery 1, delivery 2, delivery 3) delivery 2 -> next possible nodes (delivery 1, delivery 2, delivery 3) delivery 3 -> next possible nodes (delivery 1, delivery 2, delivery 3)

I assume the route will look more similar to below

Pickup 1 -> pickup 2 -> pickup 3 -> delivery 1 -> delivery 2 -> delivery 3 -> stop.

Can we make the route where the vehicle will be starting to do more pick-ups after finishing the delivery, similar to below?

pickup1 -> pickup2 -> pickup3 -> delivery1 -> delivery2 -> delivery3 -> pickup 4 -> pickup 5 -> pickup 6 -> delivery4 -> delivery5 -> pickup 6 -> stop.

Kazi On Tuesday, August 31, 2021 at 5:59:53 PM UTC+10 leev...@yahoo.de wrote:

Alternatively to James' suggestion you could also define a dimension that counts how many deliveries are currently on the tour.

So delivery_counter_callback(x, y) = 1 if is_delivery(y) else 0.

Since pickups should be served before all deliveries, set the delivery_counter_dimension.CumulVar(x) = 0 for all x in pickups.

On 31.08.21 06:56, Vinh Đặng wrote:

Dear all

I am referring to the example: https://developers.google.com/optimization/routing/pickup_delivery

Can I force all the vehicles to go pickups first, then go to deliveries, i.e. I don't want a route like:

pickup1 -> pickup2 -> delivery1 -> pickup3 -> delivery3 -> delivery2

Many thanks

Best Regards

Vinh Dang

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/CAJKBSe4LwFsNZJGoZH%3Dj-pMCKp7yG9uf%2B0e-rq3CRsFQHuww4w%40mail.gmail.com https://groups.google.com/d/msgid/or-tools-discuss/CAJKBSe4LwFsNZJGoZH%3Dj-pMCKp7yG9uf%2B0e-rq3CRsFQHuww4w%40mail.gmail.com?utm_medium=email&utm_source=footer .

-- 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/47ee2817-28a4-4284-9a8e-c5d552e2755en%40googlegroups.com.