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

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!

• It would be better you make a start, i.e. defining variables. Commented Apr 25, 2021 at 14:50
• @callculus This is a good note, I will include one of formulations of the TSP as a reference point. Commented Apr 25, 2021 at 14:52
• @RicardoCavalcanti I am not exactly sure; the problem statement as I have it does not make mention of this. I was also thinking about this, and I think it'd be reasonable to assume that the city graph contains enough edges to accommodate the salespeople. This would have to be formulated as a constraint. I somehow need to insert a constraint that says that each salesperson can only use one edge. We are not looking at feasibility here. Your example would be infeasible for this problem, so here we are trying to formulate a solution assuming feasibility. Commented Apr 25, 2021 at 15:12

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)}$$
• Is the interpretation of this constraint that at most one salesperson can use a particular edge? And we use $\leq$ since it might be the case that no salesperson uses that particular edge? Additionally, do you think you can assist with adapting the general TSP constraints to incorporate the fact that there $m$ traveling salespeople. Commented Apr 25, 2021 at 17:37
• Yes, that is the correct interpretation. For the adaptation, just add a $k$ index everywhere in the DFJ or MTZ formulation, where $k\in\{1,\dots,m\}$. Commented Apr 25, 2021 at 17:43
• If you use MTZ, also add a $k$ index to the $u_i$ variables, yielding $u_{i,k}$. Commented Apr 25, 2021 at 18:29