5
$\begingroup$

I'm learning the Ant Colony Optimization Algorithm and I would like to apply it to a variation of the TSP problem (find the path that start from a node, crosses all nodes and finish in the initial node) where you can cross a node or edge more than once. Actually, my problem wouldn't have solution for the TSP because some nodes only have one edge.

Basically, I see two problems:

  1. In most of examples I've seen, nodes are represented by (X,Y) positions and they suppose that is a complete graph, so from every node you can go to every node, which involves that an ant will always have a edge to go to a node that hasn't been visited yet. But in this problem, it may happen that an ant arrives to a node where al the adjacents nodes have already been visited, so, how would it decide the way to go? The worst case would be that there is only one node left to visit and it is the one farthest from the current node.

  2. What repeating edges involves to pheromones. If and edge is crossed several times in the tour, it could or could not have much more pheromones, depending on the implementation, and I'm not sure if it could have a negative impact.

This is a very simple example, where red edges mean that the cost is 1 and blue that is very big, for example 20. As you can see for the best path you need to repeat edges.

enter image description here

Regards.

EDIT2:

I want to add that my particular problem has around 1000 nodes and 2000 edges.

I have some new ideas. First of all it looks like I must have a way to find the distance and the path between cities, so that each ant can decide which is the next city to go. The main option is the Johnson's Algorithm which offers good performance for this sparse graph.

To store all the possible paths I could use a triangular matrix where each element is a vector of nodes. If we suppose that the mean of the paths is 50 nodes (represented with 2 bytes integers) the memory needed would be around (N: nº nodes) N*N/2*50*2 bytes so more or less 50Mb.

The other option is to have the same structure but in each element of the matrix I would have only one node, and to find the path I would have to access the position of that node and so on until I find the one I'm looking for. Because if the shortest path from node A to node C crosses B, the path is the shortest path from A to B joined with the one from B to C. This option need N*N/2*2 bytes more or less 1Mb. But it will probably have worse performance because it needs much more access to memory and I doesn't take advantage of space locality so it will have many cache misses.

About ACO, maybe I can use an algorithm like Minimun Spanning Tree or something like that to put some extra initial pheromones, but I'm not sure if that will be positive.

$\endgroup$
  • 1
    $\begingroup$ I have a gut feeling that there might be a fast algorithm based on computing minimum spanning tree first then improve the result from there(maybe deterministic, maybe even by ACO). But I don't have anything concrete. $\endgroup$ – Billiska Feb 12 '17 at 11:30
  • $\begingroup$ Thank you for the suggestion Billiska, I'm sorry that you do not have a clearer idea (improve the spanning tree is not an easy task though). If you think of anything more please tell me. Thanks. $\endgroup$ – Fylux Feb 13 '17 at 15:34
  • $\begingroup$ What is the size of your network in terms of number of vertices and edges? $\endgroup$ – orezvani Feb 16 '17 at 0:26
  • $\begingroup$ The size of the network for this case is 1000 nodes and 2000 edges approximately. $\endgroup$ – Fylux Feb 16 '17 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.