An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers

기술적 요약: 비호환 고객 문제를 가진 용량 제한 시설 위치 문제에 대한 향상된 대규모 이웃 탐색 접근법

문제 정의
본 논문은 고객 비호환성을 포함한 다중 소스 용량 제한 시설 위치 문제 (MS-CFLP-CI) 를 다룬다. 이 변형은 동일한 시설에서 서비스를 받을 수 없는 비호환 고객 쌍의 집합 ($I$) 을 도입함으로써 고전적인 MS-CFLP 를 확장한 것이다. 이 문제는 시설을 개장할지 결정하여 개장 비용 ($f_j$) 을 발생시키고, 개장된 시설 간 고객 수요 ($d_i$) 를 분배하여 운송 비용 ($c_{ij}$) 을 발생시키며, 총 비용을 최소화하는 것을 포함한다. 해법은 시설 용량 제약 ($s_j$) 을 만족하고, 고객 수요를 완전히 충족하며, 두 비호환 고객이 동일한 시설을 공유하지 않도록 보장해야 한다. 비호환성 제약의 존재는 개장된 시설 집합이 고정되어 있더라도 개장된 시설로부터 최적 공급을 찾는 하위 문제를 NP-난제로 만든다.

방법론
저자들은 MS-CFLP-CI 를 해결하기 위해 대규모 이웃 탐색 (LNS) 프레임워크를 제안한다. 이 접근법의 핵심은 현재 해법의 일부를 반복적으로 파괴하고 정밀한 혼합 정수 계획법 (MIP) 솔버 (Gurobi) 를 사용하여 이를 복구하는 과정을 포함한다.

• 해법 표현: 해법은 운송 수량의 행렬로 표현되며, 개장/폐쇄된 시설과 할당된 고객을 추적하는 보조 데이터 구조에 의해 지원된다.
• 초기 해법: 휴리스틱이 개장 비용으로 시설을 정렬하고 총 수요를 충족할 만큼의 시설을 선택한 후, 비호환성 제약을 처리하기 위해 특정 수의 추가 시설 ($k=5$) 을 더 선택함으로써 시작 해법을 구성한다. 고객은 균일 전략에 따라 할당된다.
• 파괴 연산자: 본 논문은 비호환성 제약을 위해 특별히 설계된 세 가지 새로운 파괴 연산자를 도입한다:
  1. 가장 저렴한 시설 (CF): 무작위 시설과 해당 시설의 고객들을 선택한 후, 해당 특정 고객 그룹에 대해 평균 운송 비용을 가장 낮게 제공하는 다른 개장된 시설들을 식별한다.
  2. 하이브리드 고객 (HC): 두 가지 전략의 재조합이다. 무작위 시설과 해당 시설의 고객들을 선택한 후, 해당 시설에 대한 운송 비용이 낮은 "저렴한 고객"과 운송 비용이 높은 "비싼 고객"을 식별한다. 그런 다음 이러한 특정 고객 하위 집합에 대한 최상의 서비스를 제공하는 추가 시설들을 선택한다.
  3. 폐쇄된 시설: 무작위 폐쇄된 시설과 최소 비용 측정치 ($Q_g$) 를 가진 시설들 모두 새로운 시설 개장을 탐색하기 위해 하위 문제에 포함된다.
• 복구 연산자: 파괴된 요소들에 의해 정의된 하위 문제는 Gurobi 를 사용하여 정확하게 해결된다. 계산 시간을 관리하기 위해 복구 단계에는 현재 하위 문제에 관여된 시설 수보다 최대 두 개 이하로 새로운 시설을 개장하는 것을 제한하는 제약이 포함된다. 수렴을 가속화하기 위해 솔버에 현재 하위 문제 비용을 컷오프 값으로 제공한다.
• 구성 및 튜닝: 저자들은 인스턴스 규모 (특히 시설 수가 $\le 700$인 경우와 $> 700$인 경우를 구분) 에 따라 하위 문제 크기 ($\nu$) 와 같은 매개변수를 조정하기 위해 기능 기반 매개변수 튜닝을 위해 irace 도구를 활용한다. 최종 알고리즘인 $LNS_{init,accept}$는 제안된 파괴 연산자와 개선된 초기 해법 휴리스틱, 그리고 로컬 최적점에서 벗어나는 것을 용이하게 하기 위해 동일한 비용을 가진 해법도 허용하는 수용 기준을 결합한다.

주요 기여

• 새로운 알고리즘 프레임워크: MS-CFLP-CI 문제에 대규모 이웃 탐색을 적용한 최초의 사례이다.
• 전문화된 연산자: 표준 시설 위치 휴리스틱을 넘어 비호환성 제약을 명시적으로 고려하는 파괴 연산자 (CF 및 HC) 의 설계.
• 하이브리드 정밀/휴리스틱 복구: 해법 품질과 실행 시간을 균형 있게 조절하기 위해 특정 제약으로 최적화된 복구 단계 내 정밀 MIP 솔버의 통합.
• 엄격한 분석: 개별 구성 요소 (초기화, 수용 기준, 적응형 가중치) 의 영향을 평가하기 위한 포괄적인 절제 연구 및 통계적 분석 (Friedman 및 Nemenyi 검정 사용).
• 광범위한 벤치마킹: 최대 3,000 개의 시설과 8,000 명의 고객을 포함하는 두 개의 대규모 데이터셋 (wlp 및 cflp-ci) 에 대한 평가.

실험 결과
제안된 $LNS_{init,accept}$ 방법은 MineReduce 기반 다중 시작 반복 로컬 탐색 (MR-MS-ILS), GRASP, 순열 인코딩 진화 알고리즘 (PcEA), 다중 시작 그리디 (MG), 시뮬레이션 어닐링 (SA) 을 포함한 최첨단 메타휴리스틱과 비교하여 테스트되었다.

• 성능: 제안된 방법은 두 가지 다른 시간 제한 ($10\sqrt{m}$초 및 $m$초) 하에서 두 데이터셋 모두에서 기존 모든 방법을 크게 능가했다.
• 새로운 최선 해법: 이 접근법은 두 데이터셋에 걸쳐 있는 모든 80 개 인스턴스에 대해 새로운 최선 해법을 발견했다.
• 통계적 유의성: 통계적 검정은 이전 최선 방법 (SA) 에 대한 개선이 통계적으로 유의미함을 확인했다.
• 확장성: 정밀 솔버 (Gurobi/CPLEX) 는 합리적인 시간 내에 최대 150 개 시설의 인스턴스만 최적으로 해결할 수 있었던 반면, LNS 접근법은 최대 3,000 개 시설의 인스턴스를 효과적으로 처리했다.
• 갭 감소: wlp 데이터셋의 경우, 이 방법은 기존 최선 해법에 비해 -0.68% 에서 -1.84% 범위의 갭 개선을 달성했다. cflp-ci 데이터셋의 경우 개선 폭은 -0.46% 에서 -2.09% 였다.

의의 및 주장
저자들은 그들의 방법이 MS-CFLP-CI 문제에 대한 현재 최첨단 기술임을 주장한다. 이 연구의 의의는 이전 메타휴리스틱들이 특히 더 큰 인스턴스의 경우 완전히 최적화하는 데 어려움을 겪었던 고객 비호환성으로 인한 계산 복잡성을 처리할 수 있는 능력에 있다. 본 논문은 새로운 파괴 연산자, 정밀 복구 단계, 그리고 특정 알고리즘 튜닝의 결합이 중간 크기의 이웃을 효과적으로 탐색하여 SA 및 기타 방법들이 정체되는 곳에서 우수한 해법을 찾을 수 있게 한다고 주장한다. 저자들은 겸손하게도 현재 그들의 방법이 최선이지만, 향후 작업은 인스턴스 난이도를 더 잘 이해하기 위해 인스턴스 공간 분석을 포함하고 시설 위치 변형들 다른 것들로 접근법을 확장하는 것이 될 수 있다고 언급한다.