Bin packing + VRP

[Víctor Martínez]

Hi!

I am very new to OR-TOOLS and optimization in general. I have made some examples in Python but I am facing issues trying to model my problem.

I want to program a 3D bin packing problem, in which I need to pack a list of items in different trucks (bins), minimizing the number of bins used. However, since the items must be distributed to clients in the city, the optimal route to deliver all the items of a bin will have a "route duration". Thus, I want, not only to minimize the numbers of bins, but also the route duration. Since route duration depends on the current solution, I have a nested optimization problem that could be modelled as 3D bin packing + VPR.

Is it possible to model this with OR-TOOLS? If yes, what type of optimization should be used (CP/SAT, linear, etc)?

I supposed this is too complicated, so I thought about using OSRM (http://project-osrm.org/) routing, which in the end it is just a library that optimizes the "best" route to deliver a truck. Therefore, the "route duration" of a bin can be just accessed by calling to this library. By doing this, I have another problem: since I cannot model that call to the OSRM library in the CP/SAT model, I would need to call to the function whenever OR-TOOLS proposes a intermediate solution, is this possible?

What would be your approaches here?

Thank you!

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

Hi,

this question was asked just last week. You should look it up on the forum.

here is a link to Laurent's reply: https://groups.google.com/g/or-tools-discuss/c/-oMRw3RZ8VI/m/oMXOx2WPAgAJ

On your second point, OSRM is a routing library yes, but it only gives
the path and/or distance for point to point trips. One cool feature
is the ability to snag a whole matrix of trip times and distances in
one call.

This matrix is needed for the call to ORTools, whether CPSAT or
Routing.

It really depends on what the primary problem is. If the hard part is
the bin packing, then go with CPSAT solver and try to simplify the
routing. If the routing is hard, use the routing solver and simplify
the bin packing part.

So, for example if you expect to visit just a handful of destinations
to deliver the contents of the truck, then you can probably insert
that step using CPSAT's circuit constraint. If you need more than
just a few destinations, of if you have a lot of trucks/customers,
then the routing problem is probably best served by the routing
solver.

Personally, I can't see a scenario where you really have to go to town
on the binpacking side of things though. Trucks are large, so in
practice if you add one more truck, you'll have plenty of space to
load more stuff and can ignore the need for the optimal load out from
bin packing.

Maybe run a few scenarios in the bin packing optimizer and get an
approximate average capacity per truck if you use a reasonably fast
heuristic, then use that figure as the capacity for your trucks in a
routing solver implementation.

Good luck
James

On Tue, Apr 27, 2021 at 07:48:29AM -0700, Víctor Martínez wrote:
> Hi!
>
> I am very new to OR-TOOLS and optimization in general. I have made some

> examples in Python but *I am facing issues trying to model my problem*.

>
> I want to program a 3D bin packing problem, in which I need to pack a list
> of items in different trucks (bins), minimizing the number of bins used.
> However, since the items must be distributed to clients in the city, the
> optimal route to deliver all the items of a bin will have a "route
> duration". Thus, I want, not only to minimize the numbers of bins, but also
> the route duration. Since route duration depends on the current solution, I

> have a nested optimization problem that could be modelled as *3D bin
> packing + VPR.*
>
> *Is it possible to model this with OR-TOOLS?* If yes, what type of

> optimization should be used (CP/SAT, linear, etc)?
>
> I supposed this is too complicated, so I thought about using OSRM
> (http://project-osrm.org/) routing, which in the end it is just a library
> that optimizes the "best" route to deliver a truck. Therefore, the "route
> duration" of a bin can be just accessed by calling to this library. By
> doing this, I have another problem: since I cannot model that call to the

> OSRM library in the CP/SAT model, *I would need to call to the function
> whenever OR-TOOLS proposes a intermediate solution, is this possible?*

>
> What would be your approaches here?
>
> Thank you!
>

> --
> 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/123f44f6-0b76-4fb3-9499-ec61c42183b8n%40googlegroups.com.


--

James E. Marca
Activimetrics LLC