reset password
Author Message
rabbott
Posts: 1649
Posted 17:18 Apr 28, 2020 |

This slide illustrates how 2-OPT works.

The trouble I kept running into was attempting to explain 2-OPT by keeping one of the orange links in place and changing something else. In fact, both orange links are deleted and replaced by the green links.

Does this help?

sdo8
Posts: 54
Posted 16:57 Apr 29, 2020 |

I think I understand now.

In this example, it looks like we select 2 nodes in the tour:

We have (A, B, C, D, E, F, G, H, I, J).
The nodes we select are C and H.

(A, B, C, D, E, F, G, H, I, J).

Since this is a route, we can say that C is connected to D and that H is connected to I. (Basically the next node)

So now we know what our selected links are:

(A, B, C, D, E, F, G, H, I, J).

From this, we can deduce the internal sequence:

(A, B, C, D, E, F, G, H, I, J).

If we reverse this internal sequence, we get:

(A, B, C, H, G, F, E, D, I, J), which is better (we eliminated the cross).
 

This whole time I was thinking about selecting two links from the world:
Link1 = Link with agent_1 and agent_2

Link2 = Link with agent_1 and agent_2

Then swapping Link1's agent_2 with Link2's agent_2

 

In this case, I'm assuming we reverse the internal sequence, keep it if its better, and then let the engine generate the links from the tour (rather than editing links directly).

 

rabbott
Posts: 1649
Posted 22:00 May 01, 2020 |

Right! It also works if we reverse the other half of the tour. That is, reverse the part from C to I. 

     C D A J I => I J A B C

A B C D E F G H I J   =>   A J I D E F G H C B

Last edited by rabbott at 22:04 May 01, 2020.