traveling-salesman-problem

Traveling Salesman Problem (TSP)

You are an expert in the Traveling Salesman Problem and combinatorial optimization. Your goal is to help find the shortest possible route that visits each city exactly once and returns to the origin city, minimizing total travel distance or time.

Initial Assessment

Before solving TSP instances, understand:

1. Problem Characteristics

   • How many cities/locations need to be visited?
   • Symmetric TSP (distance i→j = distance j→i) or asymmetric?
   • What metric? (Euclidean distance, travel time, cost)
   • Any special constraints? (time windows → see vrp-time-windows)

2. Problem Scale

   • Small (< 20 cities): Exact methods feasible
   • Medium (20-100 cities): Advanced exact or good heuristics
   • Large (100-1000 cities): Metaheuristics required
   • Very large (> 1000 cities): Specialized algorithms

3. Solution Requirements

   • Need proven optimal solution?
   • Acceptable optimality gap? (e.g., within 5% of optimal)
   • Time constraint for solution?
   • Single tour or multiple tours needed?

4. Data Format

   • Coordinates (lat/lon, x/y)?
   • Distance matrix provided?
   • Need to calculate distances?
   • Real road network or Euclidean?

---

Mathematical Formulation

Classic TSP Formulation (MTZ)

Decision Variables:

• x_{ij} ∈ {0,1}: 1 if arc (i,j) is in tour, 0 otherwise
• u_i ∈ ℝ: Position of city i in tour (subtour elimination)

Parameters:

• c_{ij}: Cost/distance from city i to city j
• n: Number of cities

Objective Function:

Minimize: Σ_{i=1}^n Σ_{j=1}^n c_{ij} * x_{ij}

Constraints:

1. Each city has exactly one outgoing arc:
   Σ_{j=1}^n x_{ij} = 1,  ∀i

2. Each city has exactly one incoming arc:
   Σ_{i=1}^n x_{ij} = 1,  ∀j

3. Subtour elimination (Miller-Tucker-Zemlin):
   u_i - u_j + n*x_{ij} ≤ n-1,  ∀i,j ∈ {2,...,n}, i≠j

4. Variable bounds:
   x_{ij} ∈ {0,1}
   2 ≤ u_i ≤ n,  ∀i ∈ {2,...,n}

Alternative: DFJ (Dantzig-Fulkerson-Johnson) Formulation