Traveling salesman with a twist: must visit each node twice and must "wait" between returning to each node?

87 Views Asked by At

Please be kind if this question violates the rules as I am still working on my Stack Exchange question-asking intuition.

The motivation for this problem is the optimal deployment of automated lawnmowers.

The problem Let there be $n$ nodes (lawns) in a fully-connected, undirected graph with defined edge lengths $\textbf{E}_{ij}$ (basic TSP).

The graph exhibits triangle equality, $\textbf{E}_{ij} + \textbf{E}_{jk} \geq \textbf{E}_{ik} \forall \space i, j, k$ in the graph. Ie A->B->C must not be faster than A->C. I have a feeling this property has a name but I don't know it.

First twist You must visit each node at least twice.

Second twist After the first visit to each node $\textbf{V}_i$, you must travel (wait) $\textbf{W}_i$ units of distance (time) before returning to node $\textbf{V}_i$ for the second visit. For additional visits, this constraint does not apply: no further waiting necessary.

If a node has been visited once it is considered "open." When an open node is visited (so that node is visited twice so far in total) it is considered "closed".

Third twist You may only have $m$ "open" nodes at a time. If you traverse the graph, hitting each node only once, you must turn back and visit one of those once-visited nodes before moving on to your first touch of the $m^{th}$ node.

You can also wait at a node if you want.

The goal is to hit all nodes at least twice with the least distance/time traveled

My thoughts so far I know the TSP is not perfectly solved. I usually use the Elastic Net for the original TSP. So I'm guessing these twists have not been solved. I think the solution to the first twist would just be to repeat the one-pass TSP twice—but haven't proven it.

My answerable question is: Has this problem been formalized? Has anyone approximated it in a computationally feasible way? It seems to me that with the fame of the TSP, someone has at least thought of this before. But I am having a hard time using the right verbiage to find that work on Google scholar, arXiv, etc.