El problema del viajero familar multiagentecapacitado

Ponente(s): Saúl Domínguez Casasola, José Luis González Velarde, Yasmín Á. Ríos Solís

En el problema del viajero familiar multiagente capacitado (CFTSP por sus siglas en inglés Capacitated Family Travel Salespersons Problem), se tienen varios conjuntos de nodos que llamamos familias y el objetivo es visitar un número fijo de nodos de cada familia con varios agentes de manera que se minimice la distancia total de los recorridos de los agentes. La mayor contribución reside justamente en considerar varios agentes capacitados puesto que el FTSP introducido por Morán-Mirabal, González-Velarde y Resende [1], solo considera un agente que tiene capacidad infinita. La motivación práctica del CFTSP está basada en el proceso de surtido en almacenes, donde productos de una misma familia pueden encontrarse en distintas ubicaciones. La llegada de nuevas herramientas tecnológicas ha permitido la coexistencia entre productos de distintas familias en ubicaciones multi-SKU, las cuáles son visitadas por agentes con distintas capacidades. Aunado a ello, las características de cada familia relacionadas al peso del producto, pueden ser distintas. Estos aspectos son tomados en cuenta en la propuesta de un modelo matemático de programación lineal entera y un algoritmo evolutivo para solucionar el CFTSP, con el objetivo de minimizar la distancia recorrida requerida para surtir rápidamente las órdenes que recibe el almacén. Para ello se considera una gráfica $G = (\{0\}\cup\mathbf{N}, E)$ donde $\mathbf{N}$ es el conjunto de nodos, divididos en $L$ familias distintas, representadas por $F_l$, con $l = 1,...,L$, de tal modo que $F_{l_1}\cap F_{l_2}=\emptyset$, $\forall l_1 \neq l_2$; $\cup_{l=1}^L F_l = \mathbf{N}$; y $F_l \subseteq \mathbf{N}$, $\forall l$. Cada familia $l$ tiene $f_l$ nodos, con peso $w_l$, y un número $v_l \leq f_l$ de visitas requeridas, de tal modo que $\sum_{l=1}^L f_l = |\mathbf{N}|$, y consecuentemente $\sum_{l=1}^L v_l \leq |\mathbf{N}|$. Las distancias $d_{ij}>0$ entre los pares de nodos $i$ y $j$, donde $i,j \in \{0\}\cup \mathbf{N}$ e $i \neq j$, están indexadas en el conjunto de aristas $E$. Además, se tiene un conjunto $\mathbf{P} = \{1, ..., P\}$ de agentes, cada uno con capacidad $c_p$, $p \in \mathbf{P}$. Una solución factible visita la cantidad de nodos indicados por $v_l$, y ningún agente excede su capacidad de carga. Nótese que el CFTSP puede reducirse al problema del agente viajero, cuando se tiene un único agente (con suficiente capacidad), y se desea que todos los nodos de todas las familias sean visitados. Palabras clave: Programación Lineal Entera, BRKGA, TSP. REFERENCIAS [1] L. F. Morán‐Mirabal, J. L. González‐Velarde y M. G. Resende, «Randomized heuristics for the family traveling salesperson problem.» International Transactions in Operational Research, 21(1), 41-57., vol. 21, nº 1, pp. 41-57, 2014.