Asymmetric Travelling Salesman Problem - Particular case

• Nov 17th 2011, 02:13 AM
gmarques
Asymmetric Travelling Salesman Problem - Particular case
Hello,

First of all I would like to inform you that I am an IT professional and not a Maths expert so some of my vocabulary may be "mathematically incorrect".

I need to solve a particular case of the Asymmetric Travelling Salesman Problem (ATSP from now on), and I definitely need help of a Math expert on this one.

Let's suppose the following graph, where the first letter is a node in the graph, the second letter is another node, and the number is the cost from travelling between these two nodes:

A B 30
A C 30
B C 1
B D 1
C B 200
D A 1

As I stated before, the graph is asymmetric, ie. having two different nodes X and Y, the cost from X to Y may be diferent from the cost of Y to X. In fact this can be observed in the example nodes B and C (B to C costs 1 and C to B costs 200).

Another interesting fact is that not all the nodes have edges that connect each other, so my first approach was to build the missing edges finding the shortest path between the nodes who's edges are missing. The graph became then:

A B 30
A C 30
A D 31
B A 2
B C 1
B D 1
C A 202
C B 200
C D 201
D A 1
D B 31
D C 31

Now I can present the first requirement of the TSP I'm trying to solve. The general TSP states that we must visit each node only once and we must finish in the node we started.

In my case, I must visit a node at least once, and not necessarilly just once. I think this is a basic assumption of the Asymmetric TSP (or not, but I am not an expert on the subject).

Continuing with the example I applied the Hungarian algorithm (or method) to find all the possible routes that visit a node at least once, and got the following routes:

A -> C -> B -> D -> A : cost 30 + 200 + 1 + 1 = 232
B -> D -> A -> C -> B : cost 1 + 1 + 30 + 200 = 232
C -> B -> D -> A -> C : cost 200 + 1 + 1 + 30 = 232
D -> A -> C -> B -> D : cost 1 + 30 + 200 + 1 = 232

Another requirement of the TSP I need to solve is that the salesman doesn't need to finish in the same node where he started.

I concluded that If I get the paths between the last nodes visits, I get the shortest paths on the TSP, where the rule "not finishing where he started" is true.

So, applying this rule on the example, this is equivalent to removing the first step. So the paths now become:

C -> B -> D -> A : cost 200 + 1 + 1 = 202
D -> A -> C -> B : cost 1 + 30 + 200 = 231
B -> D -> A -> C : cost 1 + 1 + 30 = 32
A -> C -> B -> D : cost 30 + 200 + 1 = 231

So now we can conclude that the shortest path of this ATSP with the requirements I need is B -> D -> A -> C with the cost of 32.

Now there is a final requirement, and it's here I need help of a Maths expert. The cost of a node, is only counted once, ie. if we travel from a node X to Y, the cost of that move is only valid for the first time. The second time we travel between X and Y again, the cost will be zero.

So, let's go again to the example, and focus only in the path where we started at A:

A -> C -> B -> D : cost 30 + 200 + 1 = 231

The path I need to get from starting at A should NOT be the one above, but the next one:

A -> B -> D -> A -> B -> C : cost 30 + 1 + 1 + 0 + 1 = 33

Please note that step with cost 0. That's equivalent on the second step from A to B (the first time we did it counted 30).

How can this rule be applied in the Hungarian method? Or any other branch and bound algorithm. I can't find a way to insert this cost change/morph in the algorithm logic.

It occured to me to insert a new vertex in the graph as soon as I know that I travelled from A to B, ie. I would insert a new node - lets say AA - which path is A -> AA -> B and costs from A to AA and AA to B are both zero. This way the algorithm would prefer the path A -> AA -> B with cost zero when travelling from A to B.

Even with this approach I can't find a way to insert this new vertex in the middle of the Hungarian algorithm execution.

I have also searched on the Internet to see if someone already had the same problem, but I was not lucky to find something similar.

Any help on this one is really appreciated!

Regards and thank you
GM