2-OPT

수학적 최적화에서 2-OPT는 외판원 문제를 해결하기 위해 1958년 Croes가 제안한 간단한 지역 탐색(Local Search) 알고리즘이다.

2-OPT를 통해 경로(Route)가 꼬인(Cross over itself) 노선을 재정렬(순서 변경)하여 풀어주고, 이를 통해 비용(Traveling Cost)을 개선할 수 있다는 게 주요 아이디어이다.

- A   B -             - A - B -
    X         ==>
- C   D -             - C - D -

전체 2-OPT 지역 검색은 가능한 모든 유효한 조합을 비교하고, 교환(swap)하는 메커니즘이다.

이 기술은 외판원 문제뿐만 아니라 많은 관련 문제에 적용될 수 있으며, 간단한 변경(minor modification)을 통해 차량 경로 문제(VRP:Vehicle Routing Problem)뿐만 아니라 capacitated VRP 에 적용할 수 있다.

아래는 2-OPT swap이 주어진 경로를 변경/개선하는 방식이다 :

  2optSwap(route, i, k) {
      1. route[1]에서 route[i-1]까지 순서대로 new_route에 추가
      2. route[i]에서 route[k]까지 역순으로 new_route에 추가
      3. route[K + 1]에서 끝까지 순서대로 new_route에 추가
      return new_route;
  }

위의 방식에 대한 아래 예시를 보면 간단히 이해할 수 있을 것이다.

  example route: A ==> B ==> C ==> D ==> E ==> F ==> G ==> H ==> A
  example i = 4, example k = 7
  new_route:
      1. (A ==> B ==> C)
      2. A ==> B ==> C ==> (G ==> F ==> E ==> D)
      3. A ==> B ==> C ==> G ==> F ==> E ==> D (==> H ==> A)

이러한 알고리즘은 아래와 같이 정리할 수 있다.

  repeat until no improvement is made {
      start_again:
      best_distance = calculateTotalDistance(existing_route)
      for (i = 0; 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
                  goto start_again
              }
          }
      }
  }

참고 : 특정 노드에서 출발/도착하면, swap 후보 검색에서 이를 제거해야 한다. 그렇지 않으면 잘못된 경로를 생성한다.

예를 들어, 노드 A:

  A ==> B ==> C ==> D ==> A

노드[0]과 노드[2]의 swap을 하였다면

 C ==> B ==> A ==> D ==> A

와 같이 유효하지 않은 경로를 생성한다. 출발/종료점이 정해져 있다면 이를 제외한 노드만을 swap후보로 선택할 수 있도록 해야한다.

각주

G. A. CROES (1958). 《A method for solving traveling salesman problems》. Operations Res. 6 (1958) , pp., 791-812.

같이 보기

외부 링크

이 글은 컴퓨터 과학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다.