AG3 - Actividad Guiada 3

Nombre: Carlos Javier Bravo Intriago

Link: https://colab.research.google.com/drive/1AcCo6Z2wjOUD-hqzZWMZGL_kJ4G8IysU?usp=sharing

Github: https://github.com/carlosbravo1408/03MIAR-Algoritmos-de-Optimizacion-2025/tree/main/AG3

Carga de librerias

!pip install requests
!pip install tabulate>=0.9 networkx>=3.0
!pip install tsplib95 --no-deps
!pip install deprecated

Requirement already satisfied: requests in /home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages (2.32.5)
Requirement already satisfied: charset_normalizer<4,>=2 in /home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages (from requests) (3.4.4)
Requirement already satisfied: idna<4,>=2.5 in /home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages (from requests) (3.11)
Requirement already satisfied: urllib3<3,>=1.21.1 in /home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages (from requests) (2.6.2)
Requirement already satisfied: certifi>=2017.4.17 in /home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages (from requests) (2025.11.12)

[notice] A new release of pip is available: 24.3.1 -> 26.0.1
[notice] To update, run: pip install --upgrade pip

[notice] A new release of pip is available: 24.3.1 -> 26.0.1
[notice] To update, run: pip install --upgrade pip
Requirement already satisfied: tsplib95 in /home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages (0.7.1)

[notice] A new release of pip is available: 24.3.1 -> 26.0.1
[notice] To update, run: pip install --upgrade pip
Requirement already satisfied: deprecated in /home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages (1.2.18)
Requirement already satisfied: wrapt<2,>=1.10 in /home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages (from deprecated) (1.17.3)

[notice] A new release of pip is available: 24.3.1 -> 26.0.1
[notice] To update, run: pip install --upgrade pip

Importe de librerias

import gzip
from typing import List, Tuple, Union, Literal, Callable, Dict, Optional
import math
import os
import random
import shutil
import urllib.request

import tsplib95
import numpy as np

Métodos Auxiliares y algunas definiciones necesarias

NumericType = Union[int, float]
NodeType = int
EdgeType = Tuple[NodeType, NodeType]
SolutionType = List[NodeType]
TSProblemType = tsplib95.models.Problem

def download_tsp_file(url: str, filename: str) -> None:
    # Descarga como archivo temporal
    local_path, headers = urllib.request.urlretrieve(url, filename + ".temp")
    mime_type = headers.get_content_type()
    # Descomprimir si es formato gzip
    if "gzip" in mime_type or local_path.endswith(".gz"):
        with gzip.open(local_path, 'rb') as f_in:
            with open(filename, 'wb') as f_out:
                shutil.copyfileobj(f_in, f_out)
        os.remove(local_path)
    # Caso contrario renombra el archivo temporal
    else:
        os.replace(local_path, filename)

Carga de los datos del problema

Documentación :

• https://web.archive.org/web/http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
• https://web.archive.org/web/http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf
• https://tsplib95.readthedocs.io/en/stable/pages/usage.html
• https://tsplib95.readthedocs.io/en/v0.6.1/modules.html
• https://pypi.org/project/tsplib95/
• https://github.com/mastqe/tsplib/tree/master

Se descarga el fichero de datos ya sea en Matriz de adyacencia o en formato Euclidiano

# Matriz Adyacencia swiss42 problem (Staedte Schweiz/Fricker)
file = "swiss42.tsp"
download_tsp_file("https://raw.githubusercontent.com/mastqe/tsplib/refs/heads/master/swiss42.tsp", file)

# Coordenadas Euclidianas 51-city problem (Christofides/Eilon)
# file = "eil51.tsp"
# download_tsp_file("https://raw.githubusercontent.com/mastqe/tsplib/refs/heads/master/eil51.tsp", file)

# Coordenadas Euclidianas - 48 capitals of the US (Padberg/Rinaldi)
# file = "att48.tsp"
# download_tsp_file("https://raw.githubusercontent.com/mastqe/tsplib/refs/heads/master/att48.tsp", file)

Carga de datos y generación de objeto problem

tsp_problem: tsplib95.models.Problem = tsplib95.load(file)

# Lo siguiente NO es una buena práctica de programacion y hay gente que
# considera sucia, pero permite optimizar algo más el código. Se inyecta la
# lista de nodos en el objeto tsp_problem, con ello se evita crear una nueva
# lista cada vez que se invoca a `get_nodes()`
tsp_problem.cached_nodes = list(tsp_problem.get_nodes())

nodes: List[NodeType] = tsp_problem.cached_nodes
edges: List[EdgeType] = list(tsp_problem.get_edges())

Fig 1. Visualizacion del problema swiss.42.tsp

Probamos algunas funciones del objeto problem Distancia entre nodos

tsp_problem.get_weight(4, 1)

27

Para ver todas las funciones, véase la documentación: https://tsplib95.readthedocs.io/en/v0.6.1/modules.html

Funcionas básicas

def crear_solucion(nodos: List[NodeType]) -> SolutionType:
    """
    Se genera una solución aleatoria con comienzo en el nodo 0
    :param nodos: Lista de nodos
    :return: Lista de nodos en posiciones aleatorias sin repetición
    """
    solucion = [nodos[0]]
    for _ in nodos[1:]:
        solucion = solucion + [
            random.choice(list(set(nodos) - {nodos[0]} - set(solucion)))]
    return solucion

def distancia(a: int, b: int, problem: TSProblemType) -> NumericType:
    """
    Devuelve la distancia entre dos nodos
    :param a: Nodo a
    :param b: Nodo b
    :param problem: Instancia de tsplib95.models.Problem
    :return:
    """
    return problem.get_weight(a, b)

def distancia_total(solucion: List[int], problem: TSProblemType) -> NumericType:
    """
    Devuelve la distancia total de una trayectoria/solución
    :param solucion: Lista de Nodos
    :param problem: Instancia de tsplib95.models.Problem
    :return:
    """
    distancia_total = 0
    n = len(solucion)
    for i in range(len(solucion)):
        distancia_total += distancia(solucion[i], solucion[(i + 1)%n], problem)
    return distancia_total


sol_temporal = crear_solucion(nodes)

print("Solución Aleatoria:", sol_temporal)
print("Distancia:", distancia_total(sol_temporal, tsp_problem))

Solución Aleatoria: [0, 38, 36, 16, 11, 1, 29, 5, 24, 41, 30, 12, 2, 21, 34, 31, 3, 19, 4, 18, 35, 6, 7, 15, 32, 20, 13, 39, 9, 22, 28, 23, 37, 33, 26, 40, 8, 25, 17, 27, 14, 10]
Distancia: 4792

BÚSQUEDA ALEATORIA

Esta búsqueda explora el espacio de soluciones de manera aleatoria, una analogía sería como buscar una aguja en un pajar cogiendo paja al azar y volviéndola a tirar. Este es un método ingenuo.

def busqueda_aleatoria(
        problem: TSProblemType,
        n: int
) -> Tuple[SolutionType, NumericType]:
    """
    Busca de manera aleatoria en N iteraciones alguna mejor solución.
    :param problem: Instancia de tsplib95.models.Problem
    :param n: el número de iteraciones
    :return:
    """
    nodos = problem.cached_nodes
    mejor_solucion = []
    # Inicializamos con un valor alto
    mejor_distancia = float('inf')
    # Criterio de parada: repetir N veces pero podemos incluir otros
    for i in range(n):
        solucion = crear_solucion(nodos)  # Genera una solucion aleatoria
        distancia = distancia_total(solucion, problem)  # Calcula el valor objetivo(distancia total)
        if distancia < mejor_distancia:  # Compara con la mejor obtenida hasta ahora
            mejor_solucion = solucion
            mejor_distancia = distancia
    return mejor_solucion, mejor_distancia

# Búsqueda aleatoria con 50000 iteraciones
solucion_inicial, distancia_inicial = busqueda_aleatoria(tsp_problem, 50000)
print("Mejor solución:", solucion_inicial)
print("Distancia     :", distancia_inicial)

Mejor solución: [0, 21, 24, 9, 40, 38, 22, 39, 30, 35, 15, 1, 13, 36, 33, 27, 29, 4, 23, 25, 19, 7, 17, 14, 16, 10, 37, 5, 11, 2, 32, 18, 3, 41, 8, 28, 6, 12, 26, 34, 31, 20]
Distancia     : 3512

BÚSQUEDA LOCAL

Este criterio de búsqueda es un método heurístico de mejora iterativa que explora el vecindario de una solución candidata mediante operaciones de perturbación local (tales como swap, 2-opt, shuffle e insertion). Su enfoque se basa estrictamente en la intensificación aceptando únicamente movimientos que maximicen o minimicen el coste objetivo.

Sobre el método get_swap_delta

Se pretende simplificar el cálculo de la distancia total de la solución que tiene complejidad $O(N)$, basándose en operaciones más simples debido al intercambio de elementos. Se contempla dos posibles casos:

1. Caso Adyacente ($j = i + 1$): Los nodos están pegados ($\cdots \to P \to A \to B \to N \cdots$). Al intercambiarlos ($\cdots \to P \to B \to A \to N \cdots$), la arista central $(A, B)$ se convierte en $(B, A)$. Asumiendo simetría, se cancelan. Solo cambian las conexiones exteriores: $$ \Delta = (Cost(P, B) + Cost(A, N)) - (Cost(P, A) + Cost(B, N)) $$

2. Caso No Adyacente (Disjuntos): Los nodos están separados. Se rompen las 4 aristas incidentes a $A$ y $B$ y se reconectan cruzadas. Sea $A$ rodeado por $(P_a, N_a)$ y $B$ rodeado por $(P_b, N_b)$: $$ \Delta = [Cost(P_a, B) + Cost(B, N_a) + Cost(P_b, A) + Cost(A, N_b)] - [Cost(P_a, A) + Cost(A, N_a) + Cost(P_b, B) + Cost(B, N_b)] $$

Sobre el método get_two_opt_delta:

Este cálculo asume simetría en la matriz de distancias ($d_{ij} = d_{ji}$). Al invertir el segmento $i \dots j$, la longitud interna del sub-camino permanece constante, reduciendo la complejidad del cálculo de $O(N)$ a $O(1)$ . Para instancias asimétricas (ATSP), se debe calcular la distancia_total de recorrer el segmento en sentido inverso.

def swap_nodes(i: int, j: int, solution: SolutionType) -> SolutionType:
    """
    Intercambia la posición del nodo `i` y nodo `j`\n
    >>> swap_nodes(i=1, j=4, solution=['A', 'B', 'C', 'D', 'E', 'F'])
    >>> ['A', 'E', 'C', 'D', 'B', 'F']
    :param i: Posición Nodo i
    :param j: Posición Nodo j
    :param solution: Solución a la que se aplicara el intercambio
    :return: Nueva solución
    """
    _solution = list(solution)
    _solution[i], _solution[j] = _solution[j], _solution[i]
    return _solution

def get_swap_delta(
        i: int,
        j: int,
        solution: SolutionType,
        problem: TSProblemType
) -> NumericType:
    """
    Calcula la variación del costo total `Δ` al intercambiar los nodos
    en las posiciones i y j.\n
    Realiza una operación de complejidad constante O(1) calculando
    únicamente la diferencia local de las aristas incidentes afectadas, sin
    recorrer la ruta completa.\n
    Δ = Costoₐᵣᵢₛₜₐₛ_ₙᵤₑᵥₐₛ - Costoₐᵣᵢₛₜₐₛ_ᵣₑₘₒᵥᵢₔₐₛ
    :param i: Posición Nodo i
    :param j: Posición Nodo j
    :param solution: Solución a la que se aplicara el intercambio
    :param problem: Instancia de tsplib95.models.Problem
    :return: delta
    """
    n = len(solution)
    a_prev, a, a_next = solution[i-1], solution[i], solution[(i+1)%n]
    b_prev, b, b_next = solution[j-1], solution[j], solution[(j+1)%n]

    if j == i + 1: # Nodos adyacentes
        return (problem.get_weight(a_prev, b) + problem.get_weight(a, b_next)) - \
                (problem.get_weight(a_prev, a) + problem.get_weight(b, b_next))
    else:
        return (problem.get_weight(a_prev, b) + problem.get_weight(b, a_next) +
                 problem.get_weight(b_prev, a) + problem.get_weight(a, b_next)) - \
                (problem.get_weight(a_prev, a) + problem.get_weight(a, a_next) +
                 problem.get_weight(b_prev, b) + problem.get_weight(b, b_next))

def two_opt(i: int, j: int, solution: SolutionType) -> SolutionType:
    """
    Invierte los nodos dentro del intervalo o rango [i,j].
    >>> two_opt(i=1, j=4, solution=['A', 'B', 'C', 'D', 'E', 'F'])
    >>> ['A', 'E', 'D', 'C', 'B', 'F']
    :param i: Posición Nodo i
    :param j: Posición Nodo j
    :param solution: Solución a la que se aplicara el intercambio
    :return: Nueva solución
    """
    if i>j:
        raise ValueError("i es mayor que j")
    return solution[:i] + solution[i:j+1][::-1] + solution[j + 1:]

def get_two_opt_delta(
        i: int,
        j: int,
        solution: SolutionType,
        problem: TSProblemType
) -> NumericType:
    """
    Calcula la variación del costo total `Δ` al aplicar una inversion de
    segmento entre los índices i y j.\n
    Esta operación es de complejidad constante $O(1)$ para problemas simétricos,
    ya que la inversión del sub-camino interno conserva su longitud total. El
    cálculo se limita a los puntos de corte del grafo.\n
    Δ = [dist(i-1, j) + dist(i, j+1)] - [dist(i-1, i) + dist(j, j+1)]
    :param i: Posición Nodo i
    :param j: Posición Nodo j
    :param solution: Solución a la que se aplicara el intercambio
    :param problem: Instancia de tsplib95.models.Problem
    :return: delta
    """
    n = len(solution)
    if i == 0 and j == n - 1:
        return 0
    a, b = solution[i-1], solution[i]
    c, d = solution[j], solution[(j + 1) % n]
    return (problem.get_weight(a, c) + problem.get_weight(b, d)) - \
            (problem.get_weight(a, b) + problem.get_weight(c, d))

def shuffle(i: int, j: int, solution: SolutionType) -> SolutionType:
    """
    Del intervalo o rango [i, j], baraja los nodos dentro de ese intervalo\n
    >>> shuffle(i=1, j=4, solution=['A', 'B', 'C', 'D', 'E', 'F'])
    >>> ['A', 'E', 'C', 'B', 'D', 'F']
    :param i: Posición Nodo i
    :param j: Posición Nodo j
    :param solution: Solución a la que se aplicara el intercambio
    :return: Nueva solución
    """
    subarray = solution[i : j + 1]
    shuffled_subarray = random.sample(subarray, len(subarray))
    return solution[:i] + shuffled_subarray + solution[j + 1:]

def insertion(i: int, j: int, solution: SolutionType) -> SolutionType:
    """
    Toma el elemento de la posición `i` y lo inserta en la posición `j`
    >>> insertion(i=1, j=4, solution=['A', 'B', 'C', 'D', 'E', 'F'])
    >>> ['A', 'C', 'D', 'E', 'B', 'F']
    :param i: posición o índice del elemento a retirar
    :param j: posición o índice donde se desea insertar
    :param solution:
    :return:
    """
    _solution = list(solution)
    node_for_move = _solution.pop(i)
    _solution.insert(j, node_for_move)
    return _solution

strategies: Dict[str, Callable[[int, int, SolutionType], SolutionType]] = {
    "swap": swap_nodes,
    "2-opt": two_opt,
    "shuffle": shuffle,
    "insertion": insertion
}

delta_callback = {
    "swap": get_swap_delta,
    "2-opt": get_two_opt_delta,
}

def generar_vecina(
        solucion: SolutionType,
        problem: TSProblemType,
        variant: Literal["swap", "2-opt", "shuffle"] = "swap",
) -> Tuple[SolutionType, NumericType]:
    """
    Generador de soluciones vecinas: 2-opt (intercambiar 2 nodos) Si hay N
    nodos se generan (N-1)x(N-2)/2 soluciones.\n
    Se puede modificar para aplicar otros generadores distintos que 2-opt
    :param solucion: Lista de nodos
    :param problem: Instancia de tsplib95.models.Problem
    :param variant: Estrategia para generar la vecina: Por defecto "swap"
    :return:
    """
    mejor_solucion = list(solucion)
    mejor_distancia = distancia_total(solucion, problem)
    n = len(solucion)
    variant_callback = strategies[variant]
    es_simetrico = hasattr(problem, 'type') and problem.type == 'TSP'

    for i in range(1, n - 1):
        for j in range(i + 1, n):
            # Complejidad de estimación de distancia O(1)
            # La ventaja de esta estimación es que se puede hacer antes de
            # ejecutar la estrategia de cambio de nodos, pero es válido
            # únicamente para grafos simétricos y la operacion 2-opt o la
            # operacion swap
            if es_simetrico and variant == "2-opt":
                delta = get_two_opt_delta(i, j, mejor_solucion, problem)
            elif variant == "swap":
                delta = get_swap_delta(i, j, mejor_solucion, problem)
            else:
                delta = None
            if delta is not None:
                if mejor_distancia + delta < mejor_distancia:
                    mejor_distancia = mejor_distancia + delta
                    mejor_solucion = variant_callback(i, j, mejor_solucion)
            else:
                # Complejidad de estimación de distancia O(N)
                vecina = variant_callback(i, j, mejor_solucion)
                # Se evalúa la nueva solución ...
                distancia_vecina = distancia_total(vecina, problem)
                # ... Para guardarla si mejora las anteriores
                if distancia_vecina < mejor_distancia:
                    mejor_distancia = distancia_vecina
                    mejor_solucion = vecina
    return mejor_solucion, mejor_distancia

print("Distancia Solución Inicial:", distancia_inicial)
soluciones = [
    generar_vecina(solucion_inicial, tsp_problem),
    generar_vecina(solucion_inicial, tsp_problem, variant="2-opt"),
    generar_vecina(solucion_inicial, tsp_problem, variant="shuffle"),
]
print("Distancia Mejor Solución Local con Swap:", soluciones[0][1])
print("Distancia Mejor Solución Local con 2-OPT:", soluciones[1][1])
print("Distancia Mejor Solución Local con Shuffle:", soluciones[2][1])

Distancia Solución Inicial: 3512
Distancia Mejor Solución Local con Swap: 1844
Distancia Mejor Solución Local con 2-OPT: 1537
Distancia Mejor Solución Local con Shuffle: 2887

# Elegimos la menor solucion entre las 3 variantes (usualmente suele ser 2-opt)
nueva_solucion, nueva_distancia = min(soluciones, key=lambda x: x[1])
nueva_distancia

1537

Búsqueda Local(iteraciones):

def busqueda_local(
        solucion_inicial: SolutionType,
        problem: TSProblemType,
        variant: Literal["swap", "2-opt", "shuffle"] = "swap",
        verbose: bool = False
) -> Tuple[SolutionType, NumericType]:
    """
    Búsqueda Local(iteraciones):\n
    * Sobre el operador de vecindad 2-opt(función generar_vecina)\n
    * Sin criterio de parada, se para cuando no es posible mejorar.
    :param solucion_inicial: Lista de nodos
    :param problem: Instancia de tsplib95.models.Problem
    :param variant: Estrategia para generar la vecina: Por defecto "swap"
    :param verbose:
    :return:
    """

    #Generar una solucion inicial de referencia(aleatoria)
    solucion_referencia = list(solucion_inicial)
    mejor_distancia = distancia_total(solucion_referencia, problem)

    iteracion = 0  # Un contador para saber las iteraciones que hacemos
    while True:
        iteracion += 1  # Incrementamos el contador

        # Obtenemos la mejor vecina y la evaluamos para ver si mejoramos
        # respecto a lo encontrado hasta el momento
        nueva_solucion, distancia_vecina = generar_vecina(solucion_referencia, problem, variant)
        # Si no mejoramos hay que terminar. Hemos llegado a un minimo local
        # (según nuestro operador de vecindad 2-opt)
        if distancia_vecina < mejor_distancia:
            # mejor_solucion = copy.deepcopy(vecina)
            solucion_referencia = nueva_solucion  #Guarda la mejor solución encontrada
            mejor_distancia = distancia_vecina

        else:
            if verbose:
                print(
                    "En la iteración ", iteracion,
                    ", la mejor solución encontrada es:", solucion_referencia
                )
                print("Distancia: ", mejor_distancia)
            return solucion_referencia, mejor_distancia


mejor_solucion, mejor_distancia = busqueda_local(nueva_solucion, tsp_problem, variant="2-opt", verbose=True)

En la iteración  3 , la mejor solución encontrada es: [0, 3, 27, 2, 28, 30, 29, 8, 41, 23, 9, 40, 24, 21, 39, 22, 38, 34, 33, 20, 35, 36, 17, 37, 15, 16, 14, 19, 13, 5, 26, 18, 12, 11, 25, 10, 4, 6, 1, 7, 31, 32]
Distancia:  1397

Búsqueda local con entornos Variables (VNS)

Esta propuesta se basa en la idea de agitar (shaking) que se ha interpretado para este caso en concreto como agregar una perturbación para evitar el estancamiento en mínimos locales inherentes al operador 2-opt.

El código actual se basa en la solución para la Búsqueda por Entornos Variables (VNS) propuesta por [1], con distintos niveles de intensidad que controlan dinámicamente la diversificación del espacio de búsqueda y la preservación de las estructuras de las rutas previamente optimizadas.

El nivel más bajo de perturbación (nivel 0) únicamente hace un intercambio de 2 nodos aleatorios.

Desde el nivel 1 al nivel 3 se barajea a un segmento proporcional al nivel elegido ($0.1 \times intensidad$)

def perturbar(
        solucion: SolutionType,
        intensidad:Literal[0,1,2,3]
) -> SolutionType:
    """
    Perturba a la solución según el nivel de `intensidad` de la perturbación
    deseada.\n
    Arbitrariamente se ha elegido 4 niveles de intensidad:\n
    intensidad=0: swap a dos nodos \n
    intensidad=1: barajeo de un segmento pequeño (10% de la ruta) \n
    intensidad=2: barajeo de un segmento mediano (20% de la ruta) \n
    intensidad=3: barajeo de un segmento grande (30% de la ruta) \n
    :param solucion:
    :param intensidad:
    :return:
    """
    n = len(solucion)
    if intensidad == 0:
        i, j = random.sample(range(n), 2)
        return swap_nodes(i, j, solucion)
    subsegment = max(2, int(n * 0.1 * intensidad))
    if subsegment > n:
        subsegment = n
    i = random.randint(0, n - subsegment)
    j = i + subsegment - 1
    return shuffle(i, j, solucion)


def busqueda_local_con_entornos_variables(
        solucion: SolutionType,
        problem: TSProblemType,
        max_iter: int = 100,
        verbose: bool = False
) -> Tuple[SolutionType, NumericType]:
    solucion_actual = list(solucion)
    mejor_distancia = distancia_total(solucion_actual, problem)
    k_max = 3
    iteracion = 0

    while iteracion <= max_iter:
        k = 0
        while k <= k_max and iteracion <= max_iter:
            iteracion += 1
            posible_candidata = perturbar(solucion_actual, k)
            candidata_optimizada, distancia_candidata = busqueda_local(posible_candidata, problem, variant="2-opt")

            if distancia_candidata < mejor_distancia:
                solucion_actual = candidata_optimizada
                mejor_distancia = distancia_candidata
                k = 0
                if verbose:
                    print(
                        "En la iteración ", iteracion,
                        ", la mejor solución encontrada es:", solucion_actual
                    )
                    print("Distancia: ", mejor_distancia)
            else:
                k += 1
    return solucion_actual, mejor_distancia

mejor_solucion_vns, mejor_distancia = busqueda_local_con_entornos_variables(
    mejor_solucion, tsp_problem, 150, True
)

# Soluciones que llevan a un coste de 1273 para swiss42.tsp
# [0, 32, 34, 33, 20, 35, 36, 31, 17, 7, 37, 15, 16, 14, 19, 13, 5, 26, 18, 12, 11, 25, 10, 8, 9, 41, 23, 40, 24, 21, 39, 22, 38, 30, 29, 28, 27, 2, 3, 4, 6, 1]
# [0, 32, 34, 33, 20, 35, 36, 31, 17, 7, 37, 15, 16, 14, 19, 13, 5, 26, 18, 12, 11, 25, 10, 8, 41, 23, 9, 21, 40, 24, 39, 22, 38, 30, 29, 28, 2, 27, 3, 4, 6, 1]
# [0, 32, 34, 33, 20, 35, 36, 31, 17, 7, 37, 15, 16, 14, 19, 13, 5, 26, 18, 12, 11, 25, 10, 8, 9, 41, 23, 40, 24, 21, 39, 22, 38, 30, 29, 28, 2, 27, 3, 4, 6, 1]
# [0, 32, 34, 33, 20, 35, 36, 31, 17, 7, 37, 15, 16, 14, 19, 13, 5, 26, 18, 12, 11, 25, 10, 8, 41, 23, 9, 21, 40, 24, 39, 22, 38, 30, 29, 28, 27, 2, 3, 4, 6, 1]
# [0, 1, 6, 4, 3, 2, 27, 28, 29, 30, 38, 22, 39, 24, 40, 21, 9, 23, 41, 8, 10, 25, 11, 12, 18, 26, 5, 13, 19, 14, 16, 15, 37, 7, 17, 31, 36, 35, 20, 33, 34, 32]
# [15, 37, 7, 17, 31, 36, 35, 20, 33, 34, 32, 0, 1, 6, 4, 3, 27, 2, 28, 29, 30, 38, 22, 39, 24, 40, 21, 9, 23, 41, 8, 10, 25, 11, 12, 18, 26, 5, 13, 19, 14, 16]
# [22, 39, 21, 24, 40, 23, 41, 9, 8, 10, 25, 11, 12, 18, 26, 5, 13, 19, 14, 16, 15, 37, 7, 17, 31, 36, 35, 20, 33, 34, 32, 0, 1, 6, 4, 3, 27, 2, 28, 29, 30, 38]
# [32, 34, 33, 20, 35, 36, 31, 17, 7, 37, 15, 16, 14, 19, 13, 5, 26, 18, 12, 11, 25, 10, 8, 9, 41, 23, 40, 24, 21, 39, 22, 38, 30, 29, 28, 27, 2, 3, 4, 6, 1, 0]
# [36, 35, 20, 33, 34, 32, 0, 1, 6, 4, 3, 2, 27, 28, 29, 30, 38, 22, 39, 21, 24, 40, 23, 41, 9, 8, 10, 25, 11, 12, 18, 26, 5, 13, 19, 14, 16, 15, 37, 7, 17, 31]
# [37, 15, 16, 14, 19, 13, 5, 26, 18, 12, 11, 25, 10, 8, 9, 41, 23, 40, 24, 21, 39, 22, 38, 30, 29, 28, 27, 2, 3, 4, 6, 1, 0, 32, 34, 33, 20, 35, 36, 31, 17, 7]

En la iteración  1 , la mejor solución encontrada es: [0, 31, 17, 36, 35, 20, 33, 34, 38, 22, 39, 21, 24, 40, 9, 23, 41, 10, 25, 11, 12, 18, 26, 5, 13, 19, 14, 16, 15, 37, 7, 1, 6, 4, 3, 27, 2, 8, 29, 30, 28, 32]
Distancia:  1383
En la iteración  5 , la mejor solución encontrada es: [0, 1, 6, 4, 3, 2, 27, 28, 8, 29, 30, 38, 22, 39, 21, 24, 40, 9, 23, 41, 10, 25, 11, 12, 18, 26, 5, 13, 19, 14, 16, 15, 37, 7, 17, 31, 36, 35, 20, 33, 34, 32]
Distancia:  1315
En la iteración  9 , la mejor solución encontrada es: [0, 1, 6, 4, 3, 2, 27, 28, 30, 38, 22, 39, 21, 24, 40, 23, 41, 9, 29, 8, 10, 25, 11, 12, 18, 26, 5, 13, 19, 14, 16, 15, 37, 7, 17, 31, 36, 35, 20, 33, 34, 32]
Distancia:  1314
En la iteración  12 , la mejor solución encontrada es: [0, 1, 6, 4, 3, 2, 27, 28, 29, 30, 38, 22, 39, 24, 40, 21, 9, 23, 41, 8, 10, 25, 11, 12, 18, 26, 5, 13, 19, 14, 16, 15, 37, 7, 17, 31, 36, 35, 20, 33, 34, 32]
Distancia:  1273

SIMULATED ANNEALING

El Recocido Simulado es una metaheurística probabilística inspirada en el proceso físico de recocido de metales, donde un material se calienta y luego se enfría lentamente para alcanzar una estructura cristalina de mínima energía (estado óptimo).

A diferencia de la Búsqueda Local, que tiende a estancarse en óptimos locales por aceptar únicamente mejoras, el Recocido Simulado permite escapar de estas "trampas" aceptando temporalmente soluciones que empeoran la función objetivo.

Generación de Vecindad:

Es el mecanismo que define el conjunto de soluciones candidatas accesibles desde una solución actual mediante la aplicación de un operador de movimiento o perturbación local. La elección del operador no solo afecta la velocidad, sino la "suavidad" del recorrido por el paisaje de búsqueda: un movimiento suave permite descender gradualmente hacia el mínimo, mientras que un movimiento brusco puede destruir el progreso previo.

Vecindad Aleatoria:

Este operador selecciona dos ciudades al azar en la ruta y intercambia sus posiciones. Aunque computacionalmente ligero, es un movimiento "brusco/destructivo" desde el punto de vista topológico, ya que rompe cuatro enlaces de la ruta original. Se utiliza principalmente para diversificación brusca.

Vecindad 2-Opt:

Consiste en eliminar dos aristas no adyacentes y reconectar los nodos resultantes invirtiendo el sentido del sub-segmento intermedio. Supone una generación de vecindad más suave manteniendo la coherencia de los vecinos dentro del segmento invertido.

Vecindad por Inserción:

Extrae un nodo de su posición actual (i) y la reinserta en otra posición arbitraria (j). A diferencia del 2-opt, este movimiento no invierte el orden de los nodos intermedios. Es la variante más suave para correcciones puntuales, ya que permite mover un nodo mal ubicado sin alterar el orden ni el sentido del resto de la secuencia.

Una propuesta híbrida experimental:

Incorporado a este entregable por sugerencia técnica del asistente de IA Generativa (Gemini) para mejorar suavidad al generar vecindades óptimas.

Se aplica una estrategia probabilística combinando las dos propuestas más suaves en lo referente a la generación de vecindad. Se propone la siguiente distribución (de manera arbitraria o experimental):

• 80% 2-opt: Para resolver cruces y optimizar la forma general.
• 20% Inserción: Para reubicar nodos aislados.

Esta mezcla promete balancear (al menos experimentalmente se ha observado aquello) la corrección estructural (2-opt) con la precisión local (Inserción), evitando que el algoritmo se estanque en configuraciones que un solo operador no podría resolver.

Estrategias de Enfriamiento:

El esquema de enfriamiento es el mecanismo que regula el descenso de la temperatura $T$, determinando cuánto tiempo dedica el algoritmo a la exploración global frente a la intensificación local.

Esquema Geométrico o Descenso Exponencial:

Es la estrategia clásica y la más extendida en la literatura básica del Recocido Simulado debido a su simplicidad. $$ T_{k+1}=\alpha \cdot T_k $$ Donde típicamente $0.8≤\alpha ≤0.99$. Este método genera un decaimiento predecible, pero puede resultar inflexible: enfría con la misma "agresividad" tanto al inicio (cuando se necesita caos) como al final (cuando se necesita precisión).

Estrategia de enfriamiento de Lundy-Mees:

Incorporado a este entregable por sugerencia técnica del asistente de IA Generativa (Gemini) para mejorar la convergencia en etapas finales.

Este esquema, propuesto por [2], plantea un descenso no lineal que ajusta la velocidad de enfriamiento según la magnitud de la temperatura actual: $$ T_{k+1}=\frac{T_k}{1+\beta \cdot T_k} $$ A diferencia del esquema geométrico, esta fórmula provoca un descenso rápido cuando T es alta (evitando el desperdicio de cómputo en búsquedas aleatorias excesivas) y, crucialmente, ralentiza el enfriamiento de forma extrema cuando T se acerca a cero. Esto permite una fase de "recocido lento" o fine-tuning mucho más exhaustiva en las iteraciones finales, aumentando la probabilidad de encontrar el óptimo global en instancias complejas del TSP.

def genera_vecina_aleatorio(
        solucion: SolutionType,
        problem: TSProblemType
) -> Tuple[SolutionType, NumericType]:
    """
    Generador de 1 solución vecina 2-opt 100% aleatoria (intercambiar 2 nodos)\n
    Mejorable eligiendo otra forma de elegir una vecina.
    :param solucion:
    :return:
    """
    #Se eligen dos nodos aleatoriamente
    i, j = sorted(random.sample(range(1, len(solucion)), 2))
    #Devuelve una nueva solución pero intercambiando los dos nodos elegidos al azar
    _solucion = swap_nodes(i, j, solucion)
    delta = get_swap_delta(i, j, _solucion, problem)
    return _solucion, delta


def probabilidad(T: float, d: float) -> bool:
    """
    Función de probabilidad para aceptar peores soluciones
    :param T: Temperatura
    :param d:
    :return:
    """
    if d < 0: return True
    if T <= 1e-9: return False
    return random.random() < math.exp(-d / T)


def bajar_temperatura(T: float, beta: float = 0.99) -> float:
    """
    Función de descenso de temperatura
    :param T: Temperatura
    :param beta: coeficiente de descenso de temperatura
    :return:
    """
    return T * beta

def bajar_temperatura_lundy_mees(T: float, beta: float = 0.0001) -> float:
    """
    Función de descenso de temperatura basado en la ecuación de Lundy-Mess
    :param T: Temperatura
    :param beta: coeficiente
    :return:
    """
    return T / (1 + beta * T)

def generar_vecina_2_opt(
        solucion: SolutionType,
        problem: TSProblemType
) -> Tuple[SolutionType, NumericType]:
    """
    Función que genera vecinos basado en la operacion 2-opt
    :param solucion:
    :param problem:
    :return:
    """
    n = len(solucion)
    i, j = sorted(random.sample(range(n), 2))
    _solucion = two_opt(i, j, solucion)
    # no es un grafo simetrico
    if hasattr(problem, 'type') and problem.type == 'ATSP':
        distancia_inicial = distancia_total(solucion, problem)
        distancia_final = distancia_total(_solucion, problem)
        delta = distancia_final - distancia_inicial
    else:
        delta = get_two_opt_delta(i, j, solucion, problem)
    return _solucion, delta

def generar_vecina_insercion(
        solucion: SolutionType,
        problem: TSProblemType
) -> Tuple[SolutionType, NumericType]:
    """
    Función que genera vecinos al insertar un nodo de un sitio a otro
    :param solucion:
    :param problem:
    :return:
    """
    n = len(solucion)
    i, j = random.sample(range(n), 2)
    _solucion = insertion(i, j, solucion)
    distancia_inicial = distancia_total(solucion, problem)
    distancia_final = distancia_total(_solucion, problem)
    delta = distancia_final - distancia_inicial
    return _solucion, delta

def generar_vecina_probabilistica(
        solucion: SolutionType,
        problem: TSProblemType
) -> Tuple[SolutionType, NumericType]:
    """
    Función que probabilísticamente usa las dos estrategias de generación de
    vecindad más *suaves*.\n
    80% 2-opt\n
    20% insertion
    :param solucion:
    :param problem:
    :return:
    """
    if random.random() < 0.8:
        return generar_vecina_2_opt(solucion, problem)
    else:
        return generar_vecina_insercion(solucion, problem)

estrategia_generador_vecino = {
    "swap": genera_vecina_aleatorio,
    "2-opt": generar_vecina_2_opt,
    "insertion": generar_vecina_insercion,
    "prob": generar_vecina_probabilistica
}

calculo_temperatura = {
    "geometric": bajar_temperatura,
    "lundy-mees": bajar_temperatura_lundy_mees,
}

def recocido_simulado(
        problem: TSProblemType,
        TEMPERATURA: float,
        variante_vecino: Literal["swap", "2-opt", "insertion", "prob"] = "swap",
        variante_temperatura: Literal["geometric", "lundy-mees"] = "geometric",
        min_temp: float = 0.0001
) -> SolutionType:
    """
    :param problem: datos del problema
    :param TEMPERATURA:
    :param variante_vecino:
    :param variante_temperatura:
    :param min_temp:
    :return:
    """

    solucion_referencia = crear_solucion(problem.cached_nodes)
    distancia_referencia = distancia_total(solucion_referencia, problem)

    mejor_solucion = list(solucion_referencia)  #x* del pseudocodigo
    mejor_distancia = distancia_referencia  #F* del pseudocodigo

    variant_callback = estrategia_generador_vecino[variante_vecino]
    variant_temp_calc = calculo_temperatura[variante_temperatura]
    N = 0
    while TEMPERATURA > min_temp: # no converge
        N += 1
        #Genera una solución vecina
        vecina, delta = variant_callback(solucion_referencia, problem)

        #Si la nueva vecina es mejor se cambia
        #Si es peor se cambia según una probabilidad que depende de T y delta
        # (distancia_referencia - distancia_vecina)
        if delta < 0 or probabilidad(TEMPERATURA, abs(delta)):
            #solucion_referencia = copy.deepcopy(vecina)
            solucion_referencia = vecina
            distancia_referencia += delta

            #Si es la mejor solución de todas se guarda(siempre!!!)
            if distancia_referencia < mejor_distancia:
                mejor_solucion = list(vecina)
                mejor_distancia = distancia_referencia

        #Bajamos la temperatura
        TEMPERATURA = variant_temp_calc(TEMPERATURA)

    print("La mejor solución encontrada es ", end="")
    print(mejor_solucion)
    print("con una distancia total de ", end="")
    print(mejor_distancia)
    return mejor_solucion

print("Prueba recocido con cálculo de temperatura bajo el esquema geométrico y vecindad por intercambio (swap)")
recocido_simulado(tsp_problem, 10000, variante_vecino="swap", variante_temperatura="geometric", min_temp=0.0001)
print("\nPrueba recocido con cálculo de temperatura bajo el esquema geométrico")
recocido_simulado(tsp_problem, 10000, variante_vecino="prob", variante_temperatura="geometric", min_temp=0.0001)
print("\nPrueba recocido con cálculo de temperatura ecuación de Lundy-Mess")
mejor_solucion_sa = recocido_simulado(tsp_problem, 150, variante_vecino="prob", variante_temperatura="lundy-mees", min_temp=0.025)

Prueba recocido con cálculo de temperatura bajo el esquema geométrico y vecindad por intercambio (swap)
La mejor solución encontrada es [0, 4, 22, 16, 29, 6, 2, 18, 34, 13, 28, 37, 40, 17, 10, 35, 8, 1, 21, 27, 12, 33, 26, 38, 19, 30, 5, 32, 11, 20, 25, 31, 9, 15, 24, 3, 14, 39, 7, 23, 36, 41]
con una distancia total de 4181

Prueba recocido con cálculo de temperatura bajo el esquema geométrico
La mejor solución encontrada es [20, 33, 34, 7, 0, 32, 30, 29, 38, 39, 22, 24, 40, 21, 9, 8, 41, 23, 25, 11, 12, 10, 4, 1, 3, 2, 28, 27, 6, 5, 26, 18, 13, 19, 14, 16, 15, 37, 36, 17, 31, 35]
con una distancia total de 1638

Prueba recocido con cálculo de temperatura ecuación de Lundy-Mess
La mejor solución encontrada es [28, 2, 27, 3, 4, 6, 1, 0, 32, 34, 33, 20, 35, 36, 31, 17, 7, 37, 15, 16, 14, 19, 13, 5, 26, 18, 12, 11, 25, 10, 8, 9, 41, 23, 40, 24, 21, 39, 22, 38, 30, 29]
con una distancia total de 1273

Representación en un grafo a partir de la matriz de distancias (Optimización de posiciones usando escalado multidimensional (MDS)

Multidimensional scaling problem(MDS): https://en.wikipedia.org/wiki/Multidimensional_scaling

import networkx as nx
import matplotlib.pyplot as plt
from sklearn.manifold import MDS  # Multidimensional Scaling o Escalado Multidimensional


def plot_tsp_solution(
        problem: TSProblemType,
        tsp_solution: SolutionType,
        title: str = "",
) -> None:
    """
    Dibuja el grafo de un TSP con las posiciones calculadas mediante MDS y muestra
    solo las aristas correspondientes a la solución del TSP.

    :param distance_matrix: np.ndarray, matriz de distancias entre nodos
    :param tsp_solution: list, lista de nodos en el orden de la solución del TSP
    """
    # Validaciones para verificar si el problema esta definido por
    # coordenadas en R2
    COORD_TYPES = {'EUC_2D', 'ATT', 'CEIL_2D', 'GEO', 'PSEUDO'}
    w_type = getattr(problem, 'edge_weight_type', None)
    has_coords = (w_type in COORD_TYPES) or (len(list(problem.node_coords)) > 0)

    if has_coords:
        pos = problem.node_coords
    else:
        distance_matrix = problem.edge_weights
        num_nodes = len(distance_matrix)
        # Usar MDS para calcular posiciones de los nodos
        mds = MDS(n_components=2, dissimilarity="precomputed", random_state=40)
        positions = mds.fit_transform(distance_matrix)
        # Convertir las posiciones en un diccionario para networkx
        pos = {i: positions[i] for i in range(num_nodes)}

    # Crear un subgrafo con las aristas del camino TSP
    TSP_G = nx.Graph()
    TSP_G.add_nodes_from(tsp_solution)
    path_len = len(tsp_solution)
    for i in range(path_len):
        u = tsp_solution[i]
        v = tsp_solution[(i + 1) % path_len]
        TSP_G.add_edge(u, v, weight=problem.get_weight(u, v))
    # Dibujar el grafo
    plt.figure(figsize=(8, 6))

    # Dibujar nodos
    nx.draw_networkx_nodes(TSP_G, pos, node_color='lightblue', node_size=250)

    # Dibujar las aristas del camino TSP
    nx.draw_networkx_edges(TSP_G, pos, edge_color='red', width=2)

    # Añadir etiquetas a los nodos y pesos de las aristas
    nx.draw_networkx_labels(TSP_G, pos, font_size=8, font_weight='bold')
    edge_labels = nx.get_edge_attributes(TSP_G, 'weight')
    nx.draw_networkx_edge_labels(TSP_G, pos, edge_labels=edge_labels,
                                 font_size=6)

    plt.title(
        f"Grafo TSP con solución específica de {problem.name}"
        f" Costo Total: {distancia_total(tsp_solution, problem)}"
        f"{f' - {title}' if title else ''}"
    )

    plt.show()

plot_tsp_solution(
    problem=tsp_problem,
    tsp_solution=crear_solucion(nodes),
    title="Solución Aleatoria"
)

/home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages/sklearn/manifold/_mds.py:677: FutureWarning: The default value of `n_init` will change from 4 to 1 in 1.9.
  warnings.warn(

plot_tsp_solution(
    problem=tsp_problem,
    tsp_solution=mejor_solucion_vns,
    title="Solución con VNS"
)

/home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages/sklearn/manifold/_mds.py:677: FutureWarning: The default value of `n_init` will change from 4 to 1 in 1.9.
  warnings.warn(

plot_tsp_solution(
    problem=tsp_problem,
    tsp_solution=mejor_solucion_sa,
    title="Solución con SA"
)

/home/**/03MIAR-Algoritmos-de-Optimizacion-2025/venv/lib/python3.10/site-packages/sklearn/manifold/_mds.py:677: FutureWarning: The default value of `n_init` will change from 4 to 1 in 1.9.
  warnings.warn(

Ejemplos con otros problemas cortos de TSP

file = "att48.tsp"
download_tsp_file("https://raw.githubusercontent.com/mastqe/tsplib/refs/heads/master/att48.tsp", file)

att48_problem = tsplib95.load(file)
att48_problem.cached_nodes = list(att48_problem.get_nodes())

solucion_inicial_att48, _ = busqueda_aleatoria(att48_problem, 50000)
solucion_inicial_att48, _ = busqueda_local(solucion_inicial_att48, att48_problem, variant="2-opt", verbose=True)
mejor_solucion_att48_vns, mejor_distancia = busqueda_local_con_entornos_variables(
    solucion_inicial_att48, att48_problem, 150, True
)
plot_tsp_solution(
    problem=att48_problem,
    tsp_solution=mejor_solucion_att48_vns,
    title="Solución con VNS"
)
mejor_solucion_att48_sa = recocido_simulado(
    att48_problem, 100, variante_vecino="prob", variante_temperatura="lundy-mees", min_temp=0.05
)
plot_tsp_solution(
    problem=att48_problem,
    tsp_solution=mejor_solucion_att48_sa,
    title="Solución con SA"
)

# Soluciones que llevan un coste de 10628 para att48.tsp
# [1, 9, 40, 15, 12, 11, 13, 25, 14, 23, 3, 22, 16, 41, 34, 29, 2, 26, 4, 35, 45, 10, 24, 42, 5, 48, 39, 32, 21, 47, 20, 33, 46, 36, 30, 43, 17, 27, 19, 37, 6, 28, 7, 18, 44, 31, 38, 8]

En la iteración  4 , la mejor solución encontrada es: [1, 8, 9, 38, 31, 44, 18, 7, 28, 6, 37, 19, 27, 17, 43, 30, 36, 46, 33, 15, 12, 20, 47, 21, 32, 24, 42, 10, 45, 35, 4, 26, 2, 29, 5, 48, 39, 25, 14, 13, 23, 11, 40, 3, 34, 41, 16, 22]
Distancia:  10963
En la iteración  1 , la mejor solución encontrada es: [1, 8, 9, 38, 31, 44, 18, 7, 28, 6, 37, 19, 27, 17, 43, 30, 36, 46, 33, 15, 12, 20, 47, 21, 32, 24, 42, 10, 45, 35, 4, 26, 2, 29, 5, 48, 39, 25, 13, 14, 34, 41, 16, 22, 3, 23, 11, 40]
Distancia:  10919
En la iteración  9 , la mejor solución encontrada es: [1, 8, 9, 38, 31, 44, 18, 7, 28, 6, 37, 19, 27, 17, 43, 30, 36, 46, 33, 15, 12, 20, 47, 21, 32, 24, 45, 35, 4, 26, 10, 42, 2, 29, 5, 48, 39, 25, 13, 14, 34, 41, 16, 22, 3, 23, 11, 40]
Distancia:  10907
En la iteración  13 , la mejor solución encontrada es: [1, 8, 9, 38, 31, 44, 18, 7, 28, 6, 37, 19, 27, 17, 43, 30, 36, 46, 33, 15, 12, 20, 47, 13, 14, 25, 21, 32, 39, 48, 5, 42, 24, 10, 45, 35, 4, 26, 2, 29, 34, 41, 16, 22, 3, 23, 11, 40]
Distancia:  10853
En la iteración  14 , la mejor solución encontrada es: [1, 8, 9, 38, 31, 44, 18, 7, 28, 6, 37, 19, 27, 17, 43, 30, 36, 46, 33, 15, 12, 20, 47, 21, 32, 39, 48, 5, 42, 24, 10, 45, 35, 4, 26, 2, 29, 41, 34, 14, 25, 13, 23, 11, 40, 3, 22, 16]
Distancia:  10811
En la iteración  17 , la mejor solución encontrada es: [1, 8, 9, 38, 31, 44, 18, 7, 28, 6, 37, 19, 27, 17, 43, 30, 36, 46, 33, 15, 12, 20, 47, 21, 32, 39, 48, 5, 42, 24, 10, 45, 35, 4, 26, 2, 29, 34, 41, 16, 22, 3, 23, 14, 25, 13, 11, 40]
Distancia:  10742
En la iteración  26 , la mejor solución encontrada es: [1, 8, 9, 38, 31, 44, 18, 7, 28, 6, 37, 19, 27, 17, 43, 30, 36, 46, 33, 20, 47, 21, 32, 39, 48, 5, 42, 24, 10, 45, 35, 4, 26, 2, 29, 34, 41, 16, 22, 3, 23, 14, 25, 13, 11, 12, 15, 40]
Distancia:  10638
En la iteración  67 , la mejor solución encontrada es: [1, 9, 40, 15, 12, 11, 13, 25, 14, 23, 3, 22, 16, 41, 34, 29, 2, 26, 4, 35, 45, 10, 24, 42, 5, 48, 39, 32, 21, 47, 20, 33, 46, 36, 30, 43, 17, 27, 19, 37, 6, 28, 7, 18, 44, 31, 38, 8]
Distancia:  10628

La mejor solución encontrada es [4, 26, 42, 48, 5, 29, 2, 41, 34, 14, 25, 13, 23, 3, 22, 16, 1, 8, 9, 38, 31, 44, 18, 7, 28, 6, 37, 19, 27, 17, 43, 30, 36, 46, 33, 20, 12, 15, 40, 11, 47, 21, 39, 32, 24, 10, 45, 35]
con una distancia total de 10970

file = "eil51.tsp"
download_tsp_file("https://raw.githubusercontent.com/mastqe/tsplib/refs/heads/master/eil51.tsp", file)

eil51_problem = tsplib95.load(file)
eil51_problem.cached_nodes = list(eil51_problem.get_nodes())

solucion_inicial_eil51, _ = busqueda_aleatoria(eil51_problem, 50000)
solucion_inicial_att48, _ = busqueda_local(solucion_inicial_eil51, eil51_problem, variant="2-opt", verbose=True)
mejor_solucion_eil51_vns, mejor_distancia = busqueda_local_con_entornos_variables(
    solucion_inicial_eil51, eil51_problem, 150, True
)
plot_tsp_solution(
    problem=eil51_problem,
    tsp_solution=mejor_solucion_eil51_vns,
    title="Solución con VNS"
)
mejor_solucion_eil51_sa = recocido_simulado(
    eil51_problem, 100, variante_vecino="prob", variante_temperatura="lundy-mees", min_temp=0.05
)
plot_tsp_solution(
    problem=eil51_problem,
    tsp_solution=mejor_solucion_eil51_sa,
    title="Solución con SA"
)
# Soluciones que llevan a un coste de  426 para eil51.tsp
# [1, 22, 8, 26, 31, 28, 3, 36, 35, 20, 2, 29, 21, 16, 50, 34, 30, 9, 49, 10, 39, 33, 45, 15, 44, 42, 19, 40, 41, 13, 25, 14, 24, 43, 7, 23, 48, 6, 27, 51, 46, 12, 47, 18, 4, 17, 37, 5, 38, 11, 32]
# [2, 22, 1, 32, 11, 38, 5, 49, 9, 50, 16, 29, 21, 34, 30, 10, 39, 33, 45, 15, 37, 17, 44, 42, 19, 40, 41, 13, 25, 14, 18, 4, 47, 12, 46, 51, 27, 6, 24, 43, 7, 23, 48, 8, 26, 31, 28, 3, 36, 35, 20]

En la iteración  5 , la mejor solución encontrada es: [1, 22, 8, 26, 31, 28, 3, 36, 35, 20, 2, 29, 21, 50, 34, 30, 10, 39, 33, 45, 15, 44, 42, 19, 40, 41, 13, 25, 14, 24, 43, 7, 23, 48, 6, 27, 51, 46, 12, 47, 18, 4, 17, 37, 5, 49, 9, 16, 38, 11, 32]
Distancia:  429
En la iteración  1 , la mejor solución encontrada es: [1, 2, 22, 8, 48, 6, 23, 24, 43, 7, 26, 31, 28, 3, 36, 35, 20, 29, 16, 38, 5, 49, 9, 50, 21, 34, 30, 10, 39, 33, 45, 15, 44, 42, 40, 19, 41, 13, 25, 14, 18, 4, 17, 37, 12, 47, 51, 46, 11, 32, 27]
Distancia:  450
En la iteración  3 , la mejor solución encontrada es: [1, 22, 2, 11, 32, 46, 51, 47, 12, 37, 17, 4, 18, 14, 25, 13, 41, 19, 40, 42, 44, 15, 45, 33, 39, 10, 30, 34, 21, 50, 9, 49, 5, 38, 16, 29, 20, 35, 36, 3, 28, 31, 26, 7, 43, 24, 23, 6, 48, 8, 27]
Distancia:  449
En la iteración  4 , la mejor solución encontrada es: [1, 8, 26, 7, 43, 24, 23, 48, 6, 27, 46, 51, 47, 12, 37, 17, 4, 18, 14, 25, 13, 41, 40, 19, 42, 44, 15, 45, 33, 39, 10, 30, 34, 21, 50, 9, 49, 5, 38, 16, 29, 20, 35, 36, 3, 28, 31, 22, 2, 11, 32]
Distancia:  446
En la iteración  6 , la mejor solución encontrada es: [1, 8, 26, 7, 43, 24, 23, 48, 6, 27, 51, 46, 12, 47, 37, 17, 4, 18, 14, 25, 13, 41, 40, 19, 42, 44, 15, 45, 33, 39, 10, 30, 34, 21, 50, 9, 49, 5, 38, 16, 29, 20, 35, 36, 3, 28, 31, 22, 2, 11, 32]
Distancia:  445
En la iteración  10 , la mejor solución encontrada es: [1, 22, 2, 29, 20, 35, 36, 3, 28, 31, 8, 26, 7, 43, 24, 23, 48, 6, 14, 25, 18, 47, 17, 4, 13, 41, 19, 40, 42, 44, 37, 15, 45, 33, 39, 10, 30, 34, 21, 50, 16, 11, 38, 9, 49, 5, 12, 46, 51, 27, 32]
Distancia:  442
En la iteración  13 , la mejor solución encontrada es: [1, 22, 2, 29, 20, 35, 36, 3, 28, 31, 8, 26, 7, 43, 24, 23, 48, 6, 14, 25, 18, 47, 17, 4, 13, 41, 19, 40, 42, 44, 37, 15, 45, 33, 39, 10, 49, 9, 30, 34, 21, 50, 16, 11, 38, 5, 12, 46, 51, 27, 32]
Distancia:  441
En la iteración  16 , la mejor solución encontrada es: [1, 22, 2, 29, 20, 35, 36, 3, 28, 31, 8, 26, 7, 43, 24, 23, 48, 6, 14, 25, 18, 13, 41, 19, 40, 42, 44, 15, 45, 33, 39, 10, 30, 34, 21, 50, 16, 11, 38, 9, 49, 5, 37, 17, 4, 47, 12, 46, 51, 27, 32]
Distancia:  437
En la iteración  23 , la mejor solución encontrada es: [1, 22, 2, 29, 20, 35, 36, 3, 28, 31, 26, 8, 48, 6, 23, 7, 43, 24, 14, 25, 18, 13, 41, 19, 40, 42, 44, 15, 45, 33, 39, 10, 30, 34, 21, 50, 16, 11, 38, 9, 49, 5, 37, 17, 4, 47, 12, 46, 51, 27, 32]
Distancia:  436
En la iteración  44 , la mejor solución encontrada es: [1, 22, 2, 29, 20, 35, 36, 3, 28, 31, 26, 8, 48, 6, 23, 7, 43, 24, 14, 25, 13, 41, 19, 40, 42, 44, 15, 45, 33, 39, 10, 30, 34, 21, 50, 16, 11, 38, 9, 49, 5, 37, 17, 4, 18, 47, 12, 46, 51, 27, 32]
Distancia:  432
En la iteración  72 , la mejor solución encontrada es: [1, 22, 8, 26, 31, 28, 3, 36, 35, 20, 29, 2, 16, 50, 21, 34, 30, 10, 39, 33, 45, 15, 44, 42, 40, 19, 41, 13, 25, 14, 24, 43, 7, 23, 48, 6, 27, 51, 46, 12, 47, 18, 4, 17, 37, 5, 49, 9, 38, 11, 32]
Distancia:  428
En la iteración  83 , la mejor solución encontrada es: [1, 22, 8, 26, 31, 28, 3, 36, 35, 20, 2, 29, 21, 16, 50, 34, 30, 10, 39, 33, 45, 15, 44, 42, 40, 19, 41, 13, 25, 14, 24, 43, 7, 23, 48, 6, 27, 51, 46, 12, 47, 18, 4, 17, 37, 5, 49, 9, 38, 11, 32]
Distancia:  427
En la iteración  120 , la mejor solución encontrada es: [1, 22, 8, 26, 31, 28, 3, 36, 35, 20, 2, 29, 21, 16, 50, 34, 30, 9, 49, 10, 39, 33, 45, 15, 44, 42, 19, 40, 41, 13, 25, 14, 24, 43, 7, 23, 48, 6, 27, 51, 46, 12, 47, 18, 4, 17, 37, 5, 38, 11, 32]
Distancia:  426

La mejor solución encontrada es [2, 22, 1, 32, 11, 38, 5, 49, 9, 50, 16, 29, 21, 34, 30, 10, 39, 33, 45, 15, 37, 17, 44, 42, 19, 40, 41, 13, 25, 14, 18, 4, 47, 12, 46, 51, 27, 6, 24, 43, 7, 23, 48, 8, 26, 31, 28, 3, 36, 35, 20]
con una distancia total de 429

Nota sobre el uso de herramientas de IA generativa

En la elaboración de este notebook se emplearon herramientas de inteligencia artificial generativa de manera puntual y como apoyo conceptual, con los siguientes fines específicos:

• Propuesta conceptual de esquemas de generación de vecindades para el algoritmo de Simulated Annealing, incluyendo configuraciones topológicamente más suaves, como la combinación probabilística de operadores (por ejemplo, 80% 2-opt y 20% insertion), empleadas como punto de partida para el diseño experimental.
• Sugerencia de variantes para el ajuste fino (fine-tuning) del cooling schedule en el algoritmo de Simulated Annealing, utilizadas como guía para la exploración de parámetros y su posterior validación empírica.

La modificación del código base, así como la implementación de las nuevas variantes y ajustes, es de autoría propia o se fundamenta en material proporcionado en clase y en recursos disponibles públicamente, los cuales han sido reinterpretados, adaptados y desarrollados para los objetivos de este trabajo.

Bibliografía

• [1] N. Mladenović, P. Hansen, J. Moreno "Variable neighborhood search, " Computers & Operations Research, vol. 24, no. 11, pp. 1097-1100, Nov. 1997.
• [2] M. Lundy y A. Mees, "Convergence of an annealing algorithm," Mathematical Programming, vol. 34, no. 1, pp. 111–124, 1986.
• [3] Google, "Gemini," (versión Feb. 2026), [Modelo de Lenguaje Grande].