searches.tabu_search

This is pure Python implementation of Tabu search algorithm for a Travelling Salesman Problem, that the distances between the cities are symmetric (the distance between city ‘a’ and city ‘b’ is the same between city ‘b’ and city ‘a’). The TSP can be represented into a graph. The cities are represented by nodes and the distance between them is represented by the weight of the ark between the nodes.

The .txt file with the graph has the form:

node1 node2 distance_between_node1_and_node2 node1 node3 distance_between_node1_and_node3 …

Be careful node1, node2 and the distance between them, must exist only once. This means in the .txt file should not exist: node1 node2 distance_between_node1_and_node2 node2 node1 distance_between_node2_and_node1

For pytests run following command: pytest

For manual testing run: python tabu_search.py -f your_file_name.txt -number_of_iterations_of_tabu_search -s size_of_tabu_search e.g. python tabu_search.py -f tabudata2.txt -i 4 -s 3

Attributes

parser

Functions

find_neighborhood(solution, dict_of_neighbours)	Pure implementation of generating the neighborhood (sorted by total distance of
generate_first_solution(path, dict_of_neighbours)	Pure implementation of generating the first solution for the Tabu search to start,
generate_neighbours(path)	Pure implementation of generating a dictionary of neighbors and the cost with each
main([args])
tabu_search(first_solution, ...)	Pure implementation of Tabu search algorithm for a Travelling Salesman Problem in

Module Contents

searches.tabu_search.find_neighborhood(solution, dict_of_neighbours)

Pure implementation of generating the neighborhood (sorted by total distance of each solution from lowest to highest) of a solution with 1-1 exchange method, that means we exchange each node in a solution with each other node and generating a number of solution named neighborhood.

Parameters:

• solution – The solution in which we want to find the neighborhood.

• dict_of_neighbours – Dictionary with key each node and value a list of lists with the neighbors of the node and the cost (distance) for each neighbor.

Return neighborhood_of_solution:

A list that includes the solutions and the total distance of each solution (in form of list) that are produced with 1-1 exchange from the solution that the method took as an input

Example: >>> find_neighborhood([‘a’, ‘c’, ‘b’, ‘d’, ‘e’, ‘a’], … {‘a’: [[‘b’, ‘20’], [‘c’, ‘18’], [‘d’, ‘22’], [‘e’, ‘26’]], … ‘c’: [[‘a’, ‘18’], [‘b’, ‘10’], [‘d’, ‘23’], [‘e’, ‘24’]], … ‘b’: [[‘a’, ‘20’], [‘c’, ‘10’], [‘d’, ‘11’], [‘e’, ‘12’]], … ‘e’: [[‘a’, ‘26’], [‘b’, ‘12’], [‘c’, ‘24’], [‘d’, ‘40’]], … ‘d’: [[‘a’, ‘22’], [‘b’, ‘11’], [‘c’, ‘23’], [‘e’, ‘40’]]} … ) # doctest: +NORMALIZE_WHITESPACE [[‘a’, ‘e’, ‘b’, ‘d’, ‘c’, ‘a’, 90],

[‘a’, ‘c’, ‘d’, ‘b’, ‘e’, ‘a’, 90], [‘a’, ‘d’, ‘b’, ‘c’, ‘e’, ‘a’, 93], [‘a’, ‘c’, ‘b’, ‘e’, ‘d’, ‘a’, 102], [‘a’, ‘c’, ‘e’, ‘d’, ‘b’, ‘a’, 113], [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘a’, 119]]

searches.tabu_search.generate_first_solution(path, dict_of_neighbours)

Pure implementation of generating the first solution for the Tabu search to start, with the redundant resolution strategy. That means that we start from the starting node (e.g. node ‘a’), then we go to the city nearest (lowest distance) to this node (let’s assume is node ‘c’), then we go to the nearest city of the node ‘c’, etc. till we have visited all cities and return to the starting node.

Parameters:

• path – The path to the .txt file that includes the graph (e.g.tabudata2.txt)

• dict_of_neighbours – Dictionary with key each node and value a list of lists with the neighbors of the node and the cost (distance) for each neighbor.

Return first_solution:

The solution for the first iteration of Tabu search using the redundant resolution strategy in a list.

Return distance_of_first_solution:

The total distance that Travelling Salesman will travel, if he follows the path in first_solution.

searches.tabu_search.generate_neighbours(path)

Pure implementation of generating a dictionary of neighbors and the cost with each neighbor, given a path file that includes a graph.

Parameters:

path – The path to the .txt file that includes the graph (e.g.tabudata2.txt)

Return dict_of_neighbours:

Dictionary with key each node and value a list of lists with the neighbors of the node and the cost (distance) for each neighbor.

Example of dict_of_neighbours: >>) dict_of_neighbours[a] [[b,20],[c,18],[d,22],[e,26]]

This indicates the neighbors of node (city) ‘a’, which has neighbor the node ‘b’ with distance 20, the node ‘c’ with distance 18, the node ‘d’ with distance 22 and the node ‘e’ with distance 26.

searches.tabu_search.main(args=None)

searches.tabu_search.tabu_search(first_solution, distance_of_first_solution, dict_of_neighbours, iters, size)

Pure implementation of Tabu search algorithm for a Travelling Salesman Problem in Python.

Parameters:

• first_solution – The solution for the first iteration of Tabu search using the redundant resolution strategy in a list.

• distance_of_first_solution – The total distance that Travelling Salesman will travel, if he follows the path in first_solution.

• dict_of_neighbours – Dictionary with key each node and value a list of lists with the neighbors of the node and the cost (distance) for each neighbor.

• iters – The number of iterations that Tabu search will execute.

• size – The size of Tabu List.

Return best_solution_ever:

The solution with the lowest distance that occurred during the execution of Tabu search.

Return best_cost:

The total distance that Travelling Salesman will travel, if he follows the path in best_solution ever.

searches.tabu_search.parser