Travelling Salesman Problem Is Not A Problem, It’s A Herculean Task.

There is one problem that never goes out of fashion even though people in mathematics have tried to optimize solutions for it over decades. Yes, decades! To nobody’s surprise, the Travelling Salesman Problem (read: TSP) remains to be one of the most fascinating and complicated algorithms to innovate upon. The solutions to this problem only have a chance of remaining straightforward if the problem stops evolving, but this is not the case.

What is the objective of TSP?

The problem statement has remained the same over the years: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” In 1930, right in the very beginning, this was one of the most well-formulated optimizations which is still a powerful solution for logistics-related problems. It was only later that variations in the TSP problems made a disruptive difference in many other areas (one of them even being DNA sequencing).

TSP is no longer problem of the salesman of a company travelling to multiple cities in the least amount of time, using the least amount of money, while somehow travelling the shortest distance. It is about the world gearing towards Industry 4.0.

While we begin to figure out how to integrate the most cutting edge technology in manufacturing, TSP already gave us access to a wide variety of operations. Do you want to design an efficient micro-chip? A TSP variation could do that. Do you want to optimize the set-up cost of a paint manufacturing plant by rearranging the vicinity of colours? An asymmetric version of TSP can do that.

Is the travelling salesman problem solvable?

But let’s consider the basic problem itself. If we were to optimize the logistics of a travelling salesman, the present day application of it has the most monetary pressure on it than ever in history.

Even if you kept the problem within city limits, it would be a problem big enough to become news.

Please note, this is a real problem at a time when we prefer convenience over everything. A country’s GDP rests on its e-commerce purchases, something that TSP enthusiasts didn’t see coming five decades ago.

Fun fact, India’s e-commerce industry would have contributed $300bn by 2030, and no matter how many digital payments fly around and sale-season orders are recorded, the entire brunt of it rests on the backseat of a delivery bike/transport. There are tremendous costs associated with this, especially with return logistics being a pain-point.

What complicates the TSP logic further is the ground reality where the whole market is dependent upon cash-on-delivery, making it impossible to tell if a delivery will earn its cost back sometimes.

Another place where this problem manifests is in ride-sharing. Someone who carpools to work heavily depends on affordable and comfortable transportation, and this twice-a-day practice that happens during rush hour is not easy on anyone. There is added time and pressure for picking up each passenger, the constant deviation from the ‘main route’ to drop off the others, and the stress associated with it cannot be optimized.

Using the Hungarian method

If you want to feel the intensity of the problem closely, try solving it using the Hungarian method. Let’s assume that one delivery executive makes 15 stops in a day, it would still be too large to optimize by hand. And now let us consider the ride-sharing example where the car has to make four stops: picking up three passengers, and returning to the point of origin. Assume and allocate costs between rides, do not repeat the same route twice and solve the TSP to arrive at the minimum cost.

The calculation seems quite simple (for now), but try scaling the execution of such ‘optimised’ routes to handle deliveries worth $300 bn. It would not only blow your mind but quite possibly the RAM of your computer too.

It seems a bit unfair that such a big computational problem which, in all fairness, has taken decades to solve has suddenly grown cancerously large. And the life of this rests in the hands of a few.

Bottom Line:

The good news, however, is that there is immense scope of optimizing such routes with the help of technology. It’s just a matter of asking the right questions?—?which, what, how and why. Which entrepreneurs discover what problem first and how/why they solve it.

The e-commerce brands may not know it yet, but a solution to this problem exists. A solution where you won’t have to make any of the calculations to find the most effective, efficient, productive way of getting your products to your customers on time, thereby earning lifetime loyalty for your brand. Don’t believe it? Try LOCUS.

Want to solve real-life TSP and VRP? Check out the Locus

This post was authored by: Sreshtha Das