| 词条 | 2-opt |
| 释义 |
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. - A B - - A - B - X ==> - C D - - C - D - A complete 2-opt local search will compare every possible valid combination of the swapping mechanism. This technique can be applied to the travelling salesman problem as well as many related problems. These include the vehicle routing problem (VRP) as well as the capacitated VRP, which require minor modification of the algorithm. This is the mechanism by which the 2-opt swap manipulates a given route: 2optSwap(route, i, k) { 1. take route[0] to route[i-1] and add them in order to new_route 2. take route[i] to route[k] and add them in reverse order to new_route 3. take route[k+1] to end and add them in order to new_route return new_route; }Here is an example of the above with arbitrary input: example route: A ==> B ==> C ==> D ==> E ==> F ==> G ==> H ==> A example i = 4, example k = 7 (starting index 1) new_route: 1. (A ==> B ==> C) 2. A ==> B ==> C ==> (G ==> F ==> E ==> D) 3. A ==> B ==> C ==> G ==> F ==> E ==> D (==> H ==> A) This is the complete 2-opt swap making use of the above mechanism: repeat until no improvement is made { start_again: best_distance = calculateTotalDistance(existing_route) for (i = 1; i < number of nodes eligible to be swapped - 1; i++) { for (k = i + 1; k < number of nodes eligible to be swapped; k++) { new_route = 2optSwap(existing_route, i, k) new_distance = calculateTotalDistance(new_route) if (new_distance < best_distance) { existing_route = new_route best_distance = new_distance goto start_again } } } }Note: If you start/end at a particular node or depot, then you must remove this from the search as an eligible candidate for swapping, as reversing the order will cause an invalid path. For example, with depot at A: Swapping using node[0] and node[2] would yield which is not valid (does not leave from A, the depot).
References
See also
External links
2 : Heuristic algorithms|Travelling salesman problem |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。