non-simetrical TSP problem

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

non-simetrical TSP problem

Illyes Laszlo
Hi All,

Non-simetrical TSP problem appears when the cost to go from A->B is NOT the
same that the cost to go from B->A. There appears, when you have to climb a
mountain, or you are in a sheduling problem, where the setting times differ.

Can we solve this problem with jgap??

Regards,
Laszlo

Laszlo Illyes
Teaching-assistant
Databases, Operational Research
Sapientia University
(Csikszereda) Miercurea-Ciuc
Tel:+40266317310
Fax:+40266372099
Mobil:+40740055706
E-mail: [hidden email]
web-page: http://sapientia.siculorum.ro/~illyeslaszlo/



-------------------------------------------------------
This SF.Net email is sponsored by:
Power Architecture Resource Center: Free content, downloads, discussions,
and more. http://solutions.newsforge.com/ibmarch.tmpl
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users
Reply | Threaded
Open this post in threaded view
|

RE: non-simetrical TSP problem

Klaus Meffert
Hello Laszlo,

yes you could solve this problem with JGAP. Let me explain in with help of
the provided TSP-Example:

In class SalesmanFitnessFunction the fitness of a found TSP-path is
computed, see method evaluate(Chromosome). Tthere, the distance between two
cities is computed as:
      s += salesman.distance(genes[i], genes[i + 1]);
with s being the overall distance.

In the example, the distance function is implemented in class
TravellingSalesman as:
  public double distance(Gene a_from, Gene a_to) {
    IntegerGene a = (IntegerGene) a_from;
    IntegerGene b = (IntegerGene) a_to;
    int A = a.intValue();
    int B = b.intValue();
    if (A == 0 && B == CITIES - 1) {
      return 1;
    }
    if (B == 0 && A == CITIES - 1) {
      return 1;
    }
    return Math.abs(A - B);
  }

It would be easy to implement an additional function (method) to compute the
distance between A and B arbitrarily. E.g., by looking up the asymmetrical
distance in an array holding tupels each containing a starting point (A) and
an ending point (B) resp. starting and ending city. In the array the
(pseudo-)distance between city 1 and 2 could be given as 55.7km and between
2 and 1 as 79.8km. Pseudo-distance because my approach would be calculating
the real costs going from A to B by the normalized distance. A normalized
distance is a flat way from A to B. Thus, the pseudo-distance climbing up a
hill from A to B would be higher than the flat way, depending on the raising
of the hill.

Best

Klaus

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of
> Illyes Laszlo
> Sent: Monday, October 03, 2005 12:07 PM
> To: [hidden email]
> Subject: [jgap-users] non-simetrical TSP problem
>
> Hi All,
>
> Non-simetrical TSP problem appears when the cost to go from
> A->B is NOT the same that the cost to go from B->A. There
> appears, when you have to climb a mountain, or you are in a
> sheduling problem, where the setting times differ.
>
> Can we solve this problem with jgap??
>
> Regards,
> Laszlo
>
> Laszlo Illyes
> Teaching-assistant
> Databases, Operational Research
> Sapientia University
> (Csikszereda) Miercurea-Ciuc
> Tel:+40266317310
> Fax:+40266372099
> Mobil:+40740055706
> E-mail: [hidden email]
> web-page: http://sapientia.siculorum.ro/~illyeslaszlo/
>
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by:
> Power Architecture Resource Center: Free content, downloads,
> discussions, and more. http://solutions.newsforge.com/ibmarch.tmpl
> _______________________________________________
> jgap-users mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/jgap-users




-------------------------------------------------------
This SF.Net email is sponsored by:
Power Architecture Resource Center: Free content, downloads, discussions,
and more. http://solutions.newsforge.com/ibmarch.tmpl
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users