Blogs

I found a new book on Operations Research from Éric Taillard which begins with the Traveling Salesman Problem. It is available in print format (Taillard, 2013) and online as a PDF file.
Starting with graph theory, and continuing to Heuristics Design, this volume contains sample Python code to supplement the theory within. For example, a greedy adaptive search procedure ("GRASP") with path relinking implementation for the TSP in pseudocode,

Algorithm 10.3: GRASP-PR framework
Input: GRASP procedure (with local search LS and parameter 0   1), parameters
Imax and
Result: Population P of solutions
1 P←
2 while |P| < do
3 s←GRASP( ,LS)
4 if s /∈
P then
5 P←P∪s
6 for Imax iterations do
7 s←GRASP( ,LS)
8 Randomly draw s  ∈ P
9 Apply a path relinking method between s and s ; identifying the best solution s   of the
path
10 if s   /∈
P and s   is strictly better than a solution of P then
11 s   replaces the most different solution of P which is worse than s  ​

can be written in Python as,

from random_generators import unif # Listing 12.1
2 from tsp_utilities import * # Listing 12.2
3 from tsp_GRASP import tsp_GRASP # Listing 7.4
4 from tsp_path_relinking import tsp_path_relinking # Listing 10.6
5
6 ######### GRASP with path relinking for the TSP
7 def tsp_GRASP_PR(d, # Distance matrix
8 iterations, # Number of calls to GRASP
9 population_size, # Size of the population
10 alpha): # GRASP parameter
11
12 n = len(d[0])
13 population = [[-1] * population_size for _ in range(population_size)]
14 pop_size = iteration = 0
15 lengths = [-1] * population_size
16 while (pop_size < population_size and iteration < iterations):
17 tour, tour_length = tsp_GRASP(d, alpha)
18 iteration += 1
19 succ = tsp_tour_to_succ(tour)
20 different = True
21 for i in range(pop_size - 1):
22 if tsp_compare(population[i], succ) == 0:
23 different = False
24 break # The tour is already in population
25 if different:
26 population[pop_size] = succ[:]
27 lengths[pop_size] = tour_length
28 pop_size += 1
29 if (iteration == iterations):#Unable to generate enough different solutions
30     population_size = pop_size
31 for it in range(iteration, iterations):
32     tour, tour_length = tsp_GRASP(d, alpha)
33 iteration += 1
34 succ = tsp_tour_to_succ(tour)
35 successors, length = tsp_path_relinking(d,
36 population[unif(0,population_size-1)],tour_length, succ)
37 max_difference, replacing = -1, -1
38 for i in range(population_size):
39     if (length <= lengths[i]):
40         difference = tsp_compare(population[i], successors)
41     if difference == 0:
42         max_difference = 0
43 break
44 if difference > max_difference and length < lengths[i]:
45     max_difference = difference
46 replacing = i
47 if max_difference > 0:
48     lengths[replacing] = length
49 population[replacing] = successors[:]
50 print(’GRASP_PR population updated:’, it, length)
51
52 best = 0
53 for i in range(1, population_size):
54 if lengths[i] < lengths[best]:
55     best = i
56 return tsp_succ_to_tour(population[best]), lengths[best]​

It is a good reference tool, as well as a tutorial book. For instance, the volume has a good implementation of a Taboo Search.



References

Taillard, Éric D. "Design of Heuristic Algorithms for Hard Optimization: With Python Codes for the Travelling Salesman Problem." (2023): 287.