Need help to adapt a genetic algorithm to “solve” Traveling Salesman on Ruby

Question

I just downloaded ai4r library http://ai4r.rubyforge.org/ and i am using the genetic algorithm to get a good route from multiple places, just like this:

http://ai4r.rubyforge.org/geneticAlgorithms.html

But i need to be able to set a start city.

Any clue on how to use this on a "fixed" start city?

Answer 1

In general, not looking at the Ruby-specific implementation, you can just remove the start city, and assume that the first edge followed is from your start city to whatever the GA produces. Just make sure that first edge is included in the cost/fitness function.

Answer 2

The solution of a traveling salesmen problem is a round-trip and is therefor independent of a start-city. After you have found your solution you can take any city of the round-trip as your start-city.

EDIT: If you do not need to return to your start-city, you can select the end city, by removing the larger of the two distances that leave your start city. If you remove in your final solution the largest distance in the whole round-trip you get the overall shortest tour that is not a round-trip. This is likely what they did on the web page you linked (Dublin - Moscow looks to be the most expensive direction). However, note that the authors of that page used a wrong location for Vienna and Madrid seems to be off as well.

Another way of when you'll be needing a start-city is when you have an additional time window constraint. This constraint specifies that for each city you need to be there at a certain time, the "depot" as your start-city is called in this case has a time window that covers the whole trip. However the TSPtw is a much more complex problem and often requires advanced genetic operators. You can also model the TSPtw as a CVRPtw (Capacitated Vehicle Routing Problem with Time Windows) if you use just one vehicle. You can try our VRP implementation in HeuristicLab to solve this problem. We have a mailing list if you require further support.

Answer 3

The answer you'll get from the GA to the TSP is a cycle, that means that the first city is the on that you desire. For example, if the answer is [3 4 2 6 1 5], and I want the first city to be 2 then I can "roll" the solution to [2 6 1 5 3 4].

Although, you can reduce your problem by 1 if in your evaluation function you specify the first city. In that case you must take into account that the individuals must be modified to account this. For example, if you set the first city to #2 (problem of 6 cities) and you have an individual that is [1 2 3 4 5] (6 cities minus one). The individual to evaluate is [2 1 3 4 5 6].