14
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ Can you explain your problem more, may be by giving a small example? Let’s say 3 vehicles and 5 vertex. How the result of your model should be? $\endgroup$ – Oguz Toragay Jul 30 '19 at 15:13
  • $\begingroup$ The output should be a path for each vehicle such that each vertex is visited by at least two different agents. Edit: For instance, an example path may be for a 5 vertex example: Agent 1: $\{1,3,2,4\}$ Agent 2: $\{1,2,4,5\}$ Agent 3: $\{3,5\}$ $\endgroup$ – kemalduldul Jul 30 '19 at 15:21
8
$\begingroup$

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:


[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.

| improve this answer | |
$\endgroup$
9
$\begingroup$

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.
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ That's a great idea to solve the problem. The only point which needs to be considered as well is, by duplicating the nodes, the size of the problem grows and the curse of dimensionality may affect the performance of approximating approaches to solve the problem. $\endgroup$ – Oguz Toragay Jul 30 '19 at 17:57
  • $\begingroup$ @OguzToragay You are correct. Even worse, the additional symmetry will also decrease performance. On hindsight, duplicating the nodes is not necessary, and I will edit my answer accordingly. $\endgroup$ – Kevin Dalmeijer Jul 30 '19 at 18:13
  • $\begingroup$ Thank you for the answer. For this formulation, is it possible to use heuristics for the multiple vehicle problem, for example the one in Arkin et al. that has a 4-approximation guarantee?. Thank you. $\endgroup$ – kemalduldul Jul 30 '19 at 20:20
  • $\begingroup$ @kemalduldul I am not familiar with the paper by Arkin et al. There is large amount of literature on heuristics for vehicle routing problems. Chapter 4 in Vehicle Routing: Problems, Methods, and Applications may be a good place to start. $\endgroup$ – Kevin Dalmeijer Jul 30 '19 at 20:32
5
$\begingroup$

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$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.