Решение задачи коммивояжера путем моделирования отжига

В настоящее время я пытаюсь реализовать алгоритм для решения проблемы коммивояжера путем моделирования отжига. Основываясь на том, что я прочитал в теме, я реализовал следующее:

Некоторые дополнительные функции:

def calculate_total_distance(route, distance_matrix):
total_distance = sum(distance_matrix[route[i]][route[i+1]] for i in range(len(route) - 1))
total_distance += distance_matrix[route[-1]][route[0]]  # Return to start
return total_distance

def create_initial_route(number_of_cities):
    route = list(range(number_of_cities))
    random.shuffle(route)
    return route

def swap_two_cities(route):
    new_route = route.copy()
    city1, city2 = random.sample(range(len(route)), 2)
    new_route[city1], new_route[city2] = new_route[city2], new_route[city1]
    return new_route

Основная функция алгоритма:

def simulated_annealing(distance_matrix, initial_temperature, cooling_rate, number_of_iterations):
    current_route = create_initial_route(len(distance_matrix))
    current_distance = calculate_total_distance(current_route, distance_matrix)
    temperature = initial_temperature

    for iteration in range(number_of_iterations):
        new_route = swap_two_cities(current_route)
        new_distance = calculate_total_distance(new_route, distance_matrix)

        if new_distance < current_distance or random.random() < math.exp(-(current_distance - new_distance) / temperature):
            current_route, current_distance = new_route, new_distance
        print(current_route, current_distance)
        temperature *= cooling_rate

    return current_route, current_distance

Выполнение:

initial_temperature = 5000
cooling_rate = 0.995
number_of_iterations = 1000

optimal_route, optimal_distance = simulated_annealing(distance_matrix, initial_temperature, cooling_rate, number_of_iterations)
print("Optimal route:", optimal_route)
print("Total distance:", optimal_distance)

Я использую файл ATSP br17, который содержит 17 «городов». Как вы можете видеть на изображении ниже, расстояние более 1000 итераций не показывает никаких признаков минимизации.

Кто-нибудь может помочь советом, в чем может быть проблема в моей реализации? Любая помощь очень ценится! Спасибо!