Travelling Salesman Problem (TSP)

General Overview

The Travelling Salesman Problem (TSP) is a classic route planning challenge where a single vehicle or person must visit several different locations and return to the starting point. The aim is to choose the most efficient visiting order to minimize total travel distance, time, or cost.

---

Use Cases

Common real-world scenarios include:

• A delivery driver dropping packages at multiple addresses and returning to the depot.
• A field technician visiting several service sites in one day.
• A salesperson planning a loop of customer visits across a region.

In all of these, careful ordering of stops reduces travel time, fuel cost, and scheduling stress.

---

How It Works

This problem finds the shortest route for a single vehicle to visit multiple locations and return to the starting point with optimal ordering. Key points to pay attention to:

• Only one vehicle is used for the entire journey
• All visits must start from the same location
• The vehicle must return to the starting point
• Each destination is visited exactly once
• All jobs have equal demand (amount = 1) with no variable delivery quantities

---

General Validation

Before building or solving a TSP request, confirm:

• The vehicles list must contain a single vehicle.
• The jobs list must contain at least one job.
• The jobs must have the same start location.
• The vehicle must start at the same location as the jobs.
• The vehicle must return to start location.
• The jobs must have unique end locations.
• The jobs must have the 1 amount.
• The jobs must have the same amount.

---

Example

Scenario:

A service vehicle starts at a central depot (Location A), must visit four customers (B, C, D, E), and return to A. Distances between all locations are known.

Goal:

Find the visiting order (e.g., A → C → E → B → D → A) that results in the lowest total travel distance.

Minimal Example Payload:

{
  "vehicles": [
    {
      "id": "vehicle_1",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "per_km": 1000,
        "max_distance": 50000
      }
    }
  ],
  "jobs": [
    {
      "id": "job_1",
      "amount": 1,
      "start": {
        "coordinate": [0, 0]
      },
      "end": {
        "coordinate": [2, 3]
      }
    },
    {
      "id": "job_2",
      "amount": 1,
      "start": {
        "coordinate": [0, 0]
      },
      "end": {
        "coordinate": [5, 7]
      }
    },
    {
      "id": "job_3",
      "amount": 1,
      "start": {
        "coordinate": [0, 0]
      },
      "end": {
        "coordinate": [8, 2]
      }
    }
  ],
  "options": {
    "problem": "TSP",
    "objective": "distance",
    "solver": "heuristic",
    "map": "cartesian"
  }
}