I loved reading this, because it feels like it's only the start. Now I'm really curious (and if anyone can point me to resources) --
1) Surely there are a bunch of more obvious optimizations, like don't place candies where they would fall because of gravity and nothing supporting them underneath, or always placing the candies in order of largest to smallest, and ignore anything symmetrical or rotationally equivalent to a previous solution... and how much would this reduce the search space?
2) What is the actual metric for fitting in a box "in the best way"? That lower layers are as full as possible before adding upper layers? That shifting of contents is minimized while upright? That shifting of contents is minimized in any orientation? To minimize small gaps and try to make non-used space as contiguous and compact as possible? Or is the box size arbitrary and the goal is to find the minimal box volume?
3) Is there separately a metric for "good enough"? Should the metric not to be to fit in a specified box, but rather find the smallest box of a set of standard box sizes that can fit the candies, with any arbitrary arrangement rather than a "best"? Is this a much easier problem, or is it just as hard or harder?
I feel like Amazon must have solved this for all practical purposes.
I suspect that it would work well and be fast if you simply place items in order from largest to smallest by volume, filling from bottom to top, quickly determine which box sizes are too small, and then just find the first arrangement that works. Curious if there are pathological cases where that wouldn't work?
> I feel like Amazon must have solved this for all practical purposes.
Given that I have, more than once, received a huge box from Amazon holding an extremely small item, I don't think they have unless they're really bad at packaging stock management and had to stuff things into whatever they had available?
(To be fair, it has been infrequent but then I'm just one person and I don't believe I'm a statistical anomaly which suggests that at Amazon scale, it's happening thousands of times a day.)
> unless they... had to stuff things into whatever they had available
I assume that's exactly what happened.
You don't have to be "really bad at packaging stock management", you just have to have a supplier that is late delivering certain box sizes on a certain day. Late fulfillment is far more common than late ordering when it comes to automated systems like these.
(And the more days' worth of box stock you try to maintain in case box delivery is late, the more it costs you in warehousing. So occasionally getting a box too big is probably going to be economically optimal, when the box suppliers aren't completely perfect in supplying on time.)
Also all these boxes have to be within reach of the picker… I’ve been getting more ersatz boxes (just kinda cardboard wrapped around a single book and glued) from Amazon, probably so they don’t have to keep a huge number of pre sized boxes in stock.
When you're forced to piss in plastic bottles and wear diapers to work because the time it takes to walk to a bathroom and back can cost you your job, you're not going to go out of your way to find the right-sized box for every item.
Amazon employees are just scrambling to meet inhumane and unrealistic metrics set and enforced by assholes and algorithms that have zero concern for human rights, health, or dignity.
There are many reasons we've stopped ordering from Amazon, their treatment of their human employees being the main one. The proliferation of fake products and reviews being another. The hostile anti-competitive business practices towards small businesses is yet one more reason, and I could keep going.
I saw a recent poll that many Americans list Amazon as their favorite retailer, and it blows my mind. Do people really need same day delivery on consumer goods, for the not-low cost of the aforementioned problems?
> Do people really need same day delivery on consumer goods
No, but what I do need is low prices, reliable deliveries, easy returns, and a lot of customer reviews with photos and videos so I can get a sense of what the product actually is, and what kinds of things people like about it, and what kinds of problems they're having with it.
Amazon is literally the only delivery service in my area that doesn't just leave packages in front of my building to be stolen, but actually follows my delivery instructions for a code that lets them in -- and even has a place to put that in in the first place.
Amazon is the only store where if a product doesn't work or wasn't accurately described in the listing, I can easily drop it off at Whole Foods or UPS without having to box it up and print a label, and I don't have to worry about checking four weeks later whether I actually got refunded on my credit card because they always refund within a couple of hours. I also don't have to worry about submitting a "return request" and then waiting for an "RMA number" and then paying for return shipping.
And Amazon is the only place where popular products across all categories have thousands of reviews, rather than 10 or 5 or just 1, which lets me avoid a lot more returns than I would have to make otherwise.
Amazon sure isn't perfect, but the reality is that it's both cheaper and better than anything else for a large proportion of the things I need to buy.
I did not say it does not have any upsides. I said it's downsides (externalities) far outweigh them.
> Amazon is the only place where X
It will continue to be that way, until every other option closes, and then Amazon reverts to the norms you see elsewhere, because they have no competition remaining and no reason to provide good service.
Amazon really is a terrible retailer. Their search is a complete joke. The reviews are impossible to trust. They'll happily send you counterfeit goods. They rip off designs and new products to replace with their own inferior versions, and even customer service isn't what is used to be.
I think the main reason people use/prefer them is familiarity and availability. There are lots of things that are hard to find in local shops or even other stores online. That's in no small part because of what amazon as done to brick and mortar retail and their online competitors, but I do feel for people who want something but have no idea where they'd even start looking for it except for amazon. The situation is likely to only get worse as search engines grow increasingly less useful.
Even when you want to quit them it can be hard to escape amazon. It's work to try to determine the trustworthiness of random storefronts you've never heard of before entrusting them with your credit card info, and I've even heard stories of people who ordered from other sites, paying more than they would have on amazon, only to get their item in an amazon box.
Their product search is... interesting. I used to think that it was programmed by idiots, and wondered how Amazon, with the ability to hire all the expertise in the world, couldn't do better. Then I realised its function is not to give you what you are looking for, it's to maximize Amazon's profits, which it clearly does fantastically well. I would imagine that a lot of heavy-duty machine learning goes into Amazon's product search to make this happen.
Single parents holding down a brutal job(s), areas that are majorly under served by meager retail offerings, folks with mobility impairments, the need for specific items that are hard to get in a timely fashion from other online solutions, the list goes on.
Time in a weekday tends to be at a steep premium for me personally; between Amazon and my local grocery store that offers online ordering and in-person pickup, these offerings are a lifesaver.
In a sense, this will never be solved for outliers. I’ve been the guy the packing guys hate, ordering a few anvils. Is there any reasonable way to package such a thing in cardboard with any amount of duct tape? And that’s when I realized I’m the coyote, but Amazon isn’t acme level yet.
I doubt they have it solved, but I also doubt it is so bad that it the software intends for me to get a single USB4 cable in box suitable for a mini-fridge with a single air packing bag.
If I were cording this for amazon, I would start with a known algorithm, something like the skyline texture atlas packing algorithm. Texture atlases are old school ways to send graphics to GPUs and they had to be certain sizes even if what you wanted to draw was much small. Like if you want to draw single letters, for efficiency packing a whole font and related graphics onto a single bitmap and sending it one go was usually more efficient. This has to do with batches once being very expensive and the only way to send stuff over AGP/PCIE to the GPU, I here it is better now but I don't really know.
The skyline algorithm starts by lining up all the biggest textures along one edge, then it works down the size until one edge was full. Then it fills gaps with the largest remaining textures. This sometimes fails because "largest" is fuzzy, both longest single edge and total pixel can lead to quirks so game specific heuristics often need to be used (like creating a point system for "largest" where each item gets 1 point per pixel and 2 points per pixel if one dimension is over X or something). It was called the skyline packer because if you ran it with just colored boxes what it drew often looked like a low res city skyline, if you rotated it or packed along the bottom edge (but you always pack from topleft out because of how RAM and storage are efficiently iterated and prediction hardware, and other details)
Here is a stackexchange post where they discuss "sorting things in scanline order" by which I think they mean height and then they pack the top edge left to right. If they packed bottom first or if you flip/rotate it you might see the skyline effect, if you squint real hard:
But once that is done for the bottom plane of the box other stuff can be jammed in on top. Also not doing it in... Ruby(?), which is what I think candy Japan used, is likely to help. I like Ruby just fine, but I did a pixel comparisons routine for 1080p screenshots once in it and it took like a minute for one comparison of two images. I wrote a c-extension and that dropped to 1 second. I would guess that modern multithreaded/SIMD C++ or Rust could knock out most Amazon packing sized packing problems exhaustively really fast. Still not a great solution, but 10s per package is likely faster than the human packers can work and I would feel comfortable making such promises to a customer (then hopefully deliver ms length solutions).
And then for bigger problem spaces we can talk Monte Carlo... some other time.
Having worked in ecommerce on both merchant and SaaS side I can explain why they may have and as a customer you will basically never see it applied.
From an engineering point of view, yes you can save so much packaging for the company and optimise for a delivery to be in fewer boxes, which is a fun problem to solve.
From a retail operations point of view the cost of packaging and shipping is negligible and why it’s so often discounted. The real costs though are labour.
Your pick and packing staff are basically all judged on throughput so if someone spends 5 minutes to pack an order in 1 well fitting box they will be fired if everyone else can pack 5 orders in the same 5 minutes.
Generally speaking your packer station is set up so they either have a terminal showing their packing list, a tub of goods to pack for one or more orders, and stacks of different sized boxes.
The stations usually get messy quickly with papers etc all over the place. It’s not a place for precise work and speed is valued above all. In describing the work station I didn’t even mention scanning, taping and labelling of the package that has to happen in the same space too.
Some may argue it’s possible to be both fast and precise, but I would argue it’s not sustainable over an 8 hour shift.
Finally, similar to why potato crisps/chips have so much volume is that inefficient, or spacious, packing is generally better for transport as you are less likely to have goods damage each other from being too tightly packed together.
That’s why IMO generally things are packed sub-optimally from a space use perspective but actually optimally from a convenience and speed perspective.
"Not all retail" - for the place I worked at (doing "optimal" box packing), "box opening experience" was a big thing since it generally got shared on social media, etc. Hence there were constraints about not packing things on top of the feature item, all items had to be label upwards, "best-fit" box to look snug in photos, etc.
(but this place wasn't doing tens of thousands a day, I don't think)
> I feel like Amazon must have solved this for all practical purposes.
Seeing how some of my recent orders have been packaged, I have my doubts.
But there definitely seems to be some algorithmic packing going on. Here's an example that piqued my curiosity:
I just received two bulk DnD miniature sets, a small 3-pack of wolf miniatures, and 2 packs of silicone rings. The miniatures and the rings were ordered in separate carts on different days, but arrived on the same day.
The bulk miniatures showed up in one package (not surprising), but the wolves and ONE of the ring packs were packaged together. The last ring pack came in its own package.
Clearly whatever their algorithm is, it's calibrated to avoid "overstuffing" packages. But why not group like things together? Why put the rings with the wolves?
If anyone has insight into why Amazon's algorithm would do this, I'd love to hear about it.
AFAIK, it's from different items coming from different Amazon warehouses, and nothing to do with "overstuffing".
In your case, one ring pack came from the same warehouse as the wolves, and was the last one. So the other one had to come from a different warehouse and so was packaged on its own.
Amazon tries to distribute its stock across all its warehouses so there's hopefully an item nearby for when you want one-day delivery. But with products that aren't super popular, there's often just one.
Note that if you delay shipping with Amazon Day or no-rush when available, your items are more likely to come in a single package, because that gives Amazon the time to send items from different warehouses to a single one and then package all in one place. This seems to be based on a complicated calculation of whether that will save Amazon money, so it doesn't always happen.
1) Surely there are a bunch of more obvious optimizations, like don't place candies where they would fall because of gravity and nothing supporting them underneath, or always placing the candies in order of largest to smallest, and ignore anything symmetrical or rotationally equivalent to a previous solution... and how much would this reduce the search space?
2) What is the actual metric for fitting in a box "in the best way"? That lower layers are as full as possible before adding upper layers? That shifting of contents is minimized while upright? That shifting of contents is minimized in any orientation? To minimize small gaps and try to make non-used space as contiguous and compact as possible? Or is the box size arbitrary and the goal is to find the minimal box volume?
3) Is there separately a metric for "good enough"? Should the metric not to be to fit in a specified box, but rather find the smallest box of a set of standard box sizes that can fit the candies, with any arbitrary arrangement rather than a "best"? Is this a much easier problem, or is it just as hard or harder?
I feel like Amazon must have solved this for all practical purposes.
I suspect that it would work well and be fast if you simply place items in order from largest to smallest by volume, filling from bottom to top, quickly determine which box sizes are too small, and then just find the first arrangement that works. Curious if there are pathological cases where that wouldn't work?