TSP module


tsp.main()[source]

Todo

  • TODO: Make some visualizations
  • TODO: Add sum of distances comparision (instead of minimum criterium)
  • TODO: Real data generator (distance between town A and B should be lower than between town A and C + C and A)
  • TODO: Make report
  • TODO: Develop Genetic algorithm, new crossing methods (ranking, roulette)
tsp.generate_random_route(data: numpy.array, number_of_drivers: int = 1, start_town: int = 0) → tuple[source]

Function which generate random route

Parameters:
  • data (np.array) – distance matrix
  • number_of_drivers (int) – number of travelers/drivers
  • start_town (int) – index of starting town
Returns:

tuple of distances and routes of each travelers
Return type:

tuple
tsp.make_random_matrix(number_of_towns: int = 16, min_distance: int = 10, max_distance: int = 100) → int[source]

Function to make random matrix of distances between town

Parameters:
  • number_of_towns (int) – number of towns in matrix
  • min_distance (int) – minimal distance between towns
  • max_distance (int) – maximum distance between towns
Returns:

distance matrix
Return type:

int
tsp.distance_comparision(first_dist: numpy.array, second_dist: numpy.array, kind='min') → bool[source]

Distance comparision function

Parameters:
  • first_dist (np.array) – first distance to compare
  • second_dist (np.array) – second distance to compare
  • kind (str) – type of comparision
Returns:

True or False depends of which of dinstaces are “better”
Return type:

bool

Random search implementation

Parameters:
  • data (np.array) – distances matrix
  • test_time (float) – time of testing
  • number_of_drivers (int) – number of travelers
  • dist_comp (str) – type of distance comparision
  • start_town (int) – starting_town
Returns:

tuple of best distances and routes of each travelers
Return type:

tuple
tsp.simulated_annealing(data: numpy.array, test_time: float = 1, number_of_drivers: int = 1, start_town: int = 0, initial_temperature: float = 400000, temp_decrease_ratio: float = 0.99, use_swap: bool = True) → tuple[source]

Simulated Annealing implementation

Parameters:
  • data (np.array) – distances matrix
  • test_time (float) – time of testing
  • number_of_drivers (int) – number of travelers
  • start_town (int) – starting_town
  • initial_temperature (float) – hyperparameter of SA
  • temp_decrease_ratio (float) – hyperparameter of SA
  • use_swap (bool) – Swap two elements of route list instead of generate new random route
Returns:

tuple of best distances and routes of each travelers
Return type:

tuple
tsp.genetic_algorithm(data: numpy.array, test_time: float = 1, number_of_drivers: int = 1, population_quantity: int = 10, start_town: int = 0) → tuple[source]

Genetic algorithm implementation

Parameters:
  • data (np.array) – distances matrix
  • test_time (float) – time of testing
  • number_of_drivers (int) – number of travelers
  • population_quantity (int) – number of instances in population
  • start_town (int) – starting_town
Returns:

tuple of best distances and routes of each travelers
Return type:

tuple

Return Home