¿Qué es y para qué sirve Google OR-Tools?

Google OR-Tools es un paquete de software portable de código abierto para resolución de problemas de optimización. Así mismo, cuenta con metaheurísticas que buscan encontrar la mejor solución a un problema entre un conjunto de posibles soluciones. Or-Tools es una herramienta potente, diseñada para abordar los problemas más difíciles del mundo en el enrutamiento de vehículos, los flujos, la programación de números enteros y lineales y la programación de restricciones.

Una de las ventajas potenciales de Google Or-Tools consiste en que, a pesar de estar desarrollado en lenguaje C++, permite el modelamiento de problemas en múltiples lenguajes de programación, del mismo modo, cuenta con múltiples solucionadores específicos para resolverlos, algunos comerciales y algunos de código abierto.

Fuente: Google OR-Tools

Centrémonos en la posibilidad de modelar un problema de optimización en un lenguaje de programación, puesto que las oportunidades son cada vez más interesantes. En la academia, la enseñanza de la investigación de operaciones, el proceso de modelamiento y el mundo de los solucionadores, es tan a menudo, atomizado, que carece de practicidad.

La obtención, el procesamiento y la disposición de un volumen considerable de datos, su convergencia en un modelo de optimización y su eventual integración hacia un solucionador, son procesos complejos, que implican con regularidad la reunión de herramientas poco compatibles.

Google Or-Tools, al permitir el modelamiento en diversos lenguajes de programación, ofrece un sinfín de posibilidades de integración entre herramientas de obtención y tratamiento de información; así mismo, ofrece posibilidades ilimitadas de desarrollo de soluciones, como por ejemplo interfaces de usuario amigables, o integración con sistemas de integración de recursos, app’s, plataformas webs, dispositivos con un sistema de conexión a internet de las cosas (IoT), y mucho más.

Suponga, por ejemplo, que quiere desarrollar un modelo que le permita mejorar la eficiencia del proceso de recogida de paquetes, un típico problema de distribución y recolección de última milla, abordado dentro de la investigación de operaciones como un problema VRP (Vehicle Routing Problem). En su versión básica, requerirá de un conjunto de nodos y el costo que representa el arco que une a cada par (origen y destino). Sin embargo, asumamos que el criterio de optimización está basado en la distancia entre nodos, y, además, que se pretende, dado el volumen de datos requeridos, integrar una interfaz de programación externa que le permita obtener los tiempos entre nodos desde una plataforma como Google Maps.

Por otro lado, la flota de vehículos disponibles tiene una capacidad limitada (CVRP), y la información relacionada al número de vehículos y su capacidad volumétrica, se encuentra actualizada todos los días en archivo csv accesible desde el servidor de la empresa.

La información relacionada con los destinos, o puntos de entrega, así mismo la dimensión volumétrica de los paquetes se puede obtener desde una solución desarrollada a la medida por la compañía, la cual mantiene la información actualizada en tiempo real y exporta diariamente estos datos en formato xls.

Pretender integrar los datos de entrada, que a su vez son salidas desde plataformas diferentes, en formatos diferentes; algunos de ellos, información en tiempo real; procesar y organizar dicha información, integrarlos en un modelo de optimización y luego ejecutar un solucionador, haciendo uso de las herramientas típicas como Solver, Storm, Tora, WinQSB, Crystall Ball, etc., resultaría sumamente complejo, y en algunos casos imposible.

Sin embargo, haciendo uso, por ejemplo, de un lenguaje de programación como Python, es posible desarrollar un código (script) que automatice las solicitudes hacia una API de Google Maps (HTML), decodifique sus respuestas (JSON), permitiendo disponer de la información relacionada con la distancia más probable para una hora de programación de salida de la flota en particular.

Así mismo, es posible ejecutar un script básico que extraiga la información contenida en un archivo csv y un archivo xls. Posteriormente, y haciendo uso de las librerías de enrutamiento de Google Or-Tools, toda esta data puede integrarse en un modelo de programación basada en restricciones que ejecutará una metaheurística como solucionador.

Como resultado, diariamente es posible mediante la integración de información actualizada en tiempo real en múltiples plataformas, a través de múltiples servidores, poder ejecutar un modelo de programación basado en restricciones que me permita obtener las rutas más eficientes de acuerdo a la metaheurística y a los parámetros del solucionador.

Dicho de otro modo, es posible integrar al modelo y al solucionador cualquier desarrollo que se base en un lenguaje común, por ejemplo: Python.

¡Sí, las ventajas potenciales son asombrosas!

¿Qué tipo de modelos se pueden resolver mediante Google OR-Tools?

Google OR-Tools incluye solucionadores para:

¿Qué tan potente es el solucionador?

De acuerdo al MiniZinc Challenge 2020, competencia internacional de solucionadores de programación de restricciones, Google OR-Tools obtuvo tres medallas doradas en cuatro categorías de evaluación.

Fuente: MiniZinc Challenge (2020)

¿Cómo puedo instalar Google OR-Tools?

Con asombro descubrimos desde esta plataforma (Ingeniería Industrial Online), que en la actualidad muchas personas nos escriben solicitando información para instalar WinQSB en computadores de 64 bits. El asombro es aún mayor cuando descubrimos que algunas instituciones de formación aún utilizan WinQSB como solucionador de modelos de investigación de operaciones.

Pues bien, esas incompatibilidades tecnológicas, no solo se han sorteado con Google OR-Tools, existen además múltiples solucionadores perfectamente compatibles con gran parte de los sistemas operativos de la actualidad. Ahora bien, OR-Tools es compatible con sistemas Linux, Mac y Windows; sin embargo, su instalación varía de acuerdo al lenguaje de programación que quieran utilizar.

Una guía completa de instalación la pueden encontrar en el siguiente enlace:

Ventajas de ser un software de código abierto

Una de la mayores ventajas que presenta Google OR-Tools consiste en que es un software de código abierto, de tal manera que su modelo de desarrollo se basa en la colaboración. Esto representa un beneficio potencial, dado que cientos de personas, día a día, se encuentran formulando modelos de optimización en diversos lenguajes de programación.

Una evidencia de ello es la colaboración entorno a la formulación de problemas de enrutamiento de vehículos, ya que a través de las contribuciones que pueden observarse en GitHub o un su foro de discusión en Google Groups, se han desarrollado modelos para diversas variaciones del modelo base, dentro de las que podemos encontrar:

Y mucho más, como colaboraciones a problemas de optimización específicos, integraciones con API’s desarrolladas por Google, como Distance Matrix API de Google Maps.

¿Los requerimientos técnicos son un limitante para su uso?

De ninguna manera. Y le vamos a explicar la razón.

Si queremos utilizar Google OR Tools en nuestro ordenador, sí tenemos algunos requerimientos técnicos, ahora bien, todos gratuitos. Requerimos la instalación de Python, un entorno de desarrollo integrado (IDE), y de la instalación de su librería (or tools).

Sin embargo, para su aprendizaje y uso básico, podemos utilizar entornos virtuales, como por ejemplo: Colaboratory de Google. ¿En qué consiste?

Colaboratory, también llamado «Colab», te permite ejecutar y programar en Python en tu navegador con las siguientes ventajas:

Es decir, podemos utilizar toda la potencia de las máquinas de Google para ejecutar nuestros modelos… ¡Genial! 

De hecho, vamos a utilizar esta herramienta en cada modelo que desarrollemos en este portal, compartiremos nuestros códigos y esperamos que les sean de gran utilidad.

En próximos artículos desarrollaremos modelos de optimización y metaheurísticas haciendo uso de Google OR-Tools, de tal manera que de la mano descubran esta gran herramienta.