Ruta Optima

El Problema de la Ruta Optima
José Enrique González Cornejo
01 de mayo 2009

Un agente debe visitar una Lista de Clientes diseminados en N direcciones localizadas en una zona XY. Se conocen los costos o distancias d(i,j) para ir del CLIENTE i al CLIENTE j.

Nótese que se asume d(i,j)=0 cuando i=j. Es decir, la diagonal de la matriz asociada es 0.

Los costos d(i,j) pueden representar una reducción de una serie de factores, o puede cada factor ser tratado en forma individual con su unidad de medida (accesibilidad, distancia métrica, prioridad,.. etc), para posteriormente decidir en un modelo ponderado.

Es decir, el concepto distancia d(i,j) puede representar costo, tiempo u otra medida que se requiera establecer entre los nodos.

Este es un problema de optimización combinatoria, se puede realizar por múltiples métodos de programación lineal (Ver Traveling Salesman Problem, TSP).

DocIRS ha trabajado dos métodos computacionales:

i) Uno por optimización de tramos, el cual presentamos a continuación, como así mismo simulamos el algoritmo DociRS con un desarrollo de matrices de 4x4 hasta 200x200 (Ejecutar Simulación) con valores enteros aleatorios, donde se puede seleccionar el orden de la matriz y decidir si se desea que la matriz sea simétrica o no. Una vez ejecutada la formulación, el sistema despliega la ruta óptima y su costo asociado. (Ver Edsger Dijkstra/1959)

ii) Un segundo método por permutaciones (todo los posibles caminos, (N-1)!, lo hacemos por medio de un algoritmo aleatorio). Este último método "por permutaciones", - resulta ser experimentalmente más exacto-. Sin embargo, no lo utilizamos, dado que cuando el número de puntos es grande, entonces la cantidad de combinaciones es aún mayor. Por tanto, los tiempos de respuesta para lograr la Ruta Optima, son extensos (Por ejmeplo, con sólo 10 puntos se tienen 362.880 posibles caminos). Además, este camino resultante es global, dado que se decide por el mínimo del costo total de cada combinación y no por etapas sucesivas. Es decir, presupone que para optimizar se debe realizar la ruta sólo de esa forma. (Ver Ejemplo Simple Permutaciones para la Ruta Optima y probar el Simulator de Permutaciones)

¿En qué orden se debe visitar a los CLIENTES para minimizar el costo total del desplazamiento?

Descripción de un Algoritmo de la Ruta Óptima

1. Se elige un punto de partida. (En nuestro caso rotularemos el origen siempre desde el 1)

2. Se decide ir seguidamente al CLIENTE más cercano.

3. Se va seguidamente a otro CLIENTE, el más cercano (desde el punto de vista de la métrica en cuestión), que no haya sido visitado todavía, hasta que así se hayan visitado todos los CLIENTES, vuelve entonces al punto de partida.

4. Se anota el costo obtenido del recorrido y se vuelve a comenzar eligiendo sucesivamente todos los CLIENTES de la lista como un punto de partida.

En síntesis, partimos del origen 1, y buscamos todas las líneas que inciden en el punto y determinamos el mínimo costo entre los puntos conectados. Se guarda tramo y se realiza recurrentemente el mismo ejercicio, a partir del punto de llegada, eliminando el tramo encontrado en los siguientes pasos.

Cuando uno entra en un punto ya ocupamos esa línea de entrada, de ahí, sólo nos queda seleccionar la línea de salida del punto (Ocupamos sólo 2 líneas por punto).

La ruta buscada es un ciclo, dado que se retorna al punto de partida rotulado con 1. Se retorna al punto de partida, una vez que se haya pasado por todos los puntos agendados.

Si un punto es equidistante (en costo) de otro y si los costos son mínimos, el algoritmo programado no efectúa pruebas sucesivas con cada uno de los puntos, sino que escoge sistemáticamente aquel que esté primero en su orden.

Formalmente, si se considera una matriz de distancias d_ij sobre un grafo completo G,

1, si se utiliza la línea i-j

X_ij =

0, si no se utiliza la linea i-j

Donde X_ij es una variable dicotómica de decisión, entonces se puede ilustrar el modelo mátematico de selección como:

Min d_ijX_ij

Ejemplo con 7 CLIENTES.

1. Lista seleccionada con su localización, dada

Nótese que un grafo completo tiene (n-1) líneas por punto, donde n es el número de puntos.

2. La Matriz cuadrada d(i,j) con las distancias o costos entre las localizaciones establecidas

MATRIZ DE DISTANCIAS (COSTOS*) ENTRE CLIENTES SELECCIONADOS EN EL ZONA XY
(No necesariamente distancias métricas. Nótese que se asume la matriz como simétrica)

Matriz d(i,j) de Valores Enteros Aleatorios entre 1 y 40
Orden: 7 x 7

d(i,j)	1	2	3	4	5	6	7
1	0	37	39	37	28	33	22
2	37	0	40	36	9	13	8
3	39	40	0	23	19	17	40
4	37	36	23	0	23	5	14
5	28	9	19	23	0	31	31
6	33	13	17	5	31	0	23
7	22	8	40	14	31	23	0

La Matriz d(i,j) del ejemplo es simétrica.(El costo es igual de ida o vuelta)
Nótese que la distancia o costo d(i,j)=0 cuando i = j.

3. La solución

Cadena que contiene la Ruta Optima y su valor total de la distancia o costo.

SOLUCIÓN EN LA ZONA XY

Ruta Optima Resultante

1 [22] 7 [8] 2 [9] 5 [19] 3 [17] 6 [5] 4 [37] 1

Minimo [fi] = 92

4. Formalización del algoritmo utilizado

El algoritmo con que se resolvió el problema Ruta Óptima para Visitar CLIENTES, es mediante una técnica matemática llamada Programación Dinámica⁽¹⁾, dado que la solución se aproxima tomando decisiones en etapas sucesivas y de este modo es posible retomar la ruta en diferentes períodos, asumiendo que el costo o distancia es constante( d(0,j) "j=1,2,.. . N). Es decir, desde el origen hasta cualquier dirección (o nodo) de la lista de CLIENTES a visitar. (ver Programación con Diseño Modular o Top-Down)

El problema se abordó, bajo las siguientes condiciones:

i) La solución se logra a través de una secuencia de decisiones, una en cada etapa.
ii) La secuencia de decisiones cumple con el principio del óptimo.
iii) Definición recursiva de la solución.
iv) Cálculo del valor de la solución óptima mediante una matriz temporal donde se almacenan la soluciones parciales
v) Construcción de la solución.

Sea D={d(i,j)} la matriz cuadrada de orden n, donde cada d(i,j) Î R es el costo o distancia de ir desde i hasta j. La matriz D tiene un grafo completo⁽²⁾ G asociado. La diagonal de la matriz D es cero. Es decir, d(i,j)=0 para i=j. La matriz del ejemplo es simétrica. Es decir, se han considerado sólo los valores d(i,j), donde i>j.

grafo 7 puntos_ruta óptima grafo 7 puntos_ruta óptima animada

Sea {pi} el conjunto de los n puntos (o nodos) del grafo G.(n Î N)

Sea el punto p1Î {pi} el punto de partida. (Arbitrariamente lo localizamos en el rotulo 1 del LISTA DE CLIENTES SELECCIONADOS).

Entonces, existen (n-1)! caminos que pasan una sola vez por cada punto pi, con pi¹p1.

Sea Q={qi} el conjunto de todos los posibles caminos hamiltonianos⁽³⁾ que se pueden obtener sobre el grafo G, partiendo de p1. (Nótese que en cada camino qi, todos los puntos intermedios entre el primero y el ultimo, tiene sólo dos líneas que inciden: una línea que entra y otra que sale.)

Sea Ci, el costo de cada sumatoria ∑ d(i,j) que se obtiene de cada camino qi Î Q.

Sea F={fi} el conjunto de puntos asociados al camino que representa el Cm=min(ci, F). Es decir, Cm f1-->f2-->f3-->...fn (Nótese que f1=p1) i.e. fi: la política de costo mínimo de la etapa. Donde se establece la siguiente Restricción: fk+1¹fk Ù fk+1¹ fk-1 Ù fk+1¹ fk-2... Ù..fk+1¹ f1.

Entonces la relación recursiva dinámica se expresa como: Para cada uno de los fk+1=min{(d(i,j), fk ->{pi}/ bajo Restriccion} Û
f(k,i) = min [d(i,j) + f(k-1,,j)] para todos los arcos (i,j) en la red, donde i es el estado de inicio y j estado destino.

Luego, $q_k0Î Q / q_k={f_ki} cuyo costo o distancia es Cm.

function ruta_optima()
{
/*ALGORITMO DE OPTIMIZACION DE RUTA EN JAVASCRIPT
///José Enrique González Cornejo, 01/05/2009
///https://www.docirs.cl/ruta_optima.htm
///https://www.docirs.cl/simulacion_aleatoria_ruta_optima.asp
///La función devuelve una cadena con un recorrido óptimo,
///desde el punto de vista, del Método Por Tramos DocIRS
///con la siguiente sintaxis: a1-->d[a1][a2]-->....,an-->d[an][1]-->a1
///Se asume que vienen parámetros globales: numero_nodos, la matriz d[i][j] cargada con sus correspondientes valores
*/

var donde=new Array() /// Almacena el punto donde estamos situados
var minimo=new Array() /// Almacena el valor mínimo d[i][j] seleccionado
var v=new Array() /// Rotulación de los nodos. Por simplicacion del algoritmo v(j)=j
var kkk=0 //Contador
var MMM   //Comienza numero gande, se Almacena Mínimo
var restriccion="," //Cadena donde se van guardando los nodos ya seleccionados.
var m //iterador local
var i //iterador local
var j //iterador local
var nodo_doble //variable auxiliar para limpiar la duplicacion de rotulos en los tramos
var ss //cadena resultante que contiene la serie de la ruta óptima ,a1,a2,a3,.....,an,a1
//'=============================
                donde[0] = 1
                v[1]=1
                for(var j=2;j<=numero_nodos;j++)
                {
                   v[j]=j
                }
                v[numero_nodos+1]=1
//'=============================

do
{
MMM = Math.pow(10,20)

   i = donde[kkk]
   kkk = kkk + 1
   restriccion = restriccion + donde[kkk - 1] + ","

                for(var j=2;j<=numero_nodos;j++)
                {

                if(i!= j)
                {
                   if(d[i][j] < MMM)
                   {
                      tt="," + j + ","
                               if(InStr(restriccion, tt)==0)
                   {
                               MMM = d[i][j]
                               donde[kkk] = j
                   }
                }
                }

                }

                if(MMM == Math.pow(10,20))
                 {minimo[kkk] = 0}
                    else
                 {minimo[kkk] = MMM}

}
while (kkk<numero_nodos-1);
/////////////////////////////
   ss = ""
   for(m = 0;m<=numero_nodos - 2;m++)
         {
          var punto1 = v[donde[m]]
          var punto2 = v[donde[m + 1]]
          ss = ss + punto1 + "-->[" + d[punto1][punto2] + "]-->" + punto2 + "-->"
         }

                for(var m=1;m<=numero_nodos;m++)
                {
                  nodo_doble = "-->" + m + "-->" + m + "-->"
                ss = ss.replace(nodo_doble, "-->" + m + "-->")
                }

ss = ss + "["+d[punto2][1]+"]-->1"

return ss
}

ss = ss + "["+d[punto2][1]+"]-->1"

return ss
}

...Al concluir la rutina, el arreglo f contiene las posiciones de los puntos del camino optimo q Þ d(f[i],f[i+1]) es la distancia o costo mínimo entre cada par de nodos f[i] y f[i+1] \Cm=∑fi es el costo o distancia optima para cubrir el grafo G. Todos los otros valores resultantes y referenciales se expresan en función de esta secuencia.

La simulación del algoritmo que asociamos al presente artículo, la realizamos con valores enteros aleatorios acotados. Sin embargo, el recurso de valores aleatorios puede ser utilizado entre alguntos puntos, donde no tenemos informacón certera acerca de la distancia o costo que los separa, sino que conocemos el sólo el intervalo del costo o distancia entre dichos puntos. Es decir, ahí es posible aplicar un método análgo a Monte Carlos para aproximar y llenar la matriz d(i,j) que requiere el algoritma como insumo.

⁽¹⁾La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas. Una subestructura óptima significa que soluciones óptimas de subproblemas pueden ser usadas para encontrar las soluciones óptimas del problema en su conjunto.

⁽²⁾Grafo Completo implica que todos los nodos están conectados entre ellos o que a cada punto de G inciden n-1 líneas.

⁽³⁾En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez.

⁽⁴⁾función InStr utilizada en el algoritmos para detectar ocurrencias en la variable dinámica Restricción, la cual es utilizada como una cadena de texto separada por comas, donde vamos acumulando los puntos seleccionados.

function InStr(n, s1, s2)
{
var numargs=InStr.arguments.length;
if(numargs<3)
return n.indexOf(s1)+1;
else
return s1.indexOf(s2, n)+1;
}

Bibliografía:

Harary Frank. Graph Theory, Addison-Wesley Publishing Company,1969
Hamdy A. Taha. Operations Research, Macmillan Publishing,1976
Edsger Dijkstra in 1959
González Cornejo José Enrique, Tratamiento Documental de Datos, Published by CIDE-REDUC 1990
DocIRS,SII, DIPRES: FONDO DE MODERNIZACION DE LA GESTIÓN PÚBLICA, INFORME FINAL, PROPUESTA "OPTIMIZACIÓN DEL PROCESO DE PRESENCIA FISCALIZADORA EN TERRENO,SII"

Programación con Diseño Modular o Top-Down