Proyecto - Actividades: 5 a 10

Algoritmo para Sistema Distribuido

Básicamente un sistema distribuido, es aquel en el cual los componentes que se encargan de ejecutar procesos/tareas, estos componentes se caracterizan por poseer recursos propios, no necesitan ser compartidos. Además un componente al ser independiente también puede solicitar ayuda de otro o varios.

Presentación del caso

Para esta práctica decidimos realizar un sistema para optimizar problemas de ruteo de vehículos, conocidos como: VRP. Son un problema clásico de optimización combinatoria con múltiples aplicaciones, en el que consiste en un depósito central, en donde una flotilla de vehículos disponibles con capacidad de transportación determinada, para entregar a productos a clientes con cierta demanda. El objetivo de este tipo de problemas es minimizar los costos de transportación al diseñar las rutas con ciertas restricciones operacionales.

Nos enfocamos en la variante del VRP con latencia, esta última representa el tiempo que espera un nodo en ser "atendido/visitado" y depende de la distancia existente entre los nodos anteriores a él y al deposito, el objetivo es reducir ese tiempo de espera.

Disponemos de los datos siguientes: cantidad de clientes con su respectiva demanda, cantidad de vehículos/viajes, coordenadas (x,y) que indican la posición de los clientes (el depósito se considera como el origen). Pueden obtenerse de archivos de texto (texto plano) con la estructura siguiente:

Donde indica "ServiceTimes:" y el renglón siguiente, se utilizan en otra variante del VRP, en nuestro caso no necesitamos estos datos. Debe respetarse la información presente en cada renglón, esto quiere decir que nuestra información debe estar presente en los renglones: 1, 2, 3, 5; y a partir del 10, por tratarse de los puntos coordenados.

Utilizamos los lenguajes de programación: Java y Python 3.2. El primero debido a que es multiplataforma y está ampliamente difundido; sobre él se codificó el "Servidor". El segundo es un "lenguaje scripting", sencillo y fácil de aprender; debido a esto es utilizado preferentemente en áreas de investigación científica, y para nuestro caso de aplicación resulta muy útil, además se dispone del código fuente siempre que se necesite modificar, para codificar el "Cliente".

Método de Solución Utilizado

Se optó por usar dos métodos existentes: "vecino más cercano" e "inserción de nodos". El primero es uno de los más conocidos para resolver "el problema del viajero" (TSP), ofrece una vía rápida para construir una solución; el segundo, selecciona cada nodo de la solución inicial ("tour") y lo intercambia entre todas las posiciones posibles en el mismo.

Algoritmo para construir solución inicial ("Vecino Más Cercano")

1. Inicio
2. Determinar cantidad de viajes, distancias, demandas, capacidad.
3. Seleccionar un punto actual (el depósito es por "default").
4. Hacer ciclo 1:
1. Guardar el punto actual en un arreglo (puntos seleccionados).
2. Guardar el punto actual en un arreglo (visitados)
3. Hacer ciclo 2:
1. Buscar el nodo mas próximo (vecino) al punto actual y que no esté en visitados
2. Terminar ciclo hasta no encontrar otro vecino.
3. Guardar el punto actual en un arreglo (puntos seleccionados).
4. Guardar el punto actual en un arreglo (visitados)
5. Acumular la distancia existente entre el vecino y el punto actual.
6. Acumular la demanda del vecino (suma).
7. Si suma excede la capacidad: quitar el vecino de los puntos seleccionados, restar su demanda respectiva, restar su distancia respectiva y terminar ciclo 2.
8. Cambiar el punto actual al vecino.
4. Fin del ciclo 2.
5. Acumular suma a la demanda cubierta.
6. Reiniciar suma a cero.
7. Calcular la latencia de los puntos seleccionados.
8. Guardar en una matriz los puntos seleccionados y también la latencia.
9. Cambiar el punto actual al depósito.
10. Si la demanda cubierta es igual o excede a la demanda total: terminar el ciclo 1.
5. Fin del ciclo 1.
6. Regresar la matriz de puntos seleccionados y latencias.
7. Fin

Diagrama de Flujo

Algoritmo para optimizar la solución ("Inserción de nodos")

1. Inicio
2. Determinar viaje (puntos seleccionados), distancias, latencia del viaje.
3. Seleccionar elemento de los puntos seleccionados[longitud] a excepción del primero y el último.
4. Guardar posición del elemento.
5. Quitar elemento del viaje.
6. Hacer ciclo i de 0 a (longitud del viaje-1):
1. Si i no equivale a la posición del elemento: insertar elemento en el viaje, cuya posición indica i, si la latencia del viaje es menor o igual a la anterior: guardar el viaje y guardar su latencia; quitar elemento del viaje.
7. Fin del ciclo.
8. Regresar el viaje y su latencia
9. Fin

Diagrama de Flujo

Algoritmo que se encarga de pedir, procesar y enviar la información (cliente)

1. Inicio
2. Guardar "listo" en mensaje.
3. Hacer ciclo 1:
4. Establecer conexión con el Servidor en puerto 5000
5. Enviar mensaje
6. Recibir información
7. Guardar la información recibida en paquete
8. Si paquete es igual a "nulo":
1. Cerrar la conexión.
2. Terminar ciclo 1.
9. Si no es asi:
1. Desempaquetar paquete.
2. Guardar paquete.
10. Mostrar "Procesando datos recibidos ->" y paquete[nombre]
11. Guardar hora local en t_inicio.
12. Guardar paquete en datos.
13. Guardar datos[coordenadas] en coordenadas[x][y].
14. Crear matriz.
15. Hacer ciclo 2 de 0 hasta cantidad de coordenadas (i):
1. Crear arreglo calculados.
2. Hacer ciclo 3 de 0 hasta cantidad de coordenadas (j):
1. Calcular la distancia euclidiana de coordenadas[i][0],coordenadas[i][1],coordenadas[j][0],coordenadas[j][1].
2. Agregar la distancia euclidiana en calculados.
3. Agregar calculados a la matriz.
4. Reiniciar calculados a 0.
5. Fin ciclo 3.
16. Fin ciclo 2
17. Calcular por Vecino Más Cercano(datos[viajes],datos[clientes],matriz,datos[capacidad],datos[demanda]).
18. Guardar resultado en viajes.
19. Crear arreglo mejorados.
20. Iniciar latencia total en 0.
21. Hacer ciclo 4 sobre viajes (en subtour):
1. Calcular por Inserción De Nodos(subtour[0],matriz,subtour[1]).
2. Guardar resultado en info.
3. Incrementar latencia total con info[1].
4. Empaquetar info.
5. Guardar en empaquetamiento.
6. Agregar empaquetamiento en mejorados.
22. Fin ciclo 4.
23. Guardar hora local en t_final.
24. Empaquetar mejorados, latencia_total y (t_final - t_inicio).
25. Guardar en mensaje.
26. Enviar mensaje al Servidor.
27. Fin ciclo 1.
28. Fin

Diagrama de Flujo

Algoritmo que se encarga de la conexión entre nodos (servidor)

1. Inicio
2. Iniciar Servidor, escuchar en puerto 5000.
3. Hacer ciclo 1 hasta cantidad de archivos (i):
1. Lectura de archivo[i].
2. Guardar la información de la lectura en arreglo temporal (numClientes,numViajes,capacidad,demandas,coordenadas).
3. Empaquetar el arreglo temporal.
4. Guardar el empaquetamiento en un arreglo (instancias[i])
4. Fin ciclo 1.
5. Iniciar contador en 0
6. Hacer ciclo 2 (para atender conexiones):
1. Aceptar conexión con cliente.
2. Recibir mensaje.
3. Si la longitud del mensaje es mayor o igual a 5:
1. Guardar en paquete la información de instancias[contador]
4. Guardar en paquete la información de instancias[contador]
1. Si la longitud del mensaje es igual a 5 y el nombre de la instancia[contador] no es "nulo":
1. Mostrar "Nodo Disponible -> Enviando datos".
2. Mostrar "Nodo Disponible -> Enviando datos".
3. Si la longitud del mensaje es mayor a 5:
1. Desempaquetar mensaje.
4. Desempaquetar mensaje.
1. Guardar desempaquetamiento.
2. Mostrar nodo que envió el mensaje, nombre de la instancia que procesó y los resultados obtenidos.
5. Si no es así:
1. Mostrar "No existe información nueva disponible".
6. Mostrar "No existe información nueva disponible".
7. Enviar paquete.
8. Cerrar la conexión.
5. Incrementar 1 en contador.
7. Fin ciclo 2.
8. Fin

Diagrama de Flujo

Pruebas

Una vez lograda la conexión "cliente/servidor" y la exitosa transmisión de datos, se obtienen los siguientes resultados:

Servidor

Al recibir una notificación se identifica que el cliente no procesó datos previamente, por lo cual simplemente se envía la información. Al procesar los datos el cliente, envía los resultados por lo cual ahora el servidor muestra "en formato" los mismos; envía nuevos datos al cliente en cuestión.

Cliente

Se muestra un mensaje indicando la recepción de los datos (entre ellos un "nombre" asignado a éstos). una vez terminado el procesamiento se envían los resultados (implícitamente espera nuevos datos); al recibir un mensaje indicando que no existe mas información para procesar el cliente cerrará la conexión.

Resultado Final

Definimos una serie de mensajes que determinan cuando hay información, también se agrega un formato a cada Nodo donde indica que no hay datos disponibles. Una vez logrado, el Sistema Distribuido fue capaz de proporcionar información y procesarla en tiempo real, dar "fomato de presentación" a la misma y mostrarla en los nodos correspondientes.

Evidencia

Esta es la ejecución del "Servidor", puede apreciarse el Nodo que envió la información y su respectiva instancia (datos que procesó). En esta situación: una PC de escritorio realizó la Instancia 12; una laptop, la Instancia 5; finalmente, otra laptop pidió información pero ya no había disponible porque los Nodos anteriores previamente habían solicitado datos (lo que aparece en pantalla son las últimas "peticiones" atendidas). A continuación la muestra de cada Nodo:

Información que pidió y procesó la PC de escritorio.

Información que pidió y procesó la laptop.

Petición que hizo la última laptop.

Conclusión

La clase donde obtuvimos la idea: Temas Selectos de Optimización, resultó de ayuda en cuanto a los métodos o técnicas que ofrece para la optimización combinatoria. Sobre todo porque existen "métodos voraces y métodos aleatorios". Fue un verdadero desafío codificar los métodos para optimizar las instancias que se utilizaron, incluso tratándose de algoritmos voraces como los que utilizamos (esto quiere decir que escanea todas las posibles combinaciones). En su mayoría los problemas que ocurrieron fueron en orden de aparición: el tour poseía nodos repetidos, o bien faltaban; olvidar la matriz de distancias (vital para el proceso), cuidar la capacidad del subtour, entre errores de sintaxis. La simplicidad de utilizar Python y las funciones que ofrece para arreglos permitieron facilitar acciones como mover un nodo de un subtour e ir insertando en cada posición posible del mismo, el hecho de ser débilmente tipado también ayudó bastante.

El "Servidor" codificado con Java no resultó tan difícil, incluso la utilización de "Pool de Threads", gracias a éste último pudimos crear una fila para las instancias y "despacharlas" cada vez que se recibía una petición. Referente a la comunicación las consideraciones fueron: dado que son dos lenguajes de programación diferentes, Java considera que el flujo de datos termina cuando se encuentra una tabulación ("\n") como si se tratase de un fichero, mientras que Python recibe el flujo (típico de él); los menajes y su respectiva longitud para identificar cuando piden información y cuando la entregan.

Finalmente los Sistemas Distribuidos resultan bastante útiles para la optimización combinatoria, ya que cada algoritmo que pretenda procesar la información poseerá sus propios recursos. Sobre todo con instancias cuya cantidad de nodos supera los 200 (en sitios web sobre VRP existen instancias con hasta 460).
Se pone en evidencia cuando nuestro algoritmo codificado fue ejecutado anteriormente en forma secuencial en una PC con todas las instancias disponibles una tras otra donde el tiempo de ejecución fue mayor a comparación del sistema distribuido.

Agradecemos a la Dra. Iris Abril Martínez Salazar por proporcionarnos orientación y ayuda sobre este tema y sus problemas.