Complejidad, números grandes y problemas logísticos

Complejidad, números grandes y problemas logísticos Fernando Sandoya, Ph.D. Cuenta la historia que en 1938 un niño de 9 años, ante un pedido de su tío el matemático E. Kasner de que imaginara el número más grande posible, pensó en el 1 seguido de cien ceros (10100) y lo llamó gogol (en inglés googol); es decir, diez mil hexadecillones. Kasner anunció esta curiosidad en su libro “Las matemáticas y la imaginación”, y se pueden contar algunas anécdotas sobre este número, una de las más curiosas es que los fundadores de Google iban a llamar a su sitio Googol, no obstante por la mala ortografía de Larry Page quedó como Google. Pero ¿qué tan grande es este monstruoso número? Si tenemos que referirnos a números grandes podríamos pensar en las cosas más numerosas, por ejemplo, cuántos granos de arena existen en la tierra, o mejor aún cuántos átomos hay en la tierra, o que tal esto: cuántos átomos existen en todo el universo. Sorprendentemente, estimaciones recientes indican que en todo el universo existen alrededor de 1080 átomos (How Many Atoms Are There in the Universe?, John Carl Villanueva, 2009), esto quiere decir que en todo el universo no existe un gogol de átomos. Visto así el gogol es como una materialización del infinito, ahora bien, ¿qué tiene que ver esto con los problemas logísticos? Un problema común en la logística de las empresas constituye el ruteo de vehículos, por ejemplo, supongamos que una empresa debe efectuar la entrega de un producto, desde un almacen, a clientes dispersos en una región geográfica determinada, entonces, el problema consiste en establecer una ruta que minimice la distancia total recorrida. Si pensamos en evaluar todas las rutas posibles y de ahí seleccionar la mejor, tendríamos que evaluar todas las permutaciones de los } sitios a visitar. Por ejemplo, si se tiene que visitar a 3 clientes { }, { }, desde la base b, las posibles rutas son 6: { { }, { } { }, { } como se muestra en la Fig.1. Así, para resolver el problema bastaría con obtener todas las permutaciones y luego calcular la distancia asociada a cada una de esas rutas para por fin seleccionar la del trayecto más corto.

Figura 1. Posibles rutas

Pero el número de permutaciones de n objetos es igual al factorial de n (es decir n!), así, en un problema con n clientes, la cantidad de rutas posibles es n!, y como para calcular la distancia recorrida se necesitan alrededor de n2 operaciones, para un problema con n clientes a visitar se necesitarían n!×n2 operaciones. Y como 68!×682 es aproximadamente 10100, esto significa que resolver por este procedimiento un caso con 68 clientes requeriría de un gogol de operaciones. La supercomputadora más rápida del planeta

1 Complejidad, números grandes y problemas logísticos, Revista FOCUS, marzo 2015

actualmente, la Tianhe-2, que tiene un rendimiento de unos 34 petaFLOPS (34×1015 flops1) demoraría 1.07×1076 años en resolver este problema con 68 clientes; es decir un tiempor mayor que el tiempo transcurrido desde el Big Bang hasta hoy (1.4×1015 años). Claro que el método anterior está basado en la fuerza bruta y existen métodos inteligentes para resolver aproximadamente el problema. Presentamos aquí las soluciones obtenidas por dos enfoques: el primero, basado en el sentido común, que aparentemente debería proporcionar una buena solución, y el segundo basado en un modelo matemático. En el primer caso, construimos la ruta así: luego de visitar a un cliente, elegimos al cliente que todavía no ha sido servido y que está ubicado en la posición más cercana, le damos el servicio y así continuamos hasta que todos hayan sido atendidos, esta estrategia ocasiona una mayor distancia recorrida y por tanto una mayor inversión de tiempo y capital humano, técnico y económico. Por ejemplo, para el problema con 50 clientes distribuidos en una región de 100 km2 que se muestra en la Fig.2, esta estrategia de solución origina la ruta y la distancia recorrida mostradas en la Fig.3. Figura 2. DISTRIBUCIÓN DE LOS CLIENTES EN UNA REGIÓN DE 100 km

2

Figura 3. LONGITUD RECORRIDA CON LA SOLUCIÓN OBTENIDA POR SENTIDO COMÚN: 858 km 100

80

60

40

20

0 0

20

40

60

80

100

1

FLOPS es el acrónimo de FLoating-point Operations Per Seconds, es decir el número de operaciones de punto flotante por segundo.

2 Complejidad, números grandes y problemas logísticos, Revista FOCUS, marzo 2015

Pero si utilizamos un modelo matemático de optimización, y lo resolvemos con una metaheurística2, la ruta y la distancia recorrida se reducen significativamente con los consiguientes beneficios para las empresas e instituciones, como se aprecia en la figura 4. Figura 4. LONGITUD RECORRIDA CON LA SOLUCIÓN OBTENIDA POR UN MODELO MATEMÁTICO:700 km 100

80

60

40

20

0 0

20

40

60

80

100

Y ya que el costo de tranporte es proporcional a la distancia recorrida, se puede concluir, en este ejemplo, que el incremento en el costo de transporte por utilizar el sentido común y no utilizar un un modelo matemático es del 23%. Esta situación se repite en otros problemas logísticos: de secuenciación de la producción, de planificación de turnos, de distribución, etc. y está originado por la gran complejidad de los mismos. La lección de todo esto es que si no se utiliza una metodología formal basada en modelos matemáticos de optimización para resolver los problemas logísticos, se está perdiendo mucho dinero, desperdiciando más rápidamente recursos como choferes, combustible y vehículos.

2

Una metaheurística es un procedimiento para diseñar algoritmos altamente eficientes que permitan resolver modelos de optimización.

3 Complejidad, números grandes y problemas logísticos, Revista FOCUS, marzo 2015