TSP | Problema del agente viajero

Escuela Superior de Cómputo

< TSP

Problema del agente viajero

(Travelling Salesman Problem)

EMPEZAR >

Vitales Herrera Hatziry|A.D.A|3CM2

>

>

La resolución del Problema del Viajante de Comercio (TSP) plantea un crecimiento exponencial de opciones al aumentar el número de ciudades. Por ejemplo, para 3 ciudades hay 6 opciones, para 4 ciudades son 24, y así sucesivamente. En el caso extremo de asignar 15 unidades de negocio a un colaborador, las opciones ascienden a 1,307,674,368,200, equivalente a 1,000,000 veces las combinaciones de la lotería primitiva.

EXPLICACION

Introduccion

>

referencias

metodos de solucion

analisis de complejidad

algoritmos

>

>

<Introducción>

El “problema del viajante”, “problema del vendedor viajero” o “problema del agente viajero”

Tiene como objetivo encontrar un recorrido completo que conecte todos los nodos de una red, visitándolos tan solo una vez y volviendo al punto de partida, y que además minimice la distancia total de la ruta, o el tiempo total del recorrido.

Este tipo de problemas tiene gran aplicación en el ámbito de la logística y distribución, así como en la programación de curvas de producción.

El problema del agente viajero tiene una variación importante, y esta depende de que las distancias entre un nodo y otro sean simétricas o no, es decir, que la distancia entre A y B sea igual a la distancia entre B y A, puesto que en la práctica es muy poco probable que así sea.

video de explicacion

>

>

<01> explicación

Resolución matemática junto con ejemplo

EMPEZAR >

>

>

// ciclo hamiltoniano

Un ciclo hamiltoniano se refiere a un ciclo cerrado que visita cada nodo exactamente una vez. Un TSP se considera resuelto si se encuentra un ciclo hamiltoniano de longitud mínima, es decir, una secuencia de nodos que minimiza la distancia total del recorrido.

+info

>

>

// matematicamente...

Expresamos esto como N! (N factorial), que es la multiplicación de N por todos sus predecesores hasta llegar a 1. Podemos simplificarlo considerando un punto de partida conocido (la ubicación del colaborador) y simetría en las rutas, reduciendo la cantidad de opciones a (N-1)!/2. Esto significa que para 3 ciudades, hay solo 1 opción; para 4 ciudades, 3 opciones; y para 5 ciudades, 12 opciones.

+info

>

>

Aunque esta simplificación reduce las opciones a 43,589,145,600 para 15 unidades de negocio, sigue siendo una cantidad considerable. A día de hoy, con las capacidades computacionales actuales, el problema de N ciudades no se resuelve eficientemente a menos que N sea pequeño.

>

>

Existen diversos algoritmos en optimización de operaciones, siendo el más destacado el algoritmo simplex en programación lineal, desarrollado por Dantzig en la década de 1950. Aunque este método fue crucial en estrategias ganadoras durante la Segunda Guerra Mundial, la resolución eficiente del TSP para grandes escalas sigue siendo un desafío pendiente.

algoritmos

<02> metodos de solución

EMPEZAR >

>

>

// algoritmos exactos

Exploran exhaustivamente todas las posibles soluciones y seleccionan la mejor según algún criterio objetivo.

algoritmos heurÍsticos

Se basan en reglas generales o estrategias inteligentes para explorar el espacio de soluciones de manera eficiente

>

>

ALGORITMOS EXACTOS

// programacion dinamica

// algoritmo de prim

Descompone el problema en subproblemas y usa una matriz dp para almacenar distancias mínimas entre subconjuntos de nodos. Calcula eficientemente la longitud mínima de un recorrido que visita cada nodo una vez y regresa al punto de partida.

// ramificacion y acotacion

Halla el árbol de expansión mínima en un grafo ponderado no dirigido y conexo. Inicia desde un nodo arbitrario y, en cada paso, selecciona la arista de menor peso que conecta un nodo visitado con uno no visitado, repitiendo hasta incluir todos los nodos en el árbol.

//Metodo de fuerza bruta

Busca soluciones óptimas dividiendo el problema en subproblemas y descartando soluciones no prometedoras. Utiliza una estrategia de poda para mejorar la eficiencia.

Exploración exhaustiva de todas las rutas posibles sin aplicar un algoritmo sistemático. Calcula la distancia total para cada combinación y selecciona la que minimiza la distancia total.

>

>

>

>

ALGORITMOS HEURÍSTICOS

// djikstra

// Inserción Más Barata

Dado un grafo ponderado, el algoritmo de Dijkstra encuentra las distancias mínimas desde un nodo de inicio a todos los demás nodos, construyendo así un conjunto de rutas más cortas.

// Recocido Simulado

// vecino mas cercano

Comienza con una ruta parcial y, en cada paso, inserta el nodo no visitado de la manera que minimiza el costo adicional.

Utiliza una búsqueda basada en la probabilidad, permitiendo movimientos que empeoran la solución con la esperanza de evitar mínimos locales. La probabilidad de aceptar peores soluciones disminuye con el tiempo.

selecciona en cada paso el nodo más cercano al nodo actual. Aunque no garantiza la solución óptima, suele proporcionar buenas soluciones en un tiempo de cálculo eficiente.

<03> algoritmos

EMPEZAR >

>

>

algoritmos exactos

algoritmos heruristicos

Recocido simulado

Algoritmo de Prim

Metodo de fuerza bruta

Djikstra

Algoritmo de Programación Dinámica

Ramificación y acotación

Vecino más próximo

Inserción más barata

<04> analisis de complejidad

EMPEZAR >

>

>

algoritmos exactos

Metodo de fuerza bruta

Evalúa todas las n! permutaciones posibles, considerando cada orden de nodos. La complejidad resulta del crecimiento exponencial de las permutaciones.Siendo impracticable para conjuntos grandes debido a su complejidad factorial O(n!).

Ramificación y acotación

Divide el problema en subproblemas y utiliza cotas para reducir la exploración, con una complejidad dependiente del factor de ramificación b y la profundidad d el árbol de búsqueda. Si consideramos un árbol de búsqueda con factor de ramificación b y profundidad máxima d, la complejidad podría aproximarse como O(bd ).

>

>

algoritmos exactos

Algoritmo de Prim

Selecciona y agrega aristas de menor peso en cada paso, utilizando montículos para mantener la eficiencia. La complejidad se deriva de la cantidad de nodos V y aristas E en el grafo. Manteniendo una complejidad eficiente de O((V+E)logV).

Algoritmo de Programación Dinámica

Descompone el problema en subproblemas y utiliza una matriz para almacenar distancias mínimas, con una complejidad exponencial O(n2 ⋅ 2n) debido al gran número de subconjuntos generados.

>

>

algoritmos heruristicos

Djikstra

La complejidad está influenciada por la cantidad de nodos y aristas en el grafo.Utiliza una cola de prioridad para explorar nodos eficientemente, con una complejidad de O((V+E)logV), siendo apropiado para grafos con pesos no negativos.

Inserción más barata

Construye iterativamente el recorrido insertando nodos de manera óptima, con una complejidad variable que generalmente es O(n3) o mejor según la implementación.

>

>

algoritmos heruristicos

Recocido simulado

Realiza iteraciones probabilísticas para explorar el espacio de búsqueda, aceptando soluciones subóptimas con cierta probabilidad. La complejidad depende del número de iteraciones y la lógica de aceptación.

Vecino más próximo

En cada iteración, se selecciona el nodo más cercano, lo que implica calcular las distancias entre el nodo actual y los nodos no visitados. Esto requiere O(n) operaciones. Iteraciones Totales: En el peor caso, se realizan n iteraciones (una por cada nodo en el grafo). Complejidad Total: O(n2)

>

<Referencias>

Hillier, F. S., & Lieberman, G. J. (2019). Investigación de Operaciones. (9ª ed.). McGraw Hill.

López, B. S. (2020, 16 de febrero). Problema del agente viajero – TSP. Ingeniería Industrial Online. https://www.ingenieriaindustrialonline.com/investigacion-de-operaciones/problema-del-agente-viajero-tsp/

Martinez, S. G. B. (2020, 3 de junio). El Problema del Vendedor Viajero y la Optimización de Costes en Operaciones (I). LinkedIn. https://es.linkedin.com/pulse/el-problema-del-vendedor-viajero-y-la-optimizaci%C3%B3n-de-sergio-gustavo

Benites, L. (2022, 8 de enero). Ciclo Hamiltoniano: Definición Simple y Ejemplo. Statologos. https://statologos.com/ciclo-hamiltoniano/

LUDA UAM-Azc. (s. f.). Curso de Análisis de Algoritmos. http://www.aniei.org.mx/paginas/uam/CursoAA/curso_aa_30.html

Gracias por su atención

Algoritmo de Prim

Prim(Grafo): Inicializar un conjunto vacío MST (árbol de expansión mínima) Inicializar un conjunto de nodos visitados vacío Elegir un nodo de inicio aleatorio y agregarlo al conjunto de nodos visitados Mientras hay nodos sin visitar: Encontrar la arista de menor peso que conecta un nodo visitado con uno no visitado Agregar el nodo no visitado y la arista al conjunto MST Marcar el nodo como visitado Regresar MST

Un bucle es solo un borde que une un nodo consigo mismo; por lo tanto, un ciclo hamiltoniano es un camino que viaja desde un punto hacia sí mismo, visitando todos los nodos en el camino. Si un grafo con más de un nodo (es decir, un grafo no singleton) tiene este tipo de ciclo, lo llamamos grafo hamiltoniano. No existe ninguna ecuación o truco general para averiguar si un gráfico tiene un ciclo hamiltoniano; la única manera de determinar esto es hacer una búsqueda completa y exhaustiva, revisando todas las opciones.

CONTACTO

111222333

name@mail.com

Escribe una dirección genial. La calle, su número, un código postal… ¡Ya sabes!

Inserción Más Barata

Seleccionar un nodo aleatorio como inicio Recorrido = [inicio] mientras hay nodos sin visitar: nodo_a_insertar = encontrar_nodo_a_insertar(Recorrido, nodos_sin_visitar) insertar nodo_a_insertar en Recorrido en la posición que minimiza la distancia adicional eliminar nodo_a_insertar de nodos_sin_visitar Regresar Recorrido

Problema: Agente Viajero con 4 ciudades (A, B, C, D).

• Ejemplo:
• Se inicia con una ruta parcial y se insertan nodos de manera óptima.
• Construcción iterativa de la ruta óptima.

Problema: Agente Viajero con 3 ciudades (A, B, C). Ejemplo:

• Matriz de distancias entre ciudades:
• {{0, 2, 1}, {2, 0, 4}, {1, 4, 0}}.
• Subproblemas resueltos y matriz dinámica actualizada.

Metodo de fuerza bruta

mejor_solucion = ninguna mejor_distancia = infinito para cada permutación de nodos: distancia_actual = calcular_distancia(permutacion) si distancia_actual < mejor_distancia: mejor_solucion = permutacion mejor_distancia = distancia_actual Regresar mejor_solucion

Metodo de fuerza bruta

mejor_solucion = ninguna mejor_distancia = infinito para cada permutación de nodos: distancia_actual = calcular_distancia(permutacion) si distancia_actual < mejor_distancia: mejor_solucion = permutacion mejor_distancia = distancia_actual Regresar mejor_solucion

Recocido simulado

RecocidoSimulado(Grafo, TemperaturaInicial, FactorEnfriamiento): SolucionActual = GenerarSolucionAleatoria(Grafo) Temperatura = TemperaturaInicial mientras la Temperatura sea mayor que cero: SolucionVecina = GenerarSolucionVecina(SolucionActual) DeltaE = EvaluarSolucion(SolucionVecina) - EvaluarSolucion(SolucionActual) si DeltaE < 0 o aleatorio() < e^(-DeltaE/Temperatura): SolucionActual = SolucionVecina Temperatura = Temperatura * FactorEnfriamiento Regresar SolucionActual

Problema: Agente Viajero con 4 ciudades (A, B, C, D).

• Ejemplo:
• Selección iterativa del nodo más cercano en cada paso.
• Construcción de la ruta: A-B-C-D-A.

Problema: Agente Viajero con 4 ciudades (A, B, C, D). Ejemplo:

• Grafo completo ponderado con distancias entre ciudades.
• Selecciona el nodo inicial (A).
• En cada paso, agrega el nodo más cercano al recorrido actual.
• Ruta óptima: A-B-C-D-A.

Algoritmo de Kruscal

dp = Matriz con dimensiones (2^n) x n Inicializar dp[mask][i] para todos los subconjuntos de nodos y nodos finales posibles Para cada subconjunto mask: Para cada nodo i en mask: Si i no está en mask: Para cada nodo j en mask: dp[mask | (1 << i)][i] = min(dp[mask | (1 << i)][i], dp[mask][j] + distancia(j, i)) Solucion = min(dp[(2^n) - 1][i] + distancia(i, inicio) para cada nodo i)

Ramificación y Acotación

SolucionParcial = inicializar_solucion_parcial() MejorSolucion = infinito ColaDeNodos = cola de nodos para explorar insertar SolucionParcial en ColaDeNodos mientras ColaDeNodos no esté vacía: NodoActual = extraer nodo de ColaDeNodos si NodoActual representa una solución completa y mejor que MejorSolucion: MejorSolucion = NodoActual si NodoActual representa una solución parcial prometedora: expandir NodoActual generando nodos hijos insertar nodos hijos en ColaDeNodos Regresar MejorSolucion

Recocido simulado

RecocidoSimulado(Grafo, TemperaturaInicial, FactorEnfriamiento): SolucionActual = GenerarSolucionAleatoria(Grafo) Temperatura = TemperaturaInicial mientras la Temperatura sea mayor que cero: SolucionVecina = GenerarSolucionVecina(SolucionActual) DeltaE = EvaluarSolucion(SolucionVecina) - EvaluarSolucion(SolucionActual) si DeltaE < 0 o aleatorio() < e^(-DeltaE/Temperatura): SolucionActual = SolucionVecina Temperatura = Temperatura * FactorEnfriamiento Regresar SolucionActual

Djikstra

Distancia = [infinito] para cada nodo Distancia[NodoInicio] = 0 ColaPrioridad = cola con todos los nodos y sus distancias actuales mientras la ColaPrioridad no esté vacía: nodo_actual = nodo con la menor distancia en ColaPrioridad para cada vecino de nodo_actual: nueva_distancia = Distancia[nodo_actual] + distancia_entre(nodo_actual, vecino) si nueva_distancia < Distancia[vecino]: Distancia[vecino] = nueva_distancia actualizar la distancia en ColaPrioridad Regresar Distancia

Problema: Agente Viajero con 5 ciudades (A, B, C, D, E).

• Ejemplo:
• Iteraciones probabilísticas para explorar y aceptar soluciones subóptimas.
• Ajuste de la temperatura y aceptación de soluciones según la probabilidad.

Problema: Camino más corto desde A hasta todos los nodos.

• Ejemplo:
• Grafo ponderado con nodos {A, B, C}
• y aristas con pesos {A-B: 2, B-C: 3, A-C: 5}.
• Distancias mínimas desde A: A-B: 2, A-C: 5.

Inserción Más Barata

Seleccionar un nodo aleatorio como inicio Recorrido = [inicio] mientras hay nodos sin visitar: nodo_a_insertar = encontrar_nodo_a_insertar(Recorrido, nodos_sin_visitar) insertar nodo_a_insertar en Recorrido en la posición que minimiza la distancia adicional eliminar nodo_a_insertar de nodos_sin_visitar Regresar Recorrido

En resumen

La cantidad de rutas posibles en una red de n nodos está determinada por la ecuación (n-1)!. En una red de 5 nodos, por ejemplo, hay 24 rutas probables. A medida que el número de nodos aumenta, la cantidad de rutas crece factorialmente. Si el problema es simétrico, la cantidad de rutas posibles se reduce a la mitad, es decir, ((n-1)!)/2.

Vecino más cercano

Recorrido = [NodoInicio] mientras hay nodos sin visitar: nodo_actual = último nodo en Recorrido vecino_mas_cercano = encontrar_vecino_mas_cercano(nodo_actual, nodos_sin_visitar) agregar vecino_mas_cercano a Recorrido eliminar vecino_mas_cercano de nodos_sin_visitar Regresar Recorrido

Problema: Agente Viajero con 4 ciudades (A, B, C, D).

• Ejemplo:

Se generan todas las posibles permutaciones de las ciudades.Se calcula la distancia total de cada ruta.Se selecciona la ruta con la distancia mínima.

• Posibles Rutas:
• A-B-C-D-A: 35 km
• A-B-D-C-A: 31 km
• A-C-B-D-A: 40 km
• ...

Ruta Óptima: A-B-D-C-A con 31 km.

Algoritmo de Prim

Inicializar un conjunto vacío MST (árbol de expansión mínima) Inicializar un conjunto de nodos visitados vacío Elegir un nodo de inicio aleatorio y agregarlo al conjunto de nodos visitados Mientras hay nodos sin visitar: Encontrar la arista de menor peso que conecta un nodo visitado con uno no visitado Agregar el nodo no visitado y la arista al conjunto MST Marcar el nodo como visitado Regresar MST

Problema: Agente Viajero con 3 ciudades (A, B, C). Ejemplo:

• Se establece una cota superior inicial.
• Se exploran ramas y se aplican cotas para acotar la búsqueda.
• Se encuentra la solución óptima.