오늘 아침 이런 뉴스를 보았습니다.

디즈니 AI 활용 본격화, 당신만을 위한 원내 루트 제안으로

(미국 디즈니가 AI를 통해 가족 구성이나 취향에 따라 추천 어트랙션·레스토랑·효율적인 이동 루트를 제안하는 구상을 밝혔다, 라는 이야기입니다)

"어떤 어트랙션부터 돌아야 할까", "어디에서 식사를 해야 할까"를 방문객 대신 AI가 제안해 준다는... 구상입니다. 기사를 읽어보고, "아마 AI로 예측 데이터를 만들고, 최적화로 계획을 세우는 흐름이겠구나"라고 생각했습니다.

"제한 시간 내에 어떤 스팟을 어떤 순서로 돌 것인가"라는 관광 루트 문제는 오리엔티어링 문제 (Orienteering Problem)라고 불립니다.

그래서 이 기사에서는 뉴스의 구상을

AI 파트: 대기 시간이나 취향 점수와 같은 "문제의 데이터"를 생성한다 -
최적화 파트: 그 데이터를 사용하여 "최적의 원내 루트"를 계산한다

라는 2단계 파이프라인으로 해석하고, 후반부의 최적화 파트를 실제로 Python으로 구현해 보겠습니다. MILP(혼합 정수 선형 계획법)로 엄격하게 푸는 방법과, 규모가 커졌을 때를 위한 메타휴리스틱스 (Metaheuristics)를 모두 다룹니다.

참고로, 이것은 어디까지나 개인적인 상상에 의한 재현이며, 디즈니의 실제 시스템과는 전혀 관계가 없습니다. 아무것도 모릅니다. 참고로 일본 대상으로는 현재 시점에서 도쿄 디즈니 리조트로부터 유사한 AI 여행 계획 서비스의 발표는 확인되지 않는 것 같습니다.

먼저, 뉴스의 구상을 기술 파이프라인으로 번역해 보겠습니다.

가족 구성·취향 ─┐
당일 혼잡 예측 ─┼─→【AI 파트】문제의 파라미터(데이터)를 생성
원내 맵 ─┘ ・각 어트랙션의 "만족도 점수" sᵢ
...

포인트는, AI가 직접 루트를 답하는 것이 아니다라는 정리입니다. AI(기계 학습)가 잘하는 것은 "내일 14시 스페이스 마운틴의 대기 시간은 아마 85분", "이 가족은 패밀리 계열을 좋아함"과 같은 예측·스코어링 (Scoring) 부분입니다. 반면, 그 예측값을 사용하여 "그렇다면 제한 시간 내에 만족도가 최대가 되는 순서는?"이라며 조합을 결정하는 것은 최적화 (수리 최적화)의 일입니다.

"예측(AI) × 최적화"는 배송·재고·인원 배치 등 실무에서 굉장히 자주 등장하는 왕도 패턴이기도 합니다. 이번 디즈니의 구상도 그 전형적인 사례로 읽을 수 있겠다고 생각했습니다.

최적화 파트의 내용을 살펴보겠습니다. 지금까지 다루어 온 TSP/VRP와의 가장 큰 차이점은, **"전부를 돌지 않는다 (다 돌 수 없다)"**는 점입니다.

디즈니에서 하루 종일 있어도 모든 어트랙션을 다 돌 수는 없지요. 그래서, "한정된 시간 내에 만족도의 합계가 최대가 되도록, 방문할 어트랙션과 순서를 선택하는" 선택을 포함하는 문제가 됩니다. 이것이 오리엔티어링 문제입니다.

게다가 이번에는 "퍼레이드는 15:00~15:30에만 한다"와 같은 **시간대 제약 (Time Window)**도 넣고 싶으므로, 정확하게는 **OPTW (Orienteering Problem with Time Windows)**를 다룹니다.

본론은 최적화이므로, AI 파트(예측)는 여기서는 과감히 생략하고, **규칙 + 난수로 "그럴듯한 데이터"**를 만듭니다. 실무에서는 이 대기 시간 wait를 기계 학습 예측 모델이, 취향 점수 score를 추천 모델이 내뱉는다는 이미지입니다.

원내 맵 상에 스릴 계열, 패밀리 계열 등 타입이 다른 어트랙션을 배치합니다.

import numpy as np
# name, x, y, base_pop(인기), exp(체험 시간, 분), type
ATTRACTIONS = [
...

취향 점수의 핵심은 score = 인기 $\times$ 페르소나 가중치 부분입니다. 같은 "빅 썬더(인기 9)"라도,

• 스릴 광(thrill 가중치 1.8)이라면 만족도 $9 \times 1.8 = 16.2$
• 아이를 동반한 가족(thrill 가중치 0.5)이라면 만족도 $9 \times 0.5 = 4.5$

평가가 달라집니다. 이 한 줄이 '당신만을 위한' 개인화 (Personalization)를 만들어내는 것입니다.

아이를 동반한 가족(Family) 페르소나로 생성한 데이터는 다음과 같습니다.

가족 관점에서는 대기 시간이 긴 스릴형 어트랙션(빅 선더 마운틴, Big Thunder Mountain Railroad)은 점수가 낮아 '기다려서 탈 가치가 적다'고 판단되는 반면, 푸우나 퍼레이드의 점수가 높은 값으로 나타납니다. 이제 이 데이터를 최적화(Optimization)로 넘기기만 하면 됩니다.

먼저 정수 계획법 (MILP, Mixed Integer Linear Programming)으로 엄밀하게 (Strictly) 풀어보겠습니다. PuLP를 사용합니다.

결정 변수 (Decision Variable)는 3종류입니다.

• $y_i \in {0,1}$：어트랙션 $i$를 방문할지 여부
• $x_{ij} \in {0,1}$：$i$ 다음에 $j$를 방문할지 여부
• $a_i \ge 0$：$i$에 도착하는 시각

만족도 $s_i$, 예측 대기 $w_i$, 체험 시간 $e_i$, 이동 시간 $t_{ij}$, 타임 윈도우 $[o_i, c_i]$, 제한 시간 $T$라고 할 때, 정식화 (Formulation)는 다음과 같습니다.

\begin{aligned}
\text{최대화}\quad & \sum_{i} s_i\, y_i \[4pt]
\text{s.t.}\quad
...
\end{aligned}

각 제약 조건 (Constraint)의 의미는 다음과 같습니다.

세 번째 제약 조건은 '순서'를 시각 $a_i$의 단조 증가로 표현함으로써, 이상한 소규모 루프 (Subtour)가 발생하지 않도록 하고 있습니다.

import pulp
def solve_milp(inst, time_limit=180):
n, T = inst["n"], inst["T"]
...

실행합니다.

inst = build_instance("family", size="small")
res = solve_milp(inst)
print(res["status"], round(res["obj"], 1))
...

Optimal 46.4
게이트(입구/출구) → 캐리비안의 해적 → 정글 크루즈 → 담보 → 푸우 → 퍼레이드 관람 → 이츠 어 스몰 월드 → 게이트(입구/출구)

만족도 46.4로 엄밀하게 풀렸습니다 (제 환경에서는 약 84초 소요). 도착 시각 $a_i$를 나열하면 제대로 된 스케줄이 되어 있습니다.

퍼레이드 관람 도착이 218분 (타임 윈도우 210~240 사이) 안에 들어와 있는 점이 좋습니다. 빅 선더 마운틴은 '대기 시간이 긴 데 비해 가족 단위에게는 매력적이지 않다'는 판단 때문인지 채택되지 않았습니다.

같은 파크, 같은 제한 시간 6시간이라도, 페르소나를 '스릴 마니아'로 바꾸면 어떻게 될까요? build_instance("thrill")로 선호도 점수만 교체하여 푼 결과를 나란히 비교해 보겠습니다.

• 화살표 색… 제안 루트 (왼쪽=가족 / 오른쪽=스릴 마니아) -
• 점 색… 어트랙션 종류 (빨강=스릴형·초록=가족형·파랑=라이드형·보라=쇼) -
• 연한 회색 점… 이번에는 방문하지 않기로 판단된 어트랙션

왼쪽의 가족 플랜은 퍼레이드나 담보 등 가족형 위주로 이동하며, 오른쪽의 스릴 마니아 플랜은 빅 선더 마운틴을 확실히 포함하고 퍼레이드나 가족형 어트랙션은 과감히 제외하고 있는 것을 볼 수 있습니다. 데이터(선호도 점수)를 교체하는 것만으로 최적화가 자동으로 다른 루트를 제안합니다 ── 이것이 뉴스에서 말하는 '당신만을 위한 원내 루트'의 정체라고 생각합니다.

여기까지 MILP로 엄밀한 해(Optimal solution)가 나왔으니 잘 되었다고 하고 싶지만, MILP에는 규모의 벽이 있습니다. 어트랙션을 8개에서 12개로 늘리기만 해도, CBC 솔버(Solver)는 60초의 제한 시간 내에 최적해에 도달하지 못하게 됩니다.

MILP는 최적성을 보장하는 대신, 규모가 커지면 계산 시간이 폭발합니다. 그래서 등장하는 것이, 최적성은 포기하고 "적당히 좋은 해"를 고속으로 반환하는 메타휴리스틱스 (Metaheuristics)입니다.

여기서는 비교적 구현이 가볍고 효과가 높을 것 같은 방법을 사용합니다. 아이디어는 심플하며,

① "만족도 / 추가 시간"의 비율이 좋은 어트랙션부터 탐욕적 (Greedy)으로 삽입해 나간다
(단, 매번 베스트 1이 아니라 상위 몇 개 중에서 랜덤하게 선택한다)
② 2-opt로 순서를 바꿔 시간을 압축하고, 남는 시간으로 추가 삽입을 진행한다
...

①에서 랜덤성을 부여함으로써, 결정론적인 탐욕법 (Greedy Algorithm)으로는 단 한 가지 결과만 나오던 해를 수십 가지 방식으로 시도할 수 있게 됩니다.

def feasible(inst, route):
    """제한 시간과 타임 윈도우 (Time Window)를 지키고 있는지 검산한다"""
    stay, t, tw, T = inst["wait"] + inst["exp"], inst["travel"], inst["tw"], inst["T"]
    ...

polish는 2-opt (순서를 반전시켜 종료 시각을 단축) + 미방문 장소 추가 삽입이며, score_of는 방문지의 만족도 합계입니다. 모두 feasible과 같은 방식의 소박한 구현으로, 조합하는 것만으로도 적당히 좋은 해가 나옵니다.

소규모 문제에서 MILP의 엄밀해 (Exact Solution)와 휴리스틱스를 비교해 보겠습니다.

휴리스틱스는 순식간에 엄밀해와 동일한 만족도에 도달했습니다 (경로의 순서는 다른 해가 될 수도 있지만, 스코어는 최적해와 일치). 그리고 본론인 대규모 (12개 어트랙션) 문제에서는 차이가 결정적으로 벌어집니다.

MILP가 60초를 써도 만족도 30 전후의 잠정해에서 멈춰 있는 반면, 휴리스틱스는 0.1초 미만에 두 배 이상의 스코어를 뽑아내고 있습니다. 실시간으로 "당신만을 위한 루트"를 제공하고 싶은 서비스에서는, 이러한 휴리스틱스가 현실적인 선택지가 되는 것입니다.

디즈니의 "AI 원내 루트 제안" 뉴스를 최적화 문제로서 재현해 보았습니다.

• 뉴스의 구상은 "예측 (AI) → 최적화"의 2단계 파이프라인으로 읽을 수 있다. AI는 대기 시간이나 선호도 스코어를 만들고, 최적화가 "무엇을・어떤 순서로 돌 것인가"를 결정한다.
• 원내 루트 제안은 최적화의 전형적인 문제인 **오리엔티어링 문제 (Orienteering Problem, OPTW)**이다. TSP/VRP와 달리 "전부를 도는 것이 아니라, 시간 내에 만족도를 최대화하는 것"이 목적이다.
• 선호도 스코어를 교체하는 것만으로 최적 루트가 바뀌는 것이 개인화 (Personalization)의 정체다. 같은 파크라도 가족 단위와 스릴 마니아에게는 전혀 다른 플랜이 나온다.
• 소규모라면 MILP로 엄밀하게 풀 수 있지만, 규모가 커지면 시간 초과가 발생한다. 실시간 제안에는 **메타휴리스틱스 (Metaheuristics)**가 효과적이다.

"AI가 루트를 생각해 준다"라고 하면 마법처럼 들리지만, 분해해 보면 평소와 다름없는 예측 × 최적화일 뿐입니다. 이런 뉴스를 직접 손으로 재현해 보면 해상도가 확 올라가서 재미있다고 생각합니다. 도쿄 디즈니에서도 도입된다면, 꼭 내용을 상상하며 대기 시간 챌린지를 해보고 싶습니다.