アニーリング法による乗り合いのマッチング最適化
理学専攻・情報科学コース
はじめに

1a<ba

Jab ，ha は 2 次，1 次の係数である．式 (1) の変数 qik ，ylk は xa ∈ {q11 , q12 , · · · , qIK , y01 , · · · , yLK } と変換される．
2.2

実行データ

駅から多くのユーザーが移動するような状況を想定した仮想データを作成した．図 1 に作成データの一例を示す．ユーザー数は 50 人とし，3 方面に偏った状態で分布している．

乗り合いにおけるクラスタリング

2.1

佐藤 由佳

L はタクシーの乗車定員，l は乗車人数である．本研究では，L = 4 とした．変数 ylk はタクシー k の乗車人
数が l 人かどうかを決定する．l 人であれば 1，そうでなければ 0 をとる．式 (4a)，(4b) は各項のペナルティ
係数 α，β を別々に調整する必要がある．
アニーリング法を利用するため，式 (1) を以下のQUBO に変換する．
∑∑
H=
Jab xa xb +
ha xa
(5)

近年，移動利便性の向上や移動手段確保の観点から，乗合タクシーやオンデマンドバスといった乗合型の交通サービスが全国的に検討，普及し始めている．本研究では都市部における乗合タクシーに着目し，同じ出発地から異なる目的地に移動するタクシーユーザー（以下，ユーザー）が多くいるようなシチュエーションでの乗り合いを考えた．
乗り合いは，タクシーの乗車定員などの制約条件を満たしつつ，乗り合う複数ユーザーのマッチング，すなわち組合せを求める問題として捉えることができる．
このように，制約条件のもとで目的関数を最小化もしくは最大化する問題は最適化問題と呼ばれ，特に解の集合が組合せ的な構造を持つ問題を組合せ最適化問題という [1]．本研究では，この組合せ最適化問題に対し，アニーリング法によるクラスタリングを適用し，ユーザー集団のグループ分けを行った．

21940647

乗り合いのモデル

乗り合いの数理モデルは，以下である．

H=K ∑I∑

dij qik qjk + Hp1 + Hp2(1)

k=1 i<jdij はデータ間距離，I はユーザー数，K はタクシー数を示す．変数 qik はユーザー i におけるタクシー kへの乗車の有無を表しており，乗る場合は 1，乗らない場合は 0 となる．Hp1 ，Hp2 は制約項である．ユー
ザー i，j が同じタクシーに乗った場合のみ，データ間距離が加算される．同じタクシーに乗ったユーザーのデータ間距離が短いほど，式 (1) の第 1 項が小さくなり，最適な組合せが求められる．
本研究では，特徴量として各ユーザー間の目的地の位置情報を与え，データ間距離を算出した．
√dij = (lati − latj )2 + (lngi − lngj )2(2)

図 1: 作成データの一例．赤ピンが出発地，オレンジの点が各ユーザーの目的地を示す．

2.3

50 人のユーザー集団を 15 台のタクシーに乗り合わせることとした．シミュレーテッド・アニーリング法（以下，SA 法）を用いて実行した．図 2 がクラスタリング結果を地図にマッピングしたものである．この結果は，2 つの制約条件を満たし，かつペナルティ係数の小さい解である．目的地が近いユーザー同士が同じクラスになるよう，クラスタリングされていることが確認できた．

lat，lng はそれぞれ平均 0，分散 1 となるよう標準化された緯度・経度である．標準化は以下のように行なった．
forg − µ(3)σforg が元データ，µ は平均，σ は標準偏差を表す．
また，式 (1) の制約項 Hp1 ，Hp2 はそれぞれ「ユーザー 1 人は 1 台のタクシーにしか乗れない」，「タクシーには L 人以下しか乗れない」という制約条件を表し、次式で示される．
f=

Hp1 = αI (∑K∑)2qik − 1

Hp2 = β{ IK(∑∑
k=1i=1qik −L∑l=03)2
lylk+L(∑ylk − 1)2

大規模ユーザー集団分割におけるクラスタリング

本研究ではユーザー集団が大規模になると，求める乗り合いのグループ規模が最大 4 人と細かく分割する必要があるため，1 つの目的関数で良い近似解を求めることが難しい．そのため，前章のクラスタリング処理を行う前処理として，ユーザー集団の大まかな分割をアニーリング法を用いて行った．

(4a)i=1 k=1

アニーリング結果}

3.1

大まかな分割を行うモデル

3 つの分割手法を検討し，比較した．どの手法も数理モデルの第 1 項の最小化をアニーリング法によってl=0(4b)1す．第 2 項は式 (7) と同様である．第 3 項はクラスタ数を増やそうとする制約であり，クラスタ数が増えると和が小さくなる．これは，第 1 項がクラスタ数を減らす傾向を持つため，導入している．

3.2

SA 法を用いて第 2.2 節と同様の分布を持つ 100〜
500 人の仮想データに対し，手法の検証を行った．同じタクシーに乗るユーザーの目的地間の距離の総和であるコスト，タクシー数，アニーリング回数を比較した．その結果を以下の図で示す．コストは 2 クラスタ分割が最も小さくなり，複雑な手法を取るほど大きくなる傾向にあることが確認できた．タクシー数は分割手法による大きな差は生じなかった．またアニーリン
グの回数はユーザー集団の規模によってばらついているが，大体 K クラスタ分割，2 クラスタ分割，コミュニティ検出を応用した K クラスタ分割の順に増えていることが分かる．

図 2: クラスタリング結果（タクシー 15 台）．赤ピンが出発地，同色の点が同じクラスに属するユーザーの目的地である．
求める．

• 2 クラスタ分割手法
H=∑

dij (2ci − 1)(2cj − 1)

比較結果

(6)

i<j

データ間距離 dij は式 (2) で与えられている．変数 ci ∈ {0, 1} はユーザー i がどちらのクラスに所属するかを示す．同じクラスに属するユーザー間のデータ間距離は正の値で加算され，異なるクラスに属するユーザー間のデータ間距離は負の値で加算される．そのため，データ間距離の離れたユーザーは異なるクラスタに所属した方が式 (6)のコストは小さくなる．

(a) コスト．

(b) タクシー数．

• K クラスタ分割手法

H=K ∑I∑

dij qik qjk + α

k=1 i<jI (∑K∑)2qik − 1(7)i=1 k=1

データ間距離 dij は式 (2) である．変数 qik ∈ {0, 1}
はユーザー i がクラスタ k に所属するか否かを示す．データ間距離の離れたユーザーは異なるクラスに所属した方が式 (7) の第 1 項は小さくなる．
第 2 項はユーザーがちょうど 1 つのクラスに所属するようにする制約項であり，ペナルティ係数 αでその制約の大きさを調整する．

(c) アニーリング回数．

図 3: 分割手法の比較．紺が 2 クラスタ分割，青が K
クラスタ分割，オレンジがコミュニティ検出を応用した K クラスタ分割の結果である．

4• コミュニティ検出を応用した K クラスタ分割手法 [2]H =−本研究では，2 段階のクラスタリングにより乗り合いのマッチング処理を行った．大規模ユーザー集団の分割におけるクラスタリングにおいては 3 つの手法を検討し，それぞれの特性を観察した．その結果，時間（アニーリング回数）と解の良さがトレードオフの関係になっており，良い解を求めるには 2 クラスタ分割を用いればよく，それなりの解を高速に得たい場合には K クラスタ分割を用いれば良いことがわかった．

( d2 )
ijexp − 2 qik qjk
2σi<jK
Imax ∑∑
k=1+αI (Kmax∑∑
i=1+γ)2qik − 1

参考文献

k=1KImax ∑∑qik qjk

まとめ[1] 梅澤俊治，「組合せ最適化入門：線形計画から整数計画まで」，自然言語処理，Vol.21，1059-1090（2014）．

(8)

k=1 i<j第 1 項はデータ間距離 dij を正規分布に基づいて負数としたものを係数としており，変数 qik ∈ {0, 1}
はユーザー i がクラスタ k に所属するか否かを示[2] 増田直紀，今野紀雄，「複雑ネットワーク 基礎から応用まで」，近代科学社，（2010）．

2