KR

Travelling Salesperson Problem Lecture Notes

Algorithms and their Applications

The Travelling Salesperson Problem (TSP)

  • Instructor: Dr. Mahir Arzoky
  • Course: CS2004 (2024-2025)

Introduction to TSP

  • The Travelling Salesperson Problem (TSP) is a well-studied problem in optimization and heuristic search dating back to the 1930s.
  • Simple to define and significant since solving TSP can help with many real-world problems by demonstrating how they can be decomposed into TSP.

Characteristics of TSP

  • TSP is known to be NP-Hard, meaning there is no known polynomial-time solution.
  • The search space size for TSP is O(n!), representing a huge number of permutations as the number of cities increases.
  • Requires approximate or heuristic search methods (e.g., Hill Climbing, Simulated Annealing) to find solutions or partial solutions.

Definition of TSP

  • A salesperson visits n cities starting and ending at the same city, aiming to minimize the total distance traveled (the tour).
  • The tour signifies a path where each city is visited exactly once.

Distance Representation

  • d(i,j) denotes the distance from city i to city j, adhering to:
  • d(i,j) = d(j,i): distance is symmetrical
  • d(i,i) = 0: zero distance from a city to itself.
  • Example distances among cities:
  • d(1,2) = 3, d(1,3) = 4, d(1,4) = 5, etc.

TSP Solution Representation

  • Solutions can be represented by a permutation of integers from 1 to n, indicating the order in which cities are visited.
  • The total number of permutations for n cities is n! (factorial). The number of possibilities grows drastically; for instance:
  • 4 cities: 4! = 24
  • 10 cities: 10! = 3,628,800
  • 100 cities: 100! ≈ 9.333 × 10^157
  • A possible tour (e.g., [1,4,2,3]) signifies starting at city 1, visiting 4, then 2, 3, and returning to 1.

Calculating Tour Cost

  • The cost of a tour f(T) is calculated by summing the distances between consecutive cities in the tour and back to the starting city:
  • Example calculation with a tour T = [1,4,2,3]:
    • f(T) = d(1,4) + d(4,2) + d(2,3) + d(3,1) = 5 + 2.5 + 2 + 4 = 13.5
    • For T = [1,2,3,4], f(T) = 3 + 2 + 1.5 + 5 = 11.5.

Applying Hill Climbing Algorithm

  • Steps to solve TSP using Hill Climbing include:
  • Knowing the number of cities and their distance.
  • Using a representation for the tour, a random starting point, a fitness function, and a small change operator (such as swapping).

Distance Calculation

  • If given coordinates (xi, yi) for each city, use Pythagorean theorem for Euclidean distance:
  • d(i,j) = √[(xi - xj)² + (yi - yj)²]

Generating Random Permutations

  • To generate a random permutation for cities:
  1. Create a list of integers from 1 to N (number of cities).
  2. Randomly select and remove elements to form a tour.

Fitness Function and Tour Evaluation

  • The fitness function evaluates the length of the tour which we aim to minimize based on the scoring function discussed earlier.

Small Changes to Tours

  • Making changes in a tour must retain it as a permutation:
  • One operational method is the Swap operator, where two elements of the tour are swapped.

Lower Bounds in TSP Solutions

  • To gauge tour quality, lower estimates are needed. A simple approach involves Minimum Spanning Trees (MST):
  • An MST captures the shortest way to connect all cities, providing a lower limit for TSP solution costs.

Minimum Spanning Trees

  • An MST is a sub-graph that contains all nodes with the minimum edge weight sum.
  • For a TSP solution f(TSP(D)), the relation f(TSP(D)) ≥ MST(D) holds, establishing a framework for evaluating efficiency:
  • Efficiency = (MST(D) / f(TSP(D))) × 100%

Applications of TSP

  • TSP can be applied to various fields such as:
  • Vehicle routing
  • Snow plough routes
  • Parcel collection
  • Applications in computer wiring, manufacturing, scheduling, and even DNA sequencing.

Upcoming Activities

  • Next laboratory tasks will involve running and comparing algorithms for solving the TSP with a focus on practical implementation and analysis.