🤖 machine learning

Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints

본 논문은 수정된 JAMPR 모델에 기반하여 용량 및 시간 창 제약이 있는 중규모 픽업 및 배송 문제(CPDPTW)를 실시간으로 효과적으로 해결하고, 200개 노드를 초과하는 대규모 인스턴스에 대해 빠른 차선해를 제공하는 새로운 심층 강화 학습 접근 방식을 제시한다.

원저자: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

게시일 2026-08-17

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 번화하고 끊임없이 성장하는 도시에서 배송 트럭 함대의 선장이라고 상상해 보십시오. 당신의 업무는 수백 명의 고객에게 소포를 배달하고 반품 물품을 수거하는 것이지만, 당신에게는 엄격한 규칙이 있습니다. 트럭이 실을 수 있는 화물의 양이 정해져 있고, 모든 고객은 집에서 택배를 받을 수 있는 특정한 시간대가 정해져 있다는 점입니다. 너무 일찍 도착하거나 너무 늦게 도착하면, 혹은 트 van 뒷면에 상자를 너무 많이 쑤셔 넣으려고 하면 계획은 실패합니다. 이것이 바로 "픽업 및 배송 문제(Pickup and Delivery Problem)"이며, 사람(고객)이 늘어날수록 점점 더 어려워지는 거대한 퍼즐입니다.

수십 년 동안 컴퓨터는 이 문제를 해결하기 위해 초고속 계산기처럼 행동하며, 완벽한 경로를 찾기 위해 수백만 가지의 가능한 경로를 하나씩 테스트해 왔습니다. 하지만 도시가 성장하고 정지 지점(stops)의 수가 폭발적으로 증가함에 따라, 이 계산기들은 길을 잃게 됩니다. 그들은 인간이 몇 분 만에 스케치할 수 있는 경로를 찾는 데 몇 시간을 허비하거나, 최악의 경우 아예 포기하며 "이 문제를 풀 수 없습니다"라고 말해버립니다. 여기서 새로운 종류의 컴퓨터 두뇌가 등장합니다: 심층 강화 학습(Deep Reinforcement Learning)입니다. 이것을 계산기가 아니라, 게임을 하며 배우는 비디오 게임 캐릭터라고 생각하십시오. 모든 가능성을 계산하는 대신, 이 모델은 이 배송 게임을 수천 번 플레이하며 매 라운드마다 더 빠르고 똑똑해집니다. 즉, 모든 옵션을 일일이 확인하지 않고도 최선의 움직임을 포착하는 법을 배우는 것입니다.

이 논문에서 모스크바 국립 대학교와 러시아 과학 아카데미 우주 연구소의 안드레이 소로카(Andrew Soroka)와 그의 팀은 이 "비디오 게임 두뇌"에게 트럭의 제한된 공간과 엄격한 시간대라는 현실 세계의 복잡한 규칙을 처리하는 법을 가르치기로 했습니다. 그들은 기존의 스마트 모델인 JAMPR를 가져와서, 트럭이 한 곳에서 물건을 집어 다른 곳에서 전달해야 하는 '픽업 앤 딜리버리' 규칙(용량 제한을 준수하면서 물건을 주고받는 과정)을 이해할 수 있도록 특별한 업그레이드를 가했습니다.

연구진은 업그레이드된 모델이 중소 규모의 도시(정지 지점 50~200개)에서 속도의 제왕이라는 것을 발견했습니다. 이러한 시나리오에서 AI는 단 몇 초 만에 거의 완벽한 경로를 내놓을 수 있으며, 이는 경로를 계산하기 시작하는 데 훨씬 더 많은 시간이 걸리는 전통적인 "계산기" 방식들을 압도합니다. 이는 마치 배송 기사가 도시를 너무 잘 알아서 최적의 경로를 즉시 외칠 수 있는 반면, 구식 컴퓨터는 여전히 지도를 읽으려고 애쓰고 있는 것과 같습니다.

하지만 도시가 거대해지면(정지 지점 400~1,000개) 이야기는 조금 더 복잡해집니다. 여기서 AI는 속도 면에서는 여전히 승자입니다. 전통적인 방식들이 첫 1분 동안 유효한 경로조차 찾지 못해 헤매는 동안, AI는 거의 즉각적으로 "충분히 좋은" 해답을 제시합니다. 그러나 AI가 아직 완벽한 것은 아닙니다. 이 거대한 도시들을 위한 절대적인 최선의 경로를 얻으려면 AI는 며칠 동안 "훈련"을 해야 하는데, 이는 매우 긴 시간입니다. 훈련을 마친 후에도 가장 큰 규모의 문제에 대해서는 AI의 최종 경로가 무제한의 시간을 가진 전통적 방식이 결국 찾아낼 수 있는 최선의 솔루션보다 거리 측면에서 약 20% 더 비쌉니다. 실제로 최적화 시간이 불과 몇 분만 지나도, 전통적인 방식이 AI가 추가적인 훈련 없이 도달할 수 없는 더 나은 경로를 찾아내며 AI를 추월합니다.

팀은 또한 이 AI가 규칙이 변할 때 얼마나 강한지(toughness)도 테스트했습니다. 그들은 AI가 특정 테스트 조건 내에서 매우 신뢰할 수 있다는 것을 발견했습니다. 즉, 동일한 분포의 문제에 대해 전통적인 컴퓨터가 "불가능하다"며 포기했을 때조차, AI는 결코 실패하지 않고 어떤 식으로든 해답을 제시했습니다. 다만, 도시의 레이아웃이 급격하게 변하는 경우(예: 무작위로 퍼져 있는 집들의 형태에서 모두가 좁은 원 안에 모여 사는 패턴으로 변하는 경우), AI의 성능은 다소 떨어지지만 여데도 해결을 위한 첫 한 시간 동안은 전통적인 방식들을 능가합니다.

요약하자면, 이 논문은 심층 학습 접근 방식이 실시간 물류를 위한 강력한 새로운 도구임을 시사합니다. 이는 절대적인 완벽한 답이 필요한 가장 크고 복잡한 퍼즐을 위해 기존의 방식들을 완전히 대체하는 것이 아닙니다. 하지만 교통 체증이나 갑작스러운 주문 폭주에 대응하는 택배 서비스처럼, 지금 당장 빠르고 신뢰할 수 있는 답이 필요한 상황에서 이 AI는 게임 체인저입니다. 전통적인 도구들이 멈춰 서거나 실패하는 곳에서 빠르고 견고한 솔루션을 제공하기 때문입니다.

기술 요약: CPDPTW를 위한 심층 강화 학습

문제 정의

본 논문은 **용량 및 시간 창 제약이 있는 픽업 및 배송 문제(CPDPTW)**를 다룹로니다. 이는 차량 함대가 특정 픽업 위치에서 배송 위치까지 물품을 운송해야 하는 조합 최적화 문제입니다. 이 문제는 세 가지 주요 실세계 제약 조건으로 특징지어집니다:

용량(Capacity): 차량은 최대 부피 제한( $Q$ )을 가집니다.
시간 창(Time Windows): 고객은 특정 시간대 동안에만 이용 가능합니다.
픽업 및 배송(PDP): 표준 차량 경로 문제(VRP)와 달리, 물품은 데포(depot) 또는 고객으로부터 픽업되어 다른 고객에게 배송될 수 있으며, 엄격한 순서(픽업 후 배송)를 요구합니다.

저자들은 고전적인 접근 방식(혼합 정수 계획법, 휴리스틱 등)이 존재하지만, 실세계 제약 조건이 포함된 대규모 인스턴스(예: 노드 200개 초과)의 경우 높은 계산 부하, 새로운 제약 조건 처리에 대한 유연성 부족, 또는 합리적인 시간 내에 실행 가능한 솔루션을 찾는 데 실패하는 등의 어려움을 겪는다고 언급합니다.

방법론

저자들은 수정된 JAMPR (Joint Attention Model for Pickup and Routing) 아키텍처를 기반으로 한 심층 강화 학습(DRL) 접근 방식을 제안합니다.

모델 아키텍처

기반(Base): 이 모델은 Attention Model(AM)과 Pointer Networks를 확장한 JAMPR 프레임워크를 기반으로 구축되었습니다. 이는 자기 주의(self-attention) 메커니즘을 갖춘 인코더-디코더 구조를 활용합니다.
상태 표현(State Representation): 문제는 마르코프 결정 과정(MDP)으로 모델링됩니다.
- 인코더(Encoder): 노드 특징(좌표, 수요, 시간 창)을 은닉 임베딩 벡터로 인코딩합니다.
- 컨텍스트( $C(t)$ ): 문제 그래프 임베딩, 데포 인덱스, 마지막으로 추가된 노드, 그리고 남은 차량 용량을 포함합니다.
- 확장된 컨텍스트(Extended Context): PDP 및 시간 창을 처리하기 위해, 구성된 경로와 차량 특성(잔여 용량, 현재 노드, 현재 시간)에 대한 특정 임베딩을 완전 연결 신경망(fully connected neural networks)에 통합합니다. 이를 통해 여러 경로의 병렬 구축이 가능합니다.
행동 공간(Action Space): 행동은 활성 경로 $r$ 에 추가될 노드 $i$ 를 선택하는 쌍 $(r, i)$ 로 정의됩니다. 제약 조건(용량, 시간 창, PDP 순서)을 위반하지 않도록 **실행 가능성 마스크(feasibility mask)**가 적용됩니다.
정책(Policy): 디코더는 실행 가능한 노드들에 대한 어텐션 점수를 계산합니다. 이 점수들은 그리디(greedy) 선택에 사용되거나 훈련 중 소프트맥스(softmax) 분포를 통해 샘플링됩니다.

CPDPTW를 위한 수정 사항

저자들은 PDP의 특성을 해결하기 위해 표준 JAMPR 모델에 특정 수정 사항을 도입했습니다:

PDP 마스킹(PDP Masking): 배송 순서 제약(해당하는 배송이 픽업보다 먼저 일어나야 함)을 강제하기 위해 feasible() 함수에 추가적인 마스크를 도입했습니다.
연성 제약 처리(Soft Constraint Handling): 모든 고객에 대해 100% 실행 가능한 솔루션을 찾는 것이 하드 포뮬레이션(hard formulations)에서는 때때로 불가능하다는 점을 인식하여, 저자들은 SOFT 설정을 채택했습니다. 최종 비용 함수는 총 이동 거리와 누락된 고객 수의 선형 결합(각각 13:10의 가중치)입니다. 이는 모델이 부분적인 솔루션이라도 항상 생성할 수 있도록 보장합니다.

훈련 및 데이터

데이터 생성: 인스턴스는 Solomon R201 분포를 기반으로 생성되었습니다. 문제 규모는 50에서 1000개의 노드로 구성되었습니다. 트럭 용량과 시간 지평(time horizons)은 문제 규모에 따라 스케일링되었습니다.
훈련: 모델은 강화 학습을 사용하여 훈련되었으며, 조기 종료 기준(10단계 동안 비용 감소가 없는 경우)을 적용했습니다. 훈련 시간은 문제 규모에 따라 크게 달랐으며, 50개 노드 문제의 경우 3시간에서 1000개 노드 문제의 경우 336시간 이상까지 소요되었습니다.
베이스라인(Baseline): 제안된 모델은 실무에서 사용되는 표준 휴리스틱 솔버인 Google OR-Tools와 비교되었습니다.

주요 결과

성능은 세 가지 문제 규모 카테고리에 걸쳐 평가되었습니다:

1. 소규모 규모 (50 노드)

성능: 훈련된 JAMPR 모델은 빠른 최적 솔루션을 제공했으며, 최적화 초기 몇 초 동안 휴리스틱 솔루션보다 더 나은 비용을 기록했습니다.
비용: 최적화 시간이 증가함에 따라 JAMPR 모델의 결과는 점진적으로 OR-Tools의 결과에 근접했습니다. 광범위한 훈련(723 에포크) 후, 최종 결과는 OR-Tools 베이스라인과 0.3% 이내의 차이를 보였습니다.
실행 가능성: JAMPR은 100%의 인스턴스를 해결한 반면, OR-Tools는 문제 복잡도가 증가함에 따라 점점 더 많은 수의 인스턴스에서 솔루션을 찾는 데 실패했습니다.

2. 중규모 규모 (100–200 노드)

성능: 모델은 메타휴리스틱보다 최적화 초기 단계(15~200초)에서 더 우수한 빠른 아합리적(suboptimal) 솔루션을 제공했습니다.
수렴: 모델의 성능은 빠르게 정체되었지만, 속도 측면에서는 지속적으로 OR-Tools를 능가했습니다. OR-Tools는 유사한 비용 수준에 도달하기 위해 훨씬 더 긴 최적화 시간을 필요로 했습니다.
실행 가능성: JAMPR은 0%의 실패율을 유지하며 모든 인스턴스를 해결한 반면, OR-Tools는 규모가 커짐에 따라 실행 가능한 솔루션을 찾는 데 실패하는 비율이 높아졌습니다.

3. 대규모 규모 (400–1000 노드)

성능: 고차원 문제에 대해서도 신경망 모델은 여전히 OR-Tools보다 훨씬 나은(OR-Tools는 종종 솔루션을 찾지 못하는 시점인) 첫 60초 동안 빠른 아합리적 솔루션을 제공했습니다.
한계: 최적화 시간이 증가함에 따라 메타휴리스틱(OR-Tools)이 결국 신경망 모델을 앞질렀습니다. 최대 최적화 시간 동안의 JAMPR 최종 결과는 메타휴리스틱에 비해 경로 비용이 약 20% 손실되었습니다.
훈련 비용: 대규모 인스턴스의 훈련은 계산 비용이 매우 높았습니다(예: 1000개 노드에 대해 336시간). 이는 단일 GPU 환경에서 합리적인 시간 내에 모델을 완전히 최적화하는 데 제약을 주었습니다.

강건성 분석 (Robustness Analysis)

분포 변화(Distribution Shift): 모델은 데이터 분포 변화에 대한 강건성을 입증했습니다. 균등 분포(uniform)와 정규 분포(normal)가 혼합된 데이터로 테스트했을 때, 새로운 분포의 데이터가 최대 25% 포함되어 있음에도 불구하고 모델은 빠른 아합리적 솔루션을 제공하는 능력을 유지했습니다.
지표 불변성(Metric Invariance): 거리 계산을 유클리드(Euclidean)에서 맨해튼(Manhattan) 메트릭으로 전환했을 때도 모델의 성능은 일관되게 유지되었습니다.

의의 및 주장

본 논문은 CPDPTW 문제를 해결하기 위해 (수정된 JAMPR 모델을 사용한) 심층 강화 학습을 성공적으로 적용한 첫 사례라고 주장합니다.

저자들은 세 가지 주요 기여를 강조합니다:

속도와 품질의 트레이드오프: 모델은 최적화 초기 단계에서 클래식 휴리스틱보다 종종 더 우수한 빠른 아합리적 솔루션(0.1초 단위)을 제공합니다. 이는 엄격한 시간 제한이 있는 동적 시스템에서 특히 가치가 있습니다.
강건성 및 실행 가능성: 대규모 또는 복잡한 인스턴스에서 실행 가능한 솔루션을 찾지 못할 수 있는 전통적인 메타휴리스틱과 달리, 신경망 모델은 (누락된 고객에 페널티를 부여하는 SOFT 설정 하에서) 모든 문제 인스턴스에 대해 솔루션을 생성함을 보장합니다.
솔루션 존재의 확장성: 모든 테스트된 규모에서 신경망 모델의 실패율은 0을 유지하는 반면, OR-Tools의 실패율은 문제 규모가 커짐에 따라 증가합니다.

저자들은 딥 RL 모델이 현재 대규모 문제를 위해 상당한 훈련 시간을 필요로 하고, 매우 큰 인스턴스에 대해 메타휴리스틱의 최종 최적성에 아직 미치지 못할 수도 있지만, 실시간 라우팅 최적화(속도와 솔루션 존재 여부가 중요한 분야)에서 유망한 방향임을 결론짓습니다. 그들은 향후 연구로 이러한 RL 모델을 혼합 정수 계획법(MIP) 솔버와 결려하거나, 고차원 문제를 더 효과적으로 처리하기 위해 학습된 파티셔닝 정책을 사용하는 것을 제안합니다.