Robots in one of JD.com’s fully automated warehouses. Image/JD.com
In the height of the COVID-19 pandemic, with global lockdowns in full force and crowded supermarkets posing unknown risks, millions around the world were forced to venture online for their day-to-day necessities.
But as demand for goods surged, how could online retail warehouses rapidly process hundreds of thousands of orders per day, while still ensuring a safe and socially distant work environment?
Robots have been an important part of the online, retail processing pipeline in recent years. Since 2020, robots have also reduced the need for warehouse staff to work in close proximity. But with the uptick in online purchasing, businesses also need reliable optimization systems so that the growing number of warehouse robots can process orders with speed and accuracy–without colliding with each other in the busy maze of aisles.
Enter John Carlsson – the Kellner Family Early Career Chair at the USC Viterbi School of Engineering –along with his collaborators from Shanghai University of Finance and Engineering. Carlsson, who is an associate professor in the Daniel J. Epstein Department of Industrial and Systems Engineering, was approached in 2015 by China’s largest retailer, JD.com. The online shopping giant was looking to create a system for unmanned warehouses and needed a workable system to optimize their robots.
“At any given instant you’ve got orders that need to be fulfilled in the warehouse, you’ve got robots on the floor, and you have to figure out which robot is going to go and pick up which item in the warehouse and drop it off at which station for processing,” Carlsson said.
“JD.com’s warehousing area is about 17 million square meters, distributed over about 700 warehouses so that’s a lot of retail space to cover. Around 100 of their warehouses are now unmanned.”
Carlsson and his team developed a method based on the mathematical system of combinatorial optimization, where an optimal solution must be found from combination of steps and a finite set of solutions. The system allows JD.com’s robots to accurately process orders for same day delivery and has reduced storage costs by 50%. It has also allowed the company to process 10 times the normal amount of product, and enabled them to quickly adapt to the sudden demands of the pandemic.
The work was recently nominated for a prestigious 2021 Franz Edelman Prize from the Institute for Operations Research and the Management Sciences (INFORMS), a leading international award for analytics and operations research.
Carlsson said the team was particularly proud that their optimization system made use of a process called random stow, in which unrelated products are scattered in random locations on shelves across the warehouse. It’s something that may seem completely illogical to the human brain, but robots are perfectly capable of managing this system.
“You have toothbrushes next to shoes, next to Samsung galaxy phones,” Carlsson said. “Humans need to have a good mental map of how a warehouse works, but a robot is perfectly comfortable if there are 10 million items in a warehouse and they are scattered out randomly, as long as you’ve got machine intelligence that keeps track of where everything is.”
Carlsson said that in order for the robots to avoid collisions, the team used an “edge disjoint paths” algorithm tool which mapped a path that robots could follow. Paths are edge-disjoint if they don’t have any arcs in common.
“Say I’ve got an order for a Samsung Galaxy phone, and these phones are spread out all over this warehouse in 1000 different locations. And I’ve 150 robots moseying along through this warehouse,” Carlsson said. “I need to determine which robot is going to pick up which Galaxy phone and then which packing station they are going to bring it to for shipping.”
Carlsson said this process was called three-way matching–where the chosen robot is matched with the item they need to pick up and delivered to an assigned packing station. All of this is designed for optimal speed, efficiency and safety.
“Often the packing stations are busy, so for example the packing station in the upper left corner might be totally overburdened, and so the system would tell the robot to go down to the one in the lower right,” Carlsson said.
While Amazon and other companies may make use of similar optimization systems for the robots in their warehouses, Carlsson said there currently wasn’t a wealth of research available on how to create these solutions.
“There’s nothing in the literature about how to solve these kinds of issues, and so, for us it was a good research challenge to build the system from scratch and see where it goes,” Carlsson said.
The 2021 Edelman Award will be presented at the INFORMS Conference on Business Analytics and Operations Research, to be held virtually on April 12-14 2021.
Published on March 18th, 2021
Last updated on March 18th, 2021
