A Hybrid Matheuristic Framework for the Chinese Postman Problem with Load-Dependent Costs

기술 요약: 하중 의존적 비용을 고려한 중국 우체부 문제(CPP)를 위한 하이브리드 메타휴리스틱 프레임워크

문제 정의
본 논문은 고전적인 아크 라우팅 문제(Arc Routing Problem, ARP)의 변형인 하중 의존적 비용을 고려한 중국 우체부 문제(Chinese Postman Problem with Load-Dependent Costs, CPP-LC)를 다룬다. CPP-LC에서 간선(edge)을 통과하는 비용은 단순히 길이에 의해서만 결정되는 것이 아니라, 통과 시점의 차량 총중량(공차 중량 + 현재 적재량)에 따라 달라진다. 이러한 정식화는 연료 소비와 배출량이 차량 하중에 따라 증가하는 실제 물류 현장의 상황을 반영한다. 다항 시간 내에 해결 가능한 표준 CPP와 달리, CPP-LC는 일반적으로 강한 NP-난해(strongly NP-hard) 특성을 가진다. 목표는 연결된 그래프의 모든 간선을 적어도 한 번씩 방문하면서, 총 하중 의존적 이동 비용을 최소화하는 경로를 찾는 것이다.

방법론
저자들은 탐색(exploration)과 집중(intensification)의 균형을 맞추기 위해 메타휴로리스틱 탐색과 수학적 프로그래밍을 결래한 하이브리드 메타휴리스틱 프레임워크인 MaLD를 제안한다. 이 프레임워크는 다음과 같은 구성 요소로 작동한다:

1. 수학적 정식화: 본 연구는 문제를 모델링하기 위해 아크 라우팅 혼합 정수 선형 계획법(MILP) 정식화(Corberán 등의 방식 채택)를 활용한다. 계산 효율성을 높이기 위해, 저자들은 전체 문제 인스턴스가 아닌 특정 간선 부분 수열(subsequences)에 집중하는 "축소된(reduced)" MILP 모델을 사용한다.
2. 지역 탐색(Local Search): 초기 해는 탐욕적 구성 휴리스틱(Greedy Constructive Heuristic, GCH)을 사용하여 생성된다. 이후 "일반 이동(general shift)" 동작을 사용하는 지역 탐색 절차를 통해 해를 정교화한다. 이 동작에서는 간선의 부분 집합을 무작위로 제거한 뒤, 최적의 통과 방향을 결정하기 위한 동적 계획법(dynamic programming)을 사용하여 총 비용을 최소화하는 위치에 해당 간선들을 재삽입한다.
3. 재정렬 절차(Reordering Procedure): 간선이 처음 방문되었을 때 반드시 서비스되어야 한다는 제약 조건을 충족하기 위한 중요한 전처리 단계이다. 만약 어떤 간선이 서비스되기 전에 데드헤딩(deadheading, 서비스 없이 통과하는 것)을 수행하게 된다면, 해당 간선을 더 일찍 서비스하도록 순서를 재정렬한다. 이러한 조정은 대개 차량의 하중을 더 빨리 줄여줌으로써 후속 데드헤딩 비용을 낮춘다.
4. 집중화(Intensification): 지역 탐색과 재정렬을 거친 후, 알고리즘은 집중화 단계로 진입한다. 연속된 간선들로 이루어진 부분 수열을 선택하고, 나머지 경로를 고정한 상태에서 이 간선들의 최적 순열을 찾기 위해 축소된 MILP 모델을 푼다. 이를 통해 순수 메타휴리스틱이 놓칠 수 있는 특정 이웃 영역을 깊이 있게 탐색할 수 있다.
5. 개미 군집 최로화(Ant Colony Optimization, ACO): 포괄적인 비교를 위해 저자들은 ACO 메타휴리스틱도 구현하였다. 이 접근 방식에서 인공 개미들은 간선과 그 통과 방향을 나타내는 상태를 통과하며 해를 구성한다. 페로몬 경로는 향후 탐색을 유도하기 위해 해의 품질에 따라 업데이트된다.

주요 기여

• 하이브리드 프레임워크: 주요 기여는 휴리스틱 지역 탐색의 속도와 MILP 기반 집중화의 정확성을 효과적으로 결합한 MaLD의 설계이다.
• 알고리즘 확장: 기존 연구(Corberán 등)가 CPP-LC를 위한 반복 지역 탐색(ILS) 및 변수 이웃 탐색(VNS)을 도입했다면, 본 논문은 비교용 메타휴리스틱으로 ACO를 도입하고 기존 방법보다 뛰어난 성능을 보이는 MaLD 프레임워크를 개발하였다.
• 확장성 및 효율성: 축소된 MILP 모델을 부분 수열에 대해 해결함으로써, 전체 MILP를 푸는 데 드는 과도한 시간 비용을 들이지 않고도 순수 메타휴리스틱이 빠질 수 있는 지역 최적해(local optima)를 탈출할 수 있음을 입증하였다.

실험 결과
제안된 방법들은 소규모(8~10개 간선)부터 대규모(최대 232개 간선)까지 아우르는 세 가지 데이터셋(오일러 그래프 및 Christofides와 Hertz 등의 인스턴스 포함)에 대해 평가되었다.

• 해의 품질: MaLD는 일관되게 가장 높은 해의 품질을 달 나타냈다. 최적해를 알고 있는 모든 소규모 인스턴스에서 최적해를 찾아냈으며, 중규모 및 대규모 인스턴스에서 ILS, VNS, ACO보다 우수한 성능을 보였다. 구체적으로, MaLD는 중규모 인스턴스에서 ILS 및 VNS 솔루션을 약 6~7% 개선하였고, 가장 큰 인스턴스에서는 평균 1.35%를 개선하였다.
• 계산 효율성:
  • 소규모 인스턴스: 매우 작은 인스턴스의 경우 GCH가 가장 빨랐으며, ILS/VNS가 매우 경쟁력 있었다. MaLD는 약간 더 느렸으나 최적해에 도달하였다.
  • 대규모 인스턴스: ACO는 병렬 실행 능력 덕분에 솔루션 품질 면에서 ILS와 VNS를 종종 능가하면서도 현저히 낮은 계산 시간을 유지하는 등 강력한 확장성을 보여주었다. 그러나 MaLD는 계산 비용이 더 높음에도 불구하고(예: 가장 큰 그룹의 경우 약 1262초 vs ACO의 약 14초) 여전히 솔루션 품질 면에서 우월하였다.
• 구성 요소 분석: 민감도 분석 결과, 집중화 구성 요소가 대규모 인스턴스에서 솔루션 품질에 결정적인 역할을 하며, 해당 시나리오에서 지역 탐색 구성 요소보다 비용 절감에 더 크게 기여한다는 것이 밝혀졌다. 집중화 단계를 제거하면 상당한 비용 증가(예: 가장 큰 그룹에서 약 211,000 유닛)가 발생하였다.

의의 및 주장
본 논문은 MaLD 프레임워크가 적재량에 따라 이동 비용이 동적으로 변하는 복잡한 하중 의당적 경로 문제를 해결하는 데 효과적인 전략임을 주장한다. 결과는 운영 연구(정밀한 MILP)와 지능형 계산 방법(메타휴리스틱)을 잇는 하이브리드 최적화 전략이 CPP-LC의 강한 NP-난해성을 해결하는 데 필수적임을 강조한다. ACO는 대규모 인스턴스에 대해 경쟁력 있고 확장 가능한 대안이 될 수 있지만, 메타휴리스틱 접근 방식이 가장 견고한 솔루션 품질을 제공한다. 저자들은 스마트 물류 및 에너지 인지형 라우팅 연구를 촉진하기 위해 구현 코드와 데이터셋을 공개적으로 제공한다고 밝혔다.