Automation Systems 5 min read

The Traveling Salesman Problem and the Mobile Robotics Revolution

In today’s increasingly on-demand world, speed and efficiency are imperative. Whether it’s flying non-stop from Los Angeles to London, or using your smartphone to get around a traffic jam, we all want to get from point A to point B the quickest way possible. But what happens when you also need to get to points C, D, E, and F?

That’s the Traveling Salesman Problem.

The Traveling Salesman Problem (or TSP) is a classic algorithmic problem in the field of computer science that’s focused on optimization. The TSP asks the question: “If you have a list of cities you need to visit, and the cities are different distances from one other, what‘s the shortest possible route that will take you to each city and get you back to your point of origin?”

It seems like it’s a fairly easy problem to solve, right? Just pick the closest city, then the next one closest to that one, and on down the line. But once you arrive in Chicago, with both Boston and Denver roughly 1,000 miles away in opposite directions, it becomes more complicated. In fact, every time you add another city into the equation, the problem becomes harder to solve — exponentially harder — with possible routes quickly soaring into the billions and requiring a tremendous amount of computational power and time to solve.

The TSP is particularly relevant in the world of e-commerce. How? If you think of pickers in a warehouse as traveling salespeople, and the locations of the thousands of items in the warehouse as different cities, it’s easy to understand why walking time is one of the biggest expenses for fulfillment centers: it’s simply too difficult for people to figure out the quickest path through the warehouse to retrieve multiple items without logistical assistance. That’s why most fulfillment centers employ different picking strategies, including batch, wave and zone picking. This makes picking more efficient, but it still doesn’t fully solve the TSP.

The Traveling Salesman Problem Visualization

     (Image credit: n Sanity – YouTube)

The TSP belongs to a class of problems known to mathematicians as NP-Complete, meaning that no efficient algorithmic solution has been identified. The best we can hope for is an approximate solution that will not be optimal but will be reasonably close. Another such example is the knapsack problem, which can be applied to packing items in a shipping box.

Developers of mobile robotics systems, including inVia Robotics, study the TSP in order to streamline and accelerate the fulfillment process. Using machine learning, AI and heuristics, a robotics management system (RMS) examines all customer orders and quickly identifies the optimal routes for retrieving multiple items. Autonomous mobile robots (AMRs) are then dispatched throughout the warehouse to pick the items’ totes and bring them to the picking station. All of this happens in the background in a system that continuously crunches data and optimizes automatically.

And while our ongoing work attempting to solve the TSP is concentrated on perfecting warehouse automation solutions, a potential solution would have far-reaching implications for everything from global shipping networks and last mile delivery, to the rapid rollout of autonomous vehicles, to breaking unbreakable encryption codes. To put it bluntly: solve the Traveling Salesman Problem and you change the world.