The world’s leading publication for data science, AI, and ML professionals.

Hands-On Delivery Routes Optimization (TSP) with AI, Using LKH and Python

Here's how to optimize the delivery routes, from theory to code.

Photo by Mudit Agarwal on Unsplash
Photo by Mudit Agarwal on Unsplash

The code of this article can be found on this GitHub folder.

One of my favorite professors throughout my studies told me this:

"Just because your algorithm is inefficient, it doesn’t mean that the problem is hard"

This means that if you want to solve a whatever problem (easy or hard), there will always be an approach that is naive enough to be extremely inefficient. For example, let’s say you have to go to work in a new workplace. Instead of using Google Maps, you start from your house’s alley and try all the possible combinations of the streets (north, south, west, and east). By the time you will arrive to work your company might be filing bankruptcy or having you fired.

Let’s try to be a little more formal. Let’s say that in whatever business or engineering environment, you have to find the minimum or maximum of a function. For example, your company has to maximize revenue from the sales of a given department. We call this function f. The "strings" you pull, meaning the decisions that you can take to maximize the revenue is a vector x. You can’t obviously increase the sales by hiring 10⁶ people a week or making people work 18 hours a day, so you obviously have some constraints. So we say that you can make these decisions in a decision space X. So the task is this:

Let’s assume the f function is linear.

If you had to do this naively you literally stand no chance, because the space is continuous, meaning you would have to explore a closed infinite space: if x¹ is between 0 and 1, you have infinite numbers between the boundaries and the same applies for all the other variables, combinatorially. So if you have 10 variables it is like infinite¹⁰ to explore. Nonetheless, this problem can be solved with a method called simplex. This algorithm only focuses on the vertices of the X space and solves the problem in 2^n (for the worst case) where n is the number of variables of your problem. Most of the time, the runtime is actually n³, so way quicker than 2^n.

So going back to our question. Is the problem of optimizing your sales in a linear function "hard"? Not really, but if you are naive enough to try and enumerate all the possible cases then the problem doesn’t only become hard, it becomes impossible.

Now let’s say we are truck drivers. We need to run through multiple cities around the USA. For example, let’s say we need to tour multiple cities on the East Coast starting from Cincinnati, we have to visit Cleveland, Chicago, Minneapolis, New York, Nashville, and Detroit:

Screenshot made by author using Google Maps.
Screenshot made by author using Google Maps.

Now, what is the route that minimizes the distance? What is the way to follow so that I can visit all the cities while being the shortest on the road? This problem is known as the Traveling Salesman Problem (TSP).

Now, there is a huge literature on this, and this problem is known to be NP-hard, meaning that there is no known method to solve this problem in n^k computational time, where n is the number of cities and k is a constant. In short, this problem is hard because it is indeed intrinsically hard, not because we are "bad at it".

In this optimization case, what we usually do is find a compromise. We know that it would take a crazy long amount of time to find the guaranteed best solution. So we solve this problem in a way that we cannot actually guarantee to get the best of the best of the solutions, but we can get pretty close to the best solution in a much shorter amount of time. These methods are known as heuristic algorithms. The heuristic algorithm I want to use in this blog post is the Lin–Kernighan–Helsgaun (LKH) algorithm.

1. LKH’s Theory

Optimized route for a large number of cities using LKH. Image from LKH Documentation.
Optimized route for a large number of cities using LKH. Image from LKH Documentation.

So why LKH?

This method is one of the most elegant and efficient methods to solve the Travelling Salesman Problem. The coolest thing about the LKH algorithm is the fact that it scales very very well. LKH has been tested up to almost 2M cities and it is still able to find solutions in a feasible amount of time. Another desirable aspect of this approach is that, even if technically LKH does not guarantee optimality in practice LKH is usually very likely to converge to optimality within a few runs.

The idea of this method is very simple: you start with a random tour, that will have a random initial distance, and iteratively improve it by changing some of the connections and see if this decreases the initial distance. More specifically, for every iteration, you perform the so-called k-opt moves that replace k connections of the original tour, with k new ones. Once you have done that, you compute a quantity called "gain" which is the difference between the total distance of the removed edges and the total distance of the added edges. If the gain is positive, it means the move has reduced the total tour length, and the new tour is accepted. Otherwise, the algorithm discards the change and continues exploring other possible moves. If you run out of options, your algorithm stops. *

  • For more information about this method, you can read the original paper here

This method is fairly simple, but its application is extremely satisfying. Let’s take a look.

2. LKH’s Code

Let’s start by setting up our Python environment and defining the libraries.

I would like to solve this problem in the real world, meaning that I want to take boundaries that come from real areas, not just random points in a 2D space or whatever. For this reason, we will need a library called Folium to display our points on a 2D map. The LKH algorithm is implemented in the library called elkai. The other libraries are just normal ones like numpy and scipy.

We are going to add random pins in the world, and we are going to find the shortest distance route to travel around all these pins.

For this task, I created a script TravelSalesman.py with a class named TaxiDriver():



Let’s walk it step by step.

This class takes two inputs, that have default arguments. The first input is the json file that gives you the boundary box of the random points. For example, I chose to focus on the east coast of the United States. The boundaries are these:

{
    "min_lat": 30.0,
    "max_lat": 39.0,
    "min_lon": -95.0,
    "max_lon": -81.0
}

Write a file like that and put it wherever you want, then pass the path into _route_box_file_.

The other input involves where we are going to store the output. The output of this code will be the optimized route and it will be saved as a map. We can also store random routes as maps for reference.

The maps will be saved in interactive .html files. The only thing you need to provide is the folder where you want them saved. By default, the folder will be _map_folder._

The whole code can be found in this GitHub folder.

3. LKH’s applications

So the whole article can be summarized, coding-wise, in one line:

from TravelSalesman import * 

That we can use doing:

driver_ai = TaxiDriverAI()

Ok, let’s have fun with it. The first thing we do is to adopt the .generate_random_points(n) function to populate the maps with n points. For example, let’s say 100 points.

driver_ai.generate_random_points(num_points = 100)

… and let’s display them (all steps together):

from TravelSalesman import * 

driver_ai = TaxiDriverAI()
driver_ai.generate_random_points(num_points = 100)
driver_ai.static_plot()
Output made by author using code above
Output made by author using code above

Now, given the way we set our system, you would find this map in a .html file named _"random_points_map.html"_ in whatever folder you chose.

So the point is: we have to visit all these n=100 cities. If we examine all the possible paths to visit them we get:

100! = 9.332622e+157 paths

Even if computing a single path takes a nanosecond, you will not be able to visit all the paths. And that is "just" for 100 cities. In short, yes, the problem is bad, but our approach is terrible as well.

So we could say: "Ok, let’s try a random route", using the plot_with_connections() function. This function randomly connects the points of our route.

driver_ai.plot_with_connections()
Image made by author using code above
Image made by author using code above

This is one route, but it is obviously so far from ideal. We go back and forth so many times, waste a lot of gas, and travel a lot of unnecessary distance.

So we can’t visit all the routes, but it’s also very risky to just trust a random path.

In these desperate times, our LKH hero comes into play. If we use the proposed LKH above, we can get a route-optimized solution almost immediately. Is it going to be optimal optimal (meaning the best of all the possible routes)? Maybe, maybe not (we will never know because we can never possibly visit them all), but it will be very close.

All this LKH-talk can be done in one line, using the function find_shortest_path(), which applies elkai’s LKH to find the shortest path

optimal_tour = driver_ai.find_shortest_path()

The output for this particular example is:

Elkai Optimized Tour: [0, 4, 90, 78, 3, 8, 98, 77, 55, 10, 35, 70, 52, 82, 49, 58, 42, 54, 60, 2, 81, 36, 37, 74, 7, 85, 25, 57, 43, 71, 67, 47, 50, 26, 87, 79, 28, 56, 23, 66, 34, 75, 64, 88, 39, 63, 80, 29, 45, 38, 9, 73, 20, 46, 32, 22, 44, 33, 18, 13, 91, 97, 21, 83, 61, 11, 40, 24, 19, 14, 99, 93, 89, 72, 53, 65, 68, 48, 51, 1, 59, 31, 95, 96, 76, 41, 69, 92, 6, 17, 16, 94, 86, 15, 84, 27, 12, 5, 62, 30, 0]

And as it is supposed to be, we go back to the original point (otherwise it wouldn’t be a "tour"). If we use the .display_optimized_route(tour) function, we are able to display the optimized route:

driver_ai.display_optimized_route(optimal_tour)
Image made by author using code above
Image made by author using code above

Ok, now we are talking. Our algorithm is defining an optimized route that doesn’t make us waste months of our lives retraveling the same roads. This plot itself is the beauty of LKH and why I think this algorithm is so elegant and brilliant.

Just to reiterate, do we know that this is the best out of the 10¹⁵⁷ routes? Absolutely not. Is it a pretty good solution? Absolutely yes, and we can see that, by eye, we are indeed being pretty smart into finding the best routes out of so many cities.

4. LKH’s limitations

LKH is known to be a pretty good Traveling Salesman Problem (TSP) solution. Now, optimization experts can disagree with it and they might have a point. For example, Dynamic Programming (DP) guarantees an optimal solution but it’s way more expensive. Methods like Genetic Algorithms (GA) are intriguing, because they iterate from a route and find a better and better solution with a "survival of the fittest" approach. People are also improving LKH using reinforcement learning, awarding a higher score for a shorter distance of a proposed route. There are people dedicating their lives to the TSP and they are doing an amazing job at it.

On another note, the main issue of LKH’s is probably not (or not only) it’s complexity but rather its intrinsic static nature.

In real life we don’t travel in an absolute perfect world where the time to go from A to B depends only on the distance between A and B: we travel on roads. This means that traffic, time of the day, gas stations (and their prices), condition of the roads, delivery urgency are all factors that should be included (and they are not). One can think: "Ok then, let’s not optimize on , but on where convenience is a sum of all the other factors". The problem with that is this approach considers fixed factors. Methods like Dijkstra’s Algorithm are more suitable, while other approaches use Machine Learning methods to predict the time to arrive from A to B (if we do that, then we can apply LKH on the predicted times).

5. Conclusions

Thank you for "travelling" with me throughout this blog post 🙃

In this blogpost, we explored the optimization problem known as "Travelling Salesman Problem". In particular, we did it following these steps:

  1. We discussed "hard" optimization problems. An optimization problem is "hard" not necessarily because our algorithm takes a lot of times to solve it. Most of the times, the brute force approach is not feasible but that doesn’t mean that the task itself is "hard".
  2. We described the Traveling Salesman Problem (TSP), that is the problem of optimizing a "tour" of multiple points, minimizing the distance.
  3. We talked about the LKH algorithm. First we described the theory of it, then we implemented a class LKH algorithm, using Python and the elkai’s library.
  4. We applied the LKH algorithm in a real world travelling experiment, by finding the shortest route that allows you to visit all the selected cities on the east coast.
  5. We discussed LKH’s static nature and its limitations.

6. About me!

Thank you again for your time. It means a lot ❤

My name is Piero Paialunga and I’m this guy here:

Image made by author

I am a Ph.D. candidate at the University of Cincinnati Aerospace Engineering Department and a Machine Learning Engineer for Gen Nine. I talk about AI, and Machine Learning in my blog posts and on Linkedin. If you liked the article and want to know more about machine learning and follow my studies you can:

A. Follow me on Linkedin, where I publish all my stories B. Subscribe to my newsletter. It will keep you updated about new stories and give you the chance to text me to receive all the corrections or doubts you may have. C. Become a referred member, so you won’t have any "maximum number of stories for the month" and you can read whatever I (and thousands of other Machine Learning and Data Science top writers) write about the newest technology available. D. Want to work with me? Check my rates and projects on Upwork!

If you want to ask me questions or start a collaboration, leave a message here or on Linkedin:

[email protected]


Related Articles