Introducción

Si bien cuando nuestros puntos de entrega/clientes a visitar son pocos mentalmente o con ayuda de un mapa podemos intuir cual es la mejor secuencia y de ahí armar la mejor ruta para visitarlos, cuando la cantidad aumenta podemos recurrir a segmentar el problema planificando las ruta por zona por ejemplo.

La Inteligencia Artificial rompe totalmente con esos paradigmas de búsqueda y creación de la ruta manual/mental resulta por el humano, para trabaja sobre reglas claras y concisas para optimizar las rutas, minimizando los tiempos y costos asociados, para visitar a cada punto de interés.

Marco teórico llevado a la práctica

Matemáticamente hablando, este problema es de carácter exponencial, lo que quiere decir que mientras mientras más puntos tengamos que visitar exponencialmente se incrementar la cantidad de rutas posibles para visitarlos.

En los siguientes cálculos se podrá notar la dimensión del problema siendo la fórmula estadística de (n-1)!/2 rutas posibles.

  • Para 5 clientes tenemos (5-1)!/2 los que son 12 rutas posibles, algo Manejable sobre un mapa.

  • Para 10 clientes tenemos (9-1)!/2 los que son 181.440 rutas posibles, vemos como el problema comienza a crecer.

  • Para 11 clientes tenemos 1.814.400 rutas posibles.

  • Para 13 clientes tenemos 239.500.800 rutas posibles.

  • Para 20 clientes tenemos 1.216.451.004.088.320.000 rutas posibles.

Como vemos el problema crece a pasos agigantados y se ve claramente que para obtener la ruta óptima necesitamos un gran poder de cálculo, ya que que habría que probar todas las rutas posibles y quedarse con la óptima. Obviamente esto demandaría en las PCs mucho poder computacional y tiempo, demorando tanto que hasta podría a no llegar a dar una solución.

Para resolver este problema contamos con algoritmos que dan soluciones cercanas a la ruta óptima a través de métodos aproximados logrando obtener soluciones sub-óptimas en cuestión de segundos. Cuán cercana sea la solución va a depender de muchos factores como la cantidad de clientes, la distancias en ellos el tipo de camino a recorrer, etc. Ahora bien, si además le agregamos la complejidad de que los clientes no están las 24 hs los 365 días del años disponibles, que los tiempos de servicio son distintos y que queremos más de una ruta para realizar las visitas, este problema aún se complejiza mucho más.

En este caso nos basamos en el Algoritmo Genético el cual es es más utilizado estudiado para intentar resolver este tipo de problemas de transporte.

Los Algoritmos Genéticos representan un método de búsqueda idóneo dada su naturaleza paralela que permite explorar el espacio de búsqueda en varias direcciones, esta característica evita estancamientos al encontrar soluciones

sub­óptimas como en otros métodos en los que es necesario comenzar de nuevo todo el proceso al estar en uno de estos estados. Para el problema de transporte tratado, este comportamiento es de gran utilidad dado que nos permite estudiar soluciones alternas que pueden llegar a ser de gran utilidad en la toma de decisiones cuando surgen condiciones externas al problema (para más información se puede buscar NP - Completo o NP - Óptimo).


¿Encontró su respuesta?