2-opt

From Wikipedia, the free encyclopedia

In optimization, 2-opt is a simple local search algorithm first proposed by Croes in 1958 for solving the traveling salesman problem. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not.

 O   O -             O - O -
 | X         ==>     |
 O   O -             O - O -

[edit] References

  • G. A. CROES (1958). A method for solving traveling salesman problems. Operations Res. 6 (1958) , pp., 791-812.. 

[edit] See also

[edit] External links

This mathematical analysis-related article is a stub. You can help Wikipedia by expanding it.