Optimización de un problema de ruteo con restricciones de capacidad utilizando algoritmos inteligentes (algoritmo genético modificado)

Resumen

El ruteo vehicular pertenece a un tipo de problema combinatorial, a medida que se aumente el número de clientes, este tipo de problema se convierte en un tema muy complejo de solucionar computacionalmente, de tal manera que para un número mayor a 20 clientes con una sola ruta se obtiene 20!/2 combinaciones posibles1, es decir 12x1017 combinaciones, siendo esto casi imposible de resolver computacionalmente con los métodos exactos existentes. Cuando utilizamos métodos exactos se debe tener presente el modelo matemático, es decir se buscan cada una de las combinaciones posibles y se revisan cada una de las restricciones del problema. Si hablamos de las restricciones en el modelo matemático, se deben tener en cuenta aspectos como la capacidad del vehículo, las visitas a un cliente (uno a la vez) y su demanda, además del tiempo. En la vida real los problemas de enrutamiento son de mayor tamaño que 20 clientes, sin embargo en la actualidad existen métodos no exactos de solución con muy buenos resultados, estos procesos se conocen como algoritmos heurísticos y meta heurísticos, que permite a través de iteraciones lógicas llegar a obtener soluciones óptimas o cercanas al óptimo en determinados casos. Por otra parte cuando se aplica el problema de enrutamiento a problemas reales surgen otros tipos de restricciones como el tiempo, capacidad, número de vehículos, factores ambientales, de tráfico, semaforización, horas pico, zonas urbanas y contaminación acústica. Tal es el caso del ruteo de vehículos con dependencia del tiempo, en el que el tiempo de salida del vehículo determina el costo de la ruta, puesto que según la hora en que se realice el recorrido, se tendrá mayor o menor tráfico, lo que conlleva a elevar el costo no solo por distancia recorrida, sino por el tiempo que se gasta el vehículo en recorrer la ruta. En esta investigación se pretende conocer y resolver un problema de ruteo vehicular con capacidad (CVRP, Capacitated Vehicle Routing Problem), además de incluir dos restricciones como el tiempo y la capacidad teniendo en cuenta el tiempo como el recorrido de la ruta del vehículo para realizar la recolección de basuras y la llegada al relleno sanitario de cada uno de los barrios. El tiempo es un factor importante que se debe tomar en problemas de ruteo vehicular reales, debido a que el costo del recorrido de la ruta aumenta en las horas pico, esto se debe a la congestión de tráfico dependiendo del sitio y hora donde se encuentre el recolector de basura del municipio , además se debe considerar la congestión vehicular como fuente de estrés2 a los conductores y de contaminación ambiental, otro factor importante es la proliferación de plagas causantes de muchas enfermedades3 al no recoger las basura a tiempo. Este tipo de solución se prueba con diferentes instancias del problema de (CVRP, Capacitated Vehicle Routing Problem) en el capítulo 5 se muestra la ejecución del algoritmo genético para instancias publicadas en la literatura especializada y finalmente se procede a implementar la solución planteada en un caso específico.