Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem

Each language version is independently generated for its own context, not a direct translation.

이 논문은 **"여러 명의 배달 기사 (또는 여행객) 가 한 Depot(기지) 에서 출발하여 모든 고객에게 방문하고 다시 돌아오는 문제"**를 해결하는 새로운 방법을 소개합니다.

이 문제는 단순히 "가장 짧은 길을 찾는 것"이 아니라, **"가장 긴 경로를 가진 배달 기사의 일정을 최대한 짧게 만들어, 모든 기사의 업무량을 공정하게 분배하는 것"**이 목표입니다. (예: 한 명은 100km 를, 다른 한 명은 10km 만 돌아다니면 안 되죠.)

저자들은 이 문제를 해결하기 위해 **인공지능 (강화학습)**과 **정밀한 수학 계산 (MILP)**을 섞은 **'RL-CMSA'**라는 새로운 알고리즘을 개발했습니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴겠습니다.

🍕 비유: "최고의 피자 배달 팀을 꾸리는 방법"

상상해 보세요. 피자가게가 있고, 100 개의 주문이 들어왔습니다. 이제 배달 기사 10 명을 뽑아 모든 주문을 처리해야 합니다. 하지만 중요한 건, 가장 늦게 도착하는 기사 한 명만이라도 최대한 빨리 도착하게 만드는 것입니다.

기존의 방법 (HGA) 은 마치 **"운이 좋은 팀을 찾기 위해 무작위로 팀을 나누고, 실수하면 다시 섞는 방식"**이었습니다. 반면, 이 논문에서 제안한 RL-CMSA는 **"스마트한 팀장"**이 되어 다음과 같은 6 단계 과정을 거칩니다.

1. 구축 (Construct): "지능적인 팀 나누기"

기존 방식: 무작위로 지역을 나누거나, 단순히 거리만 보고 팀을 만듭니다.
RL-CMSA 방식: 팀장 (알고리즘) 은 과거의 성공적인 배달 기록을 기억합니다. "A 지역과 B 지역은 항상 같은 팀이 되어 성공했다"는 강화학습 (Q-value) 데이터를 활용합니다.
- 마치 **"이 두 동네는 항상 같은 배달원이 맡으면 효율이 좋았어!"**라는 기억을 바탕으로, 처음부터 잘 맞는 팀을 구성합니다.

2. 병합 (Merge): "최고의 레시피 모으기"

여러 번의 시도를 통해 만들어진 수많은 '배달 경로'들을 모두 모아서 **'레시피 보물상자 (Pool)'**에 담습니다.
하지만 보물상자가 너무 크면 혼란스러우니, 길이가 너무 긴 나쁜 경로들은 바로 버리고, 짧은 좋은 경로들만 선별해 둡니다.

3. 해결 (Solve): "수학의 마법으로 최적 조합 찾기"

이제 보물상자에 있는 좋은 경로 조각들을 가지고, **"어떻게 조합하면 10 개의 팀이 가장 공평하게 일할까?"**를 수학적으로 딱 계산합니다.
컴퓨터가 모든 경우의 수를 빠르게 계산해서, 현재까지의 조각들 중 가장 완벽한 조합을 찾아냅니다.

4. 개선 (Improve): "미세 조정"

수학적으로 찾은 조합도 완벽하지는 않을 수 있습니다.
- "아, 이 배달원이 지나가는 길에 다른 팀의 주문을 살짝 빼서 가져가면 더 빠르겠네?"
- "이 두 팀의 경로를 살짝 바꿔주면 균형이 맞겠네?"
이런 식으로 경로를 조금씩 움직여 (Shift/Swap) 더 짧고 공평하게 만듭니다.

5. 학습 (Learn): "성공 패턴 기억하기"

이번에도 잘 된 조합을 보면, **"이 두 동네는 같이 가는 게 좋구나!"**라는 패턴을 기억합니다.
반대로 실패한 조합은 **"이건 안 되겠어"**라고 기록합니다. 이 기억이 다음 번 '팀 나누기' 단계에 반영되어 점점 더 똑똑해집니다.

6. 적응 (Adapt): "보물상자 정리"

시간이 지나면 오래된 레시피는 잊혀집니다. 보물상자에서 너무 오래된 (성공하지 못한) 경로는 지우고, 최신의 좋은 경로들로 채워 넣습니다.

🏆 왜 이 방법이 더 좋을까요?

논문의 실험 결과에 따르면, 이 방법은 기존에 가장 잘하던 방법 (유전 알고리즘) 보다 더 빠르고, 더 일관된 좋은 결과를 냅니다.

큰 도시일수록 유리: 배달 기사의 수가 많고 도시가 클수록, 이 방법은 "수학적인 조합"과 "학습된 패턴"을 잘 섞어서 더 좋은 답을 찾습니다.
안정성: 기존 방법은 운이 좋으면 아주 잘하지만, 운이 나쁘면 엉망이 될 때가 있습니다. 하지만 RL-CMSA 는 매번 비슷한 수준으로 높은 점수를 맞춥니다. (마치 매번 90 점 이상을 받는 꾸준한 학생 vs 운 좋으면 100 점, 나쁘면 50 점인 학생)

💡 결론

이 논문은 **"배달 기사의 업무량을 공정하게 나누는 문제"**를 해결할 때, 단순히 무작위로 시도하는 것이 아니라 AI 가 과거의 성공 경험을 학습하고, 수학적으로 최적의 조합을 찾아내는 하이브리드 방식이 훨씬 효과적임을 증명했습니다.

이는 단순히 피자 배달뿐만 아니라, 드론 배송, 로봇 patrolling, 기술자 순회 등 여러 대의 차량이나 기기가 협력해야 하는 모든 분야에서 더 효율적이고 공정한 시스템을 만드는 데 쓰일 수 있습니다.

Each language version is independently generated for its own context, not a direct translation.

1. 문제 정의 (Problem Definition)

이 논문은 최소 - 최대 다중 외판원 문제 (min–max mTSP) 를 다룹니다.

배경: 일반적인 외판원 문제 (TSP) 를 확장하여, 하나의 공통 기지 (Depot) 에서 출발하여 $m$ 개의 경로를 형성하고 모든 고객을 정확히 한 번씩 방문하는 문제입니다.
목표 함수: 총 이동 거리를 최소화하는 것이 아니라, $m$ 개 경로 중 가장 긴 경로의 길이 (최대 경로 비용) 를 최소화하는 것입니다.
중요성: 이는 마지막 마일 배송, 다중 로봇 순찰, UAV 임무 계획, 기술자 라우팅 등에서 작업 부하의 균형 (Workload Balance) 과 공평성을 보장하기 위해 필수적입니다.
난이도: NP-hard 문제로, 정확한 알고리즘 (Exact Algorithms) 은 소규모 인스턴스에만 적용 가능하며, 대규모 문제에는 휴리스틱 또는 메타휴리스틱이 필요합니다.

2. 제안된 방법론: RL-CMSA

저자들은 강화 학습 (Reinforcement Learning, RL) 이 통합된 Construct, Merge, Solve & Adapt (CMSA) 프레임워크인 RL-CMSA를 제안했습니다. 이 알고리즘은 휴리스틱 탐색과 정확한 최적화 (Exact Optimization) 를 결합한 하이브리드 메타휴리스틱입니다.

알고리즘은 다음 6 가지 단계를 순환적으로 수행합니다:

3.1 Construct (구축)

목적: $n_{solutions}$ 개의 후보 솔루션을 확률적으로 생성합니다.
클러스터링 (Cluster Stage):
- $m$ 개의 차량에 대응하는 $m$ 개의 클러스터로 도시를 분할합니다.
- 강화 학습 기반: 학습된 쌍별 $q$ -값 (pairwise q-values) 을 사용하여 중심점 (Seeding) 을 선택하고 도시를 할당합니다. $q$ -값이 높은 도시 쌍은 같은 클러스터에 속할 확률이 높습니다.
- 할당 비용은 거리뿐만 아니라 $q$ -값의 호환성과 예상 경로 길이 증가분을 고려하여 계산됩니다.
경로 구축 (Route Stage):
- 각 클러스터 내에서 최우선 삽입 (Best-insertion) 휴리스틱을 사용하여 초기 경로를 생성합니다.
- 2-opt 및 Or-opt 와 같은 경로 내 (Intra-route) 국소 탐색을 적용하여 경로를 개선합니다.
- 경로 간 (Inter-route) 개선 연산자 (제거, 이동, 교환) 를 적용하여 최종 후보 솔루션을 완성합니다.

3.2 Merge (병합)

생성된 모든 후보 경로들을 Rcand (후보 경로 풀) 에 추가합니다.
동일한 도시 집합을 방문하는 경로가 중복되면 가장 짧은 경로만 유지합니다.
현재 최적 해보다 긴 경로는 풀에서 제거하여 풀의 크기를 관리합니다.

3.3 Solve (해결)

제약 집합 커버링 MILP (Mixed Integer Linear Programming):
- Rcand 풀에서 정확히 $m$ 개의 경로를 선택하여 모든 도시를 최소 한 번씩 커버하고, 선택된 경로 중 최대 길이를 최소화하는 MILP 문제를 구성합니다.
- CPLEX 와 같은 상용 솔버를 사용하여 이 부분 문제를 정확하게 해결합니다.
- 선택된 경로들이 겹칠 수 있으므로, 이 단계의 출력은 아직 유효한 mTSP 해가 아닙니다.

3.4 Improve (개선)

Solve 단계에서 나온 해를 유효한 mTSP 해로 변환하고 개선합니다.
Remove: 중복된 도시를 제거하여 유효성을 확보합니다.
Shift: 한 경로에서 다른 경로로 도시를 이동시켜 전체 길이를 줄이거나 최대 경로 길이를 개선합니다.
Swap: 서로 다른 경로 간에 도시를 교환합니다.
이 단계에서는 주요 목적 (최대 경로 길이 최소화) 을 우선시하되, 이차 목적 (총 길이) 도 고려하여 탐색과 활용 (Exploration vs Exploitation) 을 균형 있게 조절합니다.

3.5 Learn (학습)

q-value 업데이트:
- Rcand 풀과 현재 최적 해 (Rbest) 에 포함된 도시 쌍의 공출현 (Co-occurrence) 빈도를 분석합니다.
- 최적 해에서 자주 함께 등장하는 도시 쌍의 $q$ -값을 강화 (Reinforce) 하여, 다음 Construct 단계에서 같은 클러스터에 속할 확률을 높입니다.
- 반대로 최적 해에 포함되지 않은 쌍은 $q$ -값을 감소시킵니다.
- 학습이 수렴하면 $q$ -값을 초기화하여 새로운 탐색을 유도합니다.

3.6 Adapt (적응)

노화 (Ageing) 정책:
- Rcand 풀에 포함된 경로들의 '나이 (Age)'를 관리합니다.
- 현재 최적 해에 포함된 경로는 나이를 0 으로 초기화하고, 포함되지 않은 경로의 나이는 증가시킵니다.
- 나이가 임계값 (agemax) 에 도달하면 경로를 풀에서 제거하여 풀을 최신 상태와 컴팩트하게 유지합니다.

3. 주요 기여 (Key Contributions)

RL-CMSA 프레임워크: mTSP 의 min-max 변형 문제에 대해 강화 학습 (Q-learning) 을 CMSA 프레임워크에 성공적으로 통합했습니다. 이는 단순한 휴리스틱이 아닌, 학습된 지식을 통해 구축 과정을 적응적으로 조정하는 하이브리드 접근법입니다.
효율적인 클러스터링 전략: $q$ -값을 기반으로 한 확률적 클러스터링을 도입하여, 최적 해에 가까운 경로 구조를 초기 생성 단계에서부터 유도합니다.
정확한 최적화와 휴리스틱의 균형: MILP 솔버를 사용하여 부분 문제를 정확하게 해결하고, 이를 통해 생성된 고품질 경로 조합을 국소 탐색과 결합하여 전역 최적에 근접한 해를 찾습니다.

4. 실험 결과 (Experimental Results)

벤치마크: 무작위 생성 인스턴스 (도시 수 $n=50, 100, 200$ , 판매원 수 $m$ 는 $n$ 의 1%~15%) 와 TSPLIB 인스턴스 (eil51, berlin52 등) 를 사용했습니다.
비교 대상: 최신 하이브리드 유전 알고리즘 (HGA) [5] 과 비교했습니다.
성능:
- 해의 품질: RL-CMSA 는 대부분의 설정에서 HGA 보다 평균 목적 함수 값이 더 우수했습니다. 특히 인스턴스 크기와 판매원 수 ( $m$ ) 가 증가할수록 그 우위가 두드러졌습니다.
- 강건성 (Robustness): RL-CMSA 는 40 회 독립 실행 중 최적 해를 찾은 횟수 (#b) 가 HGA 보다 훨씬 높았으며, 실행 간 변동성이 적었습니다.
- 실행 시간: $n=50, 100$ 의 경우 RL-CMSA 가 HGA 보다 빠르게 최적 해를 찾았습니다. $n=200$ 인 경우 $m$ 이 작을 때는 HGA 가 빠르거나 비슷했으나, $m$ 이 커질수록 RL-CMSA 가 더 빨라졌습니다.
- 통계적 유의성: Wilcoxon 부호 순위 검정 결과, $n=100$ 및 $n=200$ ( $m \ge 5\%$ ) 인 경우 RL-CMSA 의 성능 우위가 통계적으로 유의미하게 확인되었습니다.
검색 동역학 분석: 검색 궤적 네트워크 (STN) 분석 결과, HGA 는 넓은 검색 공간을 탐색하지만 최적 해 영역에 도달하는 데 어려움을 겪는 반면, RL-CMSA 는 초기부터 유망한 영역으로 빠르게 수렴하여 일관된 고해를 산출하는 것으로 나타났습니다.

5. 의의 및 결론 (Significance & Conclusion)

문제 해결 능력: RL-CMSA 는 작업 부하 균형이 중요한 min-max mTSP 문제를 해결하는 데 있어 기존 최첨단 알고리즘 (HGA) 을 능가하는 강력한 대안임을 입증했습니다.
하이브리드 접근법의 효과: 강화 학습을 통한 지능적인 구축 (Construct) 과 MILP 를 통한 정확한 해결 (Solve) 의 결합은 대규모 조합 최적화 문제에서 탐색과 활용의 균형을 잡는 데 매우 효과적입니다.
확장성: 판매원 수가 증가할수록 (경로가 짧아질수록) 알고리즘의 성능이 더욱 향상되는 경향을 보였으며, 이는 부분 문제의 조합적 유연성이 높아지기 때문입니다.
미래 작업: 경로 풀을 더 풍부하게 만들기 위한 대규모 neighborhood 통합, 2 차 이상의 경로 특징 학습, 그리고 더 일반적인 제약 조건이 있는 라우팅 문제로의 확장 등을 계획하고 있습니다.

이 논문은 강화 학습을 메타휴리스틱의 핵심 구성 요소로 통합하여 복잡한 물류 및 라우팅 문제를 해결하는 새로운 패러다임을 제시한다는 점에서 의미가 있습니다.