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.

In reply to Asymmetric TSP on digraph by Evolutionary Algorithm? by zli034

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.