\[
\min
\sum_{v \in V_T} \Bigg( \prod_{i=1}^k s_v^i \Bigg)\,u_v(k)
\;+\;
\sum_{(u,v,w)} \sum_{i \in I}
\operatorname{cost}(u,v,w)\,x_{uvw}^i
\]
- \(x_{uvw}^i = 1\) if robot \(i\) uses the turn \((u,v,w)\).
- \(s_v^i = 1\) if robot \(i\) skips vertex \(v\).
- \(\prod_{i=1}^k s_v^i = 1\) iff no robot visits \(v\)
→ pay penalty \(u_v(k)\).
- Second term: pay turn cost whenever any robot uses \((u,v,w)\).
\[
x_{uvw}^i,\; s_v^i,\; Z \in \{0,1\}
\]
We also introduce binary variables \(s_i\) indicating whether
robot \(i\) is used in the solution.
\[
Z \le s_i \quad \forall i
\]
\[
Z \ge \left( \sum_{i=1}^k s_i \right) - (k - 1)
\]
- \(Z = 1\) iff all \(k\) robots are used.
- Otherwise at least one \(s_i = 0\) and the constraints force \(Z = 0\).
Let \(n_{vw}^i\) be a binary variable indicating whether
robot \(i\) traverses undirected edge \(\{v,w\}\).
\[
2 n_{vw}^i
+ \sum_{\substack{u \in N(v)\\ u \ne w}} x_{uvw}^i
=
2 n_{vw}^i
+ \sum_{u \in N(w)} x_{wuv}^i
\quad
\forall \{v,w\} \in E,\; \forall i \in I
\]
- Enforces a consistent flow: each edge is used equally
from both sides.
- Helps ensure that each robot follows a tour
(comes back to where it started).
Coverage and skipped vertices
\[
\sum_{u,w \in N(v)} x_{uvw}^i + s_v^i \;\ge\; 1
\quad \forall v \in V,\; \forall i \in I
\]
- If robot \(i\) uses some turn through \(v\), then
\(\sum_{u,w} x_{uvw}^i = 1\) (or > 0) and \(s_v^i\) can be 0.
- If robot \(i\) never visits \(v\), the sum is 0, so the
constraint forces \(s_v^i = 1\).
- Thus \(s_v^i\) is exactly the “skip” indicator for \(v\) and robot \(i\).
\[
s_r^i = 0 \quad \forall i
\]
- The root vertex \(r\) is never skipped: every robot’s tour
includes \(r\).
Informally, these constraints describe, for a given number \(k\) of robots:
- Which robots are actually used (\(s_i\)),
- Which vertices each robot covers (\(x_{uvw}^i\), \(s_v^i\)),
- A consistent tour-like flow on edges, and
- The total cost of covering the map, including turn costs and penalties for
uncovered vertices.