The shortest path between two points is a straight line—but figuring out the shortest path between multiple points in a crowded warehouse is a little more complex. Thankfully, Katalyst’s own Senior Software Engineer Wayne Ma and Chief Systems Architect Dave Schuler teamed up to develop a patent-pending algorithm that can quickly map out an optimal route based on bin distribution.
“In running a warehouse, the largest expense item is payroll,” says Schuler. “What that means in practical terms is that the more stuff an individual warehouse worker can pick in a unit of time, the more cost-effective the warehouse is to run.” Typical practice is to give workers a list of items to pick and a sequence in which to go about this. Two more common strategies are “S-shaped” (see below left), where workers follow a systemic, serpentine path, and the “largest gap” model (below right), in which they enter an aisle on one or both ends to the minimum point necessary to grab items.
The History
The challenge of plotting out the most efficient path is by no means a new phenomenon. Rooted in the classic “traveling salesman problem” first posed on record in the 19th century, for their efforts Ma and Schuler evoked Dijkstra’s A* algorithm from 1959 that maps the shortest path between multiple destinations. Dijkstra claimed that he developed the design in about 20 minutes, but it took a bit longer for the Katalyst team.
“We’re solving a more complicated problem,” says Schuler, noting that in its purest form A* only calculates the distance between individual points and does not account for barriers in the path. “The problem we’re solving is a global optimization of the pick path. It took us a couple of weeks to do that, and we’ve been refining it ever since and improving the performance.”
The project originated in May 2017, when Schuler’s boss Allen Frank, President of Retail and SCM at Katalyst Technologies, challenged him to craft an optimized pick path for a large home improvement brand. Schuler walked up and down every aisle at one of their stores for three days, mapping out their entire layout and bin structure (1400 bays), which was then encoded into a machine-readable map of coordinates. When there’s a list of items to pick and it’s correlated with the bins in the database, the algorithm goes to work.
The Process
Using simulated annealing, a process that involves evaluating various solutions one at a time and measuring their effectiveness—“If it’s good enough, you stop,” says Schuler—Ma admits that the algorithm might not end up on the absolute shortest pick path, but that its result will provide the most efficient option given time and computing power. Their use of A* calculates a path, compares it to another path, and the algorithm favors the more optimal one. This process repeats until there’s a satisfactory answer.
“If we have [a list of] 30 or 40 items, it will consume a lot of computing power,” says Ma. “If you want to get the shortest [path] by what we call the greedy algorithm, which is just calculating all possible routes and then comparing, it will take at least two or three days to get our results. That’s why we use this.”
“You don’t have to sit around waiting for it,” says Schuler. “It’s typically a second. It’s very fast.” It also offers an advantage over similar programs in that it can handle a warehouse of any shape, even a circular one, and account for any obstacles that could disrupt a path. Additionally, Schuler believes that the Katalyst algorithm is the only solution offered as a service, meaning that it is not tied to a single program and can be integrated with any warehouse management system. “That’s a big difference and a big advantage of our approach,” he says.
Ma and Schuler both feel confident in the algorithm’s potential to revolutionize the warehouse management industry and continue to explore new methods of growth and development. If you’re interested in learning more, check out their white paper, and reach out to them at Katalyst to see how your organization can benefit from this innovative algorithm.
