CODEWITHSUNDEEP
pythonalgorithmgraphtraveling-salesman
Peter
Peter

Reputation: 13505

Travelling Salesman with Momentum?

I have a task that is very similar to travelling salesman problem (TSP), but I'm not sure if it's easily mappable to TSP. I'm wondering if this variant has a name and known solvers already, or can be just reduced to TSP somehow.

I have a graph where nodes are (x, y) locations, and edges are smooth, continuous paths connecting those locations. As in normal TSP, the task is to visit every node while covering as little distance as possible.

The difference is that nodes have a particular orientation - and the paths linking them are constrained to pass through the node at this same orientation. You cannot just do a sudden U-turn at a node - you have to keep going the same direction as when you entered - so there is this additional bit of "state" or "momentum" associated with your direction of travel. See below picture for a visualization.

Is this mappable to generic TSP in some simple way that I'm not thinking of right now? Or if not, does this variant have a name of its own?

Edit: It helps to think of the problem as trying to route a train that can never stop through all the cities as efficiently as possible. If this problem has no name, it could be called Travelling Post Office.

enter image description here

In the above, a solution (possibly not the best) starting/ending at node 0 is 0->1->2->3->0->1->7->6->5->0->1->2->4->6->7->1->0.

Edit - Actually, the above solution does not work if we require that the end orientation matches the start orientation.

Upvotes: 0

Views: 190

Answers (1)

zen-dev
zen-dev

Reputation: 1

TLDR: Here's a link to the code that solves it (or at least the example posted above).

Explaination:

Let's take funky-graph G with n nodes and tri-edges (i, j ,k).

We will represent a set of edges as a set of integers e_{ijk} which denote how many times tri-edge (i, j, k) has been traversed. For example simple traversal of 3-graph is (0, 1, 2), (1, 2, 0), (2, 0, 1). Here e_{012} = e_{120} = e_{201} = 1 and e_{ijk} = 0 for all other i, j, k triplets.

Now we will cast the problem of finding a traversal of a funky graph as a mixed linear programming problem.

Let's consider edge (i, j, k). We define transition matrix T_{ijk} associated with this edge. It will be n x n matrix that is all zeros, apart from 2 places. T_{ijk}[i, j] = -1 and T_{ijk}[j, k] = -1.

So for example

           [0 0 0]
T_{120} =  [0 0 -1]
           [1 0 0]

(Note that we count numbers from 0, like computer scientists).

Now if for a set of edges we have

    \sum_{ijk} e_{ijk} T_{ijk} = 0

it means that this set of edges represents a cycle.

We can now flatten / reshape these matrices $T_{ijk}$ into vectors. For example $T_{120}$ becomes

t_{120} = [0 0 0 0 0 -1 1 0 0]

And in this way our constraint from above becomes a matrix constraint

Te = 0

where T is a matrix with n^2 rows and n^3 columns. Each column has either exactly one 1 at jn + jth place and exactly one -1 at in + kth place if ijk is smooth or is all zeros if tri-edge ijk is not smooth and therefore not traversable.

The second constraint that we want is that visited at least once. (TODO for tomorrow me to fill in details here).

And that's it! We just plug it into MIP (Mixed Integer Program) solver. Like this one https://developers.google.com/optimization/mip

Upvotes: 0

Related Questions