VRP + 2D packing?

[Peter Yankovich]

Hello all!

Did anyone know how to take into account the optimal layout in the car (2D or even 3D packing) while planning the optimal routes with routing solver?

PS. I found this https://github.com/google/or-tools/issues/625 and issue is closed ("added to 7.7 milestone"). Is it good news? How should i model it, if it already added?

Thanks,
Peter

[Mizux Seiha]

Issue was closed because it's a user modeling issue not a "bug" in the solver.

 To compute the 2D Bin packing you could use the CP-SAT solver and the NoOverlap2DConstraint...
-> Now the challenge is to call this sub routine each time the solver try to add a new node to a route...

[angelo manzatto]

Well, would be good to let a thread like this open for ideas on how to tackle this problem because I am facing almost the same challenge as @Peter, but worse since it involves 3D-BPP (height, width, length) + CVRPTW. 

I was thinking if it is possible to create a callback inside a dimension that uses the CP-SAT solver  each time the  solver try to add a new node to a route?

[Laurent Perron]

I do not think that solving a NP-Hard problem at each node is the way to go.

Why not approximate packing (just use volume with some margin), then solve the rest later. And if really does not fit, then resolve with the residual items.

It will still be much faster than complicating the model.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
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/ce764d41-cb8e-4b60-b444-a34869d04482n%40googlegroups.com.

[Pierre Smith]

Hi,
How can I use CP-SAT solver for routing? Do I understand correctly what I need to create my own alternative to "routing.cc" (original routing.cc was written for CP-solver)?

And another important question:
If I succeed (let's say I was able to rewrite routing.cc for CP-SAT),  could I also use parallelism (multithreading) which present in CP-SAT and doesn't work in original CP-solver?

Thanks,
Peter

среда, 14 апреля 2021 г. в 21:23:35 UTC+3, mizu...@gmail.com:

[Laurent Perron]

you can look at routing_sat.cc which implements some of the routing features.

If you manage to model your problem, you can use parallelism easily.

I do not think the whole trip is worth it from an application perspective, but feel free to try.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--

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/9ef44094-f5bb-4b1e-a00b-1f466ba1a563n%40googlegroups.com.

[Pierre Smith]

Thanks!

пятница, 16 апреля 2021 г. в 11:43:15 UTC+3, Laurent Perron:

[Antonio Braz]

Hello,

I'm also facing this issue and to overcome the challenge of calling a subroutine when the solver adds a new node I was creating a CustomSearchMonitor to override the Next method but there's little documentation on this and I can't see the Next() Method as overridable (I'm using C#), only BeginNextDecision().

Can anyone provide guidance on this approach? Are the some documentation on this?

[Laurent Perron]

Don't. Approximate the packing efficiency by removing some capacity in the vehicle and solve the packing problem once the schedule is fixed. 

--

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/5d6a5f17-c352-4d97-8cd1-dd68f9f9e759n%40googlegroups.com.

[Antonio Braz]

Thanks Laurent.

I'm also trying to address it that way but because I'm dealing with very large items with irregular shapes (construction machinery) relaxing on the vehicle capacity may lead to an empty or half empty vehicle. That's why I was trying another scenario.

Following your approach, my idea is to optimize according to Length or volume. After the solution is found loop through the routes (this is has pickups and deliveries) to check if in some part of the route we have a combination of loaded items that due to it's irregular shapes do not fit into the vehicle (I'm keep a list of those combinations) and then re-optimize with constraints to avoid those situations.

Perhaps adding those constraints right from the beginning works better. I'm concerned if I do it I might be overloading the model with constraints that will not impact the final solution ...need to test it.

[blind.line]

At the risk of making your bin packing solver much slower, you can also include circuit constraints in cpsat to capture the routing problem, to solve both at once. 

James

On Apr 18, 2023, at 05:44, Antonio Braz <amc...@gmail.com> wrote:

Thanks Laurent.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/4e3e094c-9a63-496f-9af1-1d4d3f7095c7n%40googlegroups.com.

[Antonio Braz]

Any quick guidance on how to do that?

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

On Tue, Apr 18, 2023 at 10:17:54AM -0700, Antonio Braz wrote:

Any quick guidance on how to do that? Quick? Ha ha! No, not at all. I've done similar for three projects now, and it is complicated and difficult to get right, let alone fast enough to use on real problems.

There is an example in the cpsat demos using cpsat to solve a vehicle routing problem. I started from there. >{.quotesubsequent} > On Tuesday, 18 April 2023 at 17:35:03 UTC+1 blind.lin...@gmail.com wrote: > > > At the risk of making your bin packing solver much slower, you can also > > include circuit constraints in cpsat to capture the routing problem, to > > solve both at once. > > ...

[Rod Millar]

A couple of points to add. First, in modelling a fleet doing ad-hoc point to point work, the number of jobs on-board concurrently is not likely to be very large, so the bin packing solution is not necessarily a computational burden. Second, the results can be cached to improve efficiency. The only way I could find to enforce a packing constraint in the routing solver was via the 'solution callback' mechanism, which is a bit of a kludge. Being unable to access the the prior node path sequence and associated variables prior to solution also kills a potentially easy solution to modelling an overnight 'return to base  depending on distance  from base'  requirement. Is this limitation fundamental to OR-Tools or just a design choice ?

[Laurent Perron]

Fundamental. It is the requirement for having fast local search.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/276dff8f-c196-435c-861d-2f266126995en%40googlegroups.com.