アニーリングマシンを用いたタクシー利用効率化
佐藤由佳

1(指導教員：工藤和恵)

はじめに

L はタクシーの定員，l は乗員数である．変数 ylk はタ
クシー k に l 人乗る場合は 1，そうでない場合は 0 を示す．ペナルティ係数 α, β を調整することで，二つの制約を満たし，コスト関数が最小となる解の探索を行う．
マシンに実装する際は，目的関数を次式のようなQUBO（Quadratic unconstrained binary optimization）に変換する必要がある．
∑∑
H=
Jab xa xb +
ha xa
(6)

近年，首都圏では通勤・通学時間帯における鉄道遅延や運休が日々発生している．遅延や運休が発生すると，代替手段であるタクシーはとても混み合う．この問題の解決策の一つとして，ユーザの乗り合いが挙げられる．一方で，他人とタクシーを乗り合うことに不安を感じる人も多く，目的地だけでなく，性別などのユーザの属性も考慮したグループ分けが必要となる [1]．
そこで，本研究ではアニーリングマシン「デジタルアニーラ」を利用して，距離・年齢・性別を考慮したユーザのグループ分けをシミュレーションし，観察した．アニーリングマシン「デジタルアニーラ」（以下，マシン）とは，量子アニーリングの原理をデジタル回路で再現し利用することで，組合せ最適化問題を高速に解けるハードウェアである [2]．

2a≤b式 (1) を変換すると，変数は xa = (q11 , q12 · · · , qIK ,y01 , · · · , yLK ) と置換されて，(I + L + 1)K 次元のベクトルとなる．Jab , ha はそれぞれ 2 次と 1 次の項の係数である．次元数はマシンのビット数を示す．マシンは 1024 ビット，完全グラフの環境を持つので，問題サイズはこの環境に収まるよう設定した．

モデル
グループ分けの目的関数は次式で示される．

H=IK ∑∑dij qik qjk + Hp1 + Hp2

3

ユーザデータの準備

本研究では具体的に，タクシー利用の状況を朝の通勤・通学時間帯に錦糸町駅で JR 総武線の上り方面の電車が止まった場合とし，タクシーのユーザを想定した．
ユーザの特徴量は直線距離，年齢，性別である．直線距離は出発地を錦糸町駅，目的地を両国駅，東京駅，御茶ノ水・秋葉原駅の 3 方面周辺の法人住所データから設定した．また，年齢と性別は通勤・通学定期利用者の分布を基に乱数データを作成した．図 1 は作成したユーザデータの分布である．

(1)

k=1 i≤jdij はデータ間距離，I ，K はユーザ数，タクシー数を示す．変数 qik はユーザ i がタクシー k に乗るかどうかを表し，乗る場合は 1，乗らない場合は 0 となる．
Hp1 ，Hp2 は制約項である．式 (1) を最小化することで，最適な組合せを求める．式 (1) の第 1 項（以下，コスト関数）は，ユーザ i, j が同じタクシーに乗るときのみ，データ間距離が加算される．同じタクシーに乗ったユーザ同士のデータ間距離が短いほど，コスト関数は小さくなる．
データ間距離は，ユーザの持つ各特徴量 f ごとに異なる重み wf を課し，算出した．本研究では，特徴量として出発地から目的地までの直線距離 l，年齢 a，性別 s を与え，重みは wl : wa : ws = 5 : 2 : 1 とした．
∑∑
dij =wf (fi − fj )2 /wf(2)
f =l,a,sa

f =l,a,sfi は，特徴量 f のユーザ i に関する値である．各特徴量は平均 0，分散 1 になるよう標準化されている．forg
は元データ，µ, σ は平均，分散を表す．
forg − µ(3)σ式 (1) の制約項 Hp1 ，Hp2 は，それぞれ「ユーザ 1 人は 1 台のタクシーにしか乗れない」，「タクシーには L人までしか乗れない」という制約であり, 次式のように表せる．
f=Hp1 = αI ∑K∑(qik − 1)2

図 1: ユーザデータの分布4

解かせる問題をタクシーの定員 4 人， 50 人のユーザが 15 台のタクシーに乗るグループ分けとし，アニーリングを実行した．このときに使用したビット数は 825 ビットである．式 (4) の制約の大きさを示す係数を α = 2と固定し，式 (5) の制約の大きさを示す係数 β を大きくしていくことで， 制約を満たさない人数とコスト関数の変化を観察し，チューニングを行った．
図 2 より， 係数 β が大きくなると，相対的に係数α が小さくなり，式 (4) が効きづらくなるため，1 人(4)i=1 k=1

Hp2 = βKILL∑∑∑∑{(qik −lylk )2 + (ylk − 1)2 }k=1i=1l=0

アニーリング結果

l=0(5)
7

のユーザが複数のタクシーに乗る，もしくはどのタクシーにも乗らないユーザが出てくる．また β = 0 に着目すると，どちらの制約も満たしており，式 (5) がなくとも乗車定員を守っているように見える．図 3 では，コスト関数が β = 0 で最小値をとり，複数のタクシーに乗った人数が増えるとコスト関数も上昇していることが確認できた．つまり，このグループ分けの解は，目的関数のペナルティ係数が α = 2, β = 0 のときであることを示す．

図 4: 式 (4) の制約を満たさない人数の α 依存性．凡
例の数字はタクシー数．

図 2: 各制約を満たさない人数の β 依存性

図 5: 式 (5) の制約を満たさない人数の α 依存性．凡
例の数字はタクシー数．

5

まとめと今後の課題

本研究では，タクシーユーザのグループ分けをアニーリングマシンで行い，制約項の係数 α, β のチューニング過程を観察した．係数 α = 2 のときは β = 0 で最適解となり，制約を満たさないとコスト関数は上昇することがわかった．また，乗車定員の制約項の必要性が確認できた．今後は，データ間距離のチューニン
グや目的関数に新たな制約を加えて，より現実的なシミュレーションが行えるようにモデルを改良していきたい．

図 3: コスト関数の β 依存性
以上の結果を踏まえると，乗車定員の制約として式(5) の必要性に疑問を持った．そこで，タクシー数を 13〜16 台と変動させ，式 (5) の制約がない状態 (β = 0)で，式 (4) の制約の大きさを示す係数 α を大きくしていくと，制約を満たさない人数はどのように変化するのかを検証した．
図 4 より，係数 α を大きくしていくと，式 (4) の制約が効くため，各ユーザが 1 台のタクシーに乗るようになる．一方，図 5 では，どのタクシー数でも係数 αを大きくしていくと，いずれは定員を超えたタクシーに乗ってしまう人が出てくるという結果が得られた．
よって，乗車定員の制約として式 (5) は必要であることが分かる．

謝辞本研究は未踏ターゲット事業の支援を受けています．

参考文献[1] 国土交通省, 「相乗りタクシー実証実験の結果」, http://www.mlit.go.jp/report/press/
jidosha03_hh_000288.html, （2018 年 9 月 28日アクセス）.
[2] 富 士 通, 「Digital Annealer」, http://www.
fujitsu.com/jp/digitalnnealer, （2018 年 11月 10 日アクセス）.

8