人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第27回)
SIG-AM-27-04

インタラクティブ観光経路推薦手法の構築に対する検討
Prior Investigation Towards Interactive Sightseeing Route Recommendation
Method柴田祐樹 1∗ 高間康史 1
Hiroki Shibata1
Yasufumi Takama1
東京都立大学大学院システムデザイン研究科
Graduate School of System Design, Tokyo Metropolitan Universiy1

1

Abstract: This paper reports a prior investigation towards an interactive sightseeing route recommendation
method. While most of the traditional recommendation systems just present a few solutions to its user, thisstudy assumes that users establish their own route from the distribution of degree of recommendation. Thedegree is formulated as a probability distribution. A fast iterative sampling method called Exchange Monte
Carlo is employed. The degree of recommendation is assumed to be updated based on the feedback fromusers. Through results by simulation, practical use cases are discussed.

1

はじめに

本稿ではインタラクティブ経路推薦手法について検討する．観光経路推薦では多くの不確実性を扱わなければならない．不確実性の原因として，天候の変化，人の行動に起因する外乱，センサの精度不足などがある．
この前提の推薦であっても利用者との対話を通して推薦内容を改善していくことが可能であり，その枠組みは Human in the loop と呼ばれ，研究が進められている[1]．観光経路推薦では前述の通り状況が刻一刻と変化していく．くわえて，変化に対応して利用者が待てる時間内で再度推薦を行わなければならない．この問題に関して様々な観点から研究が行われている [6, 7, 3]．
観光経路推薦では Traveling Salesman Problem (TSP)の拡張である Selective TSP (STSP) [8] が問題の定式化としてよく用いられる．TSP は最適化問題に含まれる．
最適化問題を定式化として利用した推薦手法では，最適解の近似解のいくらかを候補として推薦が広く行われる [6, 7]．しかしながらこの方法は，利用者に経路を追従する負担を強いることになり，運送計画の決定には適するが，被災地からの避難中や，休暇中の移動など状況の変化が多い用途には適していないと考える．
よって本研究では利用者に経路の大まかな方向を与え，利用者自身で実際の経路を決定可能な推薦の提示方法を考える．
本稿では，離散的な経路を提示するのではなく，経路の分布を提示することで，利用者が分布から経路を描くことができるのではないかと考える．これに対し，不確実性を扱う観光経路推薦の研究の中でも確率分布により経路生成を定式化し，Simulated Annealing (SA)[5] を用いて推薦経路を生成する研究が行われている[3]．しかしながら，[3] は分布の生成のための標本抽出法について論じておらず，確率モデルに適した問題の定式化と，SA による最適化法の提案にとどまる．
SA は温度 0 の極限分布から最適解を抽出するために，モデルの温度と呼ばれる制御変数を複数用いる．
同様に多数の温度を用いて確率分布を近似する手法に，
Exchange Monte Carlo (EMC) [9] と呼ばれる手法がある．SA が極限分布のみを近似するのに対し，EMC は任意の温度の分布を近似することが可能であるため，確率分布を近似する場合は EMC を用いた方が良い．また，EMC は最適化性能においても優れていることが報告されている．
本稿では，[3] の問題定式化に基づき，EMC を利用して確率分布の近似を行う手法を提案し，数値実験結果を，実際の利用場面と照らし合わせて考察する．評
価実験では人工データセットを用い，EMC が SA に比べ優れていることを示す．確率分布を提示することにより，利用者が自ら道順を選択することが可能な推薦
手法は著者らの確認する限り見当たらない．また，同時に，インタラクティブに利用者の状態を反映させることが経路最適化手法を目指した研究も見当たらない．
以上の課題に本研究は貢献する．

∗ 連絡先：東京都立大学システムデザイン学部情報科学〒 191-0065 東京都日野市旭が丘 6-6
E-mail: hshibata@tmu.ac.jp

ー19ー人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第27回)
SIG-AM-27-04

1.1

記法

2.2

n を自然数としたとき，[n] = {1, 2, ..., n} であるとする．
ある集合 A と添字の集合 N があるとき，AN は集合であるとし，その要素 a ∈ AN は ∀i ∈ N [ai ∈ A] を満たす系列であるとする．例えば， x ∈ R[n] は x = (x1 , x2 , ..., xn )で書かれる実数列を意味する．#A は集合 A の要素数を示す．{1, 2, ...} のように {·} を用いて定義されたものは集合であり，(1, 2, ...) のように (·) を用い定義されたものは族であるとする1 ．

2

関連研究

2.1

Traveling Salesman Problem

観光経路推薦の問題定式化に TSP がよく使われる．
N を接点の集合，E ⊂ N × N を辺の集合としてグラフ(N, E) を考える．このとき，TSP は各 n ∈ N を訪れるべき場所，各 e = (n1 , n2 ) ∈ E は n1 , n2 を結ぶ抽象的な経路であると定義する．普通は n1 , n2 を実在の経路で結ぶ最短経路がこれに選ばれる．e には重み we ≥ 0 が割り当てられる．重みはすべての辺に定義される，つまり (N, E) は完全グラフであるとされる． x が有効な経路であることを[[]]P(x) ⇔ x ∈ N [#N+1] , ∀i, j ∈ [#N] xi , x j , x1 = x#N+1と定義する．この制約 P を用いて，TSP は以下の x∗ を求める問題と定義される．

ϕ(x∗ ) = min ϕ(x), ϕ(x) =P(x)#N∑w xi ,xi+1(1)i=1

上記中の ϕ は目的関数と呼ばれる．
観光経路の選定では，訪れるべき場所が定まっているよりも，利用可能な時間が定まっている場合の方が多いと言える．利用時間を制約として，より良い経路を選ぶ問題の定式化に Selective TSP (STSP) [8] がある．
STSP は与えられた制限コスト内で訪れた地点にある価値の総和を最大化する問題として経路最適化問題を定式化する．
STSP，TSP どちらにおいても，考慮するグラフは実際の交通機関を抽象化したもので，グラフは完全であるとしており，実際の道路の接続関係とは異なる．問
題は抽象化され，完全グラフであるため解法を考えやすいという利点がこの定式化にはあるが，観光経路推薦に用いる場合，接点として設定した地点間の経路の情報，つまり移動途中の景観などの情報が失われている，という欠点がある．

観光経路推薦手法は，ユーザ毎の価値観に応じユーザ毎に異なる推薦を行うことができ，またその逆に同じユーザに推薦される経路は，同じ性質を持つものであることが求められる．このために，前節で説明したSTSP の価値は，通常ユーザの価値観をモデル化して決定される．つまり，推薦には価値観モデル化と，モデルからの解の推定をそれぞれ行うための 2 つの手法が必要となる．この 2 つをつなぐのが問題の定式化である．
推薦する経路を求める問題を定式化するが，不確実性に対処するかを考える必要がある．経路推薦における不確実性について論じた文献に [6] がある．前述した価値観モデル自体に不確実性が含まれることから，推薦問題の定式化も不確実性を扱えることが望ましい．不確実性を矛盾なくあつかう枠組みとして，Fuzzy 集合論を [6] では用いている．確率モデルによる定式化を用いた研究には Edge Vector (EV) [3] がある．本研究では主に EV を扱うため，こちらについて詳しく紹介する．
前節で述べたとおり，観光経路推薦では STSP が問題の定式化としてよく使われる．STSP は完全グラフを対象とする．これに対し EV では実際の道路地図を用いる．また，STSP が接点に観光地点の価値を割り当てるのに対し，EV ではすべての道に価値があると仮定する．また，価値，移動負荷は両方とも辺上に定義されるとしてしている．図 1 にこれらグラフの比較を示す．図中左側が従来より STSP で使われているグラフである．背面に灰色で元となった道路地図を意図したグラフを示し，興味ある地点を５つ仮定し，それぞれ興味の度合いを大きさで表現するとした丸で表している．大きな途中の細かい道はすべて抽象化された経路に置き換えられている．これにより問題の規模はものと道路地図よりずっと小さくなることがわかる．右側は EV で仮定されるグラフである．すべての道を興味ある地点と仮定して最適化を行う．問題の規模は，左側のモデル化より大きいため，高速な解法が経路生成において必要となる．これに対し，SA と仮想辺と呼ばれる概念の利用が EV で提案されている．
EV の問題定式化をここで説明する．道路地図のグラフを (N, E) とする．e ∈ E に対し w0e ≥ 0 を道に定義された重み，b0e ≥ [0, 1) を道に定義された価値とする．
n, n′ ∈ N に対し，重み w を次の通り定義する．
[](n, n′ ) ∈ E ⇒ wn,n′ = w0n,n′ , bn,n′ = b0n,n′ ,[](n, n′ ) < E ⇒ wn,n′ = s(n, n′ ), be = −Bs(n, n′ ) .
ただし s は以下で定義される．これは実最短経路を与1 添字が自然数で与えられる場合，族は組や数列という概念に等しい．

ー20

観光経路推薦ー人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第27回)
SIG-AM-27-04

Major spots only

想辺を含む状態は取りづらくなり，最終的に最適解からこれは取り除かれる．しかしながら，完全グラフでない本定式化では，途中仮想辺を経由しなければ遷移が行えない場合があり，遷移しづらいことが問題となる．これは後述する meta-Heuristics により解決される．

All edges are spots

2.3

Proposed

Conventional

組み合わせ最適化問題の近似解法には，Simulated annealing (SA) [5] や遺伝的アルゴリズム [11]，ExchangeMonte Carlo (EMC)[9], 蟻コロニー最適化 [4] と言った
meta-Heuristics (MHs) が一般に用いられる．MHs は局所最適化法と組み合わせて利用する．いずれも，局所最適化を目的関数を低下させる方向にのみ用いる貪欲
法に対し，目的関数の増加を確率的に一時的に認めることで，過適合を防ぐ手法である．TSP 系の問題に対する局所最適化法としては，k-opt 法 [10] が広く用いられる．ここでは MHs のうち，SA と EMC について説明する．
SA, EMC どちらも Markov 連鎖 Monte Carlo(MCMC)法に基づく手法である．標本を抽出したい対象の確率変数を x，その分布を p (x) と表す．MCMC では確率変数の系列 x1 , x2 , ... を用いて x を近似することを考える．このとき，十分大きな i について，⟨xi ⟩ = x となるよな系列を定める遷移確率 p (xi+1 |xi ) が存在する [2]．
実際に X を x の取りうる状態の空間としたとき，任意の x, x′ ∈ X について，以下の定式化を考えることができる．

図 1: Conceptual emages of the formulations used in Selective Traveling Salesman Problem (left) and proposed
method (right).

図 2: Comparison of 2 function shapes used in [3].
えるものである．

s(n, n′ ) = minx,mm−1∑

w xi ,xi+1 , x ∈ N [m] ,i=1x1 = n, xm = n′ , ∀i ∈ [m − 1](xi , xi + 1) ∈ E
B は罰則係数であり，EV では B > 0 の値とされる．これは超パラメータである．辺 e < E を仮想辺と呼ぶ．対応する be は罰則負荷である．以上の重みの元，EV の目的関数は次で定義される．
 m−1
m−1
 ∑∑b xi ,xi+1(2)ϕ(x, m) = Fr  w xi ,xi+1 − C  −i=1

Meta-Heuristics()
p xi+1 = x′ |xi = x =() ()A x′ , x q xi+1 = x′ |xi = x + C(x)δ(x, x′ ) (3)
ここで，(i = j ⇒ δ(i, j) = 1)∧(i , j ⇒ δ(i, j) = 0) は Kronecker のデルタであり，A は次で定義される．
()p (x = x′ )A(x′ , x) = min 1,p (x = x)i=1関数 Fr : R → R は制約関数で，STSP に対応させる場合
は，Fr (x) = lima→∞ exp (ax) と定義する．他に，Fr (x) =Fev (x) の定義も EV では用いられる．図 2 にこれら関数の形状を示す．Fev の定義の詳細は [3] に記載されている．経路の制約は次で定義される．
[]P(x, m) ⇔ x ∈ N [m] ∧ ∀i, j ∈ [m] xi , x j

さらに q は次の対称性を満たすとする．
()()
q xi+1 = x′ |xi = x = q xi+1 = x|xi = x′

時間制約に関しては Fr で表現されるため，上記には明示されない．
仮想辺 e < E が経路 x に含まれているとき，we の定義より，x に罰則が追加される．この仮想辺 e を s(e) と等しい E からなる経路に置き換えた場合の経路を x′ とすると，ϕ(x) > ϕ(x′ ) となるように，B を定める必要がある．通常 B > 1 でこれが満たされる．これにより，仮以上の式 (3) の系により系列を計算する方法は，Metropolis 法と呼ばれ，MCMC 法を実現するために考案された最初のものである．
目的関数 ϕ : X → R が与えられたとき，x の確率分布を次の Boltzmann 分布で定める．
()
1p (x = x|T ) ∼ exp − ϕ(x)(4)
Tー

また，C は次で定義される．
∑()
C(x) = 1 −A(x′ , x)q xi+1 = x′ |xi = xx′ ∈X

21ー人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第27回)
SIG-AM-27-04

この分布を SA と EMC では対象とする．上記分布は Tが小さくなるほど ϕ(x) の値が小さな x が生成されやすくなる分布である．SA ではこの性質を利用し，T → 0 の分布から最適解を抽出することを考える．この極限分布は計算ができないため，実際には MCMC で p (x = x|T )を近似しながら，T を低下させ，極限分布を近似する．
温度の低下のさせ方としては，系列の添字 i に対し，ある定数を T 0 , c 用いて T ∼ T 0 exp (−ci) とする方法がある．
他にも提案されているが，T i > T i+1 であり，T i ≤ T i+1となる温度列を定義することの有用性を主張している
文献は著者らの確認する限り見当たらない．条件が変わった場合に再度最高温度から冷却の過程を実行し直す過程が必要となる．これは，計算済みの近似解を有効利用できないことを意味し，状況の微小な変化への追従性が悪いと言える．つまり，インタラクティブな用途で用いる際の欠点となる．
EMC は複数の温度を (T l |l ∈ L) として用意する．L は適当な添字の集合である．対応する複数の分布 p(xl |T l ), l ∈L を用意する．x = (xl |l ∈ L) と置いて，これら #L の確率変数をまとめて一つの Markov 系列で近似することができる．各 l ∈ L に対する分布の違いは温度だけに限る必要はないが，本稿では温度のみを対象とする．このような異なる超パラメータを持つ確率モデルのことを複製（Replica）と呼ぶ．EMC では，複製を含めた全体のモデルに対するパラメータは不変であり，SA と異なる．この性質により，一度得られた解を引き続き改善することが可能であり，さらにそれぞれの複製は独立して計算することが可能なため，並列性に優れる．
SA，EMC ともに q は，用いる局所最適化法と同等な変化を与えるように定式化を行う．

3

いる複製間で異なる式 (4) の T について以降考える．
温度の組をT = (T 1 , T 2 , ..., T N ) とする．複製の分布( )を p xl , l ∈ L とする．ただし，添字集合 L は L ={l|l = 1, ..., N} と定義する．このとき，すべての複製をまとめた確率変数を単に x と表すこととし，その分布を次で定義する．
∏ ()p (x = x|T ) =p xl = xl |T l ,(5)l∈L

この分布を近似するために，Markov 連鎖 x1 , x2 , ... を考える．遷移確率分布に式 (3) を用いる．q を以降定義する．
ある添字の組 j, k ∈ L の対を無作為に選び以下の入れ替えを行うように q (xi+1 = x′ |xi = x) を定めるとする．

x′ = (x1 , ..., xk , ..., x j , ..., x#L ), x = (x1 , ..., x j , ..., xk , ..., x#L )上述した無作為な添字対の選択と入れ替えを実現する
q は次の通り定義される．これは Gibbs 法に等しい．

()
q xi+1 = x′ |xi = x =∑ () ()∏ ()δ x ′ j , xk δ x ′ k , x j
δ x′ l , xl p(j = j, k = k).
j,k∈Ll, j,k

分布 p(k, j) は添字の選択を行う確率分布である．一様分布とすることもできるが，計算負荷の観点から，近傍の j, k のみ生成される分布とする．式 (3) の A について，式 (5) を代入することで以下を得る．
() ()p xk = x j |T k p x j = xk |T jp (x = x′ |T )().
=p (x = x|T )p (xk = xk |T k ) p x j = x j |T j
目的関数に関して書けば，次のとおりである．丸め誤差の影響を避けるため，実際の計算には以下を用いる．

提案手法

()
p (x = x′ |T )1 (= exp −ϕ(x j ) − ϕ(xk )p (x = x|T )Tk))
1 (−ϕ(xk ) − ϕ(x j ) . (6)Tj

本稿では，EV の定式化を元に，EMC により経路の確率分布を近似する．完全グラフへ変換してから通常の STSP により最適化を実行すれば，EV の定式化は必要ない．しかしながら，その場合道の価値と負荷を変更するたびに完全グラフへの変換を実行しなければならない．利用者の行動履歴から得られる情報は，本来の道路地図に対応したものであるから，変換をせずに扱えたほうが応用性は高いと考える．また，インタラクティブ性の観点から，追加の計算負荷は避けるべきである．従い，提案手法では完全グラフへの変換をせずとも同等の計算が行える仮想辺による EV の定式化を採用する．
目的関数に式 (2) を使う．問題のグラフは EV と同様に仮想辺を用いて実際の道路地図をそのまま用いるものとする．局所最適化方には 2 変数を対象とした k-Opt法を用いる．確率分布には式 (4) を用いる．EMC が用ー

計算の手続きは次のとおりである．

1. 系列の初期値 x0 を設定後，以下を反復
2. 局所最適化と同等な q により各系列 l ∈ L を独立に更新（通常の MCMC）
3. 式 (6) の系により系列間の状態を交換（EMC の主な特色）
4. 目的とするモデル l0 の系列の現在の状態を標本として抽出

22ー人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第27回)
SIG-AM-27-04

SA は SAa, a = 1, 2, 4, 8, 16 で 5 つの条件について評価を行う．この a について，温度は式 (7) により，T (at)により定められる．つまり，a の値が大きければ，急速に温度が低下することになる．
以上の設定で EMC, SAa のいずれからも 8 つの標本を抽出して統計量を算出し，結果を考察する．疑似乱数の計算には Mersenne Twister2 ，実数の近似には倍精度浮動小数点数を用いる．

1.0e+00

0d0.5-0.5

4.2-1.0e+00

図 3: Synthesized map for experiments. Black and graydenote be = 1, be = −1 respectively.

4

評価実験

4.1

設定

格子状グラフを用いた評価実験を示す．座標点の集合を，I = [n] × [m]，接点の集合を N として，全単射
h : I → N により，辺の集合 E を次で定義する．

{}
E = (hi, j , hi+1, j )|i ∈ [n − 1] ∧ j ∈ [m] ∪{}(hi, j , hi, j+1 )|i ∈ [n] ∧ j ∈ [m − 1]
負荷は ∀e ∈ E [we = 1] とする．be (e ∈ E) は be ∈ {−1, 1}の 2 値のみを取るとし，そのうち 8 割は −1 となるように無作為に決定する．以上の定義により生成したグラ
フに b の値により色をつけた可視化を図 3 に示す．黒は be = −1，灰色は be = 1 を示す．市街地では格子状に道が配置されていることが多いため，このグラフを用いた実験は現実的であると考えている．
実験では定常状態に達する過程を観察する．実験の説
明において t は計算の進捗度を表すものとし，t = 0, t = 1でそれぞれ計算開始，計算終了を意味する．∆t を繰り返しの単位とする．実験では ∆t = 2−17 とする．∆t 計
算が進むごとに，それぞれの系列が 26 回，式 (3) により更新され，その後，モデルのパラメタの変更が EMC,SA それぞれの場合で行われる．
温度は以下により設定する．

T (τ) = exp (ln T L + (ln T H − ln T L ) v)

(7)

EMC に対して，この式を用いて，∀l ∈ L, T l = T (τ), τ =(n − 1) / (N − 1) として (T l ; l ∈ L) を定める．N = 64, つまり #L = 64 の複製が用意される．分布を近似する標本は l0 = 64 のモデルから抽出した標本のみを用いる．
状態の交換は l′ = l + 1, l, l′ ∈ L となる組 (l, l′ ) の間で行われる．

ー23

実験結果と考察

目的関数の推移を評価する．ここでは最適化性能のみを計測する．よって，目的関数の値は小さいほうが良い．実験結果を図 4 に示す．EMC の場合が最も低い目的関数の値（Energy）を示している．また，いずれのa についても，EMC は SAa より低い目的関数の値を出している．また，SAa は a が大きくなるほど，つまり温度を急激に低下させるほど精度が悪くなっているとわかる．これに比べ，EMC は急速に最適化が進行した後，その後も時間をかけるほど解が改善していることがわかる．全方法の繰り返し数は等しく，EMC は並列化により複製を並列計算できることから，その計算時間はSA と概ね等しい．それにも関わらず．EMC は SA のどの場合よりも早い段階で良い解を得られており，推薦時間にどのような期限が設定された場合でも一般的に計算を開始することが可能であると言える．一方の
SA では長い計算時間で精度を確保するか，低い精度でも短時間で結果を出すかを計算開始時に決定しなければならないが，これは一般に困難である．このことから，EMC の利用がインタラクティブな推薦に適している考える．実際の利用場面としては，例えば，不測の事態で経路を再計算しなければならないとき，ユーザがそれを緊急の事情により待てない場合が考えられる．
このとき，未知の計算時間で妥当な解の生成を開始でき，加えて時間が確保できた場合は引き続き解の改善を EMC は行える．ただし，このためには問題のグラフを再構成しない EV による定式化が合わせて必要である．
確率分布による可視化について，本稿で検討しているものを図 5 に示す．(a) は EMC, (b) SA1 により生成されたものである．正方形を縦横 256 分割した少領域に重なる経路の頻度を可視化している．(a) の方を見れば，複数の経路が重なる色が濃い部分は選択の余地がなくそこを通るべきであるとわかり，濃い経路の途中にある分岐についてはどれを選んでも問題がないことが見てわかりやすい．一方で (b) の結果では経路にまとまりがなく，道筋を見極めることが難しい．(a) がこのような可視化を可能な理由は，用いた EMC が確率
2 http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/emt.
htmlー人工知能学会 インタラクティブ
情報アクセスと可視化マイニング研究会(第27回)
SIG-AM-27-04

EMCSA2SA4SA8SA16SA114012010080604020

1.1e+00
00.8-400.6prob

1-200.4-60

0.2-8000.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

10.0e+00

図 4: History of objective function for each method.

(a) Exchange Monte Carlo: EMC
分布に従い経路を生成しているため，推薦度が正しくモデル化できているからであると言える．

まとめ

本稿では，インタラクティブ観光経路推薦手法の構築のための，経路分布推定手法を提案し，実験結果を考察した．提案手法は Exchange Monte Carlo 法を利用し，広く用いられる Simulated Annealing よりもインタ
ラクティブ性において優れた性質を持つことを実験により示した．また，推薦度の可視化により，ユーザが経路を自ら設計する場面を検討し，提案手法の想定される場面における応用性を述べた．
今後，インタラクティブ性の評価指標と対応する実験，実データを用意した評価実験を検討する必要がある．また，並列性能の改善，温度の決定法を検討する．

参考文献

1.1e+00
10.8
0.6

prob

50.40.2
0.0e+00(b) Simulated Anneaing: SA1
図 5: Visualized example of route distribution.
[6] Laporte, G., Martello, S.: Tour Route Planning Problem
for Sightseeing with the Multiroute under Several Uncertain Conditions, 2012 IEEE International Conference onSystems, Man, and Cybernetics, pp. 715-720 (2012)[1] Pinto, R., Mettler, T., Taisch, M.: Managing Supplier Delivery Reliability Risk Under Limited Information: Foundations for a Human-in-the-Loop DDS, Decision Support
System, Vol. 58, No. 2, pp. 1076-1084 (2013)[7] Ronny, K., Marko, M., Hagen, K.: A City Guide Agent
Creating and Adapting Individual Sightseeing Tours Basedon Field Trial Results, International Journal of Computational Intelligence Research, Vol. 2, No. 2 pp. 191-206(2006)[2] Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller,
A.: Equation of State Calculations by Fast Computing Machines, The Journal of Chemical Physics, Vol. 21, No. 6,
pp. 1087-1092 (1953)[8] Feillet, D., Dejax, P., Gendreau, M.: Traveling Salesman
Problem with Proﬁts: An Overview, Transportation Science, Vol. 39, No. 2, pp. 188-205 (2005)[9] Hukushima, K., Nemoto, K.: Exchange Monte CarloMethod and Application to Spin Glass Simulations, Journal of the Physical Society of Japan, Vol. 65, No. 6, pp.
1604-1608 (1995)[3] Shibata, H., Takama, Y.: Improvements on Probability
Model for Sightseeing Route Recommendation Method
Employing Generalized Formulation in terms of Edges,
33th International Conference of Technologies and Applications of Artiﬁcial Intelligence, 6 pages (2019)[10] Sohl-Dickstein, J., Mudigonda, M., DeWeese, M.: General k-Opt Submoves for the LinKernighan TSP Heuristic,
Mathematical Programming Computation, Vol. 1, No. 2-3,pp. 119-163 (2009)[4] Dorigo, M., Maniezzo, V., Colorni, A.: Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), Vol. 26, No. 1 pp. 29-41 (1996)[11] Goldberg, D.: Genetic Algorithms in Search, Optimization, and Machine Learning, 1st edition, Addison-Wesley
Professional (1989)[5] Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimization by
Simulated Annealing, Science, Vol. 220, No. 4598, pp.
671-680 (1983)

ー24ー