Planificación y Optimización Paralela de Redes Logísticas de Transporte
Conclusiones
- Conclusiones Generales
- Resultados
- Posibles Ampliaciones
- Licencias
- Cesión de Derechos
- Agradecimientos
- Bibliografía
Conclusiones Generales
A lo largo de este trabajo, se ha desarrollado como implementar un sistema que permita planificar una red logística de transporte de gas natural con el mínimo costo asociado al movimiento del mismo. El rasgo definitorio de este proyecto respecto a otros es que permite realizar análisis empíricos de sensibilidad sobre los parámetros del sistema valiéndose de computación en paralelo. Esto permite por un lado una gran flexibilidad a la hora de hacer la planificación debido a que se puede estudiar como afecta cada parámetro al sistema completo y por otro realizar este estudio en una fracción del tiempo que llevaría ejecutarlo de forma secuencial. El método de servicios web utilizado para implementar este paralelismo permite además poder desplegar la aplicación en computadores de todo tipo que posean capacidad de cálculo sobrante, no siendo necesario realizar una inversión en grandes servidores a menos que los problemas sean de una magnitud muy grande.
La planificación del sistema se realiza mediante la optimización de un modelo de programación lineal entera mixta (MILP) en el que se trata de minimizar el consumo de las estaciones de compresión a la vez que se satisface toda la demanda. Usando el resolutor matemático CPLEX, hemos realizado esta optimización.
La motivación de este proyecto reside en que realizar un análisis de este tipo manualmente resulta harto complicado, llegando a ser impracticable si se tarda más tiempo en realizar el cálculo que de el que tenemos para realizar la planificación. Por tanto, una automatización de este proceso como la que presentamos permite optimizar los recursos del sistema, repercutiendo en el coste de operación del mismo.
Resultados
Tras probar la aplicación en diferentes máquinas y con modelos de tamaños diferentes, hemos obtenido que la proporción de tiempo ahorrado al realizar el análisis de sensibilidad paralelamente es mayor cuanto más complejo es de resolver el modelo. Esto se traduce en que para modelos muy grandes o que se pretendan planificar para un número elevado de periodos, la aplicación consigue alcanzar la solución óptima en una fracción del tiempo que tardaría en hacerlo secuencialmente. Para modelos pequeños (Como el modelo de prueba presentado en el capítulo anterior) la cantidad de tiempo que se pierde en realizar la conexión a través de la red hace que no compense utilizar varias computadoras, a no ser que el análisis de sensibilidad incluya un rango muy amplio de valores.
En cualquier caso, las planificaciones reales que se realizarían en una aplicación como esta se encuentran al menos dentro de uno de ambos escenarios, por lo que los beneficios potenciales para una empresa que se valga de esta herramienta serán evidentes. No debemos de olvidar que, al tratarse de hacer una planificación, el tiempo es un factor vital. Una solución, por muy buena que sea, será inútil si para el momento que se obtiene ya no se puede aplicar. Los márgenes con los que se opera en este caso son estrechos y cualquier ahorro de tiempo que se pueda obtener significa aumentar los beneficios.
Para servidores con la misma capacidad de cómputo y carga de trabajo, se consiguen efectivamente ejecuciones muy próximas a 1/n del tiempo que tardaría en hacerse secuencialmente. Hemos creado modelos relativamente complejos que se mueven en el rango de las decenas de minutos, por tanto los beneficios de la aplicación son aparentes.
El único factor que puede hacer que este rendimiento se degrade es que los computadores sean muy dispares en cuanto a potencia o carga de trabajo se refiere. Como la solución óptima no queda compuesta hasta que se obtiene la respuesta de cada uno de ellos, el hecho de que uno se retrase implica que todo el sistema lo haga también. Para evitar esto, se utiliza el procedimiento que se encarga de descubrir que servicios web están activos para realizar una prueba de rendimiento de cada uno. En base a esto se puede planificar la cantidad de mensajes que se enviarán a cada servidor para equilibrar las cargas de trabajo.
Posibles Ampliaciones
Se ha comentado que esta aplicación utiliza una de las clases de computación en la nube a la hora de implementar el paralelismo, concretamente el de la nube privada. Un paso más allá sería colocar la aplicación en un servidor de la nube pública del tipo Plataforma como Servicio (PaaS) como podría ser un servidor de Amazon y de esta forma dejar la gestión de la infraestructura a una empresa externa, minimizando así los costes. Esto plantearía dos inconvenientes: Por un lado la sensibilidad de la información que se dejaría vagar por la red, lo cual podría protegerse con los adecuados algoritmos de encriptación y por otro la política de IBM respecto a colocar CPLEX en uno de estos servidores es restrictiva.
Como alternativa a CPLEX si se desease llevar a cabo esta tarea,
se ha investigado sobre el uso de Gurobi, otro resolutor matemático que también trabaja con OPL y dispone de licencias específicamente diseñadas para esta tarea. Gurobi incluso ofrece tutoriales para migrar desde CPLEX, por tanto podría realizarse con relativamente poco esfuerzo.
Licencias
IBM ofrece diferentes tipos de licencias para CPLEX dependiendo de el uso que se quiera dar al mismo. Esto incluye desde versiones gratuitas de prueba que están bastante limitadas en cuanto a capacidad de cálculo y que no permiten ser llamadas externamente, pasando por licencias académicas como la que hemos utilizado hasta llegar a versiones completas. El costo de cada una de ellas es a menudo confuso y es necesario ponerse en contacto con IBM para obtener un precio dependiendo de en que campos vaya a usarse el resolutor.
Cesión de Derechos
Adrián García Romero, Miguel Mena Jiménez y Alejandro Soto Rebollo, los autores del proyecto y abajo firmantes autorizamos a la Universidad Complutense a difundir y utilizar con fines académicos, no comerciales y mencionando expresamente a sus autores, tanto la propia memoria, como el código, la documentación y/o el prototipo desarrollado.
Agradecimientos
A nuestro director de proyecto, José Jaime Ruz Ortiz, por su paciencia y consejo.
A mis padres y a Raquel por su apoyo incondicional.
A mi familia por su apoyo continuo, a Yasmine por estar siempre ahí.
Bibliografía
Gorostegui López-Alonso, "Modelado, Optimización y Planificación de una Red de Distribución de Gas Natural", Trabajo Fin de Máster (Universidad Complutense de Madrid / Universidad Nacional de Educación a Distancia) 2011
Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali, "Programación lineal y flujo en redes", Limusa, 2004
Ramos Méndez, Eduardo, "Programación Lineal y Métodos de Optimización" Uned, 1991
A. H. Land and A. G. Doig, "An automatic method of solving discrete programming problems". Econometrica : pp. 497–520, 1960
Cornuejols, Gerard . "Revival of the Gomory Cuts in the 1990s. Annals of Operations Research": pp. 63-66, 2007
Herrán González, A., “Modelado, Planificación y Control de Sistemas de Distribución de Gas y Derivados del Petróleo”, Tesis Doctoral (Universidad Complutense de Madrid) 2008.
Moyer, Christopher M. "Building applications in the cloud: concepts, patterns, and projects",
Addison-Wesley, 2011