Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

기술 요약: Smart Routes – 현실적인 제약 조건이 있는 차량 경로 문제 해결을 위한 알고리즘 개발 및 비교 시스템

문제 정의
본 논문은 운송 물류의 핵심 과제인 용량 제한(capacity limits)과 배송 시간 창(delivery time windows)을 가진 고객들을 서비스하기 위해 차량 함대의 경로를 최적화하는 용량 제한 시간 창 차량 경로 문제(CVRPTW)를 다룹니다. 저자들은 수학적 정밀 접근 방식이 이론적으로는 최적해를 산출할 수 있지만, 문제의 차원이 증가함에 따라 지수적 복잡성으로 인해 적용이 심각하게 제한된다는 점을 강조합니다. 따라서 성장하는 도시 인구와 복잡한 제약 조건을 포함하는 실제 시나리오를 고려할 때, 솔루션의 품질과 탐색 시간 사이의 균형을 맞추는 것이 필요합니다. 나아가, 저자들은 연구자들이 시스템 아키텍처를 변경하지 않고도 다양한 알고리즘적 접근 방식(정밀 해법, 휴리스틱, 딥러닝)을 원활하게 통합, 비교 및 시각화할 수 있는 통합 플랫폼이 부족하다는 점을 식별했습니다.

방법론
본 연구는 CVRPTW 인스턴스에 적용되는 세 가지 뚜렷한 알고리즘 클래스에 대한 비교 분석을 수행합니다:

1. 정밀 방법(Exact Methods): 저자들은 최적해를 찾기 위해 Branch&Bound, Cutting Plane, 그리고 Branch&Cut 알고리즘을 사용하는 SCIP 최적화 스위트를 활용합니다.
2. 고전적 휴리스틱(Classical Heuristics): 본 연구는 구성적(constructive) 및 메타휴리스틱 접근 방식을 평가하며, 구체적으로 Lin-Kernighan (LKH) 휴리스틱, 2-OPT, 3-OPT 지역 탐색 방법, 그리고 Google의 OR-Tools 프레임워크를 사용합니다.
3. 심층 강화 학습(Deep Reinforcement Learning, DRL): 저자들은 수정된 버전의 JAMPR(Joint Attention Model for Pickup and Delivery with Time Windows) 모델을 활용합니다. 이 아키텍처는 특정 제약 조건을 처리하기 위해 디코더 출력에 학습 가능한 행렬($M+$)을 추가함으로써 어텐션 모델(Attention Model, AM)을 적응시킨 것입니다. 이 모델은 경로 구축을 순차적 의사결정 과정(마르코프 결정 과정)으로 취급하며, 여기서 상태(state)는 현재 경로와 미방문 노드를 포함하고, 행동(action)은 다음 노드를 선택하는 것을 포함합니다.

이러한 비교를 용이하게 하기 위해 저자들은 Smart Routes라는 커스텀 소프트웨어 플랫폼을 개발했습니다. 이 시스템은 다음과 같은 특징을 가집니다:

• 모듈형 아키텍처: 데이터 생성 및 로딩을 위한 데이터셋 모듈(Dataset module), 사용자 정의 또는 내장 모델의 훈련 및 평가를 위한 알고리즘 모듈(Algorithm module), 그리고 지표 생성 및 시각화를 위한 솔루션 모듈(Solution module)로 구성됩니다.
• 확장성: 사용자는 베이스 클래스를 상속받아 커스텀 알고리즘을 통합할 수 있으며, 이를 통해 핵심 시스템을 수정하지 않고도 새로운 아이디어를 테스트할 수 있습니다.
• 시각화: 플랫폼은 경로를 시각화하고 시간에 따른 경로 비용을 비교하는 성능 그래프를 생성하는 대화형 웹 인터페이스를 제공합니다.

실험 설정
실험은 Solomon R201 벤치마크 세트를 기반으로 생성된 인공 데이터셋을 사용하여 50개 및 100개 노드 규모에 초점을 맞추어 수행되었습니다.

• 제약 조건: 문제는 방문하지 않은 고객을 페널티 비용과 함께 건너뛸 수 있는 "소프트(soft)" 설정에서 해결되었습니다.
• 하드웨어: 테스트는 NVIDIA Tesla A40 GPU와 Intel Xeon Gold CPU가 장착된 서버에서 실행되었습니다.
• 시간 제한: 휴리스틱 및 DRL 방법에는 50개 노드의 경우 100초, 100개 노드의 경우 200초의 시간이 주어졌습니다. 정밀 방법(SCIP)은 최적해를 찾기 위해 훨씬 긴 시간인 각각 1000초와 2000초가 할당되었습니다.

주요 결과
비교 분석을 통해 다음과 같은 결과가 도출되었습니다:

• 50개 노드 인스턴스: 고전적 휴리스틱(LKH, OR-Tools)과 딥 강화 학습 모델(JAMPR) 모두 빠르게 차선해(suboptimal solutions)를 생성했습니다. 첫 10초 이내에 SCIP의 솔루션 품질은 이러한 방법들보다 열등했습니다. SCIP는 약 100초 후에 이들을 추월했지만, DRL 모델과 정밀 해법 사이의 최종 격차는 5% 미만이었습니다.
• 100개 노드 인스턴스: 정밀 방법의 한계가 뚜렷하게 나타났습니다. SCIP는 동일한 경로 비용을 달리는 데 휴리스틱 및 DRL 방법보다 약 13배 더 긴 시간이 소요되었습니다. 또한, 할당된 시간 내에 SCIP는 최적해를 찾는 데 실패했으며, 그 첫 번째 실행 가능한 솔루션은 OR-Tools 및 JAMPR가 제공한 것보다 약 50% 더 높은 비용을 기록했습니다.
• 확장성(Scalability): 문제의 차원이 두 배로 증가함에 따라 SCIP가 솔루션을 찾는 데 필요한 시간은 약 14배 증가한 반면, 휴리스틱 및 신경망 접근 방식의 성능은 비교적 안정적으로 유지되었습니다. 이는 정밀 방법이 100개 이상의 노드 문제에서는 실행 불가능해짐을 시사합니다.

의의 및 주장
본 논문은 두 가지 주요 기여를 주장합니다:

1. Smart Routes 플랫폼: VRP를 위한 정밀, 휴리스틱 및 딥러닝 접근 방식을 통합하는 통합적이고 확장 가능한 환경입니다. 저자들은 이 시스템이 딥 강화 학습을 지원하고, 내장된 시각화를 제공하며, 커스텀 알고리즘의 용이한 통합을 허용함으로써 기존 프레임워크(OR-Tools, Gurobi, SCIP 등)에 비해 상당한 이점을 제공한다고 주장합니다.
2. 접근 방식의 경험적 검증: 본 연구는 중간 규모의 문제(50개 노드)에 대해 고전적 휴리스틱과 딥 강화 학습이 정밀 솔버에 비해 솔루션 품질과 계산 시간 사이에서 우수한 트레이드오프를 제공한다는 종합적인 비교를 제공합니다. 더 큰 인스턴스(100개 노드)의 경우, 본 논문은 정밀 방법이 지수적 시간 성장으로 인해 실질적으로 불가능하다고 결론짓는 한편, 딥 강화 학습과 고급 휴리스틱이 빠르고 고품질인 차선해를 제공한다고 결론지었습니다.

저자들은 자신들의 연구를 글로벌 도시 성장 속에서 보다 효율적인 경로 최적화를 향한 단계로 위치시키며, 이 플랫폼이 물류 분야에서 새로운 알고리즘 아이디어를 신속하게 테스트하고 비교하는 것을 용이하게 한다고 강조합니다.