Introduction

The Travelling Salesman Problem (TSP) is a classic problem in optimization and logistics. The objective is to find the shortest possible route for a salesman to visit a set of cities exactly once and return to the starting city. A practical variant is the Multiple Travelling Salesmen Problem (mTSP), which involves more than one salesman. This variant adds complexity and real-world applicability, especially in fleet routing, delivery logistics, and operations research.

Problem Definition

Classic TSP

The classic TSP can be represented using a graph where:

• Nodes (cities): The locations that need to be visited.
• Edges (paths): The connections between cities, each with an associated cost or distance.

The goal is to find a Hamiltonian cycle (a loop visiting each node exactly once) with the minimum total cost. Given $n$ cities, there are $\frac{(n-1)!}{2}$ possible tours for an undirected graph, making brute-force infeasible for even moderate $n$.

Multiple Travelling Salesmen Problem (mTSP)

The mTSP introduces $m$ salesmen into the scenario:

• Each salesman starts and ends at a common depot.
• The set of cities is partitioned among the salesmen so that each city is visited exactly once by exactly one salesman.
• The objective is to minimize the total cost across all salesmen's routes.

Mathematical Formulation

Classic TSP

Given cities ${c_1, c_2, \ldots, c_n}$ and a cost matrix $D = [d_{ij}]$ where $d_{ij}$ is the travel cost from city $i$ to city $j$, the objective is:

$$\min \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij} x_{ij}$$

Subject to:

• $\sum_{j=1}^{n} x_{ij} = 1$ for all $i$ (leave each city exactly once)
• $\sum_{i=1}^{n} x_{ij} = 1$ for all $j$ (enter each city exactly once)
• $x_{ij} \in {0, 1}$
• Sub-tour elimination constraints (e.g., Miller-Tucker-Zemlin or Dantzig-Fulkerson-Johnson)

mTSP Formulation

For $m$ salesmen servicing $n$ cities, introduce a superscript $t$ for each salesman:

$$\min \sum_{t=1}^{m} \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij} x_{ij}^{(t)}$$

Subject to:

• Each city visited exactly once: $\sum_{t=1}^{m} \sum_{j=1}^{n} x_{ij}^{(t)} = 1$ for all $i$
• Each salesman departs from and returns to the depot
• Sub-tour elimination constraints for each salesman
• $x_{ij}^{(t)} \in {0, 1}$

Additional constraints can bound the minimum and maximum number of cities per salesman to ensure balanced workloads.

Solution Approaches

Exact Methods

1. Branch and Bound: Systematically explores the solution space by computing lower bounds and pruning branches that cannot improve on the best known solution. Guarantees optimality but has exponential worst-case time.
2. Mixed Integer Linear Programming (MILP): Formulates the problem as a linear program with integer constraints. Solvers like Gurobi and CPLEX can handle instances with up to a few hundred cities.

Heuristics

1. Nearest Neighbor: A greedy approach where each salesman always visits the closest unvisited city. Fast ($O(n^2)$ per salesman) but often produces suboptimal tours.
2. Cluster-First, Route-Second: Partition cities into $m$ clusters (using k-means or geographic partitioning), then solve a single-salesman TSP within each cluster.
3. Route-First, Cluster-Second: Solve one large TSP tour, then split it into $m$ segments.

Metaheuristics

1. Genetic Algorithms (GA): Evolve a population of solutions through crossover and mutation. Good at exploring diverse solutions.
2. Ant Colony Optimization (ACO): Simulates ants depositing pheromones on paths, reinforcing shorter routes over time.
3. Simulated Annealing: Accepts worse solutions with decreasing probability, helping escape local optima.
4. Tabu Search: Uses a memory structure to avoid revisiting recent solutions.

Example Scenario

Consider $n = 5$ cities and $m = 2$ salesmen with the following assignment:

Total cost: 35. A different partition might yield a lower total, so the optimization lies in both the assignment of cities to salesmen and the ordering within each route.

Applications

• Logistics and Distribution: Optimizing multi-vehicle delivery routes to minimize fuel consumption and time.
• Field Service Scheduling: Deploying technicians to customer sites across a region.
• Manufacturing: Coordinating robotic arms or tool heads visiting multiple positions on an assembly line.
• Drone Delivery: Splitting delivery targets among multiple drones with limited battery life.

Challenges

• Scalability: The mTSP is NP-hard, inheriting the intractability of the classic TSP. The additional partitioning dimension makes it even harder.
• Dynamic Environments: Real-time changes in traffic, new orders, or vehicle breakdowns require adaptive re-optimization.
• Heterogeneous Fleets: Different vehicles may have different speeds, capacities, or operating costs, adding constraints to the formulation.

Summary

The Multiple Travelling Salesmen Problem extends the classic TSP by partitioning cities among multiple agents. The mathematical formulation adds assignment variables for each salesman, and solution methods range from exact MILP solvers (for small instances) to metaheuristics like genetic algorithms and ant colony optimization (for large-scale problems). The choice of method depends on problem size, solution quality requirements, and available computation time.