simple-tsp 0.1.0

Solving the Traveling Salesman Problem

Solving the Traveling Salesman Problem

This package uses PyVRP to solve the traveling salesman problem. It can handle distance data in the following three ways.

• A dictionary whose keys are tuples of two cities and whose values are integer distances
  • A dictionary whose city type is an integer (pattern 1)
  • A dictionary whose key is a tuple of cities and whose value is a string (Pattern 2)
• Nested lists whose values are distances (pattern 3)

Functions

• tsp(distances, depot, max_iterations): Solve a traveling salesman problem and return a list of cities
  • distances: Dictionary or list of distances
  • depot: First city
  • max_iterations: Number of iterations to use in PyVRP

tsp(distances: dict[tuple[int, int], int], depot: int = 0, max_iterations: int = 100) -> list[int]
tsp(distances: dict[tuple[str, str], int], depot: str, max_iterations: int = 100) -> list[str]
tsp(distances: list[list[int]], depot: int = 0, max_iterations: int = 100) -> list[str]

• distance(lat1: float, lon1: float, lat2: float, lon2: float) -> float: Return the great circle distance (km) between two points
  • lat1: Latitude of location 1
  • lon1: Longitude of location 1
  • lat2: Latitude of location 2
  • lon2: Longitude of location 2

Usage

from simple_tsp import tsp

# Pattern 1
distances1 = {(0, 2): 1, (2, 3): 1, (3, 1): 1, (1, 0): 1}
print(tsp(distances1, 0))  # [0, 2, 3, 1]

# Pattern 2
distances2 = {("a", "c"): 1, ("c", "d"): 1, ("d", "b"): 1, ("b", "a"): 1}
print(tsp(distances2, "a"))  # ['a', 'c', 'd', 'b']

# Pattern 3
distances3 = [[0, 9, 1, 9], [1, 0, 9, 9], [9, 9, 0, 1], [9, 1, 9, 0]]
print(tsp(distances3))  # [0, 2, 3, 1]