ディズニーランドを最も効率よく楽しむ方法をグラフ理論とPythonで考える

はじめに

みなさんはディズニーランドを訪れたことがあるでしょうか。
東京ディズニーランドは日本でも有数のテーマパークであり、入場料金のみでほぼすべてのアトラクションを楽しむことができます。
この記事では東京ディズニーランドを最も効率よく楽しむ方法について真面目に考えていきます。

このネタを思いついたのは1年前のため、アトラクションの稼働状況が現在とは異なります。現在稼働中のアトラクションでの結果を知りたい場合には、記事の手順に沿って計算してみてください。

「効率よく楽しむ」とは何なのか

先述した通り、ディズニーランドは入場料金のみでほぼすべてのアトラクションを楽しむことができます。
そこで、無駄な時間を削ぎ落とし、できる限り多くのアトラクションに乗車しすることで「効率よく楽しむ」ことができるのではないだろうかと考えました。
では、ディズニーランドにおける「無駄な時間」とは何でしょうか。

そう、移動時間です。

もちろん、園内の装飾を見ながら移動することも楽しみの一つだとは思いますが、「できる限り多くのアトラクションに乗車する」という目標がある場合には不要な時間と言えます。

数学的な問題として解釈する

ここで、「ディズニーランドを最も効率よく楽しむ方法」を「アトラクションを訪問する順序の問題」としてとらえることにします。

このとき、各アトラクションの次に、そのアトラクションから最も遠いアトラクションを含むすべてのアトラクションを選択することができることから、各アトラクションを頂点とする完全グラフを用いた重み最小のハミルトン閉路を求める問題に帰結できます。
よって、この課題は巡回セールスマン問題(TSP)だと言えます。

アルゴリズムを適用して問題を解く

以下の手順で解（最適な順路）を求めます。

1. グラフ化
2. アトラクション間の重みの算出
3. TSP近似アルゴリズムの適用

TDLのグラフ化

まず、ディズニーランドのアトラクション位置と通路をグラフ化します。
ただし、訪問するアトラクションは以下の12個とし、グラフの頂点間の距離[m]を重みとします。この計測はGoogle Map上で行いました。

• ウエスタンリバー鉄道
• カリブの海賊
• ビッグサンダー・マウンテン
• スプラッシュ・マウンテン
• イッツ・ア・スモールワールド
• プーさんのハニーハント
• ホーンテッドマンション
• ミッキーの家とミート・ミッキー
• 美女と野獣”魔法のものがたり”
• スペース・マウンテン
• ベイマックスのハッピーライド
• モンスターズ・インク”ライド&ゴーシーク！”

（パークマップは東京ディズニーランドパークマップより引用）

アトラクション間の重みの算出

作成したグラフにダイクストラのアルゴリズムを適用し、各アトラクション間の最短経路とその距離を求めます。
ダイクストラアルゴリズムの手順および実装例は以下の記事で解説しています。

具体的な数値については割愛しますが、気になる方は上記の記事を参考に求めてみてください。

TSP近似アルゴリズムの適用

巡回セールスマン問題はNP困難問題であるため、正確で効率的なアルゴリズムは見つかっていません。
そこで、TSPの近似アルゴリズムであるクリストフィードのアルゴリズム（Christofides algorithm）を用いて考えます。

手順

1. 最小全域木を生成する
2. 最小全域木に含まれる頂点のうち、頂点の次数が奇数であるものをすべて見つける
3. 2 の最小重みの完全マッチングを見つける
4. 1 の最小全域木と最小重みの完全マッチングを合成して新たなグラフを作成する
5. 4 のグラフからオイラー閉路を生成する
6. 5 のオイラー閉路からハミルトン閉路を作成する

実装例

import itertools
import networkx as nx

def get_complete_graph(P, distances):
    """
    与えられた点集合と距離行列から完全グラフを構築する
    """
    g = nx.Graph()
    edges = []
    for i, j in itertools.combinations(range(len(P)), 2):
        edges.append((i, j, distances[i][j]))
    g.add_weighted_edges_from(edges)
    return g

def extract_odd_degree_vertices(T):
    """
    与えられた木の中から次数が奇数の頂点を抽出する
    """
    tg = nx.Graph()
    tg.add_edges_from(T)
    O = [v for v in tg.nodes if tg.degree(v) % 2 != 0]
    return O

def get_perfect_matching_on_subgraph_induced_by(G, O):
    """
    指定された頂点集合に基づく部分グラフから完全マッチングを取得する
    """
    sg = G.subgraph(O)
    for u, v in sg.edges:
        sg[u][v]['weight'] *= -1  # 最大マッチングに変更
    m = nx.max_weight_matching(sg, maxcardinality=True)
    return [[u, v] if u < v else [v, u] for u, v in m]

def shift_tour_start(tour, start_node):
    """
    巡回路の開始位置を指定されたノードに変更する
    """
    if start_node not in tour:
        raise ValueError("Start node not in tour")
    start_index = tour.index(start_node)
    return tour[start_index:] + tour[1:start_index + 1]

def get_christofides_tour(P, distances, T, start_node=None):
    """
    Christofides法を用いて巡回セールスマン問題の近似解を求める
    """
    G = get_complete_graph(P, distances)
    O = extract_odd_degree_vertices(T)
    pm = get_perfect_matching_on_subgraph_induced_by(G, O)
    eg = nx.MultiGraph()
    eg.add_edges_from(T + pm)

    checked = [False] * len(P)
    christofides_tour = []
    for u, v in nx.eulerian_circuit(eg):
        if not checked[u]:
            christofides_tour.append(u)
            checked[u] = True
    christofides_tour.append(christofides_tour[0])

     # スタート位置を変更
    if start_node is not None:
        christofides_tour = shift_tour_start(christofides_tour, start_node)
    
    return christofides_tour


if __name__ == '__main__':
  coordinates = np.array([
    # アトラクションの数に応じて変更
  ])

  distance = [
    # ダイクストラ法で求めた距離
  ]

  # 最小全域木の計算
  T = [(u, v) for u, v, w in nx.minimum_spanning_edges(get_complete_graph(coordinates, distance), algorithm='kruskal')]

  # Christofides法で経路を計算
  start_node = 0
  tour = get_christofides_tour(coordinates, distance, T, start_node=start_node)

  # 結果表示
  print("経路:", tour)

結果

クリストフィードのアルゴリズムで求めたアトラクションの順番とダイクストラ法で求めたアトラクション間の移動経路を合わせると以下のようになります。
コスト（合計の距離）は2280mでした。

移動速度を考える

最後に、どの程度の速度で移動すれば全てのアトラクションを訪問できるかを考えます。
設定した 12個のアトラクションの合計待ち時間は平均557.44分で、合計乗車時間は約90分です。
ディズニーランドの開園時間が9時から21時であることを考えると、移動に割り当てられる時間は72.56分となります。
求めた経路の合計距離は2280mであることから、31.42[m/分]で移動することで、目標とする12個のアトラクション全てを訪れることができます。
人の平均歩行速度2.9 km/h ~ 3.6km/hと比較すると半分程度の速度であることから、ゆったりと楽しむことができそうです。

まとめ

今回の行程では食事やパレードへの参加、写真撮影の時間を一切考慮していません。
そのため、実際にはもっと速いスピードで移動しなければならないと思います。

例えば、昼食と夕食に各30分を要したとすると、移動に充てられる時間は12.56分となり、移動速度は約10km/hと現実的ではなくなります。
一方で、昼食のみを取った場合には3.2km/hで移動すればぴったりの時間で開始地点に戻ることができます。

よって、3.2km/hで移動することを前提に、先ほどのルートで12個のアトラクションを訪問し、途中で30分間の昼食をとり、移動しながらパレードを楽しみ、閉園後にイクスピアリで夕食を取ることで、ディズニーランドを最も効率よく楽しむことができるでしょう。