대규모 VRPTW를 위한 LLM 연계 2단계 클러스터링 초기해 기반 유전알고리즘

국문 초록 (Abstract)

본 연구는 전자상거래 및 풀필먼트 환경에서 반복적으로 발생하는 시간창 제약 차량 경로 문제(Vehicle Routing Problem with Time Windows, VRPTW)를 대상으로, 메타휴리스틱과 대규모 언어모델(Large Language Model, LLM)을 결합한 새로운 하이브리드 최적화 프레임워크를 제안한다. VRPTW는 차량 용량, 고객별 서비스 시간창, 디포 운영시간 등 다양한 제약을 동시에 고려해야 하는 조합최적화 문제로서, 문제 규모가 커질수록 정확해법의 적용 가능 범위가 급격히 축소된다. 이에 따라 실제 물류 운영에서는 유전 알고리즘(Genetic Algorithm, GA)을 비롯한 메타휴리스틱이 널리 활용되고 있으며, 특히 초기해의 품질과 파라미터 설정이 해의 성능과 안정성에 큰 영향을 미치는 것으로 알려져 있다.

본 논문에서는 먼저 VRPTW를 거리 최소화를 목표로 하는 수리적 모형으로 정식화하고, 정수형 이중 구조 염색체와 2-opt 로컬 서치를 결합한 GA를 설계한다. 이어서 고객의 공간 분포를 반영하기 위해 DBSCAN–K-means 기반 2단계 클러스터링 모듈을 도입하여 초기해를 생성함으로써, 지리적으로 타당한 경로 구조를 가진 해 집단에서 탐색을 시작하도록 한다. 이러한 클러스터링 기반 초기화는 기존의 무작위 또는 단순 휴리스틱 초기화에 비해 GA의 수렴 속도와 해 품질을 개선하는 것을 목표로 한다. 여기에 더해, 본 연구의 핵심적인 차별점으로 LLM과 In-Context Learning(ICL)을 활용한 클러스터 파라미터 자동 튜닝 메커니즘을 제안한다. LLM은 해를 직접 구성하지 않고, 파일럿 실험에서 축적한 인스턴스 특성–파라미터–성능 로그를 프롬프트의 예시로 제공받아, 새로운 인스턴스에 적합한 DBSCAN 반경(ε), 최소 점 개수(MinPts), K-means 클러스터 수(k)를 추천하는 오프라인 클러스터링 파라미터 튜너로 동작한다. GA의 세대 수, 집단 크기, 교차·돌연변이 연산자 등은 고정된 상태에서, LLM은 인스턴스 특성에 따라 클러스터링 파라미터만 조정하여 초기해 품질과 탐색 출발점을 개선하는 역할을 수행한다.

실험에서는 Solomon VRPTW 벤치마크 인스턴스(C/R/RC 유형)를 대상으로, (1) 무작위/단순 초기화를 사용하는 기본 GA, (2) 고정 파라미터를 사용하는 클러스터링 GA, (3) LLM이 제안한 파라미터를 사용하는 제안 방법을 동일한 GA 코어 하에서 비교한다. 평가 지표로는 총 이동거리, 차량 수, 수렴 패턴, 근사최적해 도달 세대수, 반복 실험 간 분산(안정성), 상대 개선도를 사용하였다. 결과적으로 클러스터링 기반 방법은 기본 GA보다 우수한 성능을 보였으며, 그 중에서도 LLM–ICL 기반 파라미터 튜닝을 적용한 방법은 특히 혼합 분포(RC형) 인스턴스에서 추가적인 거리·안정성 개선을 보였다. 이를 통해 본 연구는 메타휴리스틱 상단에 LLM 기반 “자동 튜너”를 부착하는 방식이 VRPTW와 같은 대규모 물류 최적화 문제에서 실질적인 성능 향상을 가져올 수 있음을 보여준다.

다국어 초록 (Multilingual Abstract)

This paper proposes a hybrid framework for the Vehicle Routing Problem with Time Windows (VRPTW) in e-commerce fulfillment by combining a genetic algorithm (GA), two-stage clustering initialization (DBSCAN–K-means), and an LLM-based parameter auto-tuner using in-context learning (ICL). The GA uses an integer-based dual-structure chromosome and 2-opt local search, while clustering generates geographically coherent initial solutions to improve convergence and solution quality. The LLM does not construct routes; instead, it recommends instance-specific clustering parameters (DBSCAN ε/MinPts and K-means k) from pilot logs of instance features and performance, thereby improving the starting population with fixed GA settings. Experiments on Solomon VRPTW benchmarks (C/R/RC) show that clustering initialization outperforms a baseline GA, and LLM–ICL tuning yields additional distance and stability gains, especially on RC-type instances.

목차 (Table of Contents)

• 제 1 장 서론 1
• 제 1 절 연구 배경 및 목적 1
• 제 1 항 전자상거래의 성장 1
• 제 2 항 풀필먼트 시스템과 입고 물류 최적화 2
• 제 3 항 차량 경로 문제(Vehicle Routing Problem, VRP) 3
• 제 4 항 문제 정의 4
• 제 5 항 연구목적 5
• 제 2 장 이론적 배경 및 선행연구 8
• 제 1 절 차량경로문제 및 VRPTW(VRP with Time Window) 8
• 제 1 항 VRP의 정의 및 변형 문제 9
• 제 2 항 VRPTW 문제 정의 11
• 제 3 항 VRPTW 방법론 13
• 제 2 절 유전알고리즘(Genetic Algorithm)과 지역 탐색 18
• 제 1 항 GA의 기본 개념 18
• 제 2 항 VRPTW에서의 염색체 표현 방식 19
• 제 3 항 2-opt 등 경로 기반 지역 탐색과 GA의 결합 구조 21
• 제 3 절 클러스터링 기반 초기해 생성 22
• 제 1 항 VRP/VRPTW 연구에서의 클러스터링 22
• 제 2 항 K-means, DBSCAN, 극좌표(θ, r) 특성 추출 개념 23
• 제 3 항 2-Stage Clustering 구조와 장단점 24
• 제 4 절 대규모 언어모델 (Large Language Model)과 에이전트 AI 25
• 제 1 항 대규모 언어모델의 개념과 특징 25
• 제 2 항 에이전트 AI의 개념 26
• 제 3 항 최적화/스케줄링에서의 LLM 활용 사례 27
• 제 5 절 In-Context Learning(ICL) 29
• 제 1 항 ICL의 개념 29
• 제 2 항 프롬프트 내 예시 제공을 통한 암묵적 학습 매커니즘 29
• 제 3 항 전통적인 학습과 ICL의 비교 30
• 제 6 절 종합 선행연구 분석 및 연구 공백 31
• 제 1 항 VRPTW+GA+지역 탐색 선행연구 정리 31
• 제 2 항 클러스터링 기반 초기해 및 하이브리드 매타휴리스틱 선행연구 32
• 제 3 항 LLM/에이전트/ICL 기반 최적화 연구 현황 33
• 제 4 항 연구 공백 33
• 제 5 항 본 연구의 차별성 정리 34
• 제 3 장 문제 정의 및 수리적 모형 36
• 제 1 절 VRPTW 공식 정의 36
• 제 1 항 집합 및 파라미터 정의 36
• 제 2 항 해 구조 및 의사결정변수의 해석 39
• 제 2 절 수리적 모델 40
• 제 1 항 목적함수(fitness 함수) 설계 42
• 제 3 절 평가 지표 43
• 제 1 항 해 품질 지표 43
• 제 2 항 해 fitness 기반 종합 지표 44
• 제 3 항 알고리즘 비교를 위한 추가 지표 44
• 제 4 장 제안 방법 45
• 제 1 절 제안 프레임워크 개요 45
• 제 1 항 처리 절차 및 모듈 간 상호작용 45
• 제 2 항 비교 실험을 위한 알고리즘 변형 47
• 제 2 절 염색체 표현 및 기본 GA 설계 48
• 제 1 항 정수형 이중 구조 염색체 48
• 제 2 항 선택ㆍ교차ㆍ돌연변이 연산 설계 49
• 제 3 항 시간창ㆍ용량 제약 처리와 fitness 계산 50
• 제 4 항 로컬 서치(2-opt)와 GA의 결합 51
• 제 3 절 초기해 생성 52
• 제 1 항 입력 데이터 전처리 및 극좌표 특성 추출 52
• 제 2 항 1단계 : DBSCAN을 이용한 공간 분할 53
• 제 3 항 2단계 : K-means 기반 세부 클러스터링 53
• 제 4 항 클러스터를 경로로 변환하는 초기해 생성 절차 54
• 제 5 항 클러스터링 파라미터의 역할과 LLM 연계 56
• 제 5 장 실험 설계 및 결과 분석 57
• 제 1 절 실험 데이터 및 비교 시나리오 57
• 제 1 항 Solomon VRPTW 인스턴스 구성 57
• 제 2 항 알고리즘 비교 시나리오 57
• 제 2 절 파라미터 설정 59
• 제 1 항 GA 기본 파라미터 59
• 제 2 항 클러스터링 파라미터 59
• 제 3 항 실험 반복 및 초기 seed 59
• 제 3 절 성능 비교 결과 60
• 제 1 항 총 이동거리 및 패널티, 적합도 비교 60
• 제 2 항 수렴 패턴 및 근사 최적해 도달 세대 수 61
• 제 3 항 해의 안정성 및 상대 개선도 63
• 제 4 절 LLM-ICL 기반 클러스터 튜닝 효과 분석 63
• 제 1 항 제안 파라미터 패턴 분석 63
• 제 2 항 클러스터 구조 및 초기해 품질 비교 64
• 제 3 항 인스턴스 유형별 효과 64
• 제 6 장 결론 및 향후 연구 65
• 제 1 절 결론 65
• 제 2 절 연구 결과 요약 65
• 제 3 절 학술적ㆍ실무적 시사점 66
• 제 4 절 연구 한계 67
• 제 5 절 향후 연구 방향 67
• 참고문헌 69
• Abstract 74