![]() |
.., habiendo caminado largo tiempo a través de arenas, rocas y de nieves, descubrió una ruta. Y
todas las rutas van hacia la morada de los hombres. |
El
Problema de la Ruta Optima
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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:
¿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
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 dij sobre un grafo completo G,
Donde Xij es una variable dicotómica de decisión, entonces se puede ilustrar el modelo mátematico de selección como: Min 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 Matriz d(i,j) de Valores Enteros Aleatorios entre 1 y 40 Orden: 7 x 7
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
Minimo
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(1), 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:
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(2) 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.
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(3) 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}
Û Luego, $qk0Î Q / qk={fki} cuyo costo o distancia es Cm.
...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. (1)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. (2)Grafo Completo implica que todos los nodos están conectados entre ellos o que a cada punto de G inciden n-1 líneas. (3)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. (4)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) Bibliografía:
|