Travel Salesman Problem - Add constraints

[PabloRR100]

Hi Morvan, amazing work!

It is really helping me understand GAs. I am curious how could I add the constraint of having to come back to the original position, so the travel is a round trip.

In which part should the constraint be added?

Thanks in advance!

Regards,
Pablo

[MorvanZhou]

Hi Pablo,

Is the backward path really needed? To my understanding, if it finds a forward path and it treats the path as the optimal path. Then the shortest path is found no matter it is for forward or backward.
Or you want to connect the ending point with the start point? Then this would happen in the env class. You have to modify the env code.

[PabloRR100]

Hi Morvan.

The thing is that I usually have heard the problem like a salesman that is wondering how to cover all the cities and return home with the shortest distance possible. So I am speaking about round trip not forward backward.

I also starting with env code but it doesn't help as it modified by crossover and mutations and the order is not maintained. Instead, after the translation of the ADN, I stack the frist column to the last one and compute the fitness of that insed the generations loop.

``
xs, ys = ga.translateDNA(ga.population, environment.locations)

# Make the round-trip    
initial_locations = [xs[:,0], ys[:,0]]
xs = np.hstack((xs, initial_locations[0].reshape(-1,1)))
ys = np.hstack((ys, initial_locations[1].reshape(-1,1)))

fitness, total_distance = ga.get_fitness(xs, ys)

``

Can you think of a better approach?

Thanks for the response!

Best regards,
Pablo