기술 요약: 가족 용량 제한 차량 경로 문제(F-CVRP)를 위한 하이브리드 메타휴리스틱

문제 정의

본 논문은 가족 외판원 문제(FTSP)와 전형적인 용량 제한 차량 경로 문제(CVRP)의 일반화 형태인 **가족 용량 제한 차량 경로 문제(F-CVRP)**를 다룬다. F-CVRP에서는 단일 창고에서 출발하여 가족 단위로 구분된 고객들을 방문하는 용량 $Q$를 가진 $K$대의 균질한 차량 함대가 운용된다. 모든 고객을 반드시 방문해야 하는 표준 CVRP와 달리, F-CVRP에서는 각 가족 $l$로부터 특정 수($v_l$)의 구성원만을 방문해야 하며, 나머지 가족 구성원은 방문하지 않은 채로 남겨둘 수 있다. 목적은 차량 용량 제약을 준수하고 각 가족의 정확한 방문 요구 사항을 충족하면서 총 경로 비용을 최소화하는 것이다.

문제 인스턴스의 규모가 커짐에 따라 정확한 해법(exact methods)은 계산적으로 불가능해진다. 따라서 본 논문은 엄격한 시간 예산 내에 고품질의 솔루션을 제공할 수 있는 빠르고 우수한 휴리스틱을 개발하는 데 초점을 맞춘다. 이는 독립적인 솔버(solver)로서뿐만 아니라 정확한 프레임워크를 위한 프라이멀 바운드(primal bounds) 제공자로서의 역할도 수행한다.

방법론: ILS+SP 하이브리드 메타휴리스틱

저자들은 ILS+SP라는 하이브리드 메타휴리스틱을 제안하며, 이는 반복적 지역 탐색(Iterated Local Search, ILS) 프레임워크와 집합 분할(Set Partitioning, SP) 사후 최적화 단계를 결합한 것이다. 알고리즘은 다음과 같이 작동한다.

1. 반복적 지역 탐색 (ILS) 코어

탐색은 경로 풀($P$)을 유지하고 최적의 실행 가능한 솔루션($s^*$)을 추적하는 ILS 프레임워크에 의해 구동된다.

• 초기 솔루션: 최적의 병렬 삽입(Best Parallel Insertion, BPI) 휴리스틱을 통해 생성된다. 이 방식은 비용 증가를 최소화하면서 고객을 반복적으로 삽입하여 $K$개의 경로를 구축하며, 이때 가족 방문 수를 충족하도록 보장한다.
• 지역 탐색 (RVND): 지역 탐색은 9개의 이웃(neighborhood) 포트폴리오를 탐색하는 무작위 변수 이웃 하강(Random Variable Neighborhood Descent, RVND) 전략을 사용한다.
  • 경로 간 (5개): Swap(1,1), Swap(2,1), Swap(2,2), Shift(1,0), Shift(2,0).
  • 경로 내 (3개): Exchange, Reinsertion, Or-opt2.
  • 특화된 이웃 (1개): MemberRelocate. 이는 문제 특화된 연산자로, 방문된 고객을 제거하고 동일한 가족의 미방문 구성원을 모든 경로 중 최적의 위치에 삽입한다.
  • 모든 이웃은 가족 방문 수 및 활성 경로 수($K$)의 구조적 제약을 보존한다.
• 수용 기준: 표준 지역 탐색과 달리, 알고리즘은 시간 기반 냉각 스케줄을 갖는 시뮬레이티드 어닐링(Simulated Annealing, SA) 기준에 따라 악화되는 이동(worsening moves)을 수용한다. 이를 통해 지역 최적해(local minima)를 탈출할 수 있다.
• 섭동 (Perturbation): 탐색을 다양화하기 위해, 현재 솔루션을 지역 탐색으로 다시 진입시키기 전 세 가지 무작위 섭동(RandomSwap, RandomShift, 또는 RandomMemberRelocate) 중 하나를 적용한다.
• 패널티 처리: 용량 위반은 목적 함수 내의 동적 패널티 계수($\theta$)를 통해 처리되며, 이 계수는 현재 솔루션의 실행 가능성에 따라 조정되어 탐색이 실행 가능한 영역으로 유도되도록 한다.

2. 집합 분할 (SP) 사후 최적화

시간 예산을 모두 소진하면, 알고리즘은 마지막 최적화 단계를 수행한다. 이는 전체 탐색 과정 동안 수집된 용량 실행 가능한 경로들의 풀($P$)에 대해 집합 분할(Set Partitioning, SP) 문제를 정식화한다.

• SP 모델은 가족 방문 요구 사항을 충족하고 정확히 $K$개의 경로를 사용하면서 총 비용을 최소화하는 경로의 부분 집합을 선택한다.
• 풀 $P$에는 현재까지 발견된 최적의 솔루션($s^*$)을 구성하는 경로들이 포함되어 있으므로, SP의 최적 솔루션은 $s^*$보다 최소한 같거나 더 우수함이 보장된다.

주요 기여

본 논문은 기존의 최첨단 기술(특히 Bernardino와 Paias, 2024의 ILS)과 차별화되는 네 가지 주요 기여를 강조한다:

1. 집합 분할과의 하이브리드화: 이전 방식에는 없던 마테우리스틱(matheuristic) 구성 요소인 경로 풀을 재최적화하기 위한 SP 사후 최적화 단계를 도입하였다.
2. 강화된 지역 탐색: 단순히 제자리에서 교체하는 것이 아니라, 미방문 가족 구성원을 모든 경로 중 최적의 위치에 삽입하는 MemberRelocate 이웃을 구현하였다.
3. 무작위 이웃 탐색: 기존 문헌의 고정된 순서와 대조적으로, RVND를 사용하여 이웃 탐색의 순서를 무작위화하였다.
4. 시뮬레이티드 어닐링 수용: 이전 방식의 엄격한 개선 중심 수용 대신, 악화되는 솔루션을 수용하는 SA 기준을 채택하여 강화(intensification)와 다양화(diversification) 사이의 균형을 개선하였다.

계산 결과

저자들은 두 가지 벤치마크 세트로 ILS+SP를 평가하였다:

1. 표준 벤치마크 (144개 인스턴스): 고객 50명 이상의 인스턴스를 포함하는 Augerat 등(1995)의 세트에서 파생되었다.
   • 성능: 이 방법은 Bernardino와 Paias(2024)의 최첨단 휴리스틱을 상대로 모든 인스턴스에서 승리하거나 동률을 기록했다.
   • 격차 감소: 최적해(BKS)와의 평균 격차(gap)를 기존 최고치인 **1.84%**에서 **0.01%**로 줄였다.
2. 확장성 벤치마크 (120개 인스턴스): CVRP Set X (Uchoa 등, 2017)에서 파생된 더 큰 규모의 새로운 인스턴스 세트(최대 142명의 고객)이다.
   • 성능: 알고리즘은 평균 실행 시간 37초와 함께 평균 격차 **0.47%**를 달성하여, 더 큰 문제 규모에 대한 확장성을 입증했다.

의의 및 주장

본 논문은 ILS+SP를 F-CVRP를 위한 강력하고 확장 가능한 솔루션으로 자리매김한다. 저자들은 문제 특화된 이웃과 SA 수용을 특징으로 하는 정교한 ILS 프레임워크와 마테우리스틱 사후 최적화(SP)를 통합함으로써, 이 방법이 기존의 휴리스틱을 크게 능가한다고 주장한다. 결과는 이 접근 방식이 확립된 벤치마크에 대해 최적해와 일치하거나 이를 개선할 수 있을 뿐만 아니라, 더 크고 복잡한 인스턴스에도 효과적으로 확장될 수 있음을 시사하며, 이는 독립적인 적용 및 정확한 솔루션 프레임워크로의 통합 모두에 가치 있는 도구임을 보여준다.