problema de los m-viajantes de comercio (m-TSP)
distancia total mínima
El problema de los m-viajantes de comercio (m-TSP) es una variante del problema del viajante de comercio (Traveling Salesman Problem - TSP). En este problema, se trata de construir $m$ rutas, una para cada viajante de comercio (o vehículo). Al igual que en el TSP, cada cliente debe ser visitado exactamente una vez. Las rutas de los vehículos deben comenzar y finalizar en un lugar de origen y destino final que llamaremos depósito.
Se trata de $m$ vendedores o viajantes de comercio que debe visitar n ciudades para vender u ofertar sus productos. Cada viajante de comercio podrá visitar como máximo a $p$ clientes o ciudades. Cada par de ciudades puede estar comunicada o no, su distancia se define mediante $c_{ij}$. El problema es por tanto, decidir el recorrido que comenzando por una determinada ciudad $\{ 0\}$ pase por todas las demás una sola vez y vuelva finalmente a la primera, de manera que se minimice la distancia total recorrida de todas las rutas.
Sea $x_{ij}$ una variable binaria que indica si el viajante utilizará el arco de la ciudad $i$ a la $j$ en su solución. A continuación se muestra el modelo completo del problema:
$$ \displaystyle{\min \sum_{i,j \in E} {c_{ij} x_{ij}}}$$
y está sujeto a las restricciones:
$$ \displaystyle{\sum_{j \in \Delta^+(0)} {x_{0j}} =m } $$
$$ \displaystyle{\sum_{j \in \Delta^-(0)} {x_{j0}} =m } $$
$$ \displaystyle{\sum_{j \in \Delta^+(i)} {x_{ij}} =1 \quad \forall i \in V \setminus \{0\}} $$
$$ \displaystyle{\sum_{j \in \Delta^-(j)} {x_{ij}} =1 \quad \forall i \in V \setminus \{0\}} $$
$$ \displaystyle{x_{ij} \in \{0,1\}}$$
$$ \displaystyle{u_i - u_j + p \cdot x_{ij} \leq p-1 \quad \forall i,j \in E, i \neq 0, j \neq 0}$$
$$ \displaystyle{u_{i}\geq0 \quad \forall i \in V \setminus \{0\}}$$
El modelo es muy similar al del problema del viajante de comercio. La primera restricción indica que $m$ viajantes saldrán del depósito. Analizando el siguiente par de restricciones, se puede observar que sólo debe haber un arco de llegada a una ciudad o nodo, y que igualmente tan sólo debe haber un arco de salida. Con esto se garantiza que cada ciudad es visitada sólo una única vez. Por tanto, cada cliente o ciudad es un nodo intermedio de una ruta.
Sin embargo, con estas restricciones y la condición binaria de las variables $x_{ij}$, no es suficiente para garantizar que las soluciones factibles son recorridos. Es posible por tanto, que aparezca una solución formada por subrutas (no conectadas entre sí) y que cumplan las restricciones anteriormente comentadas.
Es por ello, por lo que es necesario añadir más restricciones que eviten la formación de subrutas. Una de las posibles formas de hacer esto (ya que existen varias), es la propuesta por Miller-Tucker y que se muestra en el modelo. Las variables de decisión introducidas por las condiciones de Miller-Tucker son reales y no tienen límites ni superior ni inferior. La propuesta de Tucker genera $n^2$ restricciones, mientras que otras en la literatura pueden llegar a generar $2^n$. Sin embargo, desde un punto de vista computacional, este modelo aunque más compacto es menos eficiente. En este caso, las restricciones e Tucker imponen además que en cada ruta no haya más de $p$ clientes.
En el caso de que $p=n$ (cuando no hay límite en la visita de los viajantes a los clientes), el m-TSP podría formularse como un TSP con $m$ copias del depósito, con distancia infinita entre ellos. Las soluciones a este TSP no utilizarían arcos que conectara las copias del depósito y podrían ser interpretadas fácilmente como soluciones al problema de m-viajantes de comercio.
En el caso de Grafos, este problema se aborda a través del modelo anteriormente expuesto y su resolución mediante Programación Lineal Entera Mixta.
Otra estrategia para solucionar este problema (muy común) es resolverlo sin las condiciones de Tucker. Y si en la solución aparecen subrutas, entonces introducir la restricción oportuna que evite estas subrutas y volver a resolver el problema. Este proceso de relajación-restricción se repetirá hasta obtener la solución óptima.
Además de la PLEM en la literatura existen multitud de estrategias de resolución para este problema: técnicas de aproximación, heurísticas, relajaciones, post-optimizaciones, óptimos locales, enumeración completa, meta-heurísticas y técnicas evolutivas, y otras.
Más información en:
- Miller, C. and A. Tucker, R. Zemlin, Integer programming formulations and traveling salesman problems, J. of the ACM, 7 (1960) 326-329.