この記事について
今朝こんなニュースを見かけました。
ディズニーAI活用を本格化、あなた専用の園内ルート提案へ
（米ディズニーが、AIで家族構成や好みに応じておすすめのアトラクション・レストラン・効率的な移動ルートを提案する構想を明らかにした、という話です）
「どのアトラクションから回るべきか」「どこで食事をするべきか」を、来園者の代わりにAIが提案してくれる…という構想です。パット記事を読んでみて、「たぶんAIで予測データを作って、最適化で計画を立てる流れかな」とか思いました。
「制限時間内にどのスポットをどの順で回るか」という観光ルートの問題で、オリエンテーリング問題（Orienteering Problem）と呼ばれます。
というわけで、この記事では、ニュースの構想を
- AIパート：待ち時間や好みのスコアといった「問題のデータ」を生成する
- 最適化パート：そのデータを使って「最適な園内ルート」を計算する
という2段構えのパイプラインとして読み解き、後半の最適化パートを実際にPythonで実装してみます。MILPで厳密に解く方法と、規模が大きくなったときのためのメタヒューリスティクスの両方をやります。
なお、これはあくまで個人の想像での再現であって、ディズニーの実システムとは全く関係ありません。何も知りません。ちなみに日本向けには、現時点で東京ディズニーリゾートから同様のAI旅行計画サービスの発表は確認できてなさそうです。
ニュースを技術の言葉に翻訳する
まず、ニュースの構想を技術のパイプラインに翻訳してみます。
家族構成・好み ─┐
当日の混雑予測 ─┼─→【AIパート】問題のパラメータ（データ）を生成
園内マップ ─┘ ・各アトラクションの「満足度スコア」 sᵢ
・予測待ち時間 wᵢ ／ 体験時間 eᵢ
・移動時間 tᵢⱼ ／ 公演の時間帯（タイムウィンドウ）
│
▼
【最適化パート】
制限時間 T の中で満足度の合計を最大化する
「どれを・どの順で回るか」を決める
＝ Orienteering Problem with Time Windows (OPTW)
│
▼
あなた専用の園内ルート
ポイントは、AIが直接ルートを答えているわけではないという整理です。AI（機械学習）が得意なのは「明日の14時のスペースマウンテンの待ち時間はたぶん85分」「この家族はファミリー系が好き」といった予測・スコアリングの部分。一方で、その予測値を使って「では制限時間内で満足度が最大になる順番は？」と組み合わせを決めるのは最適化（数理最適化）の仕事です。
「予測（AI）×最適化」は、配送・在庫・人員配置など実務でめちゃくちゃよく出てくる王道パターンだったりします。今回のディズニーの構想も、その典型例としても読めるな〜と思いました。
問題設定：オリエンテーリング問題とは
最適化パートの中身を見ていきます。これまで扱ってきたTSP/VRPとの一番の違いは、 「全部は回らない（回りきれない）」 という点です。
| TSP / VRP | オリエンテーリング問題（OP） | |
|---|---|---|
| 訪問対象 | 全地点を必ず訪問 | 時間内で回れる分だけ選んで訪問 |
| 目的 | 総移動距離・時間を最小化 | 集めた満足度（スコア）を最大化 |
| 制約の主役 | 全部回ること | 制限時間（時間予算） |
| たとえ | 配達は全件届ける | 観光は時間内に「おいしいとこ取り」 |
ディズニーで丸一日いても全アトラクションは回れませんよね。なので、「限られた時間で、満足度の合計が最大になるように、回るアトラクションと順番を選ぶ」という選択を含む問題になります。これがオリエンテーリング問題です。
さらに今回は「パレードは15:00〜15:30しかやっていない」のような 時間帯の制約（タイムウィンドウ） も入れたいので、正確には OPTW（Orienteering Problem with Time Windows） を扱います。
AIパート：問題のデータを生成する
本筋は最適化なので、AIパート（予測）はここでは割り切って、ルール＋乱数で「それっぽいデータ」 を作ります。実務ではこの待ち時間 wait を機械学習の予測モデルが、好みスコア score をレコメンドモデルが吐く、というイメージです。
園内マップ上に、スリル系・ファミリー系などタイプの違うアトラクションを配置します。
import numpy as np
# name, x, y, base_pop(人気), exp(体験時間,分), type
ATTRACTIONS = [
("ゲート(入口/出口)", 50, 5, 0, 0, "gate"),
("ビッグサンダー", 20, 30, 9, 4, "thrill"),
("スペースマウンテン", 80, 35, 10, 3, "thrill"),
("スプラッシュ", 15, 55, 8, 5, "thrill"),
("ホーンテッド", 35, 70, 7, 8, "thrill"),
("カリブの海賊", 30, 45, 6, 10, "ride"),
("イッツアスモール", 60, 60, 5, 11, "family"),
("プーさん", 70, 70, 6, 5, "family"),
("ダンボ", 55, 80, 4, 2, "family"),
("ティーカップ", 45, 88, 4, 2, "family"),
("ジャングルクルーズ", 25, 60, 6, 10, "ride"),
("パレード鑑賞", 50, 50, 8, 30, "show"),
("カントリーベア", 65, 45, 3, 15, "show"),
]
# まずは厳密解が現実的な時間で出る規模で試す（ゲート + 8アトラクション）
SMALL_IDX = [0, 1, 2, 5, 6, 7, 8, 10, 11]
def build_instance(persona="family", seed=42, size="small"):
rng = np.random.default_rng(seed)
idx = SMALL_IDX if size == "small" else list(range(len(ATTRACTIONS)))
sub = [ATTRACTIONS[i] for i in idx]
n = len(sub)
name = [a[0] for a in sub]
xy = np.array([[a[1], a[2]] for a in sub], dtype=float)
base_pop = np.array([a[3] for a in sub], dtype=float)
exp = np.array([a[4] for a in sub], dtype=float)
typ = [a[5] for a in sub]
# --- 待ち時間予測(分): 人気度 × 混雑 × ノイズ（本来は機械学習の予測値） ---
wait = np.clip(base_pop * 8 + rng.normal(0, 6, n), 0, None)
wait[0] = 0
# --- 好みスコア: ペルソナで重み付け（パーソナライズの核） ---
pref = {
"family": {"thrill": 0.5, "ride": 1.0, "family": 1.6, "show": 1.3, "gate": 0},
"thrill": {"thrill": 1.8, "ride": 1.0, "family": 0.3, "show": 0.6, "gate": 0},
}[persona]
score = np.array([base_pop[i] * pref[typ[i]] for i in range(n)])
score[0] = 0
# --- 移動時間(分): ユークリッド距離 / 徒歩速度 ---
diff = xy[:, None, :] - xy[None, :, :]
travel = np.sqrt((diff ** 2).sum(-1)) / 8.0
# --- タイムウィンドウ: パレードは時間固定 ---
T = 360 # 滞在6時間（全部は回りきれない＝選択が効く設定）
tw = [(0, T) for _ in range(n)]
parade = name.index("パレード鑑賞")
tw[parade] = (210, 240) # 開園3.5時間後の30分だけ実施
return dict(name=name, xy=xy, score=score, wait=wait, exp=exp,
travel=travel, tw=tw, T=T, n=n, parade=parade)
好みスコアの肝は score = 人気度 × ペルソナ重み のところです。同じ「ビッグサンダー（人気9）」でも、
- 絶叫好き（thrill重み1.8）なら満足度 $9 \times 1.8 = 16.2$
- 子連れファミリー（thrill重み0.5）なら満足度 $9 \times 0.5 = 4.5$
と評価が変わります。この一行が「あなた専用」のパーソナライズを生んでいるわけです。
子連れファミリーのペルソナで生成したデータがこちら。
| アトラクション | 種別 | 人気 | 予測待ち(分) | 体験(分) | 満足度 | タイムウィンドウ |
|---|---|---|---|---|---|---|
| ゲート | gate | 0 | 0 | 0 | 0.0 | - |
| ビッグサンダー | thrill | 9 | 66 | 4 | 4.5 | - |
| スペースマウンテン | thrill | 10 | 85 | 3 | 5.0 | - |
| カリブの海賊 | ride | 6 | 54 | 10 | 6.0 | - |
| イッツアスモール | family | 5 | 28 | 11 | 8.0 | - |
| プーさん | family | 6 | 40 | 5 | 9.6 | - |
| ダンボ | family | 4 | 33 | 2 | 6.4 | - |
| ジャングルクルーズ | ride | 6 | 46 | 10 | 6.0 | - |
| パレード鑑賞 | show | 8 | 64 | 30 | 10.4 | 210〜240 |
ファミリー視点だと、待ち時間が長い絶叫系（ビッグサンダー・スペースマウンテン）はスコアが低めで「並んでまで乗る価値が薄い」、逆にプーさんやパレードのスコアが高い、という値になっています。あとはこのデータを最適化に流すだけです。
最適化パート①：MILPで厳密に解く
まずは整数計画（MILP）で厳密に解きます。PuLP を使います。
定式化
決定変数は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$ として、定式化は次のようになります。
\begin{aligned}
\text{最大化}\quad & \sum_{i} s_i\, y_i \\[4pt]
\text{s.t.}\quad
& y_0 = 1,\quad \sum_{j} x_{0j} = 1,\quad \sum_{i} x_{i0} = 1 \\
& \sum_{i} x_{ik} = y_k,\quad \sum_{j} x_{kj} = y_k && (k \neq 0) \\
& a_j \ge a_i + \underbrace{(w_i + e_i)}_{\text{滞在}} + \underbrace{t_{ij}}_{\text{移動}} - M_{ij}(1 - x_{ij}) \\
& a_i + (w_i + e_i)\,y_i \le T \\
& a_i + (w_i + e_i) + t_{i0} \le T + M(1 - x_{i0}) \\
& o_i\, y_i \le a_i \le c_i + M(1 - y_i)
\end{aligned}
各制約の意味は次のとおりです。
| 制約 | 意味 |
|---|---|
| $y_0=1$ と入口の出入り | ゲートから出発し、ゲートに戻る |
| $\sum x_{ik} = y_k$ | 訪れるなら入次数・出次数がちょうど1（フロー保存） |
| $a_j \ge a_i + 滞在 + 移動 - M(1-x_{ij})$ | $i$ の次が $j$ なら、到着時刻は滞在＋移動の後（時間伝播＝部分巡回路除去も兼ねる） |
| $a_i + 滞在 \le T$ | 制限時間をオーバーしない |
| $a_i + 滞在 + t_{i0} \le T + \cdots$ | 最後にゲートへ戻る時間も予算に含める |
| $o_i \le a_i \le c_i$ | パレードのような時間帯制約を守る |
3つ目の制約は、「順番」を時刻 $a_i$ の単調増加で表現することで、変な小ループ（サブツアー）が出ないようにしています。
PuLPで実装
import pulp
def solve_milp(inst, time_limit=180):
n, T = inst["n"], inst["T"]
s, wait, exp, t, tw = (inst["score"], inst["wait"], inst["exp"],
inst["travel"], inst["tw"])
stay = wait + exp # 滞在 = 待ち + 体験
M = T + stay.max() + t.max()
# arc ごとに big-M を締める
Marc = {(i, j): max(0.0, tw[i][1] + stay[i] + t[i, j] - tw[j][0])
for i in range(n) for j in range(n) if i != j}
prob = pulp.LpProblem("OPTW", pulp.LpMaximize)
x = {(i, j): pulp.LpVariable(f"x_{i}_{j}", cat="Binary")
for i in range(n) for j in range(n) if i != j}
y = {i: pulp.LpVariable(f"y_{i}", cat="Binary") for i in range(n)}
a = {i: pulp.LpVariable(f"a_{i}", lowBound=0) for i in range(n)}
prob += pulp.lpSum(s[i] * y[i] for i in range(n)) # 満足度最大化
prob += y[0] == 1
prob += pulp.lpSum(x[0, j] for j in range(1, n)) == 1
prob += pulp.lpSum(x[i, 0] for i in range(1, n)) == 1
for k in range(1, n):
prob += pulp.lpSum(x[i, k] for i in range(n) if i != k) == y[k]
prob += pulp.lpSum(x[k, j] for j in range(n) if j != k) == y[k]
for i in range(n):
for j in range(1, n):
if i != j:
prob += a[j] >= a[i] + stay[i] + t[i, j] - Marc[i, j] * (1 - x[i, j])
for i in range(n):
prob += a[i] + stay[i] * y[i] <= T
prob += a[i] >= tw[i][0] * y[i]
prob += a[i] <= tw[i][1] + M * (1 - y[i])
for i in range(1, n):
prob += a[i] + stay[i] + t[i, 0] <= T + M * (1 - x[i, 0])
prob.solve(pulp.PULP_CBC_CMD(msg=0, timeLimit=time_limit))
route = extract_route(inst, {k: v.value() for k, v in x.items()})
return dict(status=pulp.LpStatus[prob.status],
obj=pulp.value(prob.objective), route=route)
def extract_route(inst, xval):
nxt = {i: j for (i, j), v in xval.items() if v and v > 0.5}
route, cur = [0], 0
while True:
cur = nxt.get(cur)
if cur is None or cur == 0:
break
route.append(cur)
return route + [0]
実行します。
inst = build_instance("family", size="small")
res = solve_milp(inst)
print(res["status"], round(res["obj"], 1))
print(" → ".join(inst["name"][i] for i in res["route"]))
Optimal 46.4
ゲート(入口/出口) → カリブの海賊 → ジャングルクルーズ → ダンボ → プーさん → パレード鑑賞 → イッツアスモール → ゲート(入口/出口)
満足度46.4で厳密に解けました（手元では約84秒）。到着時刻 $a_i$ を並べると、ちゃんとスケジュールになっています。
| 到着 | アトラクション | 待ち | 体験 |
|---|---|---|---|
| 6分 | カリブの海賊 | 54 | 10 |
| 71分 | ジャングルクルーズ | 46 | 10 |
| 132分 | ダンボ | 33 | 2 |
| 169分 | プーさん | 40 | 5 |
| 218分 | パレード鑑賞 | 64 | 30 |
| 313分 | イッツアスモール | 28 | 11 |
| 360分 | ゲートに帰着 | - | - |
パレード鑑賞の到着が 218分（タイムウィンドウ 210〜240 の中） に収まっているのがいい感じです。ビッグサンダー・スペースマウンテンは「待ち時間が長いわりにファミリーには刺さらない」という判断からか、採用が見送られました。
結果：好みでルートが変わる
同じパーク・同じ制限時間6時間でも、ペルソナを「絶叫好き」に変えるとどうなるか。build_instance("thrill") で好みスコアだけ差し替えて解いた結果を並べてみます。
- 矢印の色 … 提案ルート（左=ファミリー / 右=絶叫好き）
- 点の色 … アトラクションの種別（赤=スリル系・緑=ファミリー系・青=ライド系・紫=ショー）
- 薄いグレーの点 … 今回は回らないと判断されたアトラクション
左のファミリープランはパレードやダンボなどファミリー系を中心に回り、右の絶叫好きプランはビッグサンダー・スペースマウンテンをしっかり拾い、パレードやファミリー系はバッサリ切っているのが見て取れます。データ（好みスコア）を差し替えるだけで、最適化が自動的に別のルートを提案してくれる ── これがニュースの言う「あなた専用の園内ルート」の正体だと思います。
最適化パート②：規模が大きいとどうするか
ここまでMILPで厳密解が出てめでたし…と言いたいところですが、MILPには規模の壁があります。アトラクションを8個から12個に増やしただけで、CBCソルバーは60秒の制限時間内に最適解までたどり着けなくなります。
MILPは最適性を保証する代わりに、規模が大きいと計算時間が爆発します。そこで登場するのが、最適性は諦めて「そこそこ良い解」を高速に返すメタヒューリスティクスです。
ここでは比較的実装が軽くて効果が高そうな方法を使います。アイデアはシンプルで、
① 「満足度 / 追加時間」の比が良いアトラクションから貪欲に挿入していく
（ただし毎回ベスト1ではなく、上位数個からランダムに選ぶ）
② 2-optで順番を入れ替えて時間を詰め、浮いた分でさらに追加挿入する
③ ①②を何十回もやり直して、一番良かったルートを採用する
①でランダム性を入れることで、決定的な貪欲法だと1通りしか出ない解を、何十通りも試せるようになります。
def feasible(inst, route):
"""制限時間とタイムウィンドウを守れているか検算する"""
stay, t, tw, T = inst["wait"] + inst["exp"], inst["travel"], inst["tw"], inst["T"]
clock = 0.0
for a, b in zip(route[:-1], route[1:]):
clock += t[a, b]
clock = max(clock, tw[b][0]) # 早く着いたらタイムウィンドウまで待つ
if clock > tw[b][1] or clock + stay[b] > T:
return False
clock += stay[b]
return True
def greedy_insertion(inst, rng=None, rcl=1):
"""満足度/追加時間 の比が良い順に挿入。rcl>1 で上位 rcl 個からランダムに選ぶ"""
n = inst["n"]
route, unused = [0, 0], set(range(1, n))
while True:
cands = []
for k in list(unused):
for p in range(1, len(route)):
cand = route[:p] + [k] + route[p:]
if feasible(inst, cand):
extra = (inst["travel"][route[p-1], k] + inst["travel"][k, route[p]]
- inst["travel"][route[p-1], route[p]]
+ inst["wait"][k] + inst["exp"][k])
cands.append((inst["score"][k] / max(extra, 1e-6), k, p))
if not cands:
break
cands.sort(reverse=True)
_, k, p = cands[0] if rng is None else cands[rng.integers(0, min(rcl, len(cands)))]
route = route[:p] + [k] + route[p:]
unused.discard(k)
return route
def score_of(inst, route):
"""ルートで集めた満足度の合計（ゲートは score=0 なので二重に足してもOK）"""
return sum(inst["score"][i] for i in route)
def finish_time(inst, route):
"""ルートを実行してゲートに戻ってくる時刻"""
stay, t, tw = inst["wait"] + inst["exp"], inst["travel"], inst["tw"]
clock = 0.0
for a, b in zip(route[:-1], route[1:]):
clock += t[a, b]
clock = max(clock, tw[b][0]) # 早く着いたらタイムウィンドウまで待つ
clock += stay[b]
return clock
def two_opt(inst, route):
"""区間を反転して終了時刻を縮める（満足度は変えず、時間だけ詰める）"""
best, improved = route, True
while improved:
improved = False
for i in range(1, len(best) - 2):
for j in range(i + 1, len(best) - 1):
cand = best[:i] + best[i:j + 1][::-1] + best[j + 1:]
if feasible(inst, cand) and finish_time(inst, cand) < finish_time(inst, best) - 1e-6:
best, improved = cand, True
return best
def polish(inst, route):
"""2-optで時間を詰め、浮いた分で未訪問アトラクションを追加挿入する"""
route = two_opt(inst, route)
for k in set(range(1, inst["n"])) - set(route):
for p in range(1, len(route)):
cand = route[:p] + [k] + route[p:]
if feasible(inst, cand):
route = cand
break
return route
def solve_heuristic(inst, n_starts=40, rcl=3, seed=0):
rng = np.random.default_rng(seed)
best = polish(inst, greedy_insertion(inst)) # 1回目は純粋な貪欲
best_sc = score_of(inst, best)
for _ in range(n_starts):
route = polish(inst, greedy_insertion(inst, rng=rng, rcl=rcl))
sc = score_of(inst, route)
if sc > best_sc:
best, best_sc = route, sc
return dict(obj=best_sc, route=best)
polish は2-opt（順番を反転して終了時刻を縮める）＋未訪問の追加挿入、score_of は訪問先の満足度合計です。どれも feasible と同じノリの素朴な実装で、組み合わせるだけでそこそこ良い解が出ます。
小規模問題で、MILPの厳密解とヒューリスティクスを比べてみます。
| ペルソナ | MILP（厳密） | MILP 時間 | ひゅ | ひゅ 時間 |
|---|---|---|---|---|
| 子連れファミリー | 46.4 | 約84秒 | 46.4 | 約0.02秒 |
| 絶叫好き | 48.0 | 約17秒 | 48.0 | 約0.04秒 |
ヒューリスティクスは一瞬で厳密解と同じ満足度に到達しました（ルートの並びは別解になることもありますが、スコアは最適と一致）。そして本命の大規模（12アトラクション）では差が決定的になります。
| ペルソナ | ひゅ | ひゅ 時間 | MILP（60秒上限） |
|---|---|---|---|
| 子連れファミリー | 46.8 | 約0.09秒 | 30.7（未収束で打ち切り） |
| 絶叫好き | 67.2 | 約0.07秒 | 28.2（未収束で打ち切り） |
MILPが60秒かけても満足度30前後の暫定解で止まっているのに対し、ヒューリスティクスは0.1秒未満で倍以上のスコアを叩き出しています。リアルタイムに「あなた専用ルート」を返したいサービスでは、こういうヒューリスティクスが現実的な選択肢になるわけです。
まとめ
ディズニーの「AI園内ルート提案」のニュースを、最適化の問題として再現してみました。
- ニュースの構想は 「予測（AI）→ 最適化」の2段パイプラインとして読める。AIは待ち時間や好みのスコアを作り、最適化が「どれを・どの順で回るか」を決める
- 園内ルート提案は、最適化の定番 オリエンテーリング問題（OPTW）。TSP/VRPと違い「全部は回らず、時間内で満足度を最大化する」
- 好みスコアを差し替えるだけで最適ルートが変わるのがパーソナライズの正体。同じパークでもファミリーと絶叫好きで全然違うプランが出た
- 小規模ならMILPで厳密に解けるが、規模が大きいと時間切れ。リアルタイム提案には メタヒューリスティクス が効く
「AIがルートを考えてくれる」と聞くと魔法みたいですが、分解してみるといつもの予測×最適化だったりします。こういうニュースを自分の手で再現してみると、解像度がぐっと上がって面白いと思います。東京ディズニーでも導入されたら、ぜひ中身を想像しながら待ち時間チャレンジをしてみたいと思います。