Re: [jgap-users] question with salesman problem

[Klaus M. <jg...@kl...>]

Dear Ashish,
 
to your first question (finding the best route A-B-C-D without cycle, in
opposite to TSP):
In class TravellingSalesman change the  function "distance", so that the
block
    if (A == 0 && B == CITIES - 1) {
      return 1;
    }
    if (B == 0 && A == CITIES - 1) {
      return 1;
    }
is erased.
 
You then also need to encode the distances between the cities. For that,
introduce an array[0..n-1,0..n-1] with n = Number of CITIES (see variable
CITIES in class TravellingSalesman). In the array keep the distance between
each pair of cities. Maybe it's necessary to ensure in the "distance"
function (i.e. the fitness function) that not a city is starting and ending
point at the same time.
Instead of returning abs(A-B) (see method "distance") return the distance
between city A and B, computed via the newly introduced array.
 
Maybe first try to enhance the TSP example so that it does not rely on a
cycle but computed he shortest rout without a cycle. Then introduce the
distance array.
Best
 
Klaus
 


  _____  

From: jga...@li...
[mailto:jga...@li...] On Behalf Of Ashish
Kulkarni
Sent: Wednesday, August 15, 2007 5:15 AM
To: jga...@li...
Subject: [jgap-users] question with salesman problem


Hi
I have a situation where i need to find fastest way to visit all the points 
for example
i have point A, B, C, D 
and i know that 
A-B is 2
A-C is 3
A-D is 2
B-A is 3
B-C is 2
B-D is 5
 and so on 

so i have to find the fastest way for all possible permutations
so the permutations i have is like below

A-B-C-D
A-C-B-D
B-A-C-D
B-C-A-D 
and so on

I was thinking of using salesman algorithm to solve it, 
but in salesman, the algorithm it completes a full circlet, like it will
consider A-B-C-D-A for calculation
where as i want it to calculate only A-B-C-D 
Is it possible to do so?
Also i need to find the best soluction for A-D, then A-C, A-B etc 
this is sort of Simulated Annealing algorithm issue
Any Ideas or suggestions

Ashish