The Traveling Salesman Problem
OSRM v26.6.1
While doing my daily editing of WeeklyOSM, I stumbled upon this announcement by Project OSRM.
So… Out of curiosity, I decided to try the demo page.
At first, I thought the service was just another routing tool. Then I realized that you need at least three coordinates to use it.
Why does it require a minimum of three? I thought two coordinates would be enough to initiate a routing calculation.
Well, I decided to stop complaining and add the third coordinate anyway.
I used three important coordinates — at least for me personally — in Bandung : (1) my dormitory, (2) my campus building, and (3) my rented room, which I frequently used lately after I could no longer access my dormitory.
Sure, it feels like I’m doxxing myself here. But since I no longer live in Bandung these days, I think it’s okay. Haha.
Alright, let’s calculate.
Somehow, the final order was rearranged without my consent. Points (2) and (3) switched places. My rented room became the second stop, while my campus building moved to third.
At that point, I had no idea why it was being reordered like that.
Anyway, let’s analyze the calculated route.
First, from the dormitory to my campus.
Almost 60% of the calculated route overlaps with my usual daily route. However, I almost never use the remaining 40%, even though it seems to be a possible alternative. Why? It feels so isolated and lonely there. Almost nobody uses that route. I would rather take another route (the red path), since most people seem to prefer it.
That said, the alternative route is mainly used by pedestrians. In the demo, I could not find any configuration for whether the route should be optimized for cars, bicycles, or walking. I assume the demo uses cars by default, because it preferred the larger road accessible to cars.
Alright. Not bad.
Now, on to the next one.
Campus to rented room.
Really cool. The demo page successfully discovered the most efficient route that I frequently use in real life. Perfect.
Alright, moving on.
Rented room to dormitory.
It also successfully discovered the route that I frequently used in real life, although I am not entirely sure whether it is actually the most efficient one.
I believe another route (the red path) is more efficient. However, in real life, I stopped using it because there was a large dog roaming around the area. I preferred a safer alternative, even though it required more detouring.
But anyway, I think I misunderstood something important here.
This demo page is not for calculating ordinary routes. It is a TSP solver — the Traveling Salesman Problem.
TSP: given an unordered list of coordinates, it finds the most efficient sequence to visit all of them before returning to the origin.
Although this “efficient” part needs further clarification, especially because of the disclaimer on their GitHub documentation page:
“The trip plugin solves the Traveling Salesman Problem using a greedy heuristic (farthest-insertion algorithm) for 10 or more waypoints and uses brute force for less than 10 waypoints. The returned path does not have to be the fastest one. As TSP is NP-hard it only returns an approximation.”
“The returned path does not have to be the fastest one.” I see.
Appendix A :
Anyway, why did I still frequently travel from my rented room back to my former dormitory? Because I loved the food there. Even though I had moved to another part of the city, it seemed like I could not move on from the exclusive gourmet food that I could only find in that area.
So, almost every night, I would walk from my rented room back there just to enjoy that delicious nasi goreng. It was one of the best nasi goreng dishes I have ever tasted in my life. A flavor I could not find anywhere else in the city, or even in other cities across the country.
Appendix B :
I asked ChatGPT to explain the algorithm to me. Here’s the answer.
The farthest-insertion algorithm is a heuristic method for solving the Traveling Salesman Problem (TSP). It does not guarantee the perfect shortest route, but it tries to build a reasonably good one relatively quickly.
Suppose the points are : A, B, C, D, E
The algorithm usually starts by creating a tiny initial loop.
A common approach is : Pick one point. Find the point farthest from it. Create an initial mini-route between those points.
For example : A ↔ D ↔ A.
Next comes the “farthest insertion” part.
The algorithm looks at all unvisited points and asks : Which point is farthest from the current route?
Why choose the farthest? Because distant points are harder to fit efficiently later. If you ignore them too long, you may end up making a terrible detour near the end.
Suppose E is farthest from the current route.
Now the algorithm does insertion. It tries inserting E into every possible position in the existing route and calculates the cost increase.
Possible insertions : A → E → D → A or A → D → E → A.
The algorithm computes which option increases total distance the least.
Now repeat. Keep repeating until all points are included.
Build a route incrementally → always choose the farthest unvisited point → insert it where it damages the total distance the least.
The full TSP is notoriously hard because the number of possible routes explodes combinatorially. The farthest-insertion heuristic is a compromise. Much faster than brute force, but not always optimal. Its advantage is that it often avoids catastrophic mistakes because it handles awkward, distant points early instead of leaving them for last. That is probably why OSRM uses it for 10 or more waypoints: brute force becomes expensive as the number of points grows, so a heuristic provides a good-enough answer quickly.
Brute force is more optimal because it literally checks every possible route and picks the best one.
The farthest-insertion algorithm is greedy. At each step, it asks : “What seems best right now?” But a choice that looks good locally may accidentally create a worse overall route later. The heuristic cannot know this because it never explores all future possibilities. Once it commits to an insertion, it moves on.
Brute force works differently. Instead of making decisions step by step, it says : “Forget intuition. I will try every possible ordering.” Brute force tests every possible visit order.
With N points, the number of possible routes is roughly (N−1)!
This is why TSP is considered hard.