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 podremos llamar camino hamiltoniano). El ciclo hamiltoniano si que vuelve a A para cerrar el ciclo, al igual que el TSP.

En la web de Rutas, veréis un pequeño ejemplo de una ruta turística por el centro.

El modelo del camino hamiltoniano, es una variante (cambiando restricciones) que ya casi tengo definido, falta programar y probar. El soft de Rutas está siendo especialmente útil para probar los modelos, previo lp_solve IDE que es una maravilla.

El conocimiento y programación de estos modelos básicos, facilita el desarrollo de otros más complejos. Además se puede reaprovechar para muchos otros usos y aplicaciones.

 

Actualización (22/09/06):

Ya he modificado y programado el modelo de caminos hamiltonianos. Ahora es posible encontrar la ruta que visite n-2 nodos, partiendo de un nodo A y terminando la ruta en B (sin volver después a A).

Un curioso ejemplo se puede ver en la siguiente pantalla, donde se muestra cómo visitar algunos lugares turísticos de Castilla la Mancha, partiendo de Valencia y terminando obligatoriamente en el aeropuerto de Madrid-Barajas.