nova blog

Prof. Dr. Alex Rodríguez Villalobos

viajante de comercio

Ciclos y caminos hamiltonianos

Alex

Hoy he dedicado todo el día a buscar ciencia, estudiar y programar un nuevo modelo MILP. En este caso para el problema DMP – Delivery Man Problem: Ciclo Hamiltoniano con inicio y fin en un punto seleccionado El resultado es el mismo que el TSP, aunque no el modelo MILP (variables de decisión y restricciones diferentes). He programado el ciclo hamiltoniano, ya que quiero programar una variante de este: se trata de encontrar la ruta desde el nodo origen A hasta el nodo destino B pasando por el resto de nodos y sin volver a A después de B. (le […]

El caso de la panificadora

Alex

Para mostrar la utilidad del proyecto Rutas, he documentado un pequeño caso de ejemplo sobre un problema sencillo de transporte TSP. Se trata del caso de la panificadora Corbi. El caso está documentado paso a paso y cuidadosamente ilustrado. Espero que sea de utilidad a todos. A continuación tenéis una imagen que muestra la solución óptima del problema del caso.

El arte de la logística

Alex

A través de MathPuzzle, me entero de que con unos sencillos pasos, es posible transformar una imagen en un grafo de viajante de comercio. Tal y como explican en esta web, en primer lugar se toma la imagen y se transforma a una imagen en blanco y negro formada por puntos. Tomando las coordenadas de todos ellos se genera el grafo completo. Con un software de Grafos, como por ejemplo TSP Concorde, se resuelve el problema del Viajante de Comercio. El resultado: imágenes llenas de matemáticas como esta de la Mona Lisa.         Os animo a probar […]

Estado del proyecto Rutas

Alex

Hace casi dos meses que comencé en serio con el proyecto Rutas. Desde entonces he estado informando periódicamente en su web del avance del desarrollo. Aunque el proyecto es muy ambicioso y presenta grandes retos (conexión con GIS, gestión de datos, conexión entre la aplicación web y la aplicación de escritorio, algoritmia avanzada, etc.), me sorprende cómo he avanzado el proyecto en tan sólo 2 meses de 'ratitos libres' (desafortunadamente no dispongo de mucho tiempo para dedicarme a programar). Os pongo una captura de pantalla del programa (ver más…). Se trata de una prueba que he realizado esta mañana, donde […]

El mayor problema del mundo

Alex

En la web de Princeton sobre el Problema de Viajante de Comercio, se reta a la comunidad científica a resolver el mayor problema TSP conocido hasta la fecha con 1.904.711 ciudades de todo el mundo. El mejor resultado (a fecha de esta noticia) ha sido encontrado por Keld Helsgaun usando una variante de su algoritmo heurístico LKH. Su resultado de longitud total 7,516,353,779 fue encontrado el 23 de diciembre de 2003. Anteriormente, los mejores resultados encontrados fueron el de Helsgaun (16 Sept. 2003) con un valor de 7,517,285,610 y el de Hung Dinh Nguyen, Ikuo Yoshihara, Kunihito Yamamori, and Moritoshi […]