Utilización de la búsqueda local exhaustiva para resolver un problema de viajante de c | 10/14 | UPV

Título: Utilización de la búsqueda local exhaustiva para resolver un problema de viajante de comercio

Descripción: Se explica el concepto de búsqueda local exhaustiva y cómo se puede usar para resolver un problema de Viajante de Comercio (TSP) Andrés Romano, C. (2021). Utilización de la búsqueda local exhaustiva para resolver un problema de viajante de comercio. http://hdl.handle.net/10251/167146

Descripción automática: En este video, el investigador del grupo Roble de la Universidad Politécnica explica la búsqueda local exhaustiva aplicada al problema del viajante de comercio, un típico desafío de optimización. Inicia con la definición del espacio de soluciones, formado por todas las combinaciones posibles de elementos de un problema y describe una función objetivo que varía en función de estas soluciones.

Se introduce el concepto de movimiento y vecindario dentro del espacio de soluciones, ilustrando cómo se puede transformar una solución en otra y crear un conjunto de soluciones vecinas. A continuación, detalla el proceso iterativo de la búsqueda local exhaustiva: se parte de una solución inicial y se generan todas las soluciones vecinas (vecindario), eligiendo luego la mejor entre estas. Si esta es mejor que cualquier solución previa, se convierte en la nueva solución inicial para otra ronda de búsqueda. Este proceso se repite hasta que no se encuentra una mejor solución y se llega a un óptimo local.

Aplicando este método al problema del viajante de comercio, el presentador muestra cómo la codificación de la ruta como una permutación permite explorar soluciones vecinas mediante intercambios de elementos adyacentes. Utilizando una matriz de distancias entre ciudades, ilustra cómo se pueden evaluar y comparar las rutas para encontrar la que minimice la distancia total recorrida.

Al final del video, refiere cómo este enfoque heurístico no garantiza la solución óptima, pero destaca su eficacia para encontrar una buena solución para el problema presentado en el ejemplo, resultando ser la óptima tras completar todas las permutaciones posibles. Agradece la atención y concluye destacando la utilidad del objeto de aprendizaje presentado.

Autor/a: Andrés Romano Carlos

Curso: Este vídeo es el 10/14 del curso Métodos Cuantitativos de Organización Industrial.    • Métodos Cuantitativos de Organización Indu...  


Universitat Politècnica de València UPV: https://www.upv.es
Más vídeos en:    / valenciaupv  
Accede a nuestros MOOC: https://upvx.es

#El problema del viajante (TSP) #Algoritmos de búsqueda #Espacio de soluciones #TSP #Viajante de comercio #Búsqueda local #Heurística constructiva #ORGANIZACION DE EMPRESAS #