内容梗概

　本研究では，テーマパーク等で任意の目的地を最短時間で巡ることのできる経路を探索する方法について研究を行った．具体的には，巡回セールスマン問題をもとに，辺だけでなく点にもコスト（待ち時間）を設定し，時間経過によってコストが変動するように問題設定を行い，蟻コロニー最適化を用いて解を求めた．本問題を解くことができれば，テーマパーク等を効率的に巡る方法を知ることができるようになると期待できる．

はじめに

研究背景

　ユニバーサル・スタジオ・ジャパンやディズニーランド，ディズニーシー等のテーマパークには，多くのアトラクションが存在している．開園時間に対してアトラクションの数が多く，パークの混雑具合やアトラクションの人気によっては長い待ち時間が発生するため，一日でそれらすべてを回るのは難しい．そこで，待ち時間等を考慮して，テーマパークにあるアトラクションを効率的に巡る方法について求める問題を提案する．

研究内容

　本提案問題は，巡回セールスマン問題をもとに，アトラクションに見立てた各点に待ち時間を設定し，各辺は混雑具合によって変動する移動時間を設定した問題である．この問題に対して，蟻コロニー最適化を用いて近似最適解を求める．蟻コロニー最適化のアルゴリズムは，継続的に実行できるため，グラフが動的に変化する場合において，他のアルゴリズムよりも有効であるとされている．

待ち時間を考慮した最短時間巡回路問題の提案

巡回セールスマン問題について

　巡回セールスマン問題（Traveling Salesman Problem, TSP）とは，組み合わせ最適化問題の一つであり，計算複雑性理論においてNP困難と言われている問題のクラスに分類される．いわゆる計算量的に困難な問題である．

　セールスマンがある都市から出発し，全ての都市を一度ずつ訪問して，出発した都市に戻るとする．（図1）　その場合に，数ある巡回路の中から総移動コストが最小になる巡回路を求める問題である．（図2）

　この問題をもとにした，各辺の重みが時間ごとに変化する時間依存巡回セールスマン問題や，最大積載量や運搬車の稼働時間等を考慮した配送計画問題等の応用問題も多く存在している．

　本研究では，この巡回セールスマン問題をもとに，テーマパーク等を想定し，待ち時間を考慮した上で，巡回にかかる総時間が最小となる巡回路を求める問題を提案する．

待ち時間を考慮した最短時間巡回路問題の提案

　巡回セールスマン問題をもとに，アトラクションに見立てた各点に待ち時間を設定し，各辺は混雑具合によって変動する移動時間を設定した．この場合に，総移動時間が最小になる巡回路を求める．

　以下に定式化を示す．（式1）

　ここで，I はアトラクションの集合，t_ij はアトラクション 間の総移動時間を表し，x_ij はアトラクションi ∈ I からアトラクションj ∈ I に行くときに1，行かないときに0を取る変数である．

　また，アトラクション（i – j）間の総移動時間t_ij は，次の式2で表す．

　ここで，d_ij はアトラクション（i – j）間の距離，T は時間帯，v(T) は時間帯T における移動時間，r_j はアトラクションj ∈ I の乗車時間，w_j(T) は時間帯T におけるアトラクションj ∈ I の待ち時間を表す．

蟻コロニー最適化

蟻コロニー最適化について

　蟻コロニー最適化手法（Ant Colony Optimization, ACO）とは，蟻の群行動を模倣したメタヒューリスティックな最適化アルゴリズムであり，巡回セールスマン問題などの組み合わせ最適化問題を解くのによく用いられる．

　蟻は餌を探すためにランダムに動き回り，餌を見つけると，足跡フェロモン（以下，フェロモンとする）を付加しながら巣へと戻る．（図3）　他の蟻がそのフェロモンの跡を見つけると，ランダムな動きをやめて，そのフェロモンを辿り始める．（図4）　フェロモンを辿って餌を見つけると，またフェロモンで跡をつけながら巣へと戻っていく．フェロモンは時間が経過すると蒸発してしまうため，巣から餌までの経路が長いとフェロモンは蒸発してしまう．そのため，他の蟻はそのフェロモンの跡を見つけにくくなり，次第にその経路は選ばれなくなっていく．（図5）　巣から餌までの経路が短いと，蒸発する前に，他の蟻がそのフェロモンを見つけて辿り，フェロモンの跡を補強する．これを繰り返していくと，巣から餌までの経路が短いほどフェロモンの残留量が多くなり，正のフィードバック効果で，全ての蟻が一つの経路を辿ることになる．（図6）

　蟻コロニー最適化のアルゴリズムは，継続的に実行できるため，グラフが動的に変化する場合において，他のアルゴリズムよりも有効であるとされている．

蟻コロニー最適化のアルゴリズム

　蟻コロニー最適化は，蟻の経路選択行動とフェロモンを数値モデル化することにより最適化を行う．図7にACOのアルゴリズムを示し，以下でアルゴリズムの各行程について説明する．なお，説明は巡回セールスマン問題を解くことを前提としている．

1. 初期化

　初期化を行う．各蟻エージェントの初期位置をランダムに設定し，全経路のフェロモン情報を一定に初期化する．

2. 巡回経路の構築

　訪問するアトラクションを順次選択し，巡回路の構築を行う．訪問するアトラクションは，フェロモン情報，ヒューリスティック情報と呼ばれる二つの情報から，各蟻エージェントが確率的に選択する．

　蟻の総数をn とすると，蟻エージェントk がアトラクションi からj に行く経路を選択する評価値P_ij^k(T)は，次の式3で表される．

　ここで，T_ij はフェロモン情報，η_ij はヒューリスティック情報，α はフェロモン情報に対する乗数，β はヒューリスティック情報に対する乗数を表す．

　式3のフェロモン情報T_ij は，各蟻エージェントがこれまでに経路に付加させてきた情報で，よりコストの小さい巡回路ほど高い値となるようになっている．

　一方，ヒューリスティック情報η_ij は経路の距離の逆数を用いる．ヒューリスティック情報η_ij は，次の式4で表される．

　ここで，d_ij は経路（i – j）の距離を表す．

　ヒューリスティック情報η_ij は，蟻エージェントがアトラクションを選択するとき，巡回路の総コストに関係なく，より小さいコストとなるアトラクションほど高い確率で選択するような情報となる．

3. 分泌するフェロモンの計算

　2において，各蟻エージェントが順次選択したアトラクションの巡回路の総コストを算定する．

4. フェロモン情報の更新

　ここでは，巡回路の各経路にフェロモン情報を追加する．巡回セールスマン問題の場合，巡回路の総コストの最小化問題であるため，追加されるフェロモン情報は巡回路の総コストが小さいほど高い値とする．よって，追加されるフェロモン情報は，次の式5で表される．

　ここで，Q はフェロモンの係数，L_k(t) は蟻エージェントk が作成した巡回路の経路長を表す．

　また，t+1時点のフェロモン情報は次の式6で表される．

　ここで，ρ はフェロモンの蒸発率を表す．

　フェロモン情報が時系列的に蒸発することにより，最近の行動を重視し局所解に陥ることを回避し，大域的な解の探索を可能にする．

5. 終了条件の判定

　探索回数が最大回数以下なら2に戻る．最大回数を満足していれば終了となる．

　ACOは以上のように，比較的簡単なアルゴリズムで構成される．しかし，フェロモン情報とヒューリスティック情報の２つの情報を用いることにより，過去の設計解（巡回路）に対しての評価のみならず，個々の設計変数（経路）に対する評価も設計解の算定に考慮されるため，最短巡回路の探索に特化した手法となる．

実験

概要

　待ち時間を考慮した最短時間巡回路問題に対して，蟻コロニー最適化のアルゴリズムを解法として実験を行う．

　本実験では，ユニバーサル・スタジオ・ジャパンをモデルとし，常設されていてGoogle Map上で位置を確認することのできる以下の11個のアトラクションと入場ゲートを研究対象とする．

1. ハリウッド・ドリーム・ザ・ライド
2. ザ・フライング・ダイナソー
3. マリオカート　～クッパの挑戦状～
4. ハリー・ポッター・アンド・ザ・フォービドゥン・ジャーニー™
5. スペース・ファンタジー・ザ・ライド
6. ミニオン・ハチャメチャ・ライド
7. ジュラシックパーク・ザ・ライド
8. ハリウッド・ドリーム・ザ・ライド　～バックドロップ～
9. アメージング・アドベンチャー・オブ・スパイダーマン・ザ・ライド　4K3D
10. フライト・オブ・ザ・ヒッポグリフ™
11. ジョーズ

　各アトラクション間の距離はGoogle Maps Platform Distance Matrix APIを用いて取得した．

　また，このモデルを考える上で，次の仮定を設ける．

• 開園9:00から閉園21:00までの12時間以内に巡回を終わらせる．終わらなかった場合は強制終了．
• 入場ゲート（始点）での待ち時間は考慮しない．

　蟻コロニー最適化のアルゴリズムでは，式3のαの値とβの値，式5のQの値，式6のρの値を設定する必要がある．本実験では，次の表1に示した値を設定する．

式3のαの値	1.0
式3のβの値	1.0
式5のQの値	1.0
式6のρの値	0.9

実験

実験1

　実験1では，時間ごとに待ち時間や移動速度が変わらない静的な最短時間巡回路を求める．蟻エージェントの数は50，試行回数は100回とする．

　移動速度は75m/minとし，各アトラクションに設定した平日（木曜）と休日（土曜）の待ち時間をそれぞれ表2と表3に示す．

アトラクション番号	1	2	3	4	5	6	7	8	9	10	11
待ち時間（分）	0	36	46	46	33	16	41	0	54	12	10

アトラクション番号	1	2	3	4	5	6	7	8	9	10	11
待ち時間（分）	25	30	68	5	19	32	10	25	16	10	7

　平日の場合は0→1→11→10→9→8→7→6→5→4→3→2で所要時間383分，休日の場合は0→1→11→10→9→8→7→6→5→4→3→2で所要時間322分が出力された．

実験2

　実験2では，本研究で提案した時間ごとに待ち時間や移動速度が変わる動的な最短時間巡回路を求める．蟻エージェントの数は50，試行回数は100回とする．

　Googleに表示される混雑する時間帯のグラフをもとに，混雑が予想される10:00～15:00の移動速度を50m/minとし，それ以外を75m/minとした．また，各アトラクションに設定した平日（木曜）と休日（土曜）の時間帯ごとの待ち時間を表4と表5に示す．

	1	2	3	4	5	6	7	8	9	10	11
9:00	36	46	46	33	16	41	0	54	14	12	10
10:00	51	72	59	65	26	49	0	78	27	28	10
11:00	65	93	63	92	36	61	0	98	45	48	10
12:00	65	102	60	96	45	70	0	94	53	56	10
13:00	57	98	57	92	39	66	0	85	49	54	10
14:00	59	93	56	82	38	66	0	85	48	51	10
15:00	67	94	55	77	42	71	32	93	51	51	29
16:00	74	97	53	73	47	74	19	100	53	50	17
17:00	78	98	49	70	50	68	23	104	52	49	22
18:00	80	89	39	59	48	59	34	101	45	43	38
19:00	72	75	22	41	37	47	43	90	32	34	48
20:00	59	57	10	31	27	37	42	71	23	26	46

	1	2	3	4	5	6	7	8	9	10	11
9:00	25	30	68	5	19	32	10	25	16	10	7
10:00	30	51	71	5	42	48	10	30	15	10	0
11:00	31	95	67	5	64	79	10	40	42	10	0
12:00	39	111	67	5	69	89	10	67	65	10	0
13:00	66	114	68	5	59	88	10	105	67	10	0
14:00	75	110	70	6	58	84	17	109	63	10	24
15:00	73	106	72	17	63	82	29	105	62	9	25
16:00	71	106	75	34	71	87	17	98	67	15	15
17:00	75	112	76	71	78	91	26	99	71	35	31
18:00	82	114	66	94	75	87	41	107	70	51	48
19:00	89	104	43	104	61	78	44	117	59	59	49
20:00	95	97	19	101	46	64	43	122	43	61	47

　巡回経路による所要時間の差を見るため，それぞれ10回ずつ結果を出力した．

　平日の場合では，0→1→11→10→9→2→8→7→6→5→4→3で所要時間560分が3回，0→1→11→10→9→8→7→6→5→2→4→3で所要時間562分が4回，0→1→11→2→10→9→8→7→6→5→4→3で所要時間564分が2回，0→1→11→10→9→8→7→6→2→5→4→3で所要時間570分が1回出力された．確認できた最短経路は0→1→11→10→9→2→8→7→6→5→4→3で所要時間560分だった．

　休日の場合では，0→1→11→2→10→9→8→7→6→5→4→3で所要時間416分が4回，0→1→2→11→10→9→8→7→6→5→4→3で所要時間467が3回，0→1→11→10→9→8→7→6→5→4→3→2で所要時間503が3回出力された．確認できた最短経路は0→1→11→2→10→9→8→7→6→5→4→3で所要時間416分だった．

考察

　実験1と実験2を見比べると，時間帯によって時間が変動するため，経路が変わっている部分がある．しかし，距離に依存しているためか，待ち時間や移動速度が変わったとしても大きな変動は見られなかった．

　2のザ・フライング・ダイナソーの巡回するタイミングによって，所要時間に差が生じているように見える．これは，11個のアトラクションの中では全体的に待ち時間が長く，1日のうちの最長待ち時間と最短待ち時間の差が大きいからだと考える．

　蟻コロニー最適化のアルゴリズムの特性上，厳密な最短経路を求めるには至らなかった．実用化する際には，複数回結果を出力し，その中から人力で最も解を選択するようにするか，より精度の良いアルゴリズムを使うことで，解の精度を上げる必要があると考えた．

おわりに

　本研究では，テーマパーク等で各施設を巡ることを想定した待ち時間を考慮した最短時間巡回路問題を提案し，蟻コロニー最適化を用いて近似最適解を求めた．蟻コロニー最適化のアルゴリズムは，継続的に実行できるため，グラフが動的に変化する場合において，他のアルゴリズムよりも有効であるとされている． 提案した問題を検証した結果，例に上げた11個のアトラクションをすべて時間内に巡る経路を探索することができた．今後の課題は，複数回結果を出力し，人力で最も良い解を選択するか，より精度の良いアルゴリズムを実装する等して，解の精度を上げることである．

参考文献

1. 小石愛子，山辺有紗，東京ディズニーランドの最適巡回路，2014
2. ユニバーサル・スタジオ・ジャパン｜USJ，[オンライン]. https://www.usj.co.jp/web/ja/jp
3. Google Maps Platform のドキュメント  |  Distance Matrix API  |  Google Developers，[オンライン]. https://developers.google.com/maps/documentation/distance-matrix
4. USJリアルタイム待ち時間 | ユニバーサルスタジオジャパン待ち時間混雑情報，[オンライン]. https://usjinfo.com/wait/realtime.php（参照　2022/12/16）