The Travel Salesman Problem

The Travel Salesman Problem (TSP) is an example of a NP-problem; one where the number of possible solutions cannot be solved with a reasonable amount of time. Because the relevance in the history and applications of this particular algorithm, it has become a benchmark, a point of reference, to evaluate heuristic algorithms that connect with NP-problems.

The parameters for the algorithm are

  • ITERATIONS: float - The number of trials to try to find the best (smallest) score
  • MATRIX_DISTANCES: [[CITY_DISTANCE, ..., n=4], ..., n=4] - the matrix of distances between cities
  • CANDIDATE_ORDER_TRAVEL: [int, ..., n=4] - the arrangement of indexes in which the travel salesman will visit each city relative to CITIES
  • BEST_SCORE: the smallest score found so far in the routes between cities
  • BEST_CANDIDATE: [int, ..., n=4] - the BEST arrangement of indexes in which the travel salesman will visit each city
# MODULES
import random

# DATA DEFINITIONS

ITERATIONS = 10000


# DD. MATRIX_DISTANCES
# md = [[CITY_DISTANCE, ..., n=4], ..., n=4]
# interp. the matrix of distances between cities
md = [
        [0,16,13,5],
        [16,0,20,9],
        [13,20,0,7],
        [5, 9, 7,0]
     ]



# DD. CANDIDATE_ORDER_OF_TRAVEL
# cot = [int, ..., n=4]
# interp. the arrangement of indexes in which the travel salesman will visit each city relative to CITIES
cot = [0,1,2,3] #A,B,C,D

# DD. BEST_SCORE
# bsc = float
# interp. the smallest score found so far in the routes between cities
bsc = sum([sum(i) for i in md])

# DD. BEST_CANDIDATE
# bcot = [int, ..., n=4]
# interp. the BEST arrangement of indexes in which the travel salesman will visit each city relative to CITIES
bcot = cot

The Algorithm

  • While in range of ITERATIONS:
    • Initialize a score and set it to zero
    • Shuffle CANDIDATE_ORDER_TRAVEL
    • Traverse the MATRIX_DISTANCES using the indexes provided by CANDIDATE_ORDER_TRAVEL, while adding to the score
    • Add to the score the CANDIDATE_ORDER_TRAVEL from the last index -1, at the index 0, representing the distance from the last city back to the first one
    • Is the score better than the BEST_SCORE? T: make BEST_SCORE = score, and BEST_CANDIDATE = CANDIDATE_ORDER_TRAVEL
  • Create a STRING_OF_CITIES to populate the sequence of letters that map the indexes from BEST_CANDIDATE
  • For every INDEX in BEST_CANDIDATE:
    • Add to the STRING_OF_CITIES the string that matches the city's name at INDEX
  • Add to the STRING_OF_CITIES the string that matches the city's name at BEST_CANDIDATE at index 0

Here's a visualization of the Travel Salesman Problem!
Let's take a look at the algorithm in action! 
# MODULES
import random

# DATA DEFINITIONS

ITERATIONS = 10000


# DD. MATRIX_DISTANCES
# md = [[CITY_DISTANCE, ..., n=4], ..., n=4]
# interp. the matrix of distances between cities
md = [
        [0,16,13,5],
        [16,0,20,9],
        [13,20,0,7],
        [5, 9, 7,0]
     ]



# DD. CANDIDATE_ORDER_OF_TRAVEL
# cot = [int, ..., n=4]
# interp. the arrangement of indexes in which the travel salesman will visit each city relative to CITIES
cot = [0,1,2,3] #A,B,C,D

# DD. BEST_SCORE
# bsc = float
# interp. the smallest score found so far in the routes between cities
bsc = sum([sum(i) for i in md])

# DD. BEST_CANDIDATE
# bcot = [int, ..., n=4]
# interp. the BEST arrangement of indexes in which the travel salesman will visit each city relative to CITIES
bcot = cot

# CODE

def getCityByIndex(idx):
    if idx == 0:
        return "A"
    elif idx == 1:
        return "B"
    elif idx == 2:
        return "C"
    else:
        return "D"


for _ in range(ITERATIONS):
    random.shuffle(cot)
    score = 0
    for i in range(len(cot)-1):
        score += md[cot[i]][cot[i+1]]
    score += md[cot[-1]][cot[0]]
    if bsc > score:
        bsc = score
        bcot = list(cot)




stringOfCities = ""
for idx in bcot:
    stringOfCities += getCityByIndex(idx) + "-"
stringOfCities += getCityByIndex(bcot[0])

print(bsc)
print(stringOfCities)