TECH TALK PRESENTATION
ON
Efficient Algorithms for
Solving the Traveling
Salesman Problem in
Large Graphs
Presented By : Omkar Reddy
Ammareddy
Presenter's id : 25951A66B8
Class : CSE (AIML)
Semester : 01
Subject : Essentials Of
Problem Solving (ACSE02)
What is the Traveling Salesman Problem
(TSP)?
The TSP asks: given many locations, what is the shortest route that visits
each once and returns home? Think of a delivery driver planning a day of
stops — the aim is to save distance, time, and cost.
Simple idea Real life
Visit all cities exactly once and return Used for deliveries, service routes,
to the start. and travel planning.
Why is TSP Hard to
Solve?
The number of possible routes grows extremely
fast as we add more cities. Checking every route
becomes impossible for large numbers —
computers run out of time and power.
Combinatorial growth
10 cities → ~3.6 million routes; 15 cities → billions.
This explosion is why TSP is hard.
Practical example
Planning 50 delivery stops: too many routes for
brute force — we need smarter ways.
Simple Approach: Brute
Force
Brute force tries every possible route and picks
the shortest. It is easy to understand but only
works for very small problems.
When it works
• Very few cities (4–8)
• Teaching or checking correctness
Real-life tiny example
Choosing the best route for a short weekend trip visit
4 towns.
Smarter Approach:
Branch and Bound
Branch and bound builds partial routes and abandons
any branch that already looks worse than the best
route found so far. This prunes many possibilities and
saves time.
01 02
Step 1 Step 2
Start building routes Estimate a lower bound
step-by-step. for each partial route.
03
Step 3
Discard branches with bounds worse than current best.
Heuristic Algorithms: Good Enough,
Fast Solutions
Heuristics find very good routes quickly but don’t guarantee the absolute best. They are practical wh
matters more than perfect optimality.
Nearest Neighbor 2-opt swaps
Always go to the closest unvisited city next. FastImprove a route by swapping two edges to
and easy to explain. remove crossings and shorten distance.
Advanced Heuristic: Lin–
Kernighan
Lin–Kernighan is a strong heuristic that performs
smart multi-swap moves to improve routes. It finds
high-quality solutions for medium-size problems
quickly.
How it helps
Performs complex swaps that simple heuristics miss,
reducing total route length significantly.
Real example
Pizza chain optimizing many local deliveries to cut delivery t
and keep food hot.
Cutting-Edge: Divide
and Optimize (DualOpt)
For very large instances, we split the big problem into
smaller regions, solve each region, then merge and
refine. Modern systems add machine learning to
guide merges and improvements.
1 Divide
Partition the map into regions.
2 Solve
Use good heuristics inside each region.
3 Merge & Improve
Combine solutions and run refinements like
local search or learning-based tweaks.
Real-Life Applications
of
TSP Algorithms
These methods matter in logistics (save fuel), manufacturing (tool paths on chips), genetics
(ordering DNA pieces), and astronomy (minimizing telescope moves). Small improvements
lead to big savings.
Summary: Why
Efficient TSP
Algorithms Matter
1 Core point
Exact methods are good for small problems;
heuristics and divide-and-conquer scale to large
ones.
2 Impact
Better routes save time, money, and reduce emissions i
real-world operations.
3 Takeaway
Choose the method that matches problem size
and time limits: teach the idea, show examples,
and use heuristics for large graphs.
Practice explaining one example per slide while
pointing to the images — it makes complex ideas
feel simple.
TH A N K
YOU!!
