Pick-path optimization

Code by John J. BARTHOLDI, III and Sriram SUBRAMANIAN

The problem

What is the shortest path by which an order-picker can visit a given set of locations in a warehouse? This is an instance of the “Traveling Salesman Problem”. H. D. Ratliff and A. Rosenthal showed how to construct a minimum-length path within polynomial time by dynamic programming (cite). Here we implement a simplified version of their algorithm. This allows only limited backtracking and so can be slightly suboptimal (though rarely in practice), but is much easier to code.

How this can be useful

Travel in a warehouse is usually waste; and it comprises most of the labor cost. You can use this program to reduce this waste:

• See each order or batch: The program will allow you to page through a collection of orders and examine the sets of locations to be visited.
• Visualize the paths followed by your order-pickers: Are they are efficient? Are there obvious impediments? Where are your busy spots?
• Evaluate your warehouse layout (arrangement of rack and locations of sku's): by measuring their effects on travel by order-pickers.
• Evaluate design alternatives: How deep should the aisles be? How much benefit would be realized by concentrating popular sku's near the aisles?
• Evaluate batching strategy: What would be the effect of increasing batch size by 10 percent? Of batching by region of the warehouse?

Here is an example of how the program can compute and show the shortest possible pick paths:

A model of your warehouse

For our purposes we treat the warehouse as a network of storage locations, as suggested in this figure:

Each dot represents a position along an aisle at which an order-picker can stand to pick from either the section of shelf to his left or to his right.

Order pickers can travel between positions (dots) only by following the aisles (lines connecting the dots). An order-picker is assigned a batch (group, collection, set) of pick-lines; then he begins at the red dot, travels in a generally clockwise fashion through the warehouse while picking, and returns to the black dot.

Our program computes the (near) minimal distance route that the order-picker should follow.

To simplify the algorithm we place some small restrictions on the route to be followed by the order-picker: An order-picker must visit all required locations in the Top Zone before visiting any location in the Bottom Zone. Furthermore, he must pick sku's from the Top Zone from left to right; and he must pick all sku's in the Bottom Zone from right to left. Sku's in the Middle Zone may be picked along with those of the Top Zone (when moving left to right) or along with those of the Bottom Zone (when moving from right to left).

Use

1. Describe the map of the warehouse: by preparing a spreadsheet that labels the address of every section of shelf and specifies distances. (Here is an example that you can adapt.) Then save this as a text file that will become input to the program.

   In this example, you can see that the gray area represents named sections of shelving and the white area are aisles through which the order-pickers may travel. The leftmost column identifies the two rows that are the basis for out-and-back travel. Measurements are written in the aisles.

2. Provide a list of storage locations to be visited: This is simply a text file containing a single column whose values are addresses of sections of shelf. Typically you would generate this from an order history. (Here is an example in which the addresses correspond to the warehouse described in the previous step.) Note that the names of the storage locations must be unique: They can appear in only one place in the map of the warehouse but are otherwise arbitrary. The program will find them in the map of the warehouse you prepared in the previous step and will deduce travel paths and distances.
3. Specify what sort of travel is permitted: After you have loaded the warehouse layout and the list of locations to be visited, a popup will allow you to specify some details about exactly how an order-picker is allowed to travel:
   • Is an order-picker allowed to traverse the Top Cross Aisle? If not, he must travel from the Upper Mid Cross Aisle into and directly back out of the aisles of the Top Zone to pick a location such as x in the figure above.
   • Is an order-picker allowed to use the Bottom Cross Aisle? If not, he must travel from the Lower Mid Cross Aisle into and directly back out of the aisles of the Bottom Zone to pick a location such as z in the figure above.
   • Is an order-picker allowed to travel completely through a mid Zone aisle, from Upper Mid Aisle to Lower Mid Aisle? If not, he must travel all the way from the left to the right end of the warehouse before turning downwards and returning via the Lower Mid Aisle.
4. Specify how to batch the addresses to be visited: Finally, the popup will also allow you to specify how pick-lines are to be batched. Currently, batching is done simply by taking the next n addresses, where you specify the value of n. Alternatively, if you have prepared your input as a list in which each row has two entries, location and batch name, then the program will group the picks by batch name. This allows you to experiment with different methods of batching (for example, you could generate batches exogenously and then test the result using our program).

Run it from here!

Please read the license and disclaimers, then click to launch the latest version via Java Webstart:

If you are running the program for the first time, Java Web Start will download it (one jar file totaling only 68kb). The next time it will check only for modified jar files (an upgrade) and download them. If there has not been an upgrade, the application will start immediately.

Need Java?

This program is written in Java so it runs on any brand computer and any operating system. If you do not already have Java installed, get the latest version of J2SE by clicking here.

Need help?

It is rather tedious to prepare the description of your warehouse and we are working to make this simpler. In the meantime, if you need help preparing your data or need a modification to the program, please contact me. I cannot promise immediate assistance but if your problem is of general interest, I will either attend to it myself or perhaps engage my students to work on it.