Variable Neighborhood Search (VNS)

Variable Neighborhood Search (VNS)는 1997년 Mladenović와 Hansen이 소개한 메타휴리스틱 최적화 프레임워크입니다. 이는 미리 정의된 이웃 구조 세트 간을 체계적으로 전환함으로써 지역 최적해를 탈출합니다. 먼저 현재 해를 섭동(shaking)하여 탐색 공간의 다른 영역에 도달한 다음, 해당 영역 내에서 지역 탐색을 적용하고, 마지막으로 개선될 경우에만 새로운 해를 수용합니다. 이 방법은 조합 최적화 문제(경로 설정, 스케줄링, 그래프 문제)와 연속 최적화 모두를 처리할 만큼 유연하여, 운영 연구에서 가장 널리 사용되는 이웃 기반 메타휴리스틱 중 하나입니다.