2-옵션
2-opt
최적화에서, 2-opt는 여행 판매원 문제를 해결하기 위한 간단한 로컬 검색 알고리즘이다.2-opt 알고리즘은 비록 기본적인 움직임은 이미 Flood에 의해 제안되었지만,[1] 1958년에 Croes에 의해 처음 제안되었다.[2]스스로 넘나드는 경로를 택해 그렇지 않도록 재주문하는 것이 그 이면의 주요 생각이다.
- A - A - B - × ==> - C D - C - C - D - D -
완전한 2-옵션 로컬 검색은 스와핑 메커니즘의 가능한 모든 유효한 조합을 비교한다.이 기술은 많은 관련 문제뿐만 아니라 여행 중인 세일즈맨 문제에도 적용될 수 있다.여기에는 알고리즘을 약간 수정해야 하는 콘덴서형 VRP뿐만 아니라 차량 라우팅 문제(VRP)도 포함된다.
이것은 2옵션 스왑이 주어진 경로를 조작하는 메커니즘이다.
절차 2optSwap(route, i, k) { 1. 경로[0]를 경로[i-1]로 하고 new_route 2. 경로[i]를 경로[k]로 하고, 경로[k]를 역순으로 추가한다. 경로[k+1]를 선택하여 종료하고 new_route returnew_route; }에 추가한다. 다음은 임의 입력을 사용한 위의 예다.
- 경로 예:A → B → C → D → E → F → G → H → A
- 예제 매개 변수: i = 4, k = 7(시작 인덱스 1)
- new_route의 단계별 내용:
- (A → B → C)
- A → B → C → (G → F → E → D)
- A → B → C → G → F → E → D → (H → A)
이것은 위의 메커니즘을 이용한 완전한 2-옵션 스왑이다.
개선이 이루어지지 않을 때까지 반복하다. {best_distance = 계산하다.TotalDistance(기존_route) start_again: (i = 0; i <= 스와핑할 수 있는 노드 수 - 1; i++) { for (k = i + 1; k <= 스와핑할 수 있는 노드 수; k+++) {new_route = 2optSwap(기존_route, i, k) = 계산TotalDistance(new_distance < best_distance){ existing_route = new_route best_distance = new_distance goto start_again}}}}}}}} 참고: 특정 노드 또는 디포에서 시작/종료할 경우 순서를 반대로 바꾸면 경로가 잘못되기 때문에 검색에서 이 항목을 제거하십시오.
예를 들어, A에 디포가 있는 경우:
A → B → C → D → A
노드[0] 및 노드[2]를 사용하여 스와핑하면 생산성이 향상됨
C → B → A → D → A
유효하지 않음(A, 창고에서 떠나지 않음).
참고 항목
참조
- G. A. CROES (1958). A method for solving traveling salesman problems. Operations Res. 6 (1958) , pp., 791-812.
- M. M. FLOOD (1956). The traveling-salesman problem. Operations Res. 4 (1956) , pp., 61-75.
