グラフ理論を用いた旅行計画アプリケーションの提案
清水 蘭 (指導教員：萩田真理子)

1

はじめにで、ある 2 点が非常に近い位置にあるのに別の日に回ってしまうということを防いでいる. まとめる辺として採用する辺は、観光地間の辺のコストが観光地数の下から 2 割にあたる辺とする. 例えば 15 カ所の観光地があるとすると、完全グラフを考えているので与えられた辺の本数が 105 本であることに対し、まとめる辺として採用する辺の本数はコストが小さな 15 × 0.2 = 3 本ということになる.

旅行計画は、どの宿泊地を拠点とするのか、どのような経路で回るのか、何日で観光するのか等、考えることが沢山あり、大変である. 旅行会社のツアーを利用したり、雑誌のおすすめコースを参考にしたりすると楽にはなるが、行きたい観光地を網羅できない可能性もある。そこで、旅行に慣れていないユーザーでも簡単に旅行計画が立てられるアプリケーションを提案する.
本研究では、行きたい観光地名とその観光地にかける時間を入力すると、最適な宿泊地、観光日数、観光ルート（googlemap 上に表示）、観光地間の詳細ルート（テキスト表示）を出力するという最低限の機能を持つアプリケーションを実装し、1 つの宿泊地で全ての観光地を回るための条件についての定理を考察した.

2

3.3 宿泊地の決め方
まず、観光地の重心を求めて、求めた重心を中心として半径 1km 以内にある宿泊地を検索する. そして宿泊地候補の中で、最も知名度の高い宿泊地を採用する. 知名度に影響を与えるのは、Googleのインデックスにおけるプレイスのランキング、アプリケーションからのチェックイン回数、世界的な人気などの要因である.

提案手法
次のような重み付き完全グラフを考える

3.4 1 日で回る観光地の集合の分け方
まず、宿泊地と宿泊地から一番遠い観光地を結んだ直線の垂線を宿泊地に向けて、一日の観光時間（8 時間）を越えるまで動かしていく. 一番遠い観光地から選んでいくことで検索範囲を狭めていき、最終日に一番遠い 2 点が余ってしまい 1 日で回れなくなるということを防いでいる. 次に観光地と宿泊地のハミルトン閉路を形成し、辺と点のコストが活動時間（8.5 時間）を越えなければ集合を確定し、そうでなければ観光地を 1 つずつ減らして再びコストを計算する. 未選択の観光地がなくなるまで繰返していく.

• 観光地を点とする• 点は位置情報（経度、緯度）を持つ• 観光地にかける時間を点の重みとする• 観光地間を結ぶ道を辺とする• 観光地間の移動にかかる時間を辺の重みとする
また、位置情報や観光地間にかかる時間の取得
等は googlemap api というサービスを使用している.

3アルゴリズム
次のような方法で解を求める.

4

1. 全ての観光地からなる集合を S とする
2. S の中から観光地を 1 つ選び、その観光地と同じ宿泊地で回れる距離にある観光地の集合（S1 ）を作り、S = S \ S1 とする.
3. S1 の中で、コストが小さい辺の端点をまとめる
4. S1 を回るのに拠点とする宿泊地を選ぶ
5. S1 の中で、1 日で回る観光地の集合 (S2 ) を作り S1 = S1 \ S2 とし、S1 の中で未選択の観光地がなくなるまで 5 を繰り返す.
6. S の中で未選択の観光地がなくなるまで 2 ∼ 5を繰返す

グラフ上の全ての頂点を 1 度ずつ通る閉路をハミルトン閉路という.

ハミルトン閉路の求め方

4.1 最近追加法
重みつきの辺をもつ完全グラフを考える. まず、全ての辺の中で重みが最小の辺を追加し、追加した辺の端点と接続している辺のうち、一番小さな重みの辺を追加し、2 本まで選んだところで、三角形を形成する. そして、追加した辺の端点と接続している辺のうち一番小さな重みの辺を追加し、追加した辺の端点に接続している閉路の辺のうち、重みが大きい辺を除去し、次数が 1 の点を接続する. このようにして閉路を大きくしていき、未選択の点がなくなるまで繰り返す.

3.1 同じ宿泊地で回る観光地の集合の分け方
googlemap api より取得した観光地の位置情報
より、1 番離れた観光地 2 点のうち、北にある観光地を選び、選んだ観光地から 30km 以内にある観光地を同じ宿泊地で観光する観光地とする.

4.2 2-opt 法
まず適当な巡回路を 1 つ作る. （ここでは最近追加法で作った巡回路を初期巡回路とする）2 本の辺 (i,j),(k,l) において、辺 (i,k) の重みと辺 (j,l)の重みを足したものが、辺 (i,j) の重みと辺 (k,l) の重みを足したものより小さければ、辺を (i,k),(j,l)に繋ぎ変えて解を良くしていく.

3.2 コストが小さい辺の端点のまとめ方
コストが小さい辺とその端点のコストをまとめて、大きな 1 つの点とする. このようにすること
55

5

実行結果

6.2

以下は実際に観光地と観光地にかける時間を入力した時の実行結果の一部である.

1 つの宿泊地で全ての点を回るための必要条件

定理



与えられた重み付きグラフにおいて、どの閉路の重みも定められた値 a 以内となるように分割することができるならば、どの 2 点間の所要時間も a 以下である.


証明
2 点間の辺の重みが a より大きいと、どちらかの点は宿泊地から往復するのに a よりも多くかかってしまい、1 箇所の宿泊地では観光できない.
よってどの 2 点間の所要時間も a 以下である必要がある.

6.3
図 1: 宿泊地が 1 つの場合

1 つの宿泊地で全ての点を回るための十分条件

定理



与えられた重み付きグラフにおいて、どの2√3点間の所要時間も 2 a 以下ならば、どの閉路の重みも定められた値 a 以内となるように分割することができる.
証明
ヤングの定理より、成り立つ.
ヤングの定理



平面上の n 個の点においてどの 2 点も距離が1 を超えないように与えられている。その時、n 個の点の全ては半径 √13 の円に含まれる.
図 2: 宿泊地が複数ある場合

7



まとめと今後の課題

本研究では、簡単に旅行計画を立てられるアプ
リケーションの提案、実装、そして 1 つの宿泊地
1 つの宿泊地で全ての観光地を回るための条件
で全ての観光地を回るための条件についての定理についての定理を考察する. ここでは点の重みはを考察した.
まだ考慮していない.
今後は、点の重みを考慮した定理の考案、アルゴリズムの改良をしたい. そして、現時点でのア6.1 1 つの宿泊地で全ての点を回るためのプリケーションでは、行きたい観光地に対してそ必要十分条件の観光地にかける時間を入力しなければならない が、ユーザーが何を重点的に観光するのかによっ
定理て観光地にかける時間を自動的に設定できるよう与えられた重み付きグラフにおいて、どの閉にしたい.
路の重みも定められた値 a 以内となるように
参考文献
分割することができるための必要十分条件は、[1] J.H.van Lint,R.M.Wilson:A Course in Com宿泊地から観光地への所要時間が全て a2 以下
binatorics,Cambridge University Press,2001となっていることである.
[2] Google Maps JavaScript API v3,
 https://developers.google.com/maps/
証明
documentation/javascript/tutorial?hl=ja
全ての辺の重みが a2 ならば、最悪 1 日に 1 つの
[3] ゴロヴィナ ヤグロム 著, 松田信行 訳:幾何の地点を観光することで 1 つの宿泊地で全ての地点
帰納法, 東京図書,1962
を観光することができる.

6定理

56