Taking ideas from physics and a next-generation alternative to conventional electronics, Department of Electrical and Computer Engineering’s Alexander Khitun and Mykhaylo Balinskyy have developed a prototype that can calculate solutions to a problem that has vexed sharp-minded researchers, scientists, and engineers for nearly a century.

Solutions to the Traveling Salesman Problem (TSP) have enormous practical implications for breakthroughs in science and industry. The problem is an example of a research area known as combinatorial optimization, or finding the best option among a range of possibilities that is far too big to check one at a time.

Combinatorial optimization “has applications in artificial intelligence, theoretical computer science, applied mathematics, machine learning, software engineering, and many other domains,” Khitun said. “Other examples of practical applications include developing the best airline routes, deciding which taxis in a fleet to route to pick up fares, determining the optimal way to deliver packages, allocating jobs to people optimally, and designing water distribution networks.”

Scientific applications of TSP solutions include insights into how best to move a telescope the shortest route between two stars and reconstructing fragmentary DNA sequences in the correct order.

The roots of the problem go back to a problem faced by the business of selling door-to-door in 1830s Germany: How could salespeople make one stop at every town and city in a given territory and return to the point where their trip began? This question stemmed from the practical concern of using time efficiently and keeping travel costs low. As originally conceived by Austrian mathematician Karl Menger in the mid-1930s, the TSP poses the following: Given a list of cities and the distances between each pair of cities, find the shortest and most efficient route that visits each city exactly once and returns to the origin city.

Solutions may appear virtually insurmountable because of the staggering number of calculations involved.

In Menger’s scenario, the possible number of routes for five cities is 120, but as the number of cities increase, the number of possible routes increase by a mind-bogglingly enormous factor. The possible number of routes for 10 cities is 3,628,800. For 100 cities, the number of possible routes jumps to 9.3x10153.

“It would take an enormous amount of computer time—longer than the age of our universe—to check all possible routes one by one using all existing supercomputers combined,” Khitun said.

Using conventional computing and algorithms, researchers have typically focused on developing approximate solutions to the problem. But Khitun and Balinskyy developed a prototype device using ideas from electrical engineering, computer science, and spintronics, or the study of electrons’ spin and their magnetic properties. They also utilized, for example, a cutting-edge field called magnonics and a principle in physics known as wave superposition.

“We developed a new approach that has not been considered before,” Khitun said.

Magnonics focuses on information processing and storage using currents of magnons, a particle-like quantity that is derived from a magnetic material. It is considered an emerging alternative to conventional electronics, which relies on currents of electrons. Wave superposition describes how multiple waves—electromagnetic waves, for example—can occupy the same space at the same time without affecting one another. Magnonic waves can travel through different routes at the same time.

“It is equivalent to a large number of salesmen traveling simultaneously through all possible routes.,” Khitun said. “…More than that, it is possible to find the shortest route through the selected cities.”

“It is fundamentally different from the conventional approaches using digital computers, where one can check only one route at a time,” he added.

He and Balinskyy recently published their research, “Traveling salesman problem solution using magnonic combinatorial device”, in Scientific Reports, Nature. Their research was supported, in part, by the Intel Corporation and the National Science Foundation.

Khitun said the method he and Balinskyy developed is “much more practically feasible” than efforts of other researchers to develop solutions using quantum computing.

“There are many groups in the world building quantum computers to solve problems while we have just demonstrated a working device,” he said. “Such a device is of great practical importance for solving a variety of problems.”

For more information about the Marlan and Rosemary Bourns College of Engineering and its educational opportunities in its Electrical and Computer Engineering programs, visit the Undergraduate Engineering Programs website and its Graduate Engineering Programs website.

(Header photo courtesy of Leah Kelley/Pexels)