Approximation Algorithms for TSP in Logistics: The Search for Near-Optimal Delivery Routes
Introduction
On my first day of college I had no idea where I was supposed to go. I remember staring at “SOT CR 10” on my timetable feeling completely lost. As a fresher I did not know what SOT meant — I just assumed it was some classroom code. We ended up walking all the way towards Anviksha before realizing SOT stood for School of Technology. Looking back this was a mistake but it made me think about how confusing navigation can be when there are multiple places involved.
Then when I started studying algorithms I came across a problem in a different context: delivery routing. Imagine a delivery person who has to visit 10, 20 or even 100 locations in one trip. The problem is not how to go from one place to another. The bigger question is: in what order should all of these locations be visited so that the total distance is as small as possible? This is the idea behind the Travelling Salesman Problem (TSP).
Why Finding the Exact Route is Hard
When a problem is represented as a graph every location is a vertex. The distance between two locations is an edge. If a route visits 4 locations A, B, C and D one possible route will be A → B → D → C → A. For four or five locations we can simply check all routes and choose the shortest one. As the number of locations increases, the number of routes increases very quickly. Checking every single option takes too much time for large inputs.
Because the decision version of TSP is NP-complete finding a solution efficiently for large instances is computationally difficult. Therefore , instead of always looking for the exact answer we can use approximation algorithms to find a good route in less time while guaranteeing how far the answer can be from the optimum.
For TSP, where distances satisfy the triangle inequality: c(A, C) ≤ c(A, B) + c(B, C) the classic CLRS textbook uses a 2-approximation algorithm based on a Minimum Spanning Tree (MST).
The number “2” does not mean that the route will usually be twice as long as the optimal route. It means that in the worst case the route produced by this algorithm will cost no more than twice the optimal cost (OPT).
How the MST Algorithm Works
Find the MST: First make a Minimum Spanning Tree that connects all locations with the smallest total edge cost. As an optimal TSP tour also connects all vertices, the cost of the MST is always less than or equal to OPT.
Perform a preorder traversal: Traverse the MST in preorder. Because some vertices are visited again while moving back through the tree the resulting walk may contain repeated locations — for example A → B → D → B → C → B → A. Traversing every edge twice means the cost of this walk is 2 × MST, which is ≤ 2 × OPT.
Shortcut repeated locations: Skip any location that has already been visited and go directly to the unvisited location. Thanks to the triangle inequality taking an edge never increases the total distance. After returning to the starting point we have a TSP tour in which each location is visited once with a total cost of at most 2 × OPT.
A Small Campus Example
To see how this works with an example I used a few locations from my campus: SOT, ANV, the Canteen, SOS and the Library.
I did not have the walking distances between these locations so I used estimated distances based on their relative positions on campus. These values are for demonstration and are not actual measured distances.
For these five locations I first calculated the TSP route by checking the possible orders of visiting them. The shortest route was: SOT → ANV → Canteen → SOS → Library → SOT with a distance of 1210 m.
Get YESHA’s stories in your inbox
Join Medium for free to get updates from this writer.
I then applied the MST-based approximation algorithm. The MST had a cost of 610 m and after performing the preorder traversal and forming the TSP tour the resulting route was: SOT → Canteen → ANV → SOS → Library → SOT with a total distance of 1260 m.
The approximation ratio is: 1260 / 1210 ≈ 1.041.
So in this example the approximate route was 4.13 % longer than the optimal route.
The approximate route cost is significantly smaller than the worst-case limit of two times OPT.
Note: The distances shown are estimated values used only for demonstration.
Why Real Logistics (and Campus Walks) Get Messier
In delivery systems basic TSP is usually a starting point. Logistics companies face constraints such as vehicle capacities, delivery deadlines, driver shifts and multi-vehicle fleets, which transform the problem into the Vehicle Routing Problem (VRP).
I saw a distinction when thinking back to my campus. Finding the path from SOT 201 to ANV 201 is a shortest-path problem. However planning a multi-stop day — going from SOT to the Library to SOS then to ANV and finally to the Canteen — requires that the order of visits truly matters.
If I actually build a campus navigation system I would also need to consider more than distance. The shortest route, measured in meters is not always the option if that route has stairs, a closed entrance or a crowded path. Just as traffic conditions influence delivery routes, walking time and accessibility can also matter.
Conclusion
The Travelling Salesman Problem is an idea that is simple to describe but it becomes difficult when the number of locations increases. Approximation algorithms give us a way to find good routes without spending too much time searching for the exact solution.
The MST-based approach is one example of this. It does not always produce the possible route but for metric TSP it guarantees that the cost will not exceed twice the optimal cost.
The small campus example also showed that the actual difference can be much smaller than the worst-case guarantee. For the estimated distances I used the approximation was about 4.13 percent longer than the optimal route.
For me, what started as confusion over a timetable eventually became a way to view navigation as an algorithmic problem.
References
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms. Chapter 35 , Section 35.2: The Traveling-Salesman Problem.
- GSFC University campus. Personal observations — used only for the illustrative campus example and estimated distances.
