Un algoritmo genético con llaves aleatorias con sesgo para el problema del viajero familiar multi-agente capacitado

Saúl Domínguez Casasola, José Luis González Velarde, Yasmín Águeda Ríos Solís

Instituto Tecnológico de Estudios Superiores de Monterrey

Escuela de Ingeniería y Ciencias

[email protected]

Resumen

La motivación del problema del viajero familiar multi-agente capacitado (CFTSP-Capacitated Family Travel Salespersons Problem), son los almacenes con ubicaciones multi-SKU y productos iguales en ubicaciones distintas. Esto lleva a decidir: las ubicaciones a visitar, el orden de las visitas y su asignación a los agentes. Matemáticamente, se considera un grafo completo, cuyos nodos están divididos en familias disjuntas, el CFTSP consiste en encontrar un subconjunto de nodos a visitar, minimizando la distancia total recorrida. Se debe satisfacer la demanda para cada familia sin exceder la capacidad de los agentes. Para este problema, se propone un modelo de programación entera mixta; sin embargo, para algunas instancias no se consiguen soluciones factibles en un tiempo de cómputo razonable. Por ello, se utiliza un algoritmo genético con llaves aleatorias con sesgo, que consigue obtener buenos resultados. Finalmente, se comparan ambas estrategias, y se hacen conclusiones.