LLM 기반 여행 계획 최적화 (새 탭에서 열림)
대규모 언어 모델(LLM)은 사용자의 주관적인 취향과 정성적인 목표를 이해하는 데 탁월하지만, 개장 시간이나 이동 시간 같은 정량적인 제약 조건을 정밀하게 계산하는 데에는 한계가 있습니다. 이를 해결하기 위해 구글 리서치는 LLM이 초기 계획을 수립하고, 최적화 알고리즘이 실제 데이터를 기반으로 실행 가능성을 검증 및 조정하는 하이브리드 여행 계획 시스템을 개발했습니다. 이 시스템은 사용자의 의도를 최대한 반영하면서도 논리적으로 완벽한 일정을 생성하는 것을 목표로 합니다. **LLM과 최적화 알고리즘의 결합 구조** * 시스템은 먼저 제미나이(Gemini) 모델을 사용하여 사용자의 쿼리에 최적화된 초기 여행 계획을 생성하며, 여기에는 활동 목록, 권장 소요 시간, 중요도 등이 포함됩니다. * 생성된 초기 계획은 검색 백엔드를 통해 확보한 최신 영업시간 및 이동 시간 데이터와 결합되어 '그라운딩(Grounding)' 과정을 거칩니다. * LLM이 제안한 활동이 실행 불가능할 경우를 대비하여, 검색 시스템은 유사한 성격의 대체 활동들을 병렬적으로 추출하여 최적화 알고리즘에 전달합니다. **2단계 최적화 프로세스** * **일일 일정 최적화:** 첫 번째 단계에서는 개별 날짜 내의 활동 순서를 결정합니다. 동적 계획법(Dynamic Programming)을 활용하여 활동의 유사도와 실행 가능성을 점수화하며, 영업시간 미준수나 동선 오류가 있는 일정에는 0점을 부여하여 제외합니다. * **전체 일정 배분:** 두 번째 단계에서는 여러 날에 걸친 활동들이 겹치지 않도록 전체 경로를 구성합니다. 이는 컴퓨터 과학에서 '가중치 세트 패킹(Weighted Set Packing)' 문제로 분류되는 NP-완전(NP-complete) 문제로, 계산 복잡도가 매우 높습니다. * **지역 탐색 휴리스틱:** 복잡한 계산을 효율적으로 처리하기 위해 초기 일정에서 활동 위치를 조금씩 바꾸며 전체 점수를 높여가는 '지역 탐색 휴리스틱(Local search heuristics)'을 적용하여 최종 수렴된 최적의 일정을 도출합니다. **실제 적용 사례 및 효과** * **정성적 요구사항 충족:** "사람이 적고 덜 알려진 박물관"을 찾는 쿼리에서 일반 검색 시스템은 유명 박물관을 포함하는 오류를 범했으나, LLM 기반 시스템은 사용자의 의도를 정확히 파악하여 숨겨진 명소들로만 일정을 구성했습니다. * **물류적 실행 가능성 확보:** LLM이 샌프란시스코 여행 계획 시 도시를 가로지르는 비효율적인 동선을 제안하더라도, 최적화 알고리즘이 지리적 근접성을 고려하여 활동 순서를 재배치함으로써 현실적인 동선을 완성했습니다. 이러한 하이브리드 접근 방식은 AI의 유연한 이해 능력과 알고리즘의 엄격한 논리력을 결합하여 사용자에게 실질적으로 도움이 되는 도구를 제공합니다. 향후 이 기술은 여행 계획뿐만 아니라 복잡한 제약 조건이 얽힌 다양한 스케줄링 및 물류 최적화 분야에 광범위하게 활용될 수 있을 것으로 기대됩니다.
