Asymmetric TSP on digraph by Evolutionary Algorithm?

[zli034]

March 8th modification note: Just found out this problem is called Asymmetric TSP. I'm going to do some reading on this topic.

Hi Guys:

To have a place to talk what I like make this wonderful world much more wonderful. I appreciate everyone's opinion on calibrating this problem.

Traveling Salesman Problem(TSP) have been well studied by evolutionary algorithm, such as inver-over operator can be really good for TSP on a simple graph representation of set of cities and routes. I want to know if there are studies also about TSP on a digraph, that is directed graph.

If the distance between 2 city can be different according to the direction which people travel. Say between cities A and B, if the people travel from A to B, that can be 2 units of distance; if the people travel from B to A, then the distance becomes 1 unit of distance.

The adjacency matrix representation of distance on the digraph is also different from the simple graph cities. The adjacency matrix of simple graph of cities is only a half of the square matrix; because the entry of distances below the diagonal are just the repeats of distance entries which above the diagonal. So that in the digraph adjacency matrix representation, it is complete square matrix. There are both entries below and above the diagonal, because they represents distances travel between 2 cities in different direction. And the diagonal fills with 0, that is 0 distance.

In my opinion, the inver-over shouldn't be a good approach to the digraph TSP problem. When a permutation of cities is inverted, it fitness then be changed depending on the directions. This prevents potential fit permutation to be retained in population, if they are placed into wrong direction.

I'm not going to show you guys the matrix I have, I like to work on it by myself, otherwise it becomes other people's work. Thanks guys, all the best.

[sundialsvc4]

blink... blink...   (Anybody know how to reply to this one?)

“Well, good luck with it. . .” When you've got your PhD, invite us all to your graduation after-party.

[zli034]

This is definitely not worth a PhD.

I'm reading on Solving Symmetric and Asymmetrics TSPs by Ant Colonies, Gambardella and Dorigo (ICEC 1996). I have to think up some sort data structure before coding on their algorithm.

My lecturer said he was going to talk about Ant Colonies in those master teachings. I have had no enough attitute to stay in school. Now I have to figure it out all alone.

[gregor42]

Just found out this problem is called Asymmetric TSP. I'm going to do some reading on this topic.

A quick google search pointed me to: Inver-over Operator for the TSP which seems to be exactly what you're talking about.

It sounds to me like you're trying to write map searching software and you've noticed that the Travelling Salesman Problem when applied in the real world also has to account for one-way roads. You are looking to solve this by representing the problem space as a Directed Graph?

Rather than mutating the data structure to have different distances in either direction, why not redefine the linking structure to support one-way connections? Wouldn't this allow the current path-searching/choosing routines to continue to be used without modification?