Click Fulfillment

A fictitious Web-based product company has a collection of warehouses. Each warehouse is laid out as a north-south east-west rectangle. The shelves storing the goods are laid out north-south. South of the shelves is a one-way hallway going west. North of the shelves is a second one way hallway also going west. The entrance is at the southeast corner of the warehouse and there are two exits, one at the southwest corner and one at the northwest corner.

The aisles between the shelves are also one way going either north or south. Each robot in an aisle will put items in a mobile cart for a particular customer as the cart advances. Figure 1 shows four aisles with alternating north-direction and south-direction one-way aisles and five shelves. The carts go in the direction of the arrows. Each shelf between two aisles k and k+1 actually consists of two parts, one for aisle k and one for aisle k+1. The robot for aisle k can reach only the part of that shelf dedicated to k. Similarly, for the robot for aisle k+1 as shown in Figure 2.

What is the competitive ratio for baskets of one, two, three, or four groups?

The figures are not to scale. Each aisle is much longer than the width of that aisle as well as the width of the two shelves bordering that aisle. Time therefore is measured in units of aisle traversals (to the north or to the south as appropriate).

Let us say that there are four groups of items A, B, C, and D. For any item in a basket, there is a 1/2 chance the item is from group A (the most popular group), 1/4 from group B, 1/8 from group C, and 1/8 from group D. All the items in any group can be held in one part of one shelf.

Suppose that we have just two aisles and three shelves as in Figure 2. A purchase of items from groups A, B, or A and B together require just one traversal. However, any purchase involving items from C and D requires at least two traversals (go up on the AB aisle and then down on the CD aisle).

Define the competitive ratio to be the number of traversals required for a basket divided by the number that would be the minimum assuming some shelf design in which each shelf part has all and only the items from a single group (called a “pure group” design). Such a shelf design should describe which group to put on each of the two shelf parts dedicated to each aisle and the directionality of each aisle.

Warm-up: For the shelf design of Figure 2, what is the competitive ratio of any basket involving only items from A, B, or both?

Solution to Warm-Up: The competitive ratio is 1 because such a basket would require only one aisle traversal south to north and that’s the minimum possible.

Warm-Up 2: (a) What is the competitive ratio of any basket involving items from C, D or both? (b) What is the competitive ratio of any basket involving items from three or four groups?

Solution to Warm-Up 2: (a) The competitive ratio is 2 because the basket would have to go north on the AB aisle and then south on the CD aisle. Another design in which the CD aisle were one-way going north would require only one aisle traversal. Making both the AB and CD aisles one-way south-to-north would not work however because then a basket requiring at least one item from A or B and another from C or D would not be fillable. (b) The competitive ratio is 1 because no pure design of items on shelves could avoid two traversals for three groups or more.

Challenge 1: How many aisles would be needed to guarantee a competitive ratio of 1 regardless of the combination of groups? Hint: You may not want aisles to alternate one way north or one way south, but rather allow more one-way aisles in one direction than in the other.

Solution: We know that the aisles of Figure 2 (north: AB, south: CD) already guarantee a competitive ratio of 1 for three or four groups. A single north-pointing aisle for CD would guarantee that any purchase from a single group has a competitive ratio of 1. To capture any two groups, we would need the following additional north-direction aisles: AC, AD, BC, and BD. The net result is north: AB, CD, AC, AD, BC, BD and south: CD. Thus seven aisles altogether.

Challenge 2: Suppose we have only six aisles available in our warehouse. How would you design the aisles to minimize the probability of requiring a competitive ratio greater than 1?

Solution: Consider this six aisle design. North: AB, AC, AD, BC, BD and south: CD. The only time there would be a competitive ratio greater than 1 would be if all items belonged to one or both of the two groups C and D. Those are the least likely groups. Any single group, any other pair of groups, or any three or four groups would all achieve a competitive ratio of 1.

Business has been good. The warehouse would like to increase traffic to 160 baskets per minute, but the maximum traffic in any aisle is 40 baskets per minute. Because the vast majority of baskets contain two items, assume we must support 160 2-item baskets per minute with rare purchases of other basket sizes. Based on the probability of an item for each group, we have: AA (the probability that both items come from group A) has probability 1/4 (for example, 40 baskets per minute), AB has probability 1/8 (20 baskets per minute), BA has probability 1/8 (20 baskets per minute), and so on.

Using the seven-aisle design (north: AB, CD, AC, AD, BC, BD and south: CD), we might naively route the baskets in such a way that the first aisle that can satisfy a basket is used. Using naïve routing, 1/2 of all the 2-item basket traffic goes to the AB aisle (the AA, the AB, and the BA), which comes to 80 baskets per minute. That’s too many

Challenge 3: Using the seven-aisle design, please change the routing so no aisle has more than a 1/4 share of the traffic (40 baskets per minute) for baskets of size 2 while keeping the competitive ratio at 1 for all baskets of size two.

Solution: The route scheduling should change as follows: Send all heterogeneous group pairs through the aisles with their names (for example, a basket with an item from A and an item from C should use the AC aisle). By contrast, the AA baskets should be split evenly between the AC and AD aisles, raising them to a probability of 4/16 or 40 baskets per minute each. CC and DD can use the CD aisle, raising that probability to just 4/64 (10 baskets per minute). BB can be split between the BC and BD aisles raising each to under 2/16 (20 baskets per minute). In this way, no aisle will need to support more than 40 baskets per minute.

Upstart 1: What if the vast majority of baskets contained three items instead of two (but possibly not from three groups)? Assuming a total traffic of 160 baskets per minute and eight aisles instead of seven, can you achieve a competitive ratio of 1 for all baskets?

Define the weighted competitive ratio to be the sum over the fraction of baskets for each value of competitive ratio multiplied by that competitive ratio value. Assume we are interested only in pure designs.

Upstart 2: Given g groups, with item-in-group probabilities P, a probability distribution B on the size of the baskets, total basket traffic T, and a maximum number of aisles m, find the aisle design and the traffic schedule that will avoid exceeding aisle capacity and have the smallest weighted competitive ratio.

Upstart 3: With the same architecture, would impure designs (for example, one part of a shelf could have half the items from A and half the items of B) improve the weighted competitive ratio? Hint: Impure designs might help if certain groups are vastly more popular than others.