Asistencia: "Una variante del problema del viajante de comercio (TSP)"

Espero que les vaya bien a todos. Para aquellos que no estén familiarizados con el problema del vendedor ambulante, consulte aquí .

Actualmente estoy tratando de trabajar con una variante del TSP. Me gustaría formular el problema de una manera similar a la formulación de Dantzig-Fulkerson-Johnson y la formulación de Miller-Tucker-Zemlin, pero no sé qué restricciones debería agregar/cambiar para abordar mi problema y cómo interpretarlas.

Problema

Hay$m$vendedores ambulantes todos originarios de alguna ciudad$d$. Cada vendedor debe visitar cada uno de los otros$n−1$ciudades una vez y solo una vez y luego volver a la ciudad$d$. Ningún vendedor puede usar el mismo borde del gráfico más de una vez (por ejemplo, si un vendedor usa borde$4$-$5$, es decir, el borde de la ciudad$4$a la ciudad$5$, entonces ningún otro vendedor puede usar esa ventaja. Minimice la distancia total recorrida por el$m$vendedores

Formulación TSP

Aquí incluyo una formulación TSP para trabajar y una interpretación de las variables

Minimizar:$\sum_{k} \sum_{i} \sum_{j:j\neq i} c_{i,j} x_{k,i,j}$

Sujeto a:

$$\begin{align} &\sum_{j=2}^n x_{1,1,j} = 1\\ &\sum_{k=2}^n \sum_{j:j\neq i} x_{k,i,j} = 1 \quad \forall i > 1\\ &\sum_{i=2}^n x_{n,i,1} = 1\\ &\sum_{k=1}^{n-1} \sum_{i:i\neq j} x_{k,i,j} = 1 \quad \forall j > 1\\ &\sum_{i:i\neq j} x_{k,i,j} = \sum_{i:i\neq j} x_{k+1,j,i} \quad \forall j,k\\ &\text{all variables are binary} \end{align}$$

Variables e Interpretación:

$n$es el número de ciudades.$c_{i,j}$es la distancia entre la ciudad$i$y ciudad$j$.

$$x_{k,i,j} = \begin{cases}1,&\text{ if a salesperson's $k$-th transition is from city $i$ to city $j$}\\0,&\text{ otherwise} \end{cases}$$ Las limitaciones$\sum_{j=2}^n x_{1,1,j} = 1$y$\sum_{i=2}^n x_{n,i,1} = 1$indique que la transición 1 es la única transición que el vendedor deja la ciudad 1 y la transición$n$es la única transición en la que el vendedor entra en la ciudad$1$, respectivamente.

la restricción$\sum_{k=2}^n \sum_{j:j\neq i} x_{k,i,j} = 1 \quad \forall i > 1$se asegura de que el vendedor salga de cada ciudad$i > 1$sólo una vez. la restricción$\sum_{k=1}^{n-1} \sum_{i:i\neq j} x_{k,i,j} = 1 \quad \forall j > 1$establece que el vendedor ingresa a cada ciudad$j > 1$sólo una vez.

La última restricción dice que el número total de vendedores que ingresan a la ciudad$j$en transición$k$debe ser igual al número total de vendedores que salen de la ciudad$j$en transición$k+1$.

¡Gracias por echar un vistazo a esto!