What is the best way to algorithmically sort physical boxes?

I work part time at UPS. Part of my job consists of taking boxes from in front of me, determining if the correct cage (1 of 6 moving cages) is behind me (true about 50% of the time), and then putting the box down either in the cage or back in front of me. There can be 6-20 boxes in front of me at any given time depending on box size (essentially the available storage for the sorting algorithm). Each time a box is removed it is replaced with another random box, if there is room for that box. If the next box is particularly large, 3-4 boxes may need to be removed first (meaning that removing a box does not guarantee a new box will appear unless the total number of boxes is sufficiently small). The number of boxes can be considered infinite (UPS does ship nearly all of Amazon’s boxes, after all).

I’m trying to figure out the best strategy for sorting these boxes, partially to work faster and partially for fun.

A few more details

• 2 boxes cannot be picked up at the same time (they can be up to 70 lbs). The boxes can, however, be slid sideways. This means a box can be picked up and inserted between other boxes, but two non-adjacent boxes cannot be swapped in a single movement.

• Boxes can be stacked. However, the stack still needs to be put into the cages one by one. Stacking can reduce the number of comparisons needed (because you know all boxes in a given stack go to a certain cage), but not the number of movements required.

• Boxes must be picked up to be evaluated

• 1 cage will disappear and a new cage will appear every 10 seconds, in a predictable order

• If the correct cage is not behind me, I must either wait for the cage or set down the box on the shelf and select a new box

Computational time (seconds)

• Picking up a box: 1

• Evaluating a box: 2

• Placing a box in its original location: 0

• Placing a box in a new location: 1

Examples:

• Picking up a box, determining that the correct cage is not behind me, and putting the box back where it came f

I'll analyze some basic strategies, show that always stacking is best in your model, and then discuss a more sophisticated strategy.

Analysis of basic strategies: never stack

The simplest strategy is one where you never stack boxes: when you pick it up, if it doesn't belong to a cage behind you, you put it back down where it was. Heuristically, I expect the "never-stack" strategy requires an average of 7 seconds per box. Not good.

Why? We can model the number of times we pick up a box as a geometric distribution with parameter $0.5$; thus the average number of times you need to pick it up is 2. You spend 3 seconds each time you pick it up, including the time to evaluate it; plus 1 second more to place it into the cage, for a total of $2 \times 3 + 1 = 7$ seconds.

I'm making an assumption here that might not be quite right... but it's probably in the ballpark. Anyway, it suggests that "never stack" probably isn't a good strategy.

Analysis of basic strategies: always stack

The other extreme is to always stack boxes that can't be placed into the cage behind you. I will assume that, as you specified in a comment, for each stacked box you perfectly remember what cage it belongs to, so once a box is stacked you never need to evaluate it again.

This strategy takes 5 seconds per box, which seems pretty good. Why? Look first at the boxes that end up getting stacked. We've spent $1+2+1=4$ seconds for each box in the stack to move it into the stack, and we'll spend $1+1=2$ more seconds per box in the stack to move them all to their cage when it arrives, for a total of $6$ seconds per box. 50% of the boxes get stacked. The total time per unstacked box is 4 seconds, and the total time per stacked box is 6 seconds, for an average time per box of $0.5 \times 4 + 0.5 \times 6 = 5$ seconds.

Not bad. The great thing about always stacking is that you avoid ever evaluating any box twice.

If we think about it a bit more, it appears that "always stack" is the optimal strategy: it's not possible to lower the time per box any further. Once you've picked up a box and know it doesn't belong into a cage behind you, what are your options? You can either stack it or not. If you stack it, it'll take only 2 seconds more to deal with that box in the future. If you don't stack it, it's guaranteed to take at least 3 seconds more to deal with it again in the future, no matter what, maybe more (1 second to pick it up again, 2 seconds to evaluate it). So given your assumption that you memorize the cage number of each stacked box, but don't memorize the cage number of boxes that you didn't stack and put back in their original place -- always stacking is optimal.

So what's wrong with always stacking? Why wouldn't you always want to stack? Stacking does have a cost. It requires enough shelf space for all possible stacks. If shelf space is limited, that might potentially be an issue. Also in practice if you make the shelf too large, then that'll presumably increase the time it takes to pick up boxes and put them down somewhere else (since you have to walk further to reach the place where the stack belongs), so eventually that will be counterproductive. Also, the more stacks you have, the more the burden on your memory (since you have to remember the cage number for each stack), which presumably isn't realistic once the number of stacks gets too large.

So perhaps we should consider "shelf space" or "number of stacks" as a limited resource as well, and consider whether we can construct a strategy that is almost as fast as always stacking, but doesn't require as many stacks. With that motivation, I propose a more complicated strategy, next.

More sophisticated strategy: limited number of stacks

I'll describe a possible strategy where we try to achieve close to the same efficiency as always stacking, but with a limit on the maximum number of stacks we'll ever have. This allows a tradeoff between shelf space vs time spent per box.

Divide the shelf into two zones, an arrival zone and a holding zone. Divide the holding zone into 10 regions, labelled 0-9. Each region can hold one stack, so at any point we'll have at most 10 stacks. New boxes show up at the arrival zone. I will assume that the cages are numbered sequentially (e.g., currently cages $i,i+1,\dots,i+5$ are behind you and cage $i+6$ will be the next to appear, and cage $i+7$ will be the next after that, and so on).

At each step, pick up a box from the arrival zone. You can pick any one arbitrarily. Evaluate it. If it belongs to one of the cages behind you, put it there. Otherwise, if it belongs to one of the next 10 cages to appear, put it into the holding zone. Select the region corresponding to the last digit of the cage it belongs to. For instance, if it belongs to cage 176, put it in the region labelled 6 of the holding zone.

When a new cage arrives, go to the corresponding region in the holding zone, pick up all of the boxes and place the

StackExchange Computer Science Q#87875, answer score: 3