Si tuviera que entregar en mano 50 paquetes, ¿cómo planificaría la mejor ruta posible?

Esta pregunta se enmarca en un problema teórico que trae de cabeza desde hace mucho tiempo a matemáticos y científicos de la computación y que probablemente conozca usted mismo: el llamado problema del viajante. En pocas palabras: dada una lista de lugares y las distancias entre todos ellos, ¿cuál es la ruta más corta posible que visita cada lugar una vez y regresad de nuevo al origen tras todas ellas? Como puede entenderse a primera vista, la solución a ese problema es una propuesta muy atractiva para cualquier empresa de comercio electrónico que reparta a domicilio los bienes que vende, pues implicaría menores costes de combustible y menos conductores.

Pero hay un obstáculo: el problema se vuelve muy complicado muy rápido. "Si un solo conductor tiene que ir a 57 paradas, ya tiene un número de combinaciones posibles que alcanza mil duodecillones (10⁷⁵) de combinaciones posibles", explica el CEO de la start up de optimización de rutas radicada en Vancouver (Canadá) Routific, Marc Kuo. "Eso son 75 ceros", remarca. Los sistemas informáticos actuales tardarían días o semanas en evaluar cada ruta posible. Ante esta situación, en lugar de buscar la perfección, las empresas deben encontrar otros enfoques inteligentes para mejorar sus rutas en la medida de lo posible.

Las grandes jugadoras del sector de la mensajería y la paquetería no están dispuestas a hablar sobre el tema. Ni UPS ni DHL respondieron a las solicitudes de entrevistas. FedEx no pudo encontrar un hueco para hablar de ello a pesar de tener más de una semana de aviso. Y un portavoz de Amazon dijo solamente que la compañía trabaja "con un cierto número de diferentes proveedores de servicios de paquetería, los cuales utilizan tecnología de alta gama para entregar sus paquetes en nombre de Amazon". Más allá de eso, la compañía asegura no tener "nada que compartir".

Afortunadamente, algunas compañías más pequeñas tienen menos reservas, así que decidimos hablar con ellas.

La optimización del reparto y entrega de paquetes en el mundo real es más espinosa que el problema del vendedor viajero en varios aspectos. Primero, hay que calcular la distancia entre las diferentes ubicaciones, pero como todo usuario de Google Maps sabe, siempre hay más de una forma de realizar un viaje. El director gerente de Paragon, una empresa que ofrece software para planificar rutas y horarios en 60 países a clientes como el gigante de los supermercados británicos Tesco, Will Salter, dice que los algoritmos de búsqueda de rutas utilizados en la planificación de entregas están "altamente personalizados" en comparación con los de Google Maps. Según Salter, sus algoritmos tienen en cuenta las condiciones del camino, los cambios del tráfico en diferentes momentos del día e, incluso, el beneficio marginal de girar a la derecha en un cruce.

Por tanto, la empresa necesita tener en cuenta cientos de limitaciones. Puede que consiga calcular una ruta increíble que incluya todas sus entregas, pero, ¿cabe todo en la parte trasera de la furgoneta? ¿Cuánto tiempo más tarda el repartidor en entregar los congelados que los alimentos de primera necesidad? ¿Merece la pena entregar primero los objetos más pesados para ahorrar combustible?

El jefe de sistemas de planificación y entrega de Ocado, el minorista de comestibles en línea más grande del mundo (ver Un enjambre de 1.000 robots transporta y almacena los productos frescos del súper), James Lohr, explica que su sistema asigna primero al azar las diferentes entregas a furgonetas dentro de un área geográfica y después, una vez asignadas, averigua cuánto tiempo se tardará en hacerlas. El algoritmo combina entonces grandes y pequeños cambios, desde intercambiar el orden de dos puntos de entrega a cambiar secciones enteras de entregas entre vehículos, para evaluar qué cambios suponen una mejora y cuáles no. Con cuatro millones de movimientos por segundo y la monitorización de las mejores soluciones, su algoritmo se acerca lentamente a la ruta más óptima que puede encontrar.

Lejos del gran esfuerzo computacional para la planificación de rutas en grandes compañías, algunas empresas desarrollan también sistemas dirigidos a pequeñas empresas. Por ejemplo, el CEO de Rotific explica que su compañía espera ofrecer una planificación de rutas potente gracias a servicios en la nube a los que sus conductores podrían acceder a través de un teléfono inteligente. "Puede ser un shock, pero muchos conductores todavía planean las rutas con papel y lápiz", explica. El algoritmo de su empresa también hace cambios graduales en las rutas, pero cuando un cambio pequeño supone una gran diferencia, la atención se centra alrededor de ese cambio para maximizar la mejora. Después, el algoritmo continúa evaluando las diferentes posibilidades. Routific afirma que su servicio reduce la duración de las rutas de entrega en un 40%.

Hay una posibilidad lo suficientemente alta de que ya haya interactuado con estos algoritmos sin darse cuenta. Tanto Paragon (que trabaja en nombre de Ikea y del distribuidor de catálogos Argos) como Ocado obtienen datos de los análisis que realizan al ofrecer las ventanas de entrega a los clientes de sus webs. Las compañías proponen únicamente rutas que se ajusten a sus planes para los próximos días.

Esa es una muestra de cortesía para los conductores que, tal vez, no ha existido siempre. Paragon, Ocado y Routific han experimentado muchos problemas culturales cuando tienen que convencer a los repartidores experimentados de que sus algoritmos pueden optimizar las rutas mejor que ellos. "Hubo un momento en el que si ibas a donde los conductores almuerzan y decías que eras un planificador de rutas, temías por tu vida", recuerda el jefe de sistemas de planificación de Ocado. "Estoy exagerando ligeramente, por supuesto, pero puede ser difícil de gestionar".

Mientras tanto, más capas de dificultad se añaden sin parar al problema de la optimización en sí mismo y no parece que haya un final a la vista. Salter, de Paragon, explica que los clientes siguen pidiendo que se añadan nuevas posibilidades. Por ejemplo, las rutas que minimizan las emisiones de dióxido de carbono se han convertido en una de las opciones favoritas. "Cada año tenemos en cuenta más y más condicionantes", explica. "No creo que sea realmente posible optimizar [las rutas] que estamos planeando".