Ejemplo del Problema del Camino Más Corto en Programación Entera

El Problema del Camino más Corto (o ruta más barata) consiste en encontrar una ruta o camino óptimo entre un nodo fuente y un nodo destino, los cuales están enlazados a través de una red con arcos que poseen un cierto atributo, el cual puede ser costo, distancia, tiempo, etc.

La Programación Entera permite abordar de forma eficiente este tipo de problemas, en especial cuando la cantidad de nodos y rutas posibles resulta ser un número significativo. Utilizar en estos casos un enfoque intuitivo de resolución es tedioso y de no ser exhaustivo no garantiza la identificación de la mejor alternativa o ruta.

Consideremos el siguiente diagrama donde los números asignados a cada uno de los arcos representan la distancia en kilómetros de un nodo a otro. Se desea encontrar la ruta con la distancia mínima para ir del nodo 1 al nodo 8.

diagrama-ruta-mas-corta

El tamaño reducido de la red anterior permite encontrar el camino más corto simplemente enumerando las distintas alternativas que comenzando en el nodo 1 permita llegar al nodo 8. De esta forma las rutas posibles son:

  • Ruta 1-2-5-7-8: 4+8+17+9=38[km]
  • Ruta 1-3-4-7-8: 3+12+20+9=44[km]
  • Ruta 1-3-4-6-8: 3+12+2+22=39[km]
  • Ruta 1-3-4-8: 3+12+15=30[km]
  • Ruta 1-3-6-8: 3+4+22=29[km]

La ruta o camino más corto esta dada por la secuencia 1-3-6-8 con una distancia total de 29[km].

A continuación se formula un modelo de Programación Entera que permite extender este tipo de resultados a un problema de estas características:

Variables de Decisión:

variable-binaria-ruta-mas-c

Función Objetivo: Minimizar la distancia total en [km] dada por la siguiente expresión:

funcion-objetivo-ruta-mas-c

Restricciones:

restricciones-ruta-mas-cort

  1. La primera restricción (1) garantiza que sólo un nodo (entre el 2 y el 3) pueda ser el que se visita a continuación de comenzar en el nodo 1.
  2. La restricción (2) determina que si se visito el nodo 2 después del nodo 1, entonces necesariamente el nodo 5 será visitado después del nodo 2.
  3. La restricción (3) permite verificar que si el nodo 3 fue visitado luego del nodo 1, entonces a continuación se visita el nodo 4 o el nodo 6 (sólo uno de ellos).
  4. La restricción (4) establece que si el nodo 5 fue visitado luego del nodo 2, entonces el nodo 7 debe ser visitado luego del nodo 5.
  5. La restricción (5) garantiza que si el nodo 4 fue visitado luego del nodo 3, entonces a continuación se visita uno de los siguientes nodo: 7, 8 o 6.
  6. La restricción (6) indica que si el nodo 6 fue visitado inmediatamente luego de estar en el nodo 3 o 4, a continuación se visita el nodo 8.
  7. La restricción (7) determina que si el nodo 7 fue visitado inmediatamente luego de estar en el nodo 4 o 5, a continuación se visita el nodo 8.
  8. Finalmente la restricción (8) asegura que ya sea el nodo 7, 4 o 6 sea el último en visitar previo a terminar la ruta en el nodo 8.

Al implementar en Solver el problema del Camino más Corto o Ruta Mínima anterior se alcanzan los siguientes resultados:

solucion-optima-ruta-mas-co

Donde se corrobora que la ruta más corta (solución óptima) corresponde al camino 1-3-6-8 con una distancia total de 29[km] (valor óptimo).

El tutorial a continuación disponible en nuestro canal de Youtube muestra en detalle la implementación y resolución computacional de este problema:

Rating: 5.0. From 3 votes.
Please wait...

, , , , , ,

6 Comentarios para Ejemplo del Problema del Camino Más Corto en Programación Entera

  1. rob82 30/01/2015 en 15:02 #

    Existe la restricción o la forma, de encontrar la ruta pasando por todos los nodos ?
    Saludos.

    • GEO Tutoriales 30/01/2015 en 15:27 #

      @rob82. No es necesario pasar por todos los nodos para que, comenzando en un nodo inicial (nodo 1 en el ejemplo) se pueda llegar a un nodo destino o final (nodo 8 en el ejemplo). Existen otras aplicaciones (tipo vendedor viajero) que comenzando en un nodo inicial se deben visitar a todos los nodos una sola vez y regresar al nodo de origen. Si bien una representación gráfica de dicha situación tiene cierta relación con nuestro ejemplo, conceptualmente son aplicaciones muy distintas.

  2. Nelson 12/10/2015 en 13:18 #

    Buenas tardes, quiero saber si existe un modelo generalizado para el problema de la ruta más corta, es decir, ¿es posible utilizar subíndices y expresarlo de forma general para cualquier caso?

    • GEO Tutoriales 15/10/2015 en 14:34 #

      @Nelson. Si es posible llevar a cabo una generalización a través de la definición de parámetros para el modelo. Por ejemplo, sea [latex]d_{ij}[/latex] la distancia entre en la ruta que une al nodo i con el nodo j, con i≠j. En el caso del artículo hemos considerado una notación extendida debido a que facilita la comprensión de la problemática para un problema de tamaño menor.

  3. sebastian vasquez 12/07/2016 en 13:51 #

    Muy buena explicación. Mi duda es con la aplicación de rutas ficticias. ¿Qué cambia en esta resolución cuando se deben crear rutas ficticias?. Esto es en el caso de que una actividad tenga como predecesoras a dos actividades.
    Una ruta ficticia tiene un valor o costo de 0 y se usa para indicar que deben finalizar las actividades predecesoras de una actividad para que esta segunda comience. Pregunto esto porque resolví mi ejercicio con rutas ficticias al igual que el modelo que se explica aquí, pero no se puede resolver.

Deja un comentario