AlgoMaster

Engineering Solutions

Travelling Salesman Problem (Branch & Bound)

Find the shortest possible route that visits each city exactly once and returns to the starting city

Travelling Salesman Problem (TSP)

TSP seeks the shortest possible route that visits each city exactly once and returns to the origin city. Branch and Bound provides optimal solutions by systematically exploring and pruning the search space.

Theory & Concepts

Definition:

Given a list of cities and distances between each pair, find the shortest possible route that visits each city exactly once and returns to the starting city.

Key Points:

  • NP-Hard problem - exponential time complexity
  • Branch and bound uses lower bounds to prune suboptimal paths
  • Optimal solution guaranteed (unlike heuristic approaches)
  • Real-world applications in logistics and optimization

Applications:

  • Vehicle routing and delivery optimization
  • Manufacturing: drilling circuit boards
  • DNA sequencing and bioinformatics
  • Tourist itinerary planning

University Guidelines

Exam Weightage
8-10 marks Marks

Syllabus Coverage:

  • Travelling Salesman Problem formulation
  • Branch and bound technique
  • Lower bound calculation methods
  • Pruning strategies and optimization
  • Complexity analysis and comparison

Common Questions:

  • Solve TSP using branch and bound
  • Calculate lower bounds for TSP nodes
  • Show pruning process step by step
  • Compare with brute force approach

Exam Tips:

Calculate lower bound = path cost + minimum edges
Show pruning when bound ≥ current best
Draw search tree with bounds clearly marked
Mention O(n!) brute force vs optimized branch and bound

Algorithm Details

O(n!) worst case, significantly better with pruning
Time Complexity
O(n) for recursion stack and current path
Space Complexity

Algorithm Steps:

  1. 1Start from city 0 with empty path
  2. 2For each unvisited city, calculate lower bound
  3. 3If bound < current best, explore this branch
  4. 4If bound ≥ current best, prune this branch
  5. 5When complete tour found, update best solution
  6. 6Continue until all promising branches explored

Configure TSP

Distance Matrix:

Enter distances between cities (symmetric matrix)

From\\ToABCD
A
-
B
-
C
-
D
-

Cities:

A
B
C
D

TSP Solution

🌐

Configure the distance matrix and click "Solve TSP" to find the optimal tour