<p>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.</p>

<p>The paper <a href="http://www.sciencedirect.com/science?_ob=MImg&amp;_imagekey=B7576-4W38RJN-2-13&amp;_cdi=12890&amp;_user=965532&amp;_pii=S1570870509000389&amp;_origin=search&amp;_coverDate=01%2F31%2F2010&amp;_sk=999919998&amp;view=c&amp;wchp=dGLbVzb-zSkzS&amp;md5=ffee75b0f9e291db16023d89b304e378&amp;ie=/sdarticle.pdf" rel="nofollow">An ant colony optimization routing based on robustness for ad hoc networks with GPSs </a> 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 <em>something</em> 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.</p>

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

CC BY-SA 2.5
2011-01-26T07:38:13.507Z
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
Fabian Schuh
CC BY-SA 2.5
2011-01-25T14:39:50.697Z
2011-01-25T14:39:50.697Z
Aaron Sterling
<p>What are you specifying with benchmark? I too, is working on TSP problem using ACO. We can collaborate if you wish for.  </p>

CC BY-SA 3.0
2017-09-14T09:20:11.360Z
2017-09-14T09:20:11.360Z
Tushar
<p>Are there any publications focusing on solving TSP with ant colony optimization that consider small changes in the graph's nodes or vertices?</p>

<p>So what I have is:</p>

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

<p>and what I want is:</p>

<ul>
<li>An ant algorithm to solve the new TSP (on a subset-basis) using the original solution</li>
<li>And a benchmark</li>
</ul>

<p>Thanks for you help so far.</p>

CC BY-SA 2.5
2011-01-25T09:42:42.097Z
Googling "ant tsp", without the quotes, produces loads of useful information.
Dave Clarke
CC BY-SA 2.5
2011-01-25T10:58:35.417Z
This is not tcs
Marcos Villagra
CC BY-SA 2.5
2011-01-25T11:43:18.623Z
@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?
Fabian Schuh
CC BY-SA 2.5
2011-01-25T11:56:55.990Z
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.
Dave Clarke
CC BY-SA 2.5
2011-01-25T12:09:31.737Z
That's exactly what I need, with the constraint, that after changing the graph, I do not want to run the ACO on the full graph again, but on a subset (including the change).
Fabian Schuh
CC BY-SA 2.5
2011-01-25T12:14:35.497Z
TCS stands for Theoretical Computer Science.
Vinicius dos Santos
CC BY-SA 2.5
2011-01-25T12:42:03.167Z
It's graph-theory isnt it? So you suggest I ask at math-exchange?
Fabian Schuh
CC BY-SA 2.5
2011-01-25T13:06:55.080Z
Maybe here: http://metaoptimize.com/qa/?
Nils
CC BY-SA 2.5
2011-01-25T14:45:05.683Z
To me this is definitely TCS.
Dave Clarke
<ds.algorithms><graph-theory><tsp><heuristics>
Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices
Fabian Schuh
# Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices

(Asked by: username_0 on 2011-01-25)

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.

**Tags:** ds.algorithms, graph-theory, tsp, heuristics

> **Comments:**
> **username_1**: Googling "ant tsp", without the quotes, produces loads of useful information.  
> **username_2**: This is not tcs  
> **username_0**: @username_1: 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. @username_2: What's TCS?  
> **username_1**: 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.  
> **username_0**: That's exactly what I need, with the constraint, that after changing the graph, I do not want to run the ACO on the full graph again, but on a subset (including the change).  
> **username_3**: TCS stands for Theoretical Computer Science.  
> **username_0**: It's graph-theory isnt it? So you suggest I ask at math-exchange?  
> **username_4**: Maybe here: http://metaoptimize.com/qa/?  
> **username_1**: To me this is definitely TCS.  

---

## 2 answers

### Answer by username_5 on 2011-01-25. Score: 4 | Accepted answer

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](http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B7576-4W38RJN-2-13&_cdi=12890&_user=965532&_pii=S1570870509000389&_origin=search&_coverDate=01%2F31%2F2010&_sk=999919998&view=c&wchp=dGLbVzb-zSkzS&md5=ffee75b0f9e291db16023d89b304e378&ie=/sdarticle.pdf)  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.

> **Comments:**
> **username_0**: 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  

---

### Answer by username_6 on 2017-09-14. Score: -1

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


---

