Optimización de Transporte de Productos utilizando Algoritmos Meméticos

Abstract

El transporte de productos por carretera es un área vital de gestión en la mayoría de las empresas, esto se debe al aumento de la demanda de servicios de entrega de mercaderías por parte de los clientes. La calidad del servicio de entrega influye directamente en la preferencia de los clientes. Dicho servicio requiere de un proceso de planificación, organización, ejecución y control del funcionamiento eficiente del servicio de transporte. El problema que se desea resolver se plantea como sigue: dada una flota de vehículos los cuales pueden estar alojados en localidades distintas (ej.: distintas sucursales de un negocio), donde los vehículos parten de dicha localidad para realizar los recorridos de entrega de productos y luego regresan a sus respectivas localidades de origen. Se busca encontrar los mejores recorridos para cada vehículo de tal forma a reconciliar los diferentes objetivos del problema. Los objetivos tratados son el lucro, el tiempo de recorrido, el porcentaje de pedidos entregados y el porcentaje de conservación de los productos entregados. La metodología utilizada para la resolución del problema conlleva la implementación de algoritmos meméticos con calificación mono-objetivo. Se aplica el elitismo para conservar las mejores soluciones encontradas en las distintas generaciones. Estas soluciones se representan por el conjunto de recorridos de cada vehículo. Cada recorrido de vehículo contiene a la vez un conjunto de trayectos que inician y terminan en localidades de interés. A su vez los trayectos son representados por una lista de localidades de orden secuencial y un conjunto de productos que se transportan durante dicho trayecto. Entre los operadores evolutivos utilizados para resolver el problema se encuentran la mutación y la recombinación. Para la operación de mutación se implementan dos variantes que se eligen al azar en el momento de realizar la mutación. La primera consiste en la eliminación de localidades del recorrido en forma aleatoria y la segunda consiste en la regeneración de un trayecto elegido al azar. Para la operación de recombinación se decidió combinar los recorridos del mismo vehículo de cada agente entre sí. Cada recorrido individual es cortado en un punto aleatorio y luego recombinado con el par del otro agente. Después de las operaciones evolutivas se realizan optimizaciones locales para evitar soluciones no factibles. Finalmente, se desarrolló el software de optimización utilizando el lenguaje de programación Java y a partir de su ejecución se obtuvo un conjunto de soluciones factibles que demostraron ser resultados positivos.