Source code for evol.problems.routing.tsp

import math
from typing import List, Union

from evol.problems.problem import Problem
from evol.helpers.utils import rotating_window

[docs]class TSPProblem(Problem): def __init__(self, distance_matrix): self.distance_matrix = distance_matrix
[docs] @classmethod def from_coordinates(cls, coordinates: List[Union[tuple, list]]) -> 'TSPProblem': """ Creates a distance matrix from a list of city coordinates. :param coordinates: An iterable that contains tuples or lists representing a x,y coordinate. :return: A list of lists containing the distances between cities. """ res = [[0 for i in coordinates] for j in coordinates] for i, coord_i in enumerate(coordinates): for j, coord_j in enumerate(coordinates): dist = math.sqrt(sum([(z[0] - z[1])**2 for z in zip(coord_i[:2], coord_j[:2])])) res[i][j] = dist res[j][i] = dist return TSPProblem(distance_matrix=res)
[docs] def check_solution(self, solution: List[int]): """ Check if the solution for the TSP problem is valid. :param solution: List of integers which refer to cities. :return: None, unless errors are raised. """ set_solution = set(solution) set_problem = set(range(len(self.distance_matrix))) if len(solution) > len(self.distance_matrix): raise ValueError("Solution is longer than number of towns!") if set_solution != set_problem: raise ValueError(f"Not all towns are visited! Am missing {set_problem.difference(set_solution)}")
[docs] def eval_function(self, solution: List[int]) -> Union[float, int]: """ Calculates the cost of the current solution for the TSP problem. :param solution: List of integers which refer to cities. :return: """ self.check_solution(solution=solution) cost = 0 for t1, t2 in rotating_window(solution): cost += self.distance_matrix[t1][t2] return cost