I recently encountered the idea of traveler salesman problem with one of the foreseen advancement in the quantum computing era. To be honest, I heard of it as calculating the best possible route and always assumed that problem is well solved with Google Map's super accurate route planners. Apparently that's not the case.

In the daily life, we only plan for the shortest route in point to point. While Google Map is great at estimating the road construction, it is not meant to use for a pick up driver with 10s of locations.

They call the challenge NP-complete. As you add one more travel destination, the complexity increases exponentially.

Historical Background

The problem has been long formulated in the math academic. The challenge was defined in 1930 in Vienna. Since then, the algorithm was well explored. In fact, people believe they can handle optimization among millions of destination with sampling technique.

The only bottleneck is its speed. It just takes stupidly long.

The innovation

Today, the reasonable maximum limit is 16 destinations. And professor Takayuki Kawahara came along and declared more efficient mechanism that can handle 22 cities which would have taken 1200 years with the conventional method.  He implemented the optimization at the hardware level which he names it spin cell.

In other words, it's not only quantum computing, but many researchers are trying to improve such process in many ways. The future is bright, yet it only shows us the problem has not been solved yet.

Interest

Traveler salesman is an isolated toy example. The real world exmaple is full of constraint. How much fuel do you have? How much time can you afford at a specific destination before getting hit by the traffic jam? Is there a rapid one day delivery order you need to go back and pick up?

All of them need considerations.

That's where I'm interested in.

As I was a frequent traveler myself, planning logistics is insanely painful. Google Map is really good at  finding transport from the airport to the hotels, it is not good at coming up with travel plans (how much time I should spend on each sight) when the sight you want to visit can be more than 10.

There are many robotics dispatching system that's going to be interesting as well in the era of self-driving cars and the spread of automated mobility.