Ponente: Francisco Javier Pérez Lázaro (Universidad de La Rioja)

Lugar: Seminario Mirian Andrés (Edificio CCT)

Hora: jueves 22 de marzo, 13:00

Resumen: El problema del viajante de comercio (TSP – travelling salesman problem) trata de determinar el camino que debe seguir un comerciante que, con origen y destino en la misma ciudad, tiene que visitar n ciudades intermedias de modo que la distancia recorrida sea mínima. El TSP viene a ser uno de los enunciados más básicos de los llamados problemas de rutas de vehículos (VRP – vehicle routing problem).

En esta charla enunciaremos el TSP y analizaremos su complejidad computacional. Además formularemos su enunciado en términos de programación binaria y comentaremos algunos de los primeros algoritmos exactos y heurísticos para su resolución.

Nota: Esta charla está basada fundamentalmente en un trabajo fin de grado realizado por Salvador Peñalva García y también incluye partes de otros trabajos fin de grado previos.