2 opciones

En optimización , 2-opt es un algoritmo de búsqueda local simple para resolver el problema del viajante . El algoritmo 2-opt fue propuesto por primera vez por Croes en 1958, ^{[ 1 ]} aunque Flood ya había sugerido el movimiento básico . ^{[ 2 ]} La idea principal es tomar una ruta que se cruza consigo misma y reordenarla para que no lo haga. Una búsqueda local 2-opt completa comparará cada combinación válida posible del mecanismo de intercambio. Esta técnica se puede aplicar al problema del viajante, así como a muchos problemas relacionados. Estos incluyen el problema de enrutamiento de vehículos (VRP) y el VRP con capacidad limitada, que requieren una modificación menor del algoritmo.

Visualmente, un intercambio se ve así:

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

En pseudocódigo , el mecanismo mediante el cual el intercambio 2-opt manipula una ruta dada es el siguiente. Aquí, v1 y v2 son los primeros vértices de las aristas que se intercambiarán al recorrer la ruta:

procedimiento 2optSwap(ruta, v1, v2) { 1. Toma route[start] a route[v1] y agrégalas en orden a new_route 2. Toma route[v1+1] a route[v2] y agrégalas en orden inverso a new_route. 3. Toma route[v2+1] a route[start] y agrégalas en orden a new_route devolver nueva_ruta; }

Aquí hay un ejemplo de lo anterior con una entrada arbitraria:

• Ejemplo de ruta: A → B → E → D → C → F → G → H → A
• Parámetros de ejemplo: v1=1, v2=4 (suponiendo que el índice inicial es 0)
• Contenido de new_route paso a paso:
  1. (A → B)
  2. A → B → (C → D → E)
  3. A → B → C → D → E → (F → G → H → A)

Este es el intercambio 2-opt completo que utiliza el mecanismo anterior:

repetir hasta que no se observe ninguna mejora { mejor_distancia = calcularDistanciaTotal(ruta_existente) volver_a_comenzar: para (i = 0; i <= número de nodos elegibles para ser intercambiados - 1; i++) { para (j = i + 1; j <= número de nodos elegibles para ser intercambiados; j++) { nueva_ruta = 2optSwap(ruta_existente, i, j) nueva_distancia = calcularDistanciaTotal(nueva_ruta) si (nueva_distancia < mejor_distancia) { ruta_existente = nueva_ruta mejor_distancia = nueva_distancia ir a start_again } } } }

Los nodos o depósitos específicos que se encuentran al principio y al final de la ruta deben eliminarse de la búsqueda como candidatos elegibles para el intercambio, ya que invertir el orden provocaría una ruta no válida.

Por ejemplo, con depósito en A:

 A → B → C → D → A

El intercambio utilizando node[0] y node[2] produciría

 C → B → A → D → A

lo cual no es válido (no sale de A, el depósito).

Construir la nueva ruta y calcular la distancia de la nueva ruta puede ser una operación muy costosa, generalmente${\displaystyle O(n)}$donde n es el número de vértices en la ruta. En un caso simétrico (donde la distancia entre A y B es la misma que entre B y A), esto se puede omitir realizando una${\displaystyle O(1)}$operación. Dado que una operación 2-opt implica eliminar 2 aristas y agregar 2 aristas diferentes, podemos restar y sumar las distancias de solo esas aristas.

lengthDelta = - dist(route[v1], route[v1+1]) - dist(route[v2], route[v2+1]) + dist(route[v1+1], route[v2+1]) + dist(route[v1], route[v2])

Si lengthDeltaes negativo, significa que la nueva distancia después del intercambio será menor. Una vez que sabemos que lengthDeltaes negativo, realizamos un intercambio 2-opt. Esto nos ahorra muchos cálculos.

#include <random> #include <stdio.h> #include <vector>usando el espacio de nombres std ;clase Punto { público : float x , y ;Punto ( float x , float y ) { this -> x = x ; this -> y = y ; } Punto () { this -> x = 0.0 ; this -> y = 0.0 ; }// Distancia entre dos puntos inline float dist ( const Point & other ) const { float diffx = x - other . x ; float diffy = y - other . y ; return sqrt ( diffx * diffx + diffy * diffy ); } };// Calcula la distancia de todo el circuito float pathLength ( vector < Point > & path ) { int n = path . size (); float length = path [ n - 1 ]. dist ( path [ 0 ]); for ( int i = 0 ; i < n - 1 ; i ++ ) { length += path [ i ]. dist ( path [ i + 1 ]); } return length ; }// Reemplazar los bordes path[i]->path[i+1] y path[j]->path[j+1] // con path[i]->path[j] y path[i+1]->path[j+1] void swap_edges ( vector < Point > & path , int i , int j ) { i += 1 ; while ( i < j ) { Point temp = path [ i ]; path [ i ] = path [ j ]; path [ j ] = temp ; i ++ ; j -- ; } }// Imprime la ruta. void printPath ( string pathName , vector < Point > & path ) { printf ( "%s = [" , pathName . c_str ()); for ( int i = 0 ; i < path . size (); i ++ ) { if ( i % 10 == 0 ) { printf ( " \n  " ); } if ( i < path . size () - 1 ) { printf ( "[%.1f, %.1f], " , path [ i ]. x , path [ i ]. y ); } else { printf ( "[%.1f, %.1f]" , path [ i ]. x , path [ i ]. y ); } } printf ( " \n ]; \n " ); }// Crea una ruta de longitud n con puntos aleatorios entre 0 y 1000 vector < Point > createRandomPath ( int n ) { vector < Point > path ; for ( int i = 0 ; i < n ; i ++ ) { float x = ( float ) rand () / ( float )( RAND_MAX / 1000 ); float y = ( float ) rand () / ( float )( RAND_MAX / 1000 ); path . push_back ( Point ( x , y )); } return path ; }int main () { vector < Point > path = createRandomPath ( 100 ); printPath ( "path1" , path ); float curLength = pathLength ( path ); printf ( "path1len = %.1f; \n\n " , curLength );int n = path . size (); bool foundImprovement = true ; while ( foundImprovement ) { foundImprovement = false ; for ( int i = 0 ; i < n - 1 ; i ++ ) { for ( int j = i + 2 ; j < n ; j ++ ) { float lengthDelta = - path [ i ]. dist ( path [ i + 1 ]) - path [ j ]. dist ( path [( j + 1 ) % n ]) + path [ i ]. dist ( path [ j ]) + path [ i + 1 ]. dist ( path [( j + 1 ) % n ]);// Si la longitud de la ruta se reduce, realiza un intercambio 2-opt if ( lengthDelta < 0 ) { swap_edges ( path , i , j ); curLength += lengthDelta ; foundImprovement = true ; } } } }printPath ( "path2" , path ); printf ( "path2len = %.1f; \n " , curLength );devolver 0 ; }

ruta1 = [  [0.0, 131.5], [755.6, 458.7], [532.8, 219.0], [47.0, 678.9], [679.3, 934.7], [383.5, 519.4], [831.0, 34.6], [53.5, 529.7], [671.1, 7.7], [383.4, 66.8],  [417.5, 686.8], [589.0, 930.4], [846.2, 526.9], [92.0, 653.9], [416.0, 701.2], [910.3, 762.2], [262.5, 47.5], [736.1, 328.2], [632.6, 756.4], [991.0, 365.3],  [247.0, 982.6], [722.7, 753.4], [651.5, 72.7], [631.6, 884.7], [272.7, 436.4], [766.5, 477.7], [237.8, 274.9], [359.3, 166.5], [486.5, 897.7], [909.2, 60.6],  [904.7, 504.5], [516.3, 319.0], [986.6, 494.0], [266.1, 90.7], [947.8, 73.7], [500.7, 384.1], [277.1, 913.8], [529.7, 464.4], [941.0, 50.1], [761.5, 770.2],  [827.8, 125.4], [15.9, 688.5], [868.2, 629.5], [736.2, 725.4], [999.5, 888.6], [233.2, 306.3], [351.0, 513.3], [591.1, 846.0], [412.1, 841.5], [269.3, 415.4],  [537.3, 467.9], [287.2, 178.3], [153.7, 571.7], [802.4, 33.1], [534.4, 498.5], [955.4, 748.3], [554.6, 890.7], [624.8, 842.0], [159.8, 212.8], [714.7, 130.4],  [91.0, 274.6], [3.0, 414.3], [26.9, 709.8], [937.9, 239.9], [180.9, 317.5], [887.0, 652.1], [150.3, 681.3], [385.8, 387.7], [499.7, 147.5], [587.2, 845.6],  [590.1, 955.4], [556.1, 148.2], [983.3, 408.8], [141.8, 564.9], [252.1, 488.5], [464.0, 961.1], [126.0, 199.8], [319.2, 629.3], [126.7, 651.3], [621.6, 803.1],  [247.8, 476.4], [389.3, 203.3], [28.4, 901.7], [426.5, 142.0], [947.5, 410.3], [131.2, 885.6], [92.2, 162.2], [71.1, 365.3], [253.1, 135.1], [783.2, 455.3],  [349.5, 452.3], [808.9, 931.7], [651.6, 215.2], [679.6, 908.9], [250.1, 860.9], [471.3, 506.0], [600.4, 817.6], [755.8, 462.2], [951.4, 632.7], [439.3, 824.7] ]; ruta1len = 55723,0;ruta2 = [  [0.0, 131.5], [91.0, 274.6], [71.1, 365.3], [3.0, 414.3], [53.5, 529.7], [92.0, 653.9], [47.0, 678.9], [15.9, 688.5], [26.9, 709.8], [28.4, 901.7],  [131.2, 885.6], [247.0, 982.6], [277.1, 913.8], [464.0, 961.1], [486.5, 897.7], [439.3, 824.7], [412.1, 841.5], [250.1, 860.9], [150.3, 681.3], [126.7, 651.3],  [141.8, 564.9], [153.7, 571.7], [247.8, 476.4], [252.1, 488.5], [319.2, 629.3], [416.0, 701.2], [417.5, 686.8], [534.4, 498.5], [537.3, 467.9], [529.7, 464.4],  [516.3, 319.0], [500.7, 384.1], [471.3, 506.0], [383.5, 519.4], [351.0, 513.3], [349.5, 452.3], [385.8, 387.7], [272.7, 436.4], [269.3, 415.4], [180.9, 317.5],  [233.2, 306.3], [237.8, 274.9], [287.2, 178.3], [389.3, 203.3], [532.8, 219.0], [736.1, 328.2], [783.2, 455.3], [755.6, 458.7], [755.8, 462.2], [766.5, 477.7],  [846.2, 526.9], [904.7, 504.5], [868.2, 629.5], [736.2, 725.4], [761.5, 770.2], [722.7, 753.4], [632.6, 756.4], [621.6, 803.1], [600.4, 817.6], [624.8, 842.0],  [631.6, 884.7], [591.1, 846.0], [587.2, 845.6], [554.6, 890.7], [589.0, 930.4], [590.1, 955.4], [679.3, 934.7], [679.6, 908.9], [808.9, 931.7], [999.5, 888.6],  [955.4, 748.3], [910.3, 762.2], [887.0, 652.1], [951.4, 632.7], [986.6, 494.0], [947.5, 410.3], [983.3, 408.8], [991.0, 365.3], [937.9, 239.9], [827.8, 125.4],  [947.8, 73.7], [941.0, 50.1], [909.2, 60.6], [831.0, 34.6], [802.4, 33.1], [671.1, 7.7], [651.5, 72.7], [714.7, 130.4], [651.6, 215.2], [556.1, 148.2],  [499.7, 147.5], [426.5, 142.0], [359.3, 166.5], [383.4, 66.8], [262.5, 47.5], [266.1, 90.7], [253.1, 135.1], [159.8, 212.8], [126.0, 199.8], [92.2, 162.2] ]; path2len = 8586.2;

Visualización

• 3 opciones
• búsqueda local (optimización)
• Heurística de Lin-Kernighan

• GA CROES (1958). Un método para resolver problemas del viajante de comercio . Operations Res. 6 (1958), pp., 791-812.
• MM FLOOD (1956). El problema del viajante . Operations Res. 4 (1956), pp., 61-75.

• El problema del viajante: un estudio de caso en optimización local
• Soluciones para la mejora: Intercambios de dos opciones