Assistance: "A Traveling Salesperson Problem (TSP) variant"

Question

I hope it is going well for everyone. For those unfamiliar with the Traveling Salesperson problem, see here.

I am currently trying to work through a variant of the TSP. I would like to formulate the problem in a manner similar to both the Dantzig–Fulkerson–Johnson formulation and Miller–Tucker–Zemlin formulation but am lost on what constraints I should be adding/changing to address my problem and how to interpret them.

Problem

There are $m$ traveling salespeople all originating from some city $d$. Every salesperson must visit every one of the other $n−1$ cities once and only once and then return to city $d$. No salesperson can use the same edge of the graph more than once (e.g. if one salesperson uses edge $4$-$5$, i.e. the edge from city $4$ to city $5$, then no other salesperson can also use that edge. Minimize the total distance traveled by the $m$ salespeople.

TSP Formulation

Here I include a TSP formulation to work with and an interpretation of the variables

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

Subject To: \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 and Interpretation:

$n$ is the number of cities. $c_{i,j}$ is the distance between city $i$ and city $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}$$ The constraints $\sum_{j=2}^n x_{1,1,j} = 1$ and $\sum_{i=2}^n x_{n,i,1} = 1$ state that transition 1 is the only transition the saleperson leaves city 1 and transition $n$ is the only transition the saleperson enters city $1$, respectively.

The constraint $\sum_{k=2}^n \sum_{j:j\neq i} x_{k,i,j} = 1 \quad \forall i > 1$ makes sure that the salesperson exits each city $i > 1$ only once. The constraint $\sum_{k=1}^{n-1} \sum_{i:i\neq j} x_{k,i,j} = 1 \quad \forall j > 1$ states that the salesperson enters each city $j > 1$ only once.

The last constraint says that the total number of salespeople who enter city $j$ on transition $k$ must equal the total number of salespeople who leaving city $j$ on transition $k+1$.

Thank you for taking a look at this!

Answer 1

Take any formulation of TSP with binary variables $x_{i,j}$ that indicate whether edge $(i,j)$ is traversed. Now introduce a $k$ index for person $k$ (this is a different meaning than your $k$), include that in every variable ($x_{i,j,k}$), and make $k$ copies of each constraint. So far, the problem is separable by $k$. To enforce edge-disjointness, impose one additional family of "linking" constraints across $k$: $$\sum_k x_{i,j,k} \le 1 \quad \text{for each $(i,j)$}$$