8
$\begingroup$

A situation that we are all familiar with : How do you decide which order to place groceries in your car or which order to place food in your fridge?

enter image description here

At first glance, it appears that the "order" in which you place items might be important. For instance, if you first place a small item and then place a large item on top of the small item, it will likely be a very awkward fit and result in the smaller item being damaged (e.g. a bag of flour on top of a carton of eggs). Thus, it would seemingly make more sense to first place the bigger object and then place the smaller object on top of the bigger object. Especially for many grocery items, it would appear that some orderings might be more optimal compared to other orderings.

Using this framework, can we interpret the order in which you place groceries into your car or food item into a fridge as an optimization problem? I am not sure, but this looks like some type of combinatorial optimization problem that shares aspects with the "Knapsack Optimization Problem", "Optimal Transport Optimization Problem" and "Traveling Salesman Problem" (e.g. which ordering would require lesser steps in terms of reordering items).

$\endgroup$
7
  • 1
    $\begingroup$ Related post on SO: 3 dimensional bin packing algorithms $\endgroup$ Feb 11, 2022 at 14:52
  • 3
    $\begingroup$ Size might make this a classic packing problem, but real groceries are more interesting. Consider a multi-pack of crisps (potato chips). That's far bigger than a tin of baked beans or a bottle of water. Which way up should you stack them? Then how do you measure fragility? Then you've got 2 separate and poorly-correlated variables to optimise $\endgroup$
    – Chris H
    Feb 11, 2022 at 16:08
  • 3
    $\begingroup$ Any situation where you can numerically quantify the goodness of a solution is an optimization problem. If it's possible to say whether one solution is better than another, you can optimize. The crux of the matter is how you turn intuitive rules (e.g., small items on top of big items) into a quantifiable measure. $\endgroup$ Feb 11, 2022 at 17:50
  • $\begingroup$ 3D packing of groceries is more complex and implies extra constraints: some items are chilled/frozen/wet, some are heavy, some are light/squashable/flimsy; some items are loose and might scatter if not propped up/constrained (e.g. unsealed bag of fruit); some items you really do not want to risk overturning (e.g. rotisserie chicken, even if double-bagged). Some items are both heavy and have a smooth underside, so likely to slide when you brake/accelerate(e.g. 12-pack of cans). Perishable items you don't want to expose to sunlight; valuable items you don't want to expose to thieves' view. $\endgroup$
    – smci
    Feb 12, 2022 at 22:14
  • $\begingroup$ Tell us which if any of those implied constraints you want to factor in. You wouldn't pack 10lbs of cans on top of a crate of eggs would you? even if it was 'optimal' for L,B,H. $\endgroup$
    – smci
    Feb 12, 2022 at 22:16

3 Answers 3

10
$\begingroup$

Three-dimensional packing is a well studied class of problems. One of the main applications is indeed truck loading. See this review which lists the different kinds of constraints considered:

$\endgroup$
1
  • 1
    $\begingroup$ 3D packing of groceries is more complex and implies extra constraints: some items are chilled/frozen/wet, some are heavy, some are light/squashable/flimsy; some items are loose and might scatter if not propped up/constrained (e.g. unsealed bag of fruit); some items you really do not want to risk overturning (e.g. rotisserie chicken, even if double-bagged). Some items are both heavy and have a smooth underside, so likely to slide when you brake/accelerate(e.g. 12-pack of cans). Perishable items you don't want to expose to sunlight; valuable items you don't want to expose to thieves' view. $\endgroup$
    – smci
    Feb 12, 2022 at 22:14
6
$\begingroup$

The 3D bin packing problem is very important in additive manufacturing. Many researchers approach this problem as an optimization problem.

So yes, you can approach your stated problem as an optimization problem.


A few relevant papers including a 2020 survey below.

Some interesting pictures of the problem:

  • Multi-objective Optimization of 3D Packing Problem in Additive Manufacturing. 2014. IIE Annual Conference Proceedings, 1485–1494. Wu, S.; Kay, M.; King, R.; Vila-Parrish, A.; Warsing, D.

I am not one of the authors.

$\endgroup$
5
$\begingroup$

In addition to the size and weight considerations, there may also be "order of access" constraints. When shoving groceries in my refrigerator, I tend to use an informal LIFO ordering, which saves me having to pull a bunch of stuff out when accessing something near the back. This also comes up when loading delivery trucks (postal service, Amazon, ...), where you give the driver an ordered list of deliveries and want the boxes being delivered to be accessible in order of delivery.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.