京都観光問題

TSPと京都観光問題の違い
TSP
設定された場所数に
おける最短経路長探索
京都観光問題
それぞれの場所数に
おける最短経路長探索
+
どの地点を巡回するか考慮
＝
計算規模が更に大きくなる
Doshisha University, Intelligent Systems Design Laboratory
京都観光問題
京都観光問題の定式化
f1=Total distance
制約条件）
f2=1/(The number of places)
総時間＝拝観時間+移動時間
1/観光場所数
目的関数）
パレート最適解
集合
多目的最適化
「トレードオフの関係に
ある複数の評価基準を
同時に最適化」
総距離
出来るだけ少ない距離
で多くの箇所を訪れる
ことが目標
Doshisha University, Intelligent Systems Design Laboratory
制約によるパレート解への影響
制約（時間制限）なし
各観光場所数における
総距離が最小の巡回路
＝
パレート解
制約（時間制限）あり
拝観時間の短い観光
場所が選ばれる
60分
解は悪くなる
15分
Doshisha University, Intelligent Systems Design Laboratory

Download Report