8

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).

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
stats_noob
  • 1,831
  • 7
  • 30
  • 1
    Related post on SO: 3 dimensional bin packing algorithms – SecretAgentMan Feb 11 '22 at 14:52
  • 3
    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 – Chris H Feb 11 '22 at 16:08
  • 3
    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. – Nuclear Hoagie Feb 11 '22 at 17:50
  • 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. – smci Feb 12 '22 at 22:14
  • 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. – smci Feb 12 '22 at 22:16
  • Items bagged in paper bags you don't want to put next to anything chilled/frozen/wet, since it will cause the bag to sog and tear. – smci Feb 12 '22 at 22:18
  • Another consideration: is there any cost penalty on the sorting and stacking time to find an 'optimal' solution? Me, I carry a plastic crate into the store esp. for the chilled/frozen items, and bag/box for the other stuff, and pack it at the register. (Do you only start to pack after getting to car?) Bagging and boxing stuff by compatibility categories like that is massive complexity reduction from say 100 individual items down to 5 bags/boxes. Oh and car interiors aren't regular cuboids, they have wheel arches, tapers, the gap between the edge of a folded-down seat and the door/ front seats. – smci Feb 12 '22 at 22:26

3 Answers3

10

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:

fontanf
  • 2,623
  • 6
  • 11
  • 1
    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. – smci Feb 12 '22 at 22:14
6

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.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
5

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • 3
    Indeed, this is known as "unloading constraints" in the literature and can be found in regular packing problems https://doi.org/10.1016/j.apm.2019.01.022 as well as in problems integrating Routing and Packing https://doi.org/10.1002/net.20192 – fontanf Feb 11 '22 at 18:05