En optimización , 2-opt es un algoritmo de búsqueda local simple para resolver el problema del viajante de comercio . El algoritmo de 2 opciones fue propuesto por primera vez por Croes en 1958, [1] aunque Flood ya había sugerido el movimiento básico. [2] La idea principal detrás de esto es tomar una ruta que se cruza sobre sí misma y reordenarla para que no lo haga.
- AB - - A - B - × ==> - CD - - C - D -
Una búsqueda local completa de 2 opciones comparará todas las combinaciones válidas posibles del mecanismo de intercambio. Esta técnica se puede aplicar al problema del viajante de comercio así como a muchos problemas relacionados. Estos incluyen el problema de enrutamiento del vehículo (VRP), así como el VRP capacitado, que requieren una pequeña modificación del algoritmo.
Este es el mecanismo por el cual el intercambio de 2 opciones manipula una ruta determinada:
procedimiento 2optSwap (ruta, i, k) { 1. tome la ruta [0] a la ruta [i-1] y agréguelas para new_route 2. tome la ruta [i] a la ruta [k] y agréguelas en orden inverso a new_route 3. tome la ruta [k + 1] para terminar y agréguelos para new_route return new_route;}
Aquí hay un ejemplo de lo anterior con entrada arbitraria:
- Ruta de ejemplo: A → B → C → D → E → F → G → H → A
- Parámetros de ejemplo: i = 4, k = 7 (índice inicial 1)
- Contenido de new_route por paso:
- (A → B → C)
- A → B → C → (G → F → E → D)
- A → B → C → G → F → E → D → (H → A)
Este es el intercambio completo de 2 opciones que hace uso del mecanismo anterior:
repita hasta que no se haga ninguna mejora { mejor_distancia = calcularTotalDistancia (ruta_existente) empezar de nuevo: for (i = 0; i <= número de nodos elegibles para ser intercambiados - 1; i ++) { for (k = i + 1; k <= número de nodos elegibles para ser intercambiados; k ++) { nueva_ruta = 2optSwap (ruta_existente, i, k) new_distance = calcularTotalDistance (nueva_ruta) if (nueva_distancia)> ruta_existente = nueva_ruta mejor_distancia = nueva_distancia Ir a empezar de nuevo } } }}
Nota: Si comienza / termina en un nodo o depósito en particular, debe eliminarlo de la búsqueda como candidato elegible para el intercambio, ya que invertir el orden provocará una ruta no válida.
Por ejemplo, con depósito en A:
A → B → C → D → A
Intercambiar usando el nodo [0] y el nodo [2] produciría
C → B → A → D → A
que no es válida (no sale de A, el depósito).
Ver también
Referencias
- GA CROES (1958). Un método para resolver los problemas de los vendedores ambulantes . Operaciones Res. 6 (1958), págs., 791-812.
- MM INUNDACIÓN (1956). El problema del viajante de comercio . Operaciones Res. 4 (1956), págs., 61-75.