2
$\begingroup$

Are there any publications focusing on solving TSP with ant colony optimization that consider small changes in the graph's nodes or vertices?

So what I have is:

  • a traveling salesman problem (TSP)
  • and a single solution for the TSP
  • a slight change in the graph afterwards (extra/removed node for example)

and what I want is:

  • An ant algorithm to solve the new TSP (on a subset-basis) using the original solution
  • And a benchmark

Thanks for you help so far.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Googling "ant tsp", without the quotes, produces loads of useful information. $\endgroup$
    – Dave Clarke
    Commented Jan 25, 2011 at 9:42
  • $\begingroup$ This is not tcs $\endgroup$
    – Marcos Villagra
    Commented Jan 25, 2011 at 10:58
  • $\begingroup$ @Dave Clarke: Can the usual TSP algorithms handle changing graphs. I like to no run the full algorithm again. Just a subset to add an extra node for example. @Marcos Villagra: What's TCS? $\endgroup$
    – Fabian Schuh
    Commented Jan 25, 2011 at 11:43
  • $\begingroup$ I can imagine that such algorithm would automatically adapt to such changes, just as real ant colonies adapt to a brick being placed in their path. $\endgroup$
    – Dave Clarke
    Commented Jan 25, 2011 at 11:56
  • 5
    $\begingroup$ To me this is definitely TCS. $\endgroup$
    – Dave Clarke
    Commented Jan 25, 2011 at 14:45

2 Answers 2

Reset to default
4
$\begingroup$

Yes, there are several papers on this topic, and related ones, in the context of ant colony optimization algorithms for routing on ad hoc or mobile area networks (MANETs). In a MANET, the nodes in the network graph are mobile, and if they move too far away from their neighbors, they fall out of range, hence the communication link is broken (i.e., the edge disappears from the network graph). The routing problem essentially is: how do I keep all the vertices connected, and maintain efficient pathways between nodes, when links can disappear and reappear? Of course, if a node moves out of range from all other nodes, it is the same as if the node were deleted from the network graph.

The paper An ant colony optimization routing based on robustness for ad hoc networks with GPSs by Kadono et al. contains a "related work" section you will probably find interesting. In this paper I've linked, there is an assumption of the availability of some GPS information, which probably does not apply to you; I chose it mainly for its discussion of other papers. However, all these approaches assume something about how nodes can be deleted (or suddenly appear), in order to construct an efficient algorithm. You'll have to decide what formal assumptions hold for the problem you are trying to solve.

Search phrases like "ant colony optimization MANET" or "ant colony optimization self-stabilization" may turn up other papers of interest to you.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Unfortunatelly my univerisity subscription does not include the linked paper. Fortunatelly I could find alot of papers in ieee exporer using your seach proposal. Thanks $\endgroup$
    – Fabian Schuh
    Commented Jan 26, 2011 at 7:38
-1
$\begingroup$

What are you specifying with benchmark? I too, is working on TSP problem using ACO. We can collaborate if you wish for.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.