user-icon user-icon

Reach Us

Please fill out the form below.

Visit our Office

Evanston, IL

500 Davis Street,
Suite #701,
Evanston,
IL 60201, USA

Overview

This document provides a high-level description of the pick path optimization method (patent pending) developed by the authors.

Gaining the 21st century competitive edge requires that you be able to deliver goods to your customers faster and more economically than your competitors. Consequently, optimizing the movement of goods from shelf to transport becomes essential to building long term customer loyalty.

The authors of this paper are Wayne Ma and Dave Schuler, employees of Katalyst Technologies Inc. Katalyst specializes in warehouse management systems for retail and wholesale sales organizations.

The Problem

“Pick path” refers to the route a picker takes through the picking area to complete his or her picking tasks. Since this activity may account for 50% or more of warehouse/store operations, optimizing the pick path can provide quantifiable savings in operating costs.

Identifying an optimized pick path requires the solution of two different graph theory problems: the shortest path problem and the travelling salesperson problem.

Description of the Algorithm

In solution of the shortest path problem we have selected the A* algorithm for its performance and accuracy. A*, an elaboration of Dijkstra’s Algorithm, first proposed in 1959, was initially articulated by Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute in 1968.

A* constructs a tree of paths from the start node one step at a time, identifying the path with the smallest cost. A* is admissible, meaning that it never overestimates of reaching its goal and, because it employs an optimistic estimate of the cost of the path of each node that it considers, will consider fewer nodes than any other admissible search algorithm with the same heuristic.

The time complexity of A* varies but will be no greater than exponential. In most real world situations its complexity will be polynomial.

Our solution to the travelling salesperson problem uses simulated annealing enhanced with some heuristic improvements. Simulated annealing is a probabilistic method of timating the global optimum of a function. In this case the function is the shortest path that traverses all of the bins containing a specified group of stock keeping units (SKUs). At each step of this iterative method the presently selected optimum solution is compared with the value of a nearby solution. If the nearby solution is better than the presently selected optimum solution, it replaces the presently selected optimum solution and the process is repeated.

The optimized path and from bin to bin is determined using A*.

In most real world conditions the computational/time complexity of our optimizing algorithm is on the order of N2 log N.

Our measurements have suggested that this solution is better than either the S-shaped heuristic, traversing the warehouse or store in a systematic serpentine path, or the largest gap heuristic. In the largest gap heuristic, the route starts at the depot, proceeds to the front of the aisle closest to the depot that contains at least one SKU, and this main aisle is traversed up to and including the bin farthest from the depot containing at least one SKU. Each aisle is entered as far as the “largest gap”, the gap being the distance between any two adjacent SKUs.

If the largest gap is between adjacent SKUs the return route is through both ends of the aisle. If not, a return route from either the front or the back of the aisle is used.

Test Cases

Consider the following. In our first scenario there are five orders of one SKU each

Scenario 1

Employing the S-shaped and largest gap heuristics the pick paths would be:

S-Shaped

Largest Gap

while employing our algorithm produces an optimized pick path:

Scenario 2

In our second scenario there is one order consisting of four different SKUS:

IEmploying the S-shaped and largest gap heuristics produces the following pick paths:

S-Shaped

Largest Gap

while employing our algorithm produces the following optimized pick path:

Scenario 3

The third scenario consists of four different orders with a total of six SKUs:

Employing the S-shaped and largest gap heuristics the pick paths produces the following pick paths:

S-Shaped

Largest Gap

and our algorithm produces the following optimized pick path:

These results are summarized:

Conclusion

As can be seen our optimized algorithm produces notable savings. In addition to producing an optimized pick path our algorithm has certain other advantages over either of the other two heuristics. It is not limited as the other two heuristics are to stores or warehouses laid out in rectangular rows and aisle but may be used in stores or warehouses with any layout including

Circular
Radial
or Complex

When all of these advantages are considered our algorithm is clearly a superior approach to solving one of the most common problems in store/warehouse management.

References

Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B. (1979). "Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases". Sov.Phys. Crystallography. 24 (5): 519–524.

Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4. 4 (2): 100–107

Kees Jan Roodbergen, "Routing order pickers in a warehouse"