グラフ理論の分割問題を用いた旅行計画アプリケーションの提案
理学専攻・情報科学コース
はじめに

1

旅行計画はどのような経路で回るのか，何日で観光するのか等，考えることが沢山ある．旅行会社のツアーを利用したり雑誌のおすすめコースを参考にしたりすると楽にはなるが，行きたい観光地を網羅できない可能性もある．そこで旅行に慣れていないユーザーでも簡単に旅行計画が立てられるアプリケーションを提案する．本研究では活動時間，観光地名，宿泊地名を入力すると，観光経路，観光日数，観光地間の経路案内を出力するという機能を持つデスクトップアプリケーションを実装し，考案した分割アルゴリズムについて考察した．

提案手法

2

以下のような重み付き完全グラフ G の分割を考える．
また，マップへの描画や観光地間にかかる時間の取得
等は Google Maps API，デスクトップアプリケーションへの実装はクロスプラットフォーム実行環境であるElectron を使用している．

• 観光地を点，観光地間を結ぶ道を辺とする• 観光地にかける時間を点の重み，観光地間の移動時間を辺の重みとする
本研究では与えられた重み付き完全グラフ G を以下のように分割することを目指している．

• 各集合の経路の重みを指定された値以下にする• 分割数 k を可能な限り小さくする• 移動時間の合計を小さくする

3処理手順

3.1

大まかな分割

3.1.1

この操作によって得られた G の初期分割をゲイン値によって改良する．ゲイン値による分割改良アルゴリ
ズムは後述する．

3.2

細かい分割

以下のような手順で細かく分割していく．
∑1. Si を ⌈ w(x)/t⌉ (x ∈ V (Si )) 個に分割する
2. ゲイン値による分割改良を行う
3. 各集合内のハミルトン閉路の重みを調べる(a) 各経路の重みが t 以下ならば集合を確定する．
(b) そうでなければ重みが t より大きい集合から小さい集合へ点を移動させる．
i. 各経路の重みが t 以下ならば集合を確定する．
ii. そうでなければ重みが t より大きい集合を 2 分割して 2 に戻る．
3.3

宿泊地を決定1 日分の観光地集合と入力された各宿泊地との距離を求めて最も近い宿泊地を集合に割り当てる．
3.4

パスを作成

3.4.1

判定基準

基本的に観光経路は同じ宿泊地を始点と終点とした閉路と宿泊地から次の宿泊地へ移動する宿泊地間の長さ 1 のパスを考えているが，異なる宿泊地を始点と終点としたパスのほうが得をする場合は繋ぎ変える．
S を 1 日分の観光地集合，a を S に対応する宿泊地，b を a とは異なる宿泊地とし，辺 ab を通るような S ，a，b によって形成されるハミルトン閉路を考える．この時，点 x, y ∈ V (S) をハミルトン閉路内でそれぞれ点 a, b と接続している点とする．辺 ab，辺 ax，辺 byのうち長さが近い 2 辺に焦点を当てると，以下の 3 つの配置が考えられる．

重複を許す集合

w(x)，w(y) を点 x，点 y の重み，w(xy) を辺 xy の重み，t を 1 日の活動時間とする．ここでの観光はある拠点から出発して戻ってくる事を想定しているので，ある 2 点を宿泊地から出発して観光した時にかかる移動時間は観光地間の距離の 2 倍以上になる. 従ってある 2 点 x，y において w(xy) + (w(x) + w(y))/2 > t/2
ならば点 x と点 y は同じ集合に属さないように重複を許す集合 S1 . . . Sk を作る．違う集合に属している 2 点は同じ日に観光できないが，同じ集合に属している 2点は必ずしも同じ日に観光しなければならないという訳ではない．
3.1.2

清水蘭

図 1: 辺 ab と辺 by が近い

重複なしの集合|V (Si )| ≥ |V (Sj )|(i < j) とし，添字が小さい集合から確定していく．任意の x ∈ V (Si ) について，x ∈V (Si+1 ) ∪ . . . ∪ V (Sk ) ならば Si を除去し，そうでない時，x ∈ V (Si ) がある j > i について x ∈ V (Sj ) な
らば V (Sj ) から x を除去する．

図 2: 辺 ab と辺 ax が近い
図 1 の場合，S が対応する宿泊地 a に近いので閉路a − S − a のままとする．図 2 の場合，S に対応する

る．上段が負になれば、点 x が集合 A から集合 B へ移動することで移動先集合 B が得をする．同様に下段が負になれば移動元集合 A が得をする．つまり、上式の値が負になれば点 x が集合 A から集合 B へ移動することで集合全体の重みが小さくなる．集合の重みと∑∑k ∑w(xy)i ),y̸=xを意味する．
は， i=1 x∈V (Si ) y∈V|V(S(Si )|−1
全ての点における全ての移動に対して点ゲイン値g Si (x), GSi (x), を求め，その中から g Si (x), GSi (x) が共に負であり g Si (x) が最も小さい値をとるような移動を採用し，最も小さい g Si (x) が正になるまで新たな計算と移動を繰り返す．

図 3: 辺 ax と辺 by が近い宿泊地が b であることを意味するが，ここでは S に対応する宿泊地は a としているのでこのような配置は起こらない．
（そうでなければ各集合に宿泊地を対応させる段階で S に対応する宿泊地は b が採用されるはずである．
）図 3 の場合，元の経路 a − S − a − b よりパス
a − S − b としたほうがかなり得をするのでパスに繋ぎ変える候補とする. パスに繋ぎ変える候補の中で最も得をする（つまり a − S − a − b の辺の重みと a − S − bの辺の重みの差が最も大きい）ものからパスに繋ぎ変えていき，以下のルールによりパスが作れなくなるまで繰り返す．

3.4.2

5

分割改良アルゴリズムの考察

5.1

正当性

初期分割を P1 ，アルゴリズムに則って得られた分割を順に P2 ...Pn ，Pi (1 ≤ i ≤ n) の重みを w(Pi ) とする．
g Si (x) が負の値をとる時，移動する点 x 自身が得をし，GSi (x) が負の値をとる時，移動元集合も移動先集合も得をする場合，移動元集合が損をするがそれ以上に移動先集合が得をする場合，移動先集合が損をするがそれ以上に移動元集合が得をする場合が考えられるがいずれの場合も集合全体は重みが小さくなり得をする．
よって得られた分割の重みが以前の分割の重み以上になることはないので w(Pi ) < w(Pj )(i < j) と分かる．
よって最終分割は初期分割よりも重みが小さい．

パスのルール• 端点は宿泊地• 1 つの端点は自身の集合に対応する宿泊地でもう 1 つの端点は別の集合に対応する宿泊地• 1 つの宿泊地は 2 つ以下のパスの端点になり得る• 1 日分の集合から作られるパスは 1 つ以下• ある 2 つの宿泊地を端点とするパスは 1 つ以下

5.2

ゲイン値による分割改良アルゴリズム

4

n 個の点を k 個の集合に分割する組み合わせは k n 通りで有限である．従って全ての分割を巡ったとしても同じ分割状態に戻らない限り解を見つけて停止する．
正当性の証明よりアルゴリズムに則って移動をすると以前の分割と同じ分割状態になることはない．よって停止する．

与えられた初期分割の改良アルゴリズムとして，ゲイン値による分割改良アルゴリズムを提案する．
点 x ∈ V (A) が集合 A から異なる集合 B へ移動する時のゲイン値 g B (x) を，以下のように定義する．
∑∑{ } w(xi)w(xj)
i∈V (A)\ xj∈V (B)Bg (x) =−|V (B)||V (A)| − 16w(xj)
ここで， |V (B)| は集合 B の点と点 x の間の重みの∑w(xi)
平均， |V (A)|−1 は点 x 以外の集合 A の点と点 x の間の重みの平均を表しているので，ゲイン値が負ならばその移動は点 x にとって得をする．また，点 x が集合A から集合 B へ移動することによって変化する移動元集合と移動先集合の重みの差を以下のように表す．

|V (B)|k∈V (B)+∑(∑i∈V (A),i̸=xj∈V (A),j̸=i,x w(ij)|V (A)| − 2∑−l∈V (B),l̸=k w(kl)

−

参考文献)

|V (B)| − 1∑j∈V (A),j̸=i w(ij)|V (A)| − 1

上式において、上段は点{ }{x }が集合 B へ移った後のk ∈ V (B) と x ∪ V (B) \ k 間の辺の重みの平均と{ }点 x が集合 B へ移る前の k ∈ V (B) と V (B) \ k 間の辺の重みの平均の差の和、下段は点 x{が集合} Bへ移った後の i ∈ V (A), i ̸= x と V (A) \ i, x 間の辺の重みの平均と点x が集合 B へ移る前の i ∈ V (A) と{}V (A) \ i 間の辺の重みの平均の差の和を表してい

まとめと今後の課題

本研究では与えられた重み付き完全グラフの分割と，その初期分割を改良するアルゴリズムを考案，考察をした．また，その一環として旅行に不慣れなユーザーでも旅行計画を立てられるアプリケーションの実装をした．今後の課題として異なる初期分割から得られる解の比較，それに伴う初期分割の改良を行いたい．

∑GB (x) =(∑∑w(kx) + l∈V (B),l̸=k w(kl)

停止性)[1] J.H.van Lint，R.M.Wilson，A Course in Combinatorics，Cambridge University Press，2001[2] B.Hendrickson，R.Leland，A Multi-Level Algorithm For Partitioning Graphs，Supercomputing, 1995. Proceedings of the IEEE/ACM SC95
Conference，pp.28[3] B.Kernighan and S.Lin，An eﬃcient heuristic
procedure for partitioning graphs，Bell System
Technical Journal,29(1970)，pp.291-307[4] Google Maps JavaScript API v3，
https://developers.google.com/maps/documentation/javascript/tutorial?hl=ja