# 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 from: 3 seconds
• Picking up a box, determining the correct cage is behind me, placing the box in the cage: 4 seconds
• Picking up a box from a presorted pile and placing it in the correct cage: 2 seconds
• Picking up a box and placing it in a cage without sorting: 2 seconds (plus the time to find a new job)

For context, the current rate is around 700 boxes per hour (5.14seconds/box). So reducing the average time per box by only 0.5 seconds is a fairly significant change.

What is the most time-efficient way to move the boxes from the shelf to the correct cage? Solutions to simplified versions of this problem are also welcome.

• I don't understand how to view this as an algorithmic problem. What are the choices that you can make at each step? How do those choices affect the total time? At each step it seems there is only one choice: pick up a new box that you have never looked at before. Once you've picked up a box and evaluated it, it seems there is only one reasonable course of action: put it in the cage if it belongs in a cage. I don't see how you could ever profit from choosing not to put it in a cage, if it belongs there. So I'm not seeing what are the degrees of freedom that might affect throughput. – D.W. Feb 9 '18 at 1:54
• @D.W. Sometimes a cage is not available. In that case, you can either wait for the cage, set the box down and pick up a new box, or take time to sort the box on the shelf (to be picked up and deposited in a cage later). – Jacob Jones Feb 9 '18 at 1:58
• I’m currently writing scripts to measure the average time per box for each strategy I can think of. I’m hoping for answers that either draw parallels from existing sort methods (that I may not think to test on my own), or actually show that a given algorithm is the best possible method of sorting boxes. – Jacob Jones Feb 9 '18 at 2:01
• Let me see if I understand. If the cage is not available, and you sort it on the shelf (costing 1 to move the box to a new location), then you break even if it is paired with one other box for the same cage where you did that (because then you only need to evaluate one of them), and you win if it is paired with at last two other boxes. Does that sound right? At that point the best algorithm might depend on the specifics of the workload (distribution of how common each cage type is, etc.). – D.W. Feb 9 '18 at 2:56
• Sounds about right for those numbers. I’ve changed some of those numbers to better fit real world usage though, so it isn’t quite that simple anymore (and I’d like to be able to test different numbers when it isn’t easily done mentally). I’ll post my scripts with descriptions as an answer when I get some time, assuming you and other moderators keep it up as a good question for the site. – Jacob Jones Feb 9 '18 at 4:09

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 them into the cage. There is no need to evaluate any of them -- you already evaluated them and know which cage they belong in.

In this way, each box gets evaluated only once. It'll either be picked up once and evaluated and placed into its correct cage immediately (takes $1+2+1=4$ seconds), or picked up once, evaluated, moved to a new location, then picked up again and placed into the cage (takes $1+2+1+1+1=6$ seconds). You said about 50% of the time a box can go into its correct cage immediately, so we should expect that the average time per box is $0.5 \times 4 + 0.5 \times 6 = 5$ seconds.

Now here's what I admit this is a little bit of a lie. I oversimplified. I assumed that if you pick up a package and it isn't in the cage behind you, then it will belong to one of the next 10 cages. But what if it doesn't? What if it belongs to a cage that won't appear until even further in the future? This is the bad case. In this bad case, all you can do in this strategy is put it back into the arrival zone. Eventually, at some point in the future it'll be picked up again, and maybe then you can do something more productive with it. The cost, though, is that this means occasionally a box will have to be evaluated more than once.

So in reality, the actual average time per box will be more than 5 seconds per box. It might not be too much more. But exactly how much more depends on how often you pick up a box and discover it belongs to a cage that won't appear for a long time (how often the bad case occurs).

Of course the number 10 (the number of regions in the holding zone) is arbitrary and can be tuned. You can make it larger, to reduce how often the bad case arises; this will reduce the average time per box, at the cost of increasing the amount of shelf space you need. Of course, in practice if you make the shelf too large, then that'll actually increase the time it takes to pick up boxes and put them down somewhere else, so eventually that will be counterproductive. Alternatively, you can make that number smaller; this will reduce the amount of shelf space needed, at the cost of increasing the average time per box.

So I think this is worth a try. Its effectiveness will depend on details of the distribution of when boxes arrived vs when their cage appears, which aren't specified in the question, but if you have data on that, you should be able to simulate this strategy and see how well it will work.

# Second-level refinement of the above strategy

If you like this strategy, there is a refined version of it you could also consider. The refined version is more complicated but might reduce time per box even a little further. Divide the shelf into three zones, an arrival zone, a holding zone, and purgatory. The holding zone is divided into 10 regions, labelled 0-9, as before. Purgatory is also divided into 10 regions, labelled 0-9.

The scheme is exactly as before. The only difference is what we do if you pick up a box and discover its correct cage is at least 10 cages into the future, but less than 100 cages into the future. In that case, you put it into purgatory. You place it into the region corresponding to the next-to-last digit of the cage it belongs to. For instance, if you currently handling cages 112-117, and you pick up a box that belongs to cage 176, then you can't put it into the holding zone, but you can put it into purgatory; and you put it into the region labelled 7 of the purgatory.

Now, when a new cage arrives, do the same as before to move all boxes from the corresponding region of the holding zone into the cage. Also, for every 10th cage that arrives -- in particular, when a cage arrives whose last digit is 5 -- go to the corresponding region in purgatory and sort all of those boxes into the cages or the holding zone. About 60% of those boxes can be placed directly into a cage behind you, and the remaining 40% can go into the holding zone.

Again, there is nothing special about the numbers 10 here. You can adjust the number of regions in the holding zone, and the number of regions in purgatory (they don't need to be the same number, either), to trade off shelf space vs time per box. I don't know whether the extra complexity of this scheme will be worthwhile, but it's a natural extension to the idea above.