DEIM Forum 2023 3b-6-3

履歴データとインタラクションデータを用いた旅程推薦
大滝 啓介†

馬場 雪乃††† 株式会社豊田中央研究所 〒 112–0004 東京都文京区後楽 1-4-14 後楽森ビル 10F†† 東京大学大学院 総合文化研究科 〒 153–8902 東京都目黒区駒場 3-8-1
E-mail: †otaki@mosk.tytlabs.co.jp, ††yukino-baba@g.ecc.u-tokyo.ac.jp
あらまし 旅程計画は旅行者にとって複雑なタスクである。具体的な旅行のプランや好みを持つ旅行者がいる一方で、明確なプランを持たないが、様々な地点を訪問したいと考える旅行者が存在する。これらの旅行者をサポートすることは、モビリティ社会において重要である。より豊かな旅行体験をサポートすることを目的として、本稿では数理最適化とユーザインタラクションに基づく旅程構築手法について検討する。本稿では最尤計画法に基づく旅程構築に基づき、ユーザとのやり取りで収集できるデータを利用することで、多様な旅程を候補として生成できる新しい手法を提案し、動作を検証した結果について報告する。
キーワード 旅程推薦, オリエンテーリング問題, 最尤計画法, 数理最適化
たり、過去のデータと合わせて利用するといった議論がされて1 はじめに旅行の計画は複雑なタスクである。交通手段や訪問箇所・行動の好みは個人によって様々なため、通常の経路探索や乗換案内と比べ、高度な処理が必要となる。様々な旅行支援手法の中で、本稿では特に最適化に基づく旅程構築手法に着目する [3–5, 8]。
最適化に基づく手法では、オリエンテーリング問題とその亜種を用いた定式化が広く利用されている [6, 13]。オリエンテーリ
ング問題に基づく手法では、対象の地域において候補となる訪問地点として POI (Point-of-interest) の集合と、各 POI を訪問した際に得られる報酬と POI 間の移動コストを定める。このとき、できるだけ多くの報酬を得ながら地点をいくつか巡回する問題を解くことで、得られる解を旅程の候補として利用することができる。オリエンテーリング問題を用いる定式化において、共通の指標（レビューの平均点数など）を用いることで、汎用的な旅程が得られる。一方で個人に特化した指標（あるユーザのレビュー推定値、推定滞在時間など）を用いること
で、個人化した旅程を計算することができる。
個人化した旅程は構築することはより良いユーザ体験のために重要であり、これまでも様々な角度から研究が行われてきた。[5] では、Flickr のログデータから情報を抽出し、旅程を構おらず、手法が限定的である。我々は旅程のランキングをユー
ザに提示するというタスクにおいて、この 2 つのトピックを融合した新しい手法を構築する。
我々の本稿での貢献を以下にまとめる。我々は、関連研究において研究されてきた (1) 過去データに基づく旅程構築 と (2)インタラクションデータの活用の両方の路線に従い、(1) と (2)の両方を活用して旅程のランキングを構築するフレームワーク
を提案する。図 1 に概要を示した。我々は図 1(左上) に示すよ
うに、ユーザから収集した旅程データに基づいて旅程を作成す
る際、図 1(下) に示すようにユーザとのやり取りから情報を抽出して同時に用いることで、旅程のリストを作成する。先に述べた通り、この技法は [1] と [3] の手法をベースに、よりリッチなインタラクションデータを用いることで、異種データを併合
して旅程を構築する新しい手法である。本稿の実験では、手法を実装することで、インタラクションデータを用いることでより多様な旅程の候補を作成することができることを示す。なお
本稿は著者らのワークショップ論文 [11] に基づいて評価指標を見直し、数値実験を再検証したものになっている。

2 準

備

築した。[8] はユーザごとに POI 滞在時間を個人化し、重み付

本稿では自然数 N ∈ Z に対して集合 [N ] = {1, 2, . . . , N }けした目的関数を設計することで、個人化した旅程が効果的でを表し、全ての系列は 1 オリジンとする。POI を表す有限集あることを議論した。[1] では、POI 単位でユーザからフィー

合を I で表し、長さ L の列は X = ⟨X1 , X2 , . . . , XL ⟩ (ここでドバックを受け取り、旅程を構築する手法が議論されている。

Xj ∈ I, j ∈ [L] かつ L = |X| とする) で表す。本稿では POI

また [3] では [1] と似た手法を取りつつも、過去のデータを活

系列が旅程を表すと仮定する。例えば X は X1 を最初に、X2用して目的関数をデータ駆動型で評価する手法を議論していを次に、最後に XL を訪問する旅程とみなす。ある 2 点の POIる。これは経路最適化の分野で近年利用されている最尤計画法

間を旅程 X の中で直接移動するとき、i → j ∈ X で表す。更と似たアプローチである [2, 9]。一方で、ユーザに旅程を提示に i ∈ X は Xt = i である t ∈ [|X|] が存在することを意味すしてフィードバックを得るといったインタラクションは考慮さる。これらの記号 ∈ は列の集合 D = {X1 , . . . , X|D| } についれていない。つまり、フィードバックやデータを用いる個別のて自然に拡張して用いる。本稿の旅程最適化タスクは、k 個の議論はされてきているが、フィードバックの形が限定的であっ旅程を作成してユーザに表示するタスクである。作られた k 個

図 1: 手法の全体概要の旅程リストは L(k) = ⟨X(1) , X(2) , . . . , X(k) ⟩ で表し、添字がとを、制約 (1d) は総移動時間の制約を、制約 (1e)・(1f)・(1g)小さいものがより上位のランクの旅程とする。

は部分巡回路が含まれない旅程になっていることを表す [10]。
最後に式 (1h) は変数を定義している。

2. 1 旅程最適化のためのオリエンテーリング問題

本稿で式 (1) のオリエンテーリング問題を元にして、POI

オリエンテーリング問題はよく研究されている組合せ最適化問題のクラスであり [13]、旅程研究で広く利用されてい訪問から得られるスコアと移動距離の両方を考慮するために、
式 (1a) の目的関数の代わりに式 (2) を用いる。

る [5, 6, 8, 12]。以降では一般性を失うことなく、旅程として 1から出発して N をゴールとするものを考える。オリエンテー
リング問題は、完全グラフ G = (V, E) と G に関連付けられた重みによって定義される。集合 V = [N ] は対象とする N 地
点を表し、2 点間の移動時間 ti,j 、距離 ci,j 、各 POI の評価値

Score(i) が得られるとする。またユーザの要望に応じて、総移動時間 Tmax が与えられる。問題を形式的に定義するための決定変数として、{xi,j ∈ {0, 1} | (i, j) ∈ E} と {ui ∈ Z | i ∈ V }と定義する。ここで xi,j = 1 は POI j を POI i の直後に訪問することを表し、ui はポテンシャルを表す。このときオリエン
テーリング問題は以下の形で定義される最適化問題である。

max α ×

N
−1 X
N
X

x,u

!
Score(i) · xi,j

i=2 j=2

−β×

N X
N
X

!
ci,j · xi,j

i=1 j=1(2)
なお式 (2) の係数 α, β については α = 1 とし、2 つの項の最大値のスケールを揃えるように設定した。また以下に述べる通り長さ L の系列を常に生成する問題を考えるため、式 (1d) の制約を置き換えている。

2. 2 最尤計画法
旅程を X、全ての旅程の集合を X で表す。本稿で X は、長さが L であり 1 から出発して N に到達する旅程の集合である。最尤計画法は、旅程 X の尤度 Pr(X) を目的関数に用

max
x,u

N
X

N
−1 X
N
X

(1a)

xi,N = 1,(1b)i=2 j=2

x1,j =

N
−1
X

j=2

i=1

N
−1
X

N
X

i=1

Score(i) · xi,jxi,k =

野で注目をされている [2, 3, 9]。確率の連鎖律と一階マルコフ性の仮定から、X = ⟨X1 , X2 , . . . , XL ⟩ の 尤度 Pr(X) はPr(X) ≈ Pr(X1 )Pr(X2 | X1 ) . . . Pr(XL | XL−1 ) と近似で
き、Pr(X1 = 1) = 1 の仮定から式 (3) で表現される。

xk,j = 1(∀k = 2, . . . , N − 1),

j=2

(1c)
N
−1 X
N
X

いて maxX∈X Pr(X) を計算する最適化問題であり、この分

ti,j xi,j <= Tmax(1d)

arg max Pr(X)x,u≈ arg minx,uX

− log Pr(Xt+1 = j | Xt = i) · xij(3)(i,j)∈E

i=1 j=2

u1 = 1, uN = L
2<= N (∀i = [N ] \ {1})= ui <
ui − uj + 1 <= (N − 1)(1 − xi,j )
xi,j ∈ {0, 1}, ui ∈ Z(1e)以降では Pi,j := Pr(Xt+1 = j | Xt = i) と表す。

(1f)

2. 3 Top-k 解の生成(∀i, j ∈ [N ] \ {1})1 つの最適解を求める通常の最適化の問題設定と比較して、(1g)

旅程推薦などのアプリケーション指向の設定では複数の解が必(∀i, j ∈ [N ])(1h)

要になる。これは Top-k 最適化の文脈で研究されている手法
である [7]。本稿では簡単に Top-k リストを取得するために、
汎用ソルバーを用いつつ過去の解を制約で除きながら k 個の解ここで式 (1a) はよりスコアの高い地点を訪問すること目的関を生成する。形式的には、L(m) で m 個の解のリストを表し、数として表す。制約 (1b) と (1c) は得られる解が旅程であるこL(0) = ∅ とする。ここで 1 <= k 番目の解を生成するた=m<を行う。インタラクションデータを追加するため、上記の計算方法を以下の最適化問題として解釈する。

P̂ := arg minP(a) 旅程: A → B → C(b) Swap の例: A → C → B

X

Pi,j −

i,jsubject toX|{i → j ∈ D}||{i ∈ D}|

2

(4)

Pi,j = 1 (∀i ∈ [N ])j

遷移確率の計算方法の比較については [2, 9] などで検討されているが、本稿では旅程データの数が少なく貴重なことから、数え上げた POI の出現回数をパラメータ a > 0 を用いてスムー
ジングする簡単な推定手法を用いている。以降では単に履歴(c) Ins の例: A → D → B → C(d) Del の例: A → C

データ D のみから推定する場合の式 (4) の目的関数をロス関

図 2: 編集操作のコンセプト

数 Ldata (P, D) で表す。また履歴データのみから推定した遷移
確率を P̂ := arg min Ldata (P, D) で表す。

めには、これまでの解 X

(j)

∈L

(m−1)

に対して X =
| X

(j)

で

あるような制約を追加する。ソルバーを k 回利用することで、

L

(k)

= {X

(1)

,X

(2)

,...,X(k)} を得る。

3. 2. 2 ステップ 2: 一般化
我々の提案手法のキーアイデアは、式 (4) の推定に対して、図1 で示すようにインタラクションから収集するデータを追加することで新しい遷移確率を推定し、多様な旅程を生成すること

3 提案フレームワークである。直感的には、インタラクションデータを考慮する新しいロス関数を導入し、目的関数を Ldata (P, D) + L(P, D, Dint )本章では、我々が提案する (1) 旅程の過去データと (2) インのように一般化することで、そのような遷移確率を推定するこタラクションデータの両方を活用する旅程最適化フレームワーとができる。ここで L(P, D, Dint ) は確率 P 、履歴データ D 、クについて説明する。

インタラクションデータ Dint から定義されるロス関数である。

3. 1 ユーザによる旅程の編集

以下にそのようなロス関数を編集操作に応じて定義する。

前提として、旅行者は Web サービスやアプリを利用して、置換 (Swap)

例として L

=

4 の旅程 X=′

旅程推薦の結果を確認する。我々は旅程を確認したユーザが、⟨X1 , X2 , X3 , X4 ⟩ と X = ⟨X1 , X3 , X2 , X4 ⟩ を考え、旅程を編集することでシステムにフィードバックを返すと仮定

ユーザは X から X′ を生成したとする。このときユーし、旅程の編集操作として以下の 3 つの操作を導入する。

ザの意図 X ≺ X′ を尤度の関係式 Pr(X) < Pr(X ′ )

置換 (Swap)

旅程中の 2 地点を入れ替える。

挿入 (Ins)

旅程に新しい地点を追加する。

削除 (Del)

旅程から地点を取り除く。

これは既存の研究 [1] で考慮されていた POI 単位のフィード
バックとは異なる。例を図 2 に示す。

3. 2 最尤計画法とフィードバックデータの融合
図 1 と導入した旅程の編集操作に基づいて、提案手法を説明する。提案フレームワークは以下の 3 ステップからなる。
（ 1 ） 過去データから遷移確率行列 {Pi,j }i,j∈[N ] を推定するタ
スクを最適化問題として解釈する。
（ 2 ） 収集したインタラクションデータを追加のデータとして用いて、新しい遷移確率行列を推定する。

で表現し、この不等号を満たすようにロス関数を用いてソフト制約を付与する。例えば、ロス関数として

Lswap (PX1 ,X2 PX2 ,X3 PX3 ,X4 − PX1 ,X3 PX3 ,X2 PX2 ,X4 )を定義し、式 (4) を拡張する。
挿入 (Ins)

例として L = 3 と L = 4 の旅程 X =⟨X1 , X2 , X3 ⟩、X′ = ⟨X1 , X2 , X4 , X3 ⟩ について、ユー′
ザ が Pr(X) <= Pr(X ) を 意 図 し た と す る 。置 換の 場 合 と 同 様 に 、尤 度 の 不 等 式 と し て PX2 ,X3 <=PX2 ,X4 PX4 ,X3 をソフト制約として表現するために、
ロス関数 Lins を定義して用いる。
削除 (Del)挿入 (Ins) の場合と同様に、L = 4 と L =3 の旅程 X = ⟨X1 , X2 , X3 , X4 ⟩、X′ = ⟨X1 , X3 , X4 ⟩についてロス関数 Ldel を用いて、尤度間の関係性をソフト制約として与える。

（ 3 ） 推定した遷移確率行列を用いて旅程を k 個作成する。
以下ではそれぞれの構成ステップに従って手法を説明する。

個別の編集操作で収集したデータをまとめ、蓄積されたイ

3. 2. 1 ステップ 1: 最適化問題

ンタラクションデータ Dint に対して、以下の式で表現され蓄積された旅程履歴データ D から Pi,j を推定する手法

る推定を行うことで、新しい遷移確率を推定する。ここではは既存の研究でも検討されている [2, 3]。本稿では単純に訪

Dint := Dswap ⊔ Dins ⊔ Ddel のようにインタラクションデータ

問回数と遷移回数をカウントすることで推定を行う。つまりが蓄積されていると仮定した。

Pi,j = |{i→j∈D}||{i∈D}|のように、各 POI と POI ペアについて計算

f :=γ × Ldata (P, D)X+δ1 ×

Lswap (X1 , X2 , X3 , X4 )(X1 ,X2 ,X3 ,X4 )∈Dswap

X

+δ2 ×

Lins (X2 , X3 , X4 )(5)

(X2 ,X3 ,X4 )∈Dins

X

+δ3 ×

(p)

(p)

(a) 1st (T1 )(p)(b) 2nd (T2 )(c) 3rd (T3 )

(p)

(p)

Ldel (X1 , X2 , X3 ).

(X1 ,X2 ,X3 )∈Ddel

以 降 で は 推 定 し た 新 し い 遷 移 確 率 を ま と め て P̃:=arg min f (P ; γ, δ1 , δ2 , δ3 ) と表す。
P

3. 2. 3 ステップ 3: 旅程の生成(d) 4th (T4 )

式 (5) に基づいて P̃ を計算した後、2. 3 節で述べた手法に(e) 5th (T5 )図 3: 人気度ベースの旅程

従って k 個の旅程を作成する。新しいロス関数を追加して推定した P̃ と、履歴データのみから推定した P̄ を用いて生成した旅程を比較すると、インタラクションデータに基づいてより多様な旅程が生成されることが期待される。

4 実

験
(ll)

本章では Web サービスから収集した旅程のログデータを用い(a) 1st (T1

(ll)

)

(b) 2nd (T2

(ll)

)

(c) 3rd (T3)て提案フレームワークの動作を検証する。検証のために、Ldata
は式 (4) に対してスムージングパラメータ 0.001 でスムージン
グしたものを採用し、編集操作は置換 (Swap) のみを扱い、ロス関数には tanh(·) を用いた。
(ll)

4. 1 設(d) 4th (T4定Web サービス TripHobo にユーザが公開データとして記録している旅程を 2022 年 6 月地点で収集して用いた。各 POI の(ll)(e) 5th (T5))

図 4: 尤度ベースの旅程（この数値例では尤度ベース+人気度
ベースの旅程として同じリストを得た）

スコア Score(i) は TripAdvisor のレート（☆）の数値をそのまま用いた。データを収集する際、Tokyo でタグ付けられた複
数日の旅程を収集し、各日の移動を全て別々の旅程とみなして収集し、旅程の履歴データ D を構築した。全体のデータセット
から、特に Asakusa に関連する旅程だけを抽出して原理検証に利用した 1 。結果として 245 個の旅程データを収集し、最終的(i+p+ll)(a) 1st (T1(i+p+ll)(i+p+ll)) (b) 2nd (T2) (c) 3rd (T3(i+p+ll)(i+p+ll))

な D を得た。なお D には 29 個の POI が含まれていた。
出力として k = 5 本の旅程を 2. 3 節の手法に従って生成した。擬似的なインタラクションデータを作成するために、P̂ の
情報と 29 P4 の 4 つ組ペアの中から、M = 300 個の訓練用の操作データを作成し、学習に利用した。パラメータは置換 (Swap)にのみ注目したため、γ = 0.25, δ1 = 16, δ2 = δ3 = 0.0 を用いた。

4. 2 結果と考察
a ) 生成した旅程の可視化(d) 4th (T4) (e) 5th (T5)

図 5: インタラクションデータ+人気度+尤度ベースの旅程b ) 数値的な評価生成された旅程をスコア (PN −1 PN
i=2

j=2 Score(i)xi,j ) と移動

29 個の POI のうち出発地と目的地をランダムに選択して固コストで評価する。図 6a は目的関数の式 (2) の項を評価し、x定した上で、手法によって生成された経路群を比較する。本稿

軸に得られたスコア、y 軸を移動コストで散布図を描いたもの

では人気度ベースの旅程（図 3）、尤度ベースの旅程（図 4）、人である。図 6a より、人気度順のランキングと比較して、多様気度と尤度の両方を考慮した旅程（図 4 と同等）、更にインタな旅程が生成されていることが分かる。特にインタラクション

ラクションデータを追加した旅程（図 5）をそれぞれ図示した。

データを与えた結果は、それ以外の旅程と異なる様子が定性的に確認できた。

1：POI の緯度経度を [35.443674, 35.825408] かつ [139, 514896, 139.927981]の領域のみのデータを抽出した。

c ) 生成された旅程ランキングの評価
次に k 個の旅程リストについて図 6a で評価した数値が並んだリストを考え、スコアに対して NDCG@k (Normalized

Discounted Cumulative Gain@k, ここでは k = 5) を計算し、旅程全体を [0, 1] × [0, 1] 上の点として可視化した結果を図 6bに示す。
結果より、人気度としての評価値を少し犠牲にしながら、移動コストについての NDCG@k を改善したことが分かる。一方
でここでの NDCG@k を用いた評価はあくまでも提示された k
個の旅程だけに注目した評価であるため、注意が必要である。

(a) スコア・コスト軸の散布図 (個(b) スコア・コスト軸で NDCG@5

別の旅程)

を用いたランキング全体の評価

より大域的には、大量に用意した候補の中から、実際に出力した旅程の評価を行う必要があると考えられるが、旅程研究ではこれらの議論が十分にされていない。そのため今後はランキングとしての評価を議論していく必要がある。

4. 2. 1 インタラクションデータの数量とリストの変化
最後にインタラクションデータと生成される旅程の関係性を観察した。図 6c に、生成されるリストが学習データの個数でどのように変化するのかを可視化した。図の x 軸は学習データで利用した個数（0 から 500 まで 50 刻み）であり、y 軸はランキングを、線は同じ旅程が生成されたことを意味する。この結(c) 訓練データ数とランキングの推移

図 6: 旅程とランキングの評価。図 6a: スコアとコストの散布図。図 6c: 学習データの個数と上位 5 個の旅程の変遷。

果は、ある一定量のインタラクションデータを集める必要性を示唆している。そのため今後は、効率的なデータの収集や P̃ の学習手法の検討など、少数のインタラクションデータを有効活用する学習手法を検討する必要があると考えられる。
図 3、4、5、6a、 6c の結果より、インタラクションデータを用いることで多様で評価指標の意味で異なる旅程とランキングを生成できたことが分かる。別の解釈をすれば、我々の手法はインタラクションデータを用いることで、旅程ランキングを多様化することができた。今後の技術的な課題としては、学習手法の工夫や少量のインタラクション・正例の旅程データの有効活用などが考えられる。

5 ま と め旅程の履歴データとインタラクションデータを用いて、最尤計画法を用いて旅程のリストを構築する手法を提案し、実験によって生成された旅程の比較やランキングの変化を観察した。
今後、より詳細な学習手法やインタラクションの設計、ユーザ実験などを予定している。

文

献[1] Senjuti Basu Roy, Gautam Das, Sihem Amer-Yahia, andCong Yu. Interactive itinerary planning. In Proceedings of
ICDE2011, pp. 15–26, 2011.
[2] Rocsildes Canoy and Tias Guns. Vehicle routing by learning from historical solutions. In Proceedings of CP2019, pp.
54–70, 2019.
[3] Dawei Chen, Cheng Soon Ong, and Lexing Xie. Learning
points and routes to recommend trajectories. In Proceedingsof CIKM2016, pp. 2227–2232, 2016.
[4] Admilson Alcântara da Silva, Reinaldo Morabito, andVitória Pureza. Optimization approaches to support theplanning and analysis of travel itineraries. Expert Systems

with Applications, Vol. 112, pp. 321–330, 2018.
[5] Munmun De Choudhury, Moran Feldman, Sihem AmerYahia, Nadav Golbandi, Ronny Lempel, and Cong Yu. Automatic construction of travel itineraries using social breadcrumbs. In Proceedings of HT2010, pp. 35–44, 2010.
[6] Zachary Friggstad, Sreenivas Gollapudi, Kostas Kollias,
Tamas Sarlos, Chaitanya Swamy, and Andrew Tomkins.
Orienteering algorithms for generating travel itineraries. In
Proceedings of WSDM2018, pp. 180–188, 2018.
[7] Eugene L Lawler. A procedure for computing the k bestsolutions to discrete optimization problems and its application to the shortest path problem. Management science,Vol. 18, No. 7, pp. 401–405, 1972.
[8] Kwan Hui Lim, Jeﬀrey Chan, Christopher Leckie, andShanika Karunasekera. Personalized tour recommendation
based on user interests and points of interest visit durations.
In Proceedings of IJCAI2015, pp. 1778–1784, 2015.
[9] Jayanta Mandi, Rocsildes Canoy, Vı́ctor Bucarey, and Tias
Guns. Data driven vrp: A neural network model to learn
hidden preferences for vrp. In Proc. of CP2021, pp. 42:1–
42:17, 2021.
[10] Clair E Miller, Albert W Tucker, and Richard A Zemlin. Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), Vol. 7, No. 4, pp.
326–329, 1960.
[11] Keisuke Otaki and Yukino Baba. Maximal likelihood
itinerary planning with user interaction data. In Proceedings of the Workshop on Recommenders in Tourism (RecTour2022), Vol. 3219 of CEUR Workshop Proceedings, pp.
37–46. CEUR-WS.org, 2022.
[12] Kendall Taylor, Kwan Hui Lim, and Jeﬀrey Chan. Travel
itinerary recommendations with must-see points-of-interest.
In Proceedings of WWW2018, pp. 1198–1205, 2018.
[13] Pieter Vansteenwegen, Wouter Souﬀriau, and Dirk
Van Oudheusden. The orienteering problem: A survey. European Journal of Operational Research, Vol. 209, No. 1,
pp. 1–10, 2011.