A Novel Hybrid Heuristic-Reinforcement Learning Optimization Approach for a Class of Railcar Shunting Problems

이 논문은 철도 차량 분류 문제를 해결하기 위해 철도 특화 휴리스틱과 Q-학습을 결합한 하이브리드 휴리스틱 - 강화학습 (HHRL) 프레임워크를 제안하고, 이를 통해 한쪽 또는 양쪽 접근이 가능한 분류 선로 환경에서 효율적이고 고품질의 최적화 해법을 제공함을 보여줍니다.

핵심

🚂 1. 문제 상황: 기차yard의 혼란스러운 주차장

상상해 보세요. 거대한 기차yard에는 수백 개의 화차 (화물칸) 가 있습니다. 각 화차는 서로 다른 목적지로 가야 합니다. 하지만 지금 이 화차들은 제멋대로 섞여 있죠.

• 목표: 목적지별로 화차들을 모아서 새로운 열차를 만들어야 합니다.
• 난관: 화차들은 철로에 쌓여 있는데, 한쪽 끝에서만 접근할 수 있는 경우 (스택 구조) 와 양쪽에서 접근할 수 있는 경우 (큐 구조) 가 다릅니다.
  • 한쪽 끝만 열려 있는 경우 (OS-RSP): 스프링이 달린 접시처럼, 마지막에 들어온 것만 먼저 꺼낼 수 있습니다 (LIFO). 마치 책상 서랍에 책을 꽂아두면, 가장 위에 있는 책만 빼낼 수 있는 것과 같습니다.
  • 양쪽 끝이 열려 있는 경우 (TS-RSP): 열차yard 양쪽에 기관차가 있어서, 앞에서 넣은 것을 뒤에서 꺼낼 수도 있습니다 (FIFO). 마치 줄을 서서 기다리는 은행 창구처럼, 먼저 온 사람이 먼저 나가는 방식도 가능해집니다.

문제는 화차들이 너무 많고, 목적지도 제각각이라서 **"어떤 순서로 움직여야 가장 빠르고 연료를 아낄 수 있을까?"**를 계산하는 것이 매우 어렵다는 점입니다. 이 문제는 수학적으로도 매우 복잡한 'NP-하드' 문제입니다.

---

🧠 2. 해결책: "현장 노련한 선장"과 "AI 학습자"의 결혼

저자들은 이 난제를 해결하기 위해 두 가지 힘을 합쳤습니다. 바로 **Hybrid Heuristic-Reinforcement Learning (HHRL)**입니다.

① 현장의 지혜 (휴리스틱): "요령 있는 선장"

인공지능이 처음부터 모든 것을 배우려 하면 시간이 너무 오래 걸립니다. 그래서 먼저 현장에서 일하는 선장들의 경험칙을 적용합니다.

• 미리 정리하기 (Preprocessing): 이미 목적지에 있는 화차는 건드리지 않고 빼냅니다. 같은 목적지로 가는 화차들은 미리 묶어줍니다.
• 작은 덩어리로 나누기 (Batching): 모든 화차를 한 번에 처리하려 하지 않고, 작은 그룹 (배치) 으로 나누어 하나씩 처리합니다.
• 효과: 이렇게 하면 AI 가 고민해야 할 경우의 수가 하늘에서 땅으로 떨어집니다.

② AI 의 학습 (강화학습): "게임처럼 배우는 로봇"

정리된 작은 덩어리들을 처리할 때 Q-learning이라는 AI 기술을 사용합니다.

• 게임 방식: AI 는 화차를 움직일 때마다 보상을 받습니다.
  • 화차를 잘 옮기면 **점수 (+)**를 받습니다.
  • 비효율적으로 움직이거나 연료를 많이 쓰면 **점수 (-)**를 받습니다.
  • 모든 화차를 목적지에 잘 도착시키면 큰 보너스를 받습니다.
• 학습: AI 는 수백만 번의 시뮬레이션을 통해 "어떤 상황에서 어떤 화차를 어디로 보내야 점수가 가장 잘 나오는지" 스스로 학습합니다.

---

🔄 3. 두 가지 전략: 한쪽 기관차 vs 양쪽 기관차

이 논문은 두 가지 시나리오를 다뤘습니다.

1. 한쪽 기관차 (OS-RSP): yard 한쪽 끝에만 기관차가 있습니다. 스택 (LIFO) 방식이라서 마지막에 들어온 화차부터 꺼내야 합니다.
2. 양쪽 기관차 (TS-RSP): yard 양쪽 끝에 기관차가 두 대 있습니다. 앞쪽 기관차는 앞에서, 뒤쪽 기관차는 뒤에서 동시에 일을 합니다.
   • 핵심 아이디어: 양쪽 기관차가 있는 복잡한 문제를, 두 개의 한쪽 기관차 문제로 쪼개서 동시에 해결합니다. 마치 큰 짐을 두 사람이 나눠서 나르는 것과 같습니다.
   • 결과: 두 대의 기관차가 동시에 일하면, 작업 시간이 약 20~45% 단축되었습니다! (양쪽에서 동시에 일을 하니까 당연히 빠르죠.)

---

📊 4. 실험 결과: 왜 이 방법이 좋은가?

저자들은 120 가지의 다양한 시나리오 (작은 yard부터 거대한 yard까지) 로 실험을 해보았습니다.

• 기존 방법 (수학적 최적화): 작은 문제에서는 정답을 찾지만, 문제가 커지면 12 시간 이상 걸려도 답을 못 찾습니다. (컴퓨터가 너무 많은 경우를 다 계산해야 해서 지칩니다.)
• 기존 휴리스틱 (경험칙): 빠르지만, 최적의 답이 아닐 때가 많습니다.
• 새로운 HHRL 방법:
  • 속도: 큰 문제에서도 몇 분 안에 좋은 답을 찾습니다.
  • 정확도: 작은 문제에서는 거의 완벽한 정답 (오차 0%) 을 냈고, 큰 문제에서도 기존 방법보다 훨씬 좋은 결과를 냈습니다.

---

💡 5. 요약: 이 논문이 우리에게 주는 교훈

이 논문은 **"인공지능이 모든 것을 처음부터 배우려 하지 말고, 인간의 경험 (지혜) 을 먼저 활용하고, 그 위에 AI 를 얹어 학습시키면 훨씬 효율적이다"**는 것을 증명했습니다.

• 비유하자면:
  • 기존 방법: 모든 길을 다 걸어보면서 가장 빠른 길을 찾으려다 지쳐버린 탐험가.
  • 이 논문: 현지 가이드 (휴리스틱) 가 "저기 길이 짧아요"라고 알려주고, AI 가 그 길에서 "어떤 발걸음으로 걷는 게 가장 빠를까?"를 빠르게 학습하는 방법입니다.

이 기술은 기차yard뿐만 아니라, 컨테이너 항구에서 크레인이 컨테이너를 정리하는 일이나 공장에서의 자재 이동 등, 무언가를 쌓고 꺼내야 하는 모든 복잡한 상황에 적용될 수 있습니다.

기술 요약

1. 문제 정의 (Problem Definition)

이 논문은 화물 철도 야드 (Railyard) 에서의 차량 분류 (Shunting) 문제를 다룹니다. 야드 계획자는 도착 열차를 해체하고 목적지별로 재결합하여 출발 열차를 구성해야 합니다.

• 차량 분류의 두 가지 구성:
  • 일측 접근 (One-sided, OS-RSP): 모든 선로가 한쪽 끝 (스위치 단) 에서만 접근 가능합니다. 이는 스택 (Stack) 구조로, 후입선출 (LIFO) 순서로 차량을 인출합니다.
  • 양측 접근 (Two-sided, TS-RSP): 선로의 양쪽 끝에서 모두 접근 가능합니다. 이는 큐 (Queue) 구조를 지원하며, 선로에 따라 선입선출 (FIFO) 또는 후입선출 (LIFO) 순서를 혼용할 수 있습니다. 두 대의 기관차가 동시에 양쪽 끝에서 작업을 수행할 수 있어 유연성이 높지만, 계획의 복잡성이 급증합니다.
• 목표: 여러 출발 열차를 구성하기 위해 차량 그룹 (동일 목적지를 가진 연속된 차량들) 을 분류 선로에서 출발 선로로 이동시키는 일련의 이동 순서를 찾아 총 분류 비용 (기관차 이동 거리 및 노력) 을 최소화하는 것입니다.
• 난이도: 이 문제는 NP-hard 문제로 알려져 있으며, 특히 차량과 선로의 수가 많을 경우 전통적인 최적화 기법으로 해결하기 어렵습니다.

2. 제안된 방법론 (Methodology)

저자들은 복잡한 TS-RSP 문제를 해결하기 위해 하이브리드 휴리스틱 - 강화 학습 (HHRL) 프레임워크를 제안했습니다. 이 프레임워크는 크게 세 단계로 구성됩니다.

2.1 문제 분해 (Decomposition)

• TS-RSP 를 OS-RSP 로 변환: 양측 접근 문제 (TS-RSP) 를 두 개의 결합된 일측 접근 하위 문제 (Subproblem A 와 B) 로 분해합니다.
• 분할 전략: 각 선로에 있는 차량 그룹들을 두 기관차의 작업 영역으로 나눕니다.
  • APS (A-Preferential Split): 홀수 개의 그룹이 있을 때 A 쪽에 더 많은 그룹을 할당.
  • ROBS (Rotating Odd-Balance Split): 홀수 개의 그룹이 있을 때 A 와 B 쪽을 번갈아 가며 할당하여 부하를 균형 있게 분산.
• 이를 통해 양측 문제를 병렬로 해결 가능한 일측 문제로 변환합니다.

2.2 전처리 (Preprocessing)

Q-learning 의 상태 - 행동 공간 (State-Action Space) 을 축소하기 위해 초기 야드 구성을 표준화하는 5 단계 전처리 과정을 거칩니다.

1. 불필요한 그룹 제거: 이미 목적지 선로에 있거나 분류 선로 끝단에 있는 불필요한 그룹 제거.
2. 머리 그룹 병합 (Head-group Merging): 인접한 선로에 있는 동일 목적지 그룹을 하나로 통합하여 그룹 수 감소.
3. 상위 분류 선로 집중: 모든 차량 그룹을 가장 상위 분류 선로 (Top Classification Track) 로 이동시켜 단일 열차 형성.
4. 목적지 없는 그룹 제거: 분류 선로에 있는 목적지 없는 그룹을 다른 선로로 이동시켜 제거.
5. 선로 축소: 불필요한 분류 선로를 제거하여 표준화된 레이아웃 생성.

2.3 고정 f-그룹 배칭 (Fixed f-Group Batching)

• 표준화된 상태에서 차량 그룹을 고정된 크기 $f$의 배치 (Batch) 로 나눕니다.
• 각 배치마다 Q-learning을 독립적으로 적용하여 정책을 학습합니다.
• 이 방식은 전체 상태 공간을 탐색하지 않고도 각 작은 서브문제에 대해 효율적으로 학습을 수행하게 하여 확장성 (Scalability) 을 확보합니다.

2.4 Q-learning 모델

• 상태 (State): 각 선로에 있는 차량 그룹의 순서.
• 행동 (Action): 한 선로에서 다른 선로로 연속된 차량 그룹을 이동시키는 것.
• 보상 (Reward): 이동 비용의 음수값 (비용 최소화) 및 모든 차량이 목적지에 도달했을 때의 완료 보너스.
• 학습: $\epsilon$-greedy 전략을 사용하여 탐색과 활용을 균형 있게 조절하며 Q-table 을 업데이트합니다.

3. 주요 기여 (Key Contributions)

1. 양측 문제의 분해 알고리즘: TS-RSP 를 두 개의 결합된 OS-RSP 하위 문제로 변환하는 두 가지 매핑 함수 (APS, ROBS) 를 도입하여 두 기관차의 조정을 명시적으로 고려합니다.
2. RL 기반 모델링: OS-RSP/TS-RSP 를 Q-learning 에 적합하도록 재구성했습니다. 단일 차량뿐만 아니라 연속된 차량 그룹을 유연하게 이동시키고, 분류 - 분류, 분류 - 출발, 출발 - 출발 간 모든 선로 이동을 지원합니다.
3. 확장성 있는 HHRL 프레임워크: 대규모 실증 문제에 적용 가능하도록 도메인 특화 휴리스틱 (전처리, 배칭) 과 Q-learning 을 통합했습니다. 이는 상태 - 행동 공간을 축소하고 탐색을 유도하여 계산 효율성을 극대화합니다.
4. 광범위한 실험 검증: 120 개의 테스트 인스턴스 (소형, 중형, 대형) 를 통해 제안된 알고리즘의 효율성을 입증했습니다.
5. TS-RSP 의 효율성 입증: 양측 접근 방식이 일측 접근 방식보다 메이크스팬 (작업 완료 시간) 을 크게 단축함을 통계적으로 증명했습니다.

4. 실험 결과 (Results)

• 실험 환경: Apple M3 Pro 칩, 18GB 메모리. 60 개의 OS-RSP 및 60 개의 TS-RSP 인스턴스 (소/중/대형 각 20 개씩).
• OS-RSP 성능 비교:
  • MIP (혼합 정수 계획법) 및 기존 휴리스틱 (ARG-DP) 과 비교:
  • 소형/중형: HHRL 은 MIP 가 최적해를 찾은 경우와 유사하거나 더 좋은 성능을 보였습니다 (중형 6 개 사례에서 0% 최적성 간격 달성).
  • 대형/해결 불가 사례: MIP 와 ARG-DP 는 12 시간 시간 제한 내에 해를 찾지 못한 14 개의 중형 사례 및 모든 대형 사례에서 HHRL 이 모든 인스턴스에 대해 합리적인 시간 (평균 178~332 초) 내에 실행 가능한 해를 생성했습니다.
• TS-RSP 성능 비교 (APS vs ROBS):
  • ROBS가 APS보다 평균 메이크스팬이 더 짧아 작업 효율성이 높았습니다 (작업 시간 22.85% ~ 44.75% 단축).
  • 반면, ROBS 는 전체 분류 비용 (Objective Value) 이 APS 보다 약간 높았으며, 이는 작업 시간 단축과 비용 최소화 사이의 트레이드오프를 보여줍니다.
• 통계적 유의성: t-검정 결과, TS-RSP 의 메이크스팬이 OS-RSP 보다 통계적으로 유의미하게 짧음이 확인되었습니다 ($p < 10^{-10}$).

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

• 실용적 가치: 기존에 NP-hard 문제로 인해 대규모 야드 계획에 적용하기 어려웠던 복잡한 분류 문제를, 휴리스틱과 강화 학습을 결합한 HHRL 을 통해 실용적인 시간 내에 해결할 수 있음을 입증했습니다.
• 운영 효율성: 양측 접근 (Two-sided) 야드 구성이 두 대의 기관차를 활용함으로써 작업 시간을 획기적으로 단축할 수 있음을 보여주어, 현대 화물 야드의 혼잡 완화 및 시간 민감성 대응 능력 향상에 기여합니다.
• 확장성: 이 프레임워크는 컨테이너 야드의 컨테이너 재배치 문제나 철강 슬래브 관리 문제 등 스택 구조와 우선순위가 필요한 다른 조합 최적화 문제에도 적용 가능합니다.
• 향후 연구: 출발 선로의 사전 결정이 없는 상황, 동적 차량 유입/유출 등 불확실성이 포함된 확률적 환경, 그리고 더 큰 상태 공간을 처리하기 위한 Deep Q-Network (DQN) 적용 등을 향후 연구 과제로 제시했습니다.

요약하자면, 이 논문은 복잡한 철도 차량 분류 문제를 해결하기 위해 도메인 지식 (휴리스틱) 과 데이터 기반 학습 (RL) 을 융합한 혁신적인 프레임워크를 제안하며, 이를 통해 기존 최적화 기법의 한계를 극복하고 운영 효율성을 크게 향상시켰음을 입증했습니다.