A variant of the Multiple Traveling Salesman Problem

Question

I am trying to find a reference (or a reformulation) of a variant of the multiple Traveling Salesman Problem, where multiple agents need to visit each vertex in a graph with minimal cost.

Most of the literature that I found requires that only one agent needs to visit each vertex, but I am looking to generalize this to requiring multiple and different agents visiting some of the vertices. I have been trying to form this problem into the multiple Traveling Salesman problem, (and eventually use an approximation algorithm) but I have not been successful in reformulating the problem.

Some of the references that I looked into were

• Arkin, Esther M., Refael Hassin, and Asaf Levin. "Approximations for minimum and min-max vehicle routing problems." Journal of Algorithms 59.1 (2006): 1-18, and

• Bektas, Tolga. "The multiple traveling salesman problem: an overview of formulations and solution procedures." Omega 34.3 (2006): 209-219.

But, as I mentioned before, these papers require that each vertex is visited only once, and I want to require multiple agents to visit some of the vertices.

Answer 1

Y. Kaempfer and L. Wolf, in their recent paper [1] applied ML techniques to solve the Multiple Traveling Salesmen Problem (mTSP). They provide a mathematical model for problem formulation which can be modified to cover what you need in the solution to your problem.

You can replace the constraint (2d) which is:

$$\forall 2\leq j \leq n: \sum\limits_{i=1}^{n}\sum\limits_{k=1}^m \delta_{i,j,k}=1 \ \ (2d)$$

with:

$$\forall 2\leq j \leq n: \sum\limits_{i=1}^{n}\sum\limits_{k=1}^m \delta_{i,j,k} \geq 2 \ \ (2d')$$

depends on the number of agents that need to visit each vertex.

The rest of the constraints in their model can be kept the same. In addition to the mentioned paper the following resources could also be helpful:

• Multiple Traveling Salesman Problem (mTSP) in Neos guide

• A Multi-Agent Approach for Solving Traveling Salesman Problem [2], in which you may find some hints regarding the approximation approach to solve the problem.

• There is also a similar question in Stack Overflow: Travelling Salesman with multiple salesmen?

---

[1] Kaempfer, Yoav, and Lior Wolf. "Learning the multiple traveling salesmen problem with permutation invariant pooling networks." arXiv preprint arXiv:1803.09621 (2018).

[2] Tiejun, Zhou, Tan Yihong, and Xing Lining. "A multi-agent approach for solving traveling salesman problem." Wuhan University Journal of Natural Sciences 11.5 (2006): 1104-1108.

Answer 2

You can model your problem by defining separate variables for each traveling salesman. Below I will use 'vehicle' instead of 'traveling salesman', which is more common in this setting.

Defining separate variables

Let $n$ be the number of customers and let $m \le n$ be the number of vehicles. For each vehicle $k = 1, \dots, m$, define the variables $$x_{ij}^k := \begin{cases} 1 & \textrm{ if vehicle $k$ travels from $i$ to $j$} \\ 0 & \textrm{ else.} \end{cases}$$

Constraints

• For each vehicle $k$, add constraints to make sure that the variables $x_{ij}^k$ describe a valid route. It is important that customers cannot be visited twice by the same vehicle. If you don't know the number of vehicles in advance, choose $m=n$ and make sure that empty routes are allowed (all $x_{ij}^k = 0$ for all $i$ and $j$ for a given $k$).
• Add constraints that say that every node is visited by the appropriate number of vehicles. Note that the earlier constraints enforce that each visit is by a unique vehicle.
• You can enforce that node $i$ can only be visited by certain vehicles by setting $x_{pi}^k = 0$ for all $p \in V$ if $k$ and $i$ are incompatible.

Answer 3

I'd like to add a few more ideas that could be important for solving this problem. I agree that a multiple-vehicle integer programming formulation may be a reasonable approach. In an arc-based model, decision variables $x^k_{ij}$ specify that vehicle/salesperson $k$ travels between $i$ and $j$ on its subtour. In such a formulation, you should create multiple copies for each vertex that needs to be visited multiple times, not create edges between vertex copies, and add a side constraint that ensures that vehicle/salesperson $k$ visits at most one copy of any vertex. Note that making copies introduces some symmetries that can create computational problems. A modeling idea to avoid some difficulties that might arise due to such symmetries is to allow vehicle $k$ to only visit copies $\{1,2,...,k\}$ of any vertex by not including certain edges/variables.

It may be important to include some constraints on the tours generated. For example, you could constrain the number of visits made by each vehicle: $$\sum_{ij} x^k_{ij} \leq c$$ or constrain the total duration of each vehicle tour: $$\sum_{ij} t_{ij} x^k_{ij} \leq d \quad .$$ If you want to be sure that vehicles serve tours with roughly the same number of visits or same total duration, you could use a minimax objective where you minimize $z$ and constrain $$z \geq \sum_{ij} x^k_{ij} \quad \text{or} \quad z \geq \sum_{ij} t_{ij} x^k_{ij} \quad \forall \; k \quad .$$

One minor problem with such an arc-based formulation is that subtour elimination constraints will be required for each vehicle/salesperson. Since no individual vehicle needs to serve all vertices, it is important to use appropriate SEC constraints. One option is the Miller-Tucker-Zemlin approach that introduces ordering decision variables (in this case, for each vehicle). If all the vehicles have a common base/depot vertex 0, then the typical SEC constraints that prevent cycles that do not include vertex 0 will work with minor modifications. Since these types of constraints are added dynamically, symmetry requires that you add them for each vehicle when they are required for any vehicle and that all copies of vertex $i$ should be included in the subtour set $S$.