Revista internacional de inteligencia de enjambre y computación evolutiva

Abstracto

Un algoritmo inmunológico para la optimización combinatoria: el problema de la distribución de combustible como caso de estudio

Pavone M*, Costanza J y Cutello V

Resumen Los problemas de ruteo son tareas clásicas de optimización combinatoria que encuentran mucha aplicabilidad en numerosos escenarios industriales y del mundo real. Una variante desafiante del problema de ruteo es el Problema de Distribución de Combustible (FDP) que una empresa de transporte debe enfrentar en sus operaciones diarias. La actividad principal de una empresa de combustible para transporte es reabastecer todas sus tiendas, es decir, estaciones de servicio, a lo largo de un mapa geográfico, con el objetivo de minimizar sus costos generales. En este trabajo de investigación presentamos una heurística híbrida basada en la metáfora del sistema inmune para resolver el FDP, que básicamente pide encontrar un conjunto de rutas lo más cortas posibles para un número fijo de vehículos de la empresa con el fin de satisfacer las diversas demandas recibidas de los clientes. En particular, el algoritmo inmunológico presentado se inspira en el principio de selección clonal, cuyas características clave son los operadores de clonación, hipermutación y envejecimiento. Dicho algoritmo también se caracteriza por tener (i) un enfoque determinista basado en el algoritmo Depth First Search (DFS) - utilizado en el esquema de asignación de un vértice a un vehículo - y (ii) un operador de búsqueda local, basado en la exploración del vecindario. El algoritmo ha sido probado en una instancia de datos reales, con 82 vértices, y otras 25 instancias artificiales diferentes, tomadas del benchmark de coloración de grafos DIMACS. Los resultados experimentales presentados en este trabajo, no sólo prueban la robustez y eficiencia del algoritmo desarrollado, sino que también muestran la bondad de la búsqueda local y el enfoque basado en el algoritmo DFS. Ambas metodologías ayudan al algoritmo a explorar mejor el complejo espacio de búsqueda.