Lably
Skip to content

2-opt

  • 15 min read
  • 2 chapters

Related on Lably

Through Mathematical optimization

Lab · Class 12Linear Programming

Pseudocode

Visually, one swap looks like:

- A B - - A - B - × ==> - C D - - C - D -

In pseudocode, the mechanism by which the 2-opt swap manipulates a given route is as follows. Here v1 and v2 are the first vertices of the edges that are to be swapped when traversing through the route:

<b id="mwFw">procedure</b> 2optSwap(route, v1, v2) { 1. take route[start] to route[v1] and add them in order to new_route 2. take route[v1+1] to route[v2] and add them in reverse order to new_route 3. take route[v2+1] to route[start] and add them in order to new_route <b id="mwGA">return</b> new_route; }

Here is an example of the above with arbitrary input:

  • Example route: A → B → E → D → C → F → G → H → A
  • Example parameters: v1=1, v2=4 (assuming starting index is 0)
  • Contents of new_route by step:
    1. (A → B)
    2. A → B → (C → D → E)
    3. A → B → C → D → E → (F → G → H → A)

This is the complete 2-opt swap making use of the above mechanism:

<b id="mwJw">repeat until</b> no improvement is made { best_distance = calculateTotalDistance(existing_route) start_again: <b id="mwKA">for</b> (i = 0; i <= number of nodes eligible to be swapped - 1; i++) { <b id="mwKQ">for</b> (j = i + 1; j <= number of nodes eligible to be swapped; j++) { new_route = 2optSwap(existing_route, i, j) new_distance = calculateTotalDistance(new_route) <b id="mwKg">if</b> (new_distance < best_distance) { existing_route = new_route best_distance = new_distance goto start_again } } } }

The particular nodes or depots that are at the start and at the end of the path should be removed from the search as an eligible candidates for swapping, as reversing the order would cause an invalid path.

For example, with depot at A:

A → B → C → D → A

Swapping using node[0] and node[2] would yield

C → B → A → D → A

which is not valid (does not leave from A, the depot).

Sign in to keep reading

One more chapter is free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard