RE: [jgap-user] TSP problem attached file

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
Report Content as Inappropriate

RE: [jgap-user] TSP problem attached file

Klaus Meffert
Hello Laszlo,

It is no problem to model a TSP having no closed route (beginning and ending
in the same city) with JGAP.

Your requirement about the 2-part chromosome results, as I understood it,
from your need to evolve two properties for a single city. Namely the order
in which the city is visited and the day (resulting from a time window) in
which the visit takes place. Two JGAP-solutions came to my mind:
1) Use a CompositeGene for each city. It contains two genes, one for the
first property and one for the second.
2) Use a single Gene for each city with n+1 Genes in a Chromosome, n=number
of cities the last Gene in the Chromosome represents a double number betwen
0 and 1 and is meant as a factor (or percentage) for the time window. I.e.,
the time window may be [a,b] and the factor may be f. Then, the evolved day
of visit, d, is d = a+round((b-a)*f). With that a unification of non
unifyable time windows (because they possibly spawn over a different number
of days for each city) is reached.

A further suggestion may be to compress a list of time windows cities as
Given cities A, B, C, D and E.
C has a time window that forces the visitor to visit C directly after B and
directly before D in any way.
Then, just evolve the route for A, B and D. In the resulting list, insert C
between B and D.

What do you think?



> -----Original Message-----
> From: Illyes Laszlo
> Sent: Monday, October 03, 2005 11:57 AM
> To: Klaus Meffert
> Dear Klaus,
> I am in the middle of the TSP.

> My problem, like you see, if you read the paper [was attached] are:
> MTSP (Multiple Traveller Sailsperson Problem) with 2 part chromosome.
> - if there is a defined TSP with no return to the basis. To
> go from A to B and visit the others between.
> - if I can define a 2 part chromosome, the first one with the
> normal recombination, the second in other form and evolve
> them together??
> I will give you a hand to make the crossover operators for
> all recombination problems.
> Regards
> Laszlo
> Laszlo Illyes
> Teaching-assistant
> Databases, Operational Research
> Sapientia University
> (Csikszereda) Miercurea-Ciuc

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]