Traveling Salesman Problem (TSP)

The Metric TSP imposes the triangle inequality on distances: the direct path between two cities is never longer than any indirect route via a third city. This property, which holds in Euclidean space and road networks, enables the use of efficient approximation algorithms like Christofides' algorithm, which guarantees a solution within 1.5 times the optimal length. It is the most studied and computationally tractable variant, forming the basis for more complex problems.

In the Asymmetric TSP (ATSP), the distance from city A to city B is not necessarily equal to the distance from B to A. This models real-world scenarios like one-way streets, airline routes with differing headwinds, or delivery routes with different loading/unloading times. The ATSP is significantly harder to approximate than its symmetric counterpart. Common solution approaches include transforming it into a symmetric problem with twice the nodes or using specialized integer programming formulations.

The Multiple Traveling Salesmen Problem (mTSP) extends the classic problem by employing multiple salesmen (or vehicles) to service all cities. Key constraints include:

• Fleet size: A fixed or variable number of vehicles.
• Depot configuration: One central depot or multiple depots.
• Objective: Minimize total distance, longest route (min-max), or balanced workload. This is a direct generalization to the Vehicle Routing Problem (VRP), where additional constraints like vehicle capacity are added.

The Traveling Salesman Problem with Time Windows (TSPTW) adds a critical temporal dimension: each city (or customer) must be visited within a specified time interval [e_i, l_i]. Arriving early results in idle waiting time; arriving late is infeasible. This variant is fundamental to just-in-time logistics, home delivery services, and technician dispatch. Solving TSPTW requires algorithms that handle both sequencing and scheduling, often using dynamic programming or sophisticated constraint programming models.

The Capacitated TSP (CTSP) introduces a load constraint. The salesman has a vehicle with a finite capacity Q. Each city has a demand d_i (positive for delivery, negative for pickup), and the total load carried along the route must never exceed Q. This variant bridges the gap between the pure TSP and the Capacitated Vehicle Routing Problem (CVRP). Solutions often involve constructing routes that respect capacity, making it a fundamental model for last-mile delivery and inventory routing.

The Profitable TSP (PTSP) or Prize-Collecting TSP relaxes the requirement to visit all cities. Each city offers a prize (or profit) p_i, but visiting it may incur a cost (distance). The objective is to find a tour that maximizes the total collected prize minus the travel cost, potentially within a time or distance budget. This models scenarios like field service routing where not all tasks can be completed, or tourist itinerary planning where attractions are selected based on interest and proximity.

Construction heuristics build a tour from scratch by making a series of locally optimal decisions. They are extremely fast (O(n²) or better) but often produce solutions 10-25% above optimal.

• Nearest Neighbor: Starts at a random city, repeatedly visits the closest unvisited city, and finally returns to the start. Prone to getting trapped in poor local structures.
• Greedy (Multi-Fragment): Sorts all edges by length and iteratively adds the shortest edge that does not create a vertex of degree 3 or a premature cycle.
• Insertion Heuristics (e.g., Nearest, Farthest, Cheapest): Start with a subtour and repeatedly insert the remaining city that minimizes the increase in tour length according to a chosen criterion.
• Christofides Algorithm: A classic approximation algorithm for metric TSP that guarantees a solution within 1.5 times the optimal length. It builds a Minimum Spanning Tree (MST), adds a minimum-weight perfect matching on its odd-degree vertices, and forms an Eulerian circuit.

These algorithms start with a feasible tour (often from a construction heuristic) and iteratively improve it by exploring neighborhoods—sets of tours reachable by a defined operation.

• k-opt Moves: The most famous local search for TSP. A 2-opt move removes two edges and reconnects the paths to form a new, shorter tour. The Lin-Kernighan heuristic is a variable-depth, highly effective k-opt variant that is a standard benchmark.
• 3-opt / 4-opt: Remove three or four edges and reconnect the segments in all possible ways, exploring a larger neighborhood for better improvements at higher computational cost.
• Or-opt: Relocates a chain of 1-3 consecutive cities to a different position in the tour.
• The search continues until a local optimum is reached, where no move in the defined neighborhood yields an improvement.

Metaheuristics are high-level strategies designed to guide underlying heuristics to escape local optima and explore the solution space more thoroughly. They do not guarantee optimality but often find near-optimal solutions for very large-scale problems.

• Simulated Annealing (SA): Inspired by thermodynamics. It occasionally accepts worse solutions with a probability that decreases over time ("cooling"), allowing the search to escape poor local optima.
• Genetic Algorithms (GA): A population-based approach. Tours ("chromosomes") are combined ("crossover") and randomly altered ("mutation") over generations, with selection pressure favoring shorter tours.
• Ant Colony Optimization (ACO): Inspired by ant foraging. Artificial "ants" probabilistically construct tours based on "pheromone" trails, which are reinforced on shorter edges, leading to emergent, self-reinforcing good paths.
• Tabu Search: Enhances local search by maintaining a short-term memory ("tabu list") of recently visited solutions to avoid cycling and encourage exploration of new regions.

Recent advances leverage new computational paradigms and problem structures for specific TSP variants.

• Concorde TSP Solver: The de facto exact solver for large-scale symmetric TSP, using advanced branch-and-cut and linear programming techniques. It has solved an 85,900-city instance to optimality.
• Reinforcement Learning (RL): Models TSP as a sequential decision-making process. Attention-based models (e.g., Transformer architectures) are trained via policy gradient methods to construct tours, learning heuristics that generalize across problem sizes.
• Dynamic Programming on Subsets (DPS): While Held-Karp is the classic example, modern implementations use bitmask tricks and memory optimization to push the feasible limit for exact solutions.
• Decomposition & Cluster-First, Route-Second: For massive instances, cities are clustered geographically, the TSP is solved within each cluster, and then the clusters are connected. This is common in Vehicle Routing Problem (VRP) solvers.

Mixed-Integer Programming (MIP) is a mathematical optimization technique where some decision variables are constrained to be integers. It is the primary exact method for formulating and solving NP-hard problems like the TSP and VRP to proven optimality.

• Formulation: Combines linear constraints with integer variables (e.g., binary variables to indicate if an edge is in a tour).
• Solvers: Commercial (Gurobi, CPLEX) and open-source (SCIP) solvers use Branch and Bound and cutting-plane methods.
• Use Case: Solving small to medium-scale TSP/VRP instances exactly or providing strong lower bounds for heuristic methods.

Heuristics are practical rules for finding good solutions quickly, while metaheuristics are high-level frameworks for guiding heuristics. They are essential for tackling large-scale TSP instances where exact methods are intractable.

• Constructive Heuristics: Nearest Neighbor, Christofides Algorithm (provides a 1.5x approximation guarantee for metric TSP).
• Improvement Heuristics: 2-opt, 3-opt (local search that swaps tour edges).
• Metaheuristics: Genetic Algorithms, Simulated Annealing, Ant Colony Optimization. These explore the solution space to avoid local optima.

Constraint Programming (CP) is a paradigm for solving combinatorial problems by stating relations between variables as constraints. It uses powerful propagation and search algorithms, making it highly effective for problems with complex, heterogeneous constraints.

• Strengths: Naturally models logical constraints (e.g., precedence, disjunctions, all-different).
• Contrast with MIP: Often better for feasibility problems and highly constrained scheduling; MIP often stronger for pure optimization.
• Application in Scheduling: Used for Job Shop Scheduling and VRPs with intricate time-window and synchronization rules.

A problem is NP-hard if it is at least as hard as the hardest problems in NP. No known algorithm can solve all instances of an NP-hard problem in polynomial time. The decision version of the TSP is NP-complete.

• Implication: For large problem sizes, we must rely on heuristics or approximation algorithms, as finding the provably optimal solution is computationally prohibitive.
• Practical Impact: Justifies the use of optimality gaps to measure heuristic solution quality against known bounds.
• Related Class: NP-complete problems have verifiable solutions; TSP is a canonical example.

Model Predictive Control (MPC), or Receding Horizon Control, is an advanced method for real-time system control. It solves a finite-horizon optimization problem at each time step and implements the first control action, making it ideal for dynamic, online scheduling.

• Core Loop: 1) Predict system state over a horizon using a model. 2) Solve an optimization (e.g., a short-horizon VRP). 3) Execute the first step. 4) Re-measure and repeat.
• Application: Real-time replanning for autonomous vehicle fleets, adjusting routes dynamically for new orders, traffic, or agent failures.
• Link to TSP: The short-horizon optimization within MPC often solves a TSP or VRP subproblem.