Pero sucedió que el Principito, 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.

Antoine de Saint -Exupéry

EL PROBLEMA DE LA RUTA ÓPTIMA PARA VISITAR A CLIENTES
José Enrique González Cornejo
01 de mayo 2009

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

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.

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

Descripción del Algoritmo de la Ruta Óptima

1. Se elige un punto de partida.

2. Se decide ir seguidamente el 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. 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.

Si un CLIENTE es equidistante (en costo) de otro y si los costos son mínimos, el algoritmo programado no efectúa pruebas sucesivas con cada una de las CLIENTES, sino que escoge sistemáticamente aquella que esté primero en su orden. Para obligar a efectuar la segunda prueba, es preciso aumentar artificialmente el coste del primer trayecto, sólo ligeramente, y pedir una segunda ejecución.

Nótese que una vez encontrada la ruta optima para una  origen dado (Oficina Regional), la distribución de de la cobertura se realizará de acuerdo a los recursos y tiempos disponibles y administrables en el origen.(Oficina Regional).

Ejemplo con 7 CLIENTES. (Todos los Rut`s y distancias son inventados aleatoriamente):

1. Lista de Ruts seleccionada con su localización, dada

LISTA DE CLIENTES SELECCIONADOS EN EL ZONA XY

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

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)

Se selecciona la opción si la Matriz d(i,j) es simétrica o asimétrica.
 Nótese que la distancia o costo d(i,j)=0 cuando i = j.

3.         La solución

Tabla que contiene la Ruta Optima, publicando el valor total de la distancia o costo.

4. Formalización del algoritmo

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 (u Oficina Regional) 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.

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.

 ...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 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.

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
• Programación con Diseño Modular o Top-Down
• Grafo conexo definido como árbol