3-opt
In optimization, 3-opt is a simple local search algorithm for solving the travelling salesman problem and related network optimization problems.
3-opt analysis involves deleting 3 connections (or edges) in a network (or tour), reconnecting the network in all other possible ways, and then evaluating each reconnection method to find the optimum one. This process is then repeated for a different set of 3 connections.
See also
References
- F. BOCK (1965). An algorithm for solving traveling-salesman and related network optimization problems. unpublished manuscript associated with talk presented at the 14th ORSA National Meeting.
- S. LIN (1965). Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44, 2245-2269. Available as PDF
- S. LIN AND B. W. KERNIGHAN (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Res. 21, 498-516. Available as PDF
- Local Search Heuristics. (n.d.) Retrieved June 16, 2008, from http://www.tmsk.uitm.edu.my/~naimah/csc751/slides/LS.pdf
This article is issued from Wikipedia - version of the 10/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.