「マルチメディア，分散，協調とモバイル(DICOMO2021)シンポジウム」 令和3年6月-7月

交通機関利用時の心理状態を考慮した三密を回避するための交通経路推薦手法の検討
田谷 瑛悟1,2

平野 陽大1

松田 裕貴1,2,3

諏訪 博彦1,2

安本 慶一1,2

概要：現在，COVID-19 の流行に伴って，三密を回避するための経路推薦システムが求められている．既存の研究において混雑を考慮した経路を推薦するシステムは存在するが，交通機関の利用人数を考慮し，接触リスクの低い経路を推薦できるシステムは我々の知る限り存在しない．本研究では，時間や費用などの移動に伴って消費するリソースを抑えつつ，ユーザが三密を回避できる経路推薦手法を提案する．我々は交通機関利用時に感じる心理状態に着目する．ユーザは交通機関を利用して移動したとき，他人との接触が多いと感染の恐れから不安に感じると考える．そこで，移動に伴う他人との接触回数と時間から接触リスクを定義し，リスクを最小化する経路を求める．一方で，追加の行動（乗換・徒歩など）が発生すると，ユーザは自身のリソースを消費するため不快に感じると考える．そこで，接触リスクに加えて，時間・
費用・スタミナの 3 要因を消費リソースと定義し，接触リスクと消費リソースを最小化する多目的経路探索問題を解く．本稿では上記の問題を定式化し，遺伝的アルゴリズムの一つである NSGA-III に基づくア
ルゴリズムを提案する．また，奈良県奈良市地域を対象に，アルゴリズムの有用性を評価するための評価実験を設計する．

Proposal of a route recommendation method balancing reassurance
index and coziness index to avoid the Three Cs in public transportation
EIGO TAYA1,2

YODAI HIRANO1 YUKI MATSUDA1,2,3
KEIICHI YASUMOTO1,2

HIROHIKO SUWA1,2

な経路情報を十分に提供することが挙げられる [3]．経路

1. はじめに情報が不足すると，ユーザは目的地に移動するための適切

現代社会において，公共交通機関は人々の生活を支えるな移動手段か判断できずに不安を抱き，利用を諦める場合

移動手段としての役割を果たしており，公共交通機関の維がある．そのため，ユーザに対して適切な経路情報を提供

持は社会的な課題となっている [1]．公共交通機関を維持し，利用の不安を取り除く必要がある．

するためにはユーザの満足度を向上させ，交通機関の利用2019 年 11 月に中国の武漢市で確認された COVID-19 はを促進する必要がある [2]．ここでの満足度とは，交通機その後爆発的に感染拡大し，2021 年 5 月時点で人間社会に関利用前後におけるユーザのサービスに対する総合的な経

対して経済的・衛生的・社会的に深刻な問題を引き起こし験と定義されており，車内の清潔さや安全性，料金，定時ている [4]．これを受け，世界中の人々が日常生活におい運行性など，様々な要素から構成される．満足度向上のたて他人と 2m 以上の物理的な距離を取る「ソーシャルディ

めには，清掃方法見直しによる車内の清潔さの向上やダイ

スタンス」を実施し，感染拡大の防止に努めている．しかヤの見直しによる定時運行性の向上などのアプローチが考し，電車やバスのような，大勢の人が 1 つの車両に乗車すえられる．アプローチの 1 つとして，交通機関利用に必要るような公共交通機関を利用する場合，乗客同士の物理的距離を保つことは難しく，感染のリスクがある．このよう123奈良先端科学技術大学院大学
理化学研究所 革新知能統合研究センター（AIP）
国立研究開発法人科学技術振興機構 さきがけ

© 2021 Information Processing Society of Japanな状況下において，ユーザは交通機関の利用に不安を抱き，利用を取りやめる可能性がある．今後も COVID-19 によ― 1180 ―る影響が継続すると見込まれ，交通機関のユーザ減少を防に関連した既存研究の概要と課題について述べる．3 章でぐための解決策を模索することが急務となっている．我々

は，提案システムの実現に向けた問題設定と想定する環境

は，その解決策の 1 つとして交通経路推薦が有効だと考えを示す．4 章で，適用するアルゴリズムについて述べ，5 章

る．感染のリスクは，他人と一定の物理的な距離を確保でで，評価実験の設計について述べる．最後に，6 章で本稿きない状態（三密）が 15 分程度継続することで高まる．そについてまとめる．

のため，他人と接触回数を減らせるような交通経路を把握し，移動すれば感染リスクを抑えられる．これを実現する
ためには，他人と接触する回数と時間を考慮した経路推薦

2. 関連研究2.1 経路推薦システム
一般に経路推薦システムでは，道路や交通網を基に作成が必要となる．
これまでに様々な交通経路推薦法が提案されており，各されたグラフネットワークに対して，出発地から目的地にユーザの嗜好やコンテキストに適した経路を推薦する研究

到達する際の総コスト（時間や距離など）が最適な経路をが存在する [5], [6], [7]．一部の研究では，車両の混雑度を求める．これによりユーザの経路選択を支援することが可基に経路を推薦する研究 [8], [9] が存在するものの，混雑度能になるが，ユーザの要求は必ずしも単一ではない．例えをカテゴリ（満車，空席わずか，空車など）として扱ってば，目的地に最も早く移動できる経路を知りたいユーザもおり，人数は考慮していない．感染症が流行する状況下にいれば，最も安い料金で移動できる経路を知りたいユーザ

おいては，交通機関の利用人数を考慮し，他人との接触リも存在する．このようなユーザの多様な要求に応えるため

スクの低い経路を推薦する必要があるが，そのような経路に，様々な手法を用いた交通経路推薦システムが提案され推薦に関する研究は著者らの知る限り存在しない．

ている．

本研究では，時間や費用などの移動に伴って消費するリ

Rohit らは，インドの通勤者の嗜好に応じて快適なルー

ソースを抑えつつ，ユーザが三密を回避するための経路推トを推薦するためのシステムを提案している [5]．スマー

薦手法を提案する．手法実現のために，我々は交通機関利

トフォンから収集される GPS 情報やクエリ情報を基に車用時に感じる心理状態に着目する．ユーザは交通機関を利

両の移動速度や座席占有率を推定し，推定結果を基に快適用して移動したとき，他人との接触が多いと感染の恐れかなルートを選択している．Liu らは，各都市において，よら不安に感じると考える．そこで，移動に伴う他人との接り個人に適した経路を推薦するためのシステムを提案して触度合い（接触回数と時間）から接触リスクを定義し，三いる [6]．具体的には，ユーザからのクエリが発生した時密を回避する経路を推薦する．一方で，ユーザは移動する

点で，時間や料金などの単一の目的関数に基づき，移動手

とき，自身のリソース（時間，費用，スタミナ）を消費す

段ごとの最適な経路を探索する．その後，天候や地理などる．そのため，三密を回避するために追加の移動（乗換，の都市特有データと検索クエリから構築された分類モデル

徒歩移動など）が発生すると，回避しない場合と比べて，を用いて，各ユーザの嗜好に即した経路を選択している．

到着時刻が遅くなる，歩くことで疲労するなど，リソース

Handte らは，Wi-Fi を用いて各バス車内の混雑度を収集の消費が大きくなる．ユーザのリソースは限られているた

し，混雑を回避する経路推薦システムを提案している [9]．

め，接触リスクの最小化により消費リソースが大きくなる

バスの運行本数が多く，代替できる経路が多く存在するエ

ことは望ましくない．そこで，本研究では，接触リスクにリアであることを前提に，同時刻帯の便の中から最も混雑

加えて，時間・費用・スタミナの 3 要因を消費リソースとしない経路を推薦している．Bajaj らは，車両の混雑度や定義し，接触リスクと消費リソースを考慮した経路推薦を遅延を用いて交通の不便さをモデル化し，ユーザの過去の行う．これにより，ユーザに対して感染のリスクが低く，

検索クエリに基づいて経路を推薦している [8]．Wang ら移動による負担が少ない経路を提示可能とする．

は，ユーザの移動状態や時々刻々と変化するコンテキスト

本稿では上記の問題に対し，接触リスク・時間・費用・に適した経路を推薦するために，a*アルゴリズムのヒュー

スタミナを目的関数とする多目的経路最適化問題として定リスティック関数をニューラルネットワークを用いて学習式化する．経由する地点の数を N とすると，この問題は少させる手法を提案している [7]．Hu らは，危険物の配送になくとも 2N 以上の組み合わせ数が存在するため，現実的おいて，より配送リスクの少ない経路を推薦するために，な時間で解を求めるためにはヒューリスティックアルゴリ

都市の道路からリスクをモデル化し，より少ない経路を選ズムで解く必要がある．そこで，遺伝的アルゴリズムの一択している [10]．

種である NSGA-III に基づいてアルゴリズムを設計する．

以上の研究では．多様なユーザの要求に対応するために，また，提案手法の有効性を評価するため，奈良県奈良市の過去に収集した検索クエリなどを用いてユーザの嗜好に適「ならまち」と呼ばれる地域を対象に評価する実験を設計した経路を推薦している．一部の研究では車両の混雑や，する．

輸送のリスクを考慮しているが，交通機関の利用人数から以降の章構成は以下の通りである．2 章では，提案手法© 2021 Information Processing Society of Japan

感染リスクを考慮して経路を推薦する研究は，著者らの知― 1181 ―る限り存在しない．本研究では，移動時における他人との接触回数や時間から接触リスクを定義し，移動における感染のリスクを抑えることを目指す．一方で，移動に伴って発生するコスト（時間，金銭，スタミナ）を消費リソース

べる．

3. 問題設定
3.1 想定環境と定義し，接触リスクと消費リソースのトレードオフを考

本研究では，COVID-19 のような感染症が流行する社会

慮する．すなわち，本研究では複数の目的関数におけるト情勢下で，人々が三密を回避することが求められている状

レードオフを考慮した多目的経路探索問題を解くことが目況を想定する．このような状況下において，移動者の目的的となる．

を他人との接触リスクの最小化と設定する．接触リスクを抑える一方で，移動者は乗り換えや迂回によって追加のリ
ソースを消費する必要がある．ここでのリソースを所要時2.2 多目的経路探索問題
一般に，多目的経路探索問題を解くアプローチは，スカ

間，費用，スタミナの 3 要素と設定する．本問題は特定地

ラー法とパレート法に大別される [11]．スカラー法では複域内の移動における PoI（駅・停留所を含む地点）の選択

数の目的関数を単一の目的関数に変換することで多目的経と移動方法を接触リスク・所要時間・費用・スタミナの 4路探索問題を解く．例えば，各目的関数に対して重みを設要因を目的関数として各関数のトレードオフを考慮する．

定し，重みの線形加重和を求めることで単一の目的関数に

図 1 に扱う問題の概念図を示す．システムに入力され変換する手法などが存在する [12], [13]． この手法では 1 回

る情報を出発地と目的地とし，移動方法（徒歩，バス，電の実行で 1 つの解しか求めることができず，パレートフロ

車，タクシー）と PoI の選択・並び替えを探索の対象とす

ンティア（最適な解の集合）を求めるためには繰り返し実る．そして探索の結果として，複数の経路情報，接触リス

行する必要がある．加えて，各目的関数に対する順位付け

ク，消費リソースを設定する．以上より，本問題は移動にを事前に設定しておく必要がある．経路推薦においてユー

伴う消費リソースの最小化と接触リスクの最小化を目指す

ザの要求（時間や料金など）は多様であり，事前に目的関

多目的経路最適化問題である．

数を順位付けることは難しい．従って，本研究で扱う問題
に対し，スカラー法を適用することは最適であるとは言え3.2 前提条件
本研究では，接触リスクを算出するために運行している

ない．
一方でパレート法は，解同士の優越関係を利用して探索

交通機関の利用人数を収集する必要がある．従来の経路推することで多目的経路探索問題を解く．スカラー法と比較薦システムでは，「空車」「空席多数」「満車」のように混して厳密なパレートフロンティアは得られないものの，一雑情報をカテゴリとして扱っており [5], [8], [9]，個々の運度の探索で近似的なパレートフロンティアを得られる．ま行車両における利用人数を考慮して推薦するシステムは存た，多くのパレート法では遺伝的アルゴリズムが採用され在しない．しかし，近年では IoT デバイスの高機能化に伴ている [14], [15], [16], [17]．これらのアルゴリズムは高い

い，リアルタイムに利用人数を計測可能になりつつある．

探索性能を持つことが知られているものの，目的関数が 4

現に，著者らが所属する研究グループでは，利用者の持つつ以上存在する「多数目的最適化問題」において解の収束

スマートフォンから発せられる BLE 信号を基に，リアル性に問題があることが指摘されている．そこで，解探索にタイムに利用人数を収集するシステムの実現に取り組んで

おいて方向性を与えることで多数目的最適化問題においている [20]．従って，本研究では交通機関の利用人数は計測

も収束性が低下せず，多様なパレートフロンティアを求めできる情報として問題を設定する．

られる NSGA-III が提案されている [18]．本問題は接触リ
スク・時間・費用・スタミナの 4 つの目的関数を扱う多数

3.3 定式化

目的最適化問題であり，通勤者や観光客など幅広いユーザ

経路の制約を対象にするため，多様な経路を求める必要がある．従っ

本研究で扱う問題は，公共交通機関を利用する移動者をて，本研究で扱う問題に対し，パレート法の NSGA-III で対象に，移動に伴う接触リスクと消費リソースを最小化で解くことが適していると考える．

きる経路を求める問題である．特定地域内に存在する全て

これまでに著者らが所属する研究グループでは，観光にの PoI（観光地・駅・停留所）に対し，移動者の経由是非

おけるリソース消費と満足度を最適化する問題に取り組んの集合を P oI とし，移動者がある PoI を経由するかどうでいる．Hirano ら [19] は，NSGA-II と 2-opt を組み合わかを pi で表す．このとき，移動者が PoI の i を経由して目せたアルゴリズムを提案しており，現在は NSGA-III に拡的地へ移動する場合，pi は 1 となり，移動しない場合は 0

張することでより多様な解を求めることに取り組んでいとなる．この制約を式 (1) で表す．

る．本稿ではこのアルゴリズムを交通経路推薦の問題に適用し，問題の定式化やアルゴリズムの設計方法について述© 2021 Information Processing Society of Japan― 1182 ―pi ∈ {0, 1}

(1)

入力

探索空間

出力

移動手段

出発地

複数の経路

目的地
徒歩

バス

電車

タクシー

既知の情報
接触リスク

2

3

1
PoI1
PoI2

Path1
Path2

・混雑情報
・消費リソースS

G

消費リソース

時間・混雑情報
・消費リソース
・移動手段

費用

スタミナ

5

4

図 1

本問題の概要図

また，ある PoI の i から j へ移動できるかを xijlm で表移動に必要な費用 E は，PoI 間を移動するときに利用すす．移動者が到着時刻 l までに移動手段 m で pi から pj にる交通手段の料金と設定する．従って費用 E は式 (7) のよ

移動する場合，xijlm は 1 となり，移動しない場合は 0 とうに定義される．

なる．この制約を式 (2) で表す．また，出発地から目的地へ移動する移動者が経由する xijlm のリストを X と定義

E=

N ∑
N
N ∑
N ∑
∑

eijlm xijlm(7)

i=1 j=1 l=1 m=1

し，式 (3) で表す．

xijlm ∈ {0, 1}(2)

X = (xi1 j 1 l1 m1 , xi2 j 2 l2 m2 , · · · , xin j n ln mn )(3)

移動の所要時間 T は，PoI 間の移動にかかる時間と PoIでの乗り換えや待機にかかる時間と設定する．従って所要時間 T は式 (8) のように定義される．

k

式 (3) において，n = k における到着地点 j と，次の経
路 n = k + 1 の出発地点 i

k+1

T =

は等しくなければいけない．

tijlm xijlm +i=1 j=1 l=1 m=1

また，n = k + 1 における到着時刻 l は，n = l における到着時刻よりも大きい必要がある．これらの制約を下記の式

N ∑
N ∑
N ∑
N
∑

N
∑

t i pi(8)

i=1

次にスタミナを定義する．本研究では文献 [19] に従い，消費するスタミナを肉体的な疲労と定義し，疲労の指標でで表すあるカロリーからスタミナを求める．ここで，肉体的な疲

ik+1 = j k(∀k ∈ {1, n − 1})(4)

lk+1 > lk(∀k ∈ {1, n − 1})(5)

労は PoI の移動と PoI での行動で求まるとし，式 (9) で定義される．

PoI での行動（乗り換えや待機など）や PoI 間の移動でS=接触する人数を c, 所要時間を t，費用を e，スタミナを s

N ∑
N ∑
N ∑
N
∑

sijlm xijlm +i=1 j=1 l=1 m=1で表す．特に，経由する pi で接触する人数を ci ，所要時間

N
∑

si pi

(9)

i=1

を ti ，スタミナを si とし，経路 xijlm で移動するときに接本問題は，出発地から目的地に向かうときの接触リスク，

触する人数を cijlm ，所要時間を tijlm ，費用を eijlm ，スタ

所要時間，費用，スタミナの最小化を目的とする．従って，

ミナを sijlm と定義する．

目的関数を以下の式 (10) で定義する．

接触リスクと消費リソース

Minimize R, E, T, S

はじめに接触リスクを定義する．R で表される接触リス

subject to (1)(2)(3)(4)(5)

クは，PoI で行動，および PoI 間を移動したときに接触した人数と時間により決定する値と仮定した．従って接触リ
スク R は式 (6) のように定義される．ここで，式 (6) の第1 項は PoI を移動するときの接触リスクを表し，第 2 項はPoI に滞在しているときの接触リスクを表す．
R=

N ∑
N ∑
N ∑
N
∑

cijlm tijlm xijlm +i=1 j=1 l=1 m=1© 2021 Information Processing Society of Japan

N
∑
i=1

ci ti pi(10)

3.4 問題の困難性
本問題は，出発地の PoI から目的地点の PoI に移動する経路のうち，接触リスク・時間・費用・スタミナが最小となる経路を求める問題である．この問題を移動手段を徒歩(6)のみに限定し，各 PoI の経由有無を考える問題に単純化した場合において，経由 PoI の組み合わせ数は 2N 通り存在

― 1183 ―する．本問題では，徒歩以外の移動手段（電車・バス・タ

本節では表 1 の変数を用いて，アルゴリズムの各ステップクシー）や各 PoI での待機を考慮に入れるため，組み合わについて説明する．

せ数は少なくとも 2N 通りよりも大きい．そのため，全て初期化の経路に対して接触リスク・時間・費用・スタミナを考慮

アルゴリズムの探索世代数を T ，母集団の数を N ，初期

して探索する場合，現実時間内で解くことは困難である．

アーカイブ母集団 Q0 = ∅ に設定する．その後，N 個の経

従って，ヒューリスティックアルゴリズムを適用して問題路データを生成し，初期の探索母集団 P0 を設定する．

を解く必要がある．

トーナメント選択
探索母集団 Pt からランダムに個体を選択し，各個体の4. 提案手法

接触リスク・費用・時間・スタミナを用いてトーナメント

4.1 アルゴリズム概要

を適用する．そしてトーナメントにおいて優れた N/2 個

本研究の目的は，経路のコストを多目的化した探索により複数の多様な経路を提示し，移動者の意思決定を支援すの個体を Qt に追加する．
変異ることである．そのため，移動者に提示する経路は必ずし

Qt の中からランダムに α ∗ N/2 の個体を選択（α は変異もパレート最適解である必要はないものの，移動者が納得確率）し，選択個体に対して増加変異を実行する．また一できる質を持つ解（準パレート最適解）が必要となる．そ方の α ∗ N/2 の個体に対して，減少変異を実行する．

こで解の多様性を担保するように設計された NSGA-III[18]非優越ソート
各世代 t（1 ≤ t ≤ T ）において，母集団とアーカイブに基づいて，アルゴリズムを設計する．
なお，提案アルゴリズムでは一般的な遺伝的操作である母集団を組み合わせて，At = Pt ∪ Qt を生成する．この「交叉」を含んでいない．本問題で求める経路（解個体）は，

At に対して非優越ソートを実行し，全個体をランク i 毎に制約 (4),(5) の通り，前後の経路に対して時間の順序関係分類する．ランク i は，ある解を完全に優越する解の数とを考慮している．そのため，交叉によって前後の経路を入して算出される．全ての解のランクを決定するために，式れ替えると致死個体となる可能性が極めて高い．従って，(6)(7)(8)(9) で算出される各要素に関して比較する．そし提案アルゴリズムでは交叉は行わず，変異のみで解を探索て，At に従って各ランクごとに Fi (i = 1, 2, . . . ) に解を追

する．

加する．
ニッチ保存
次世代の探索母集団 Pt+1 = ∅ を生成し，変数 i = 1 を

4.2 解の表現方法
本問題では，出発地から目的地に移動するための移動手設定する．そして，非優越ソートで与えたランク上位の個段と経由する PoI の順番を移動者に提示する必要がある．

体から探索母集団 Pt+1 に対して，|Pt+1 | + |Fi | ≤ N であ従って，本アルゴリズムで扱う解個体は図 2（左）のようる限り，要素を加える．すなわち，Pt+1 = Pt+1 ∪ Fi とに，2 つの PoI とその間を移動するための移動手段の列とi = i + 1 を実行する．このとき，|Pt+1 | + |Fi | = N となして扱う．この解個体の移動手段列（左）は PoI と移動手

る場合は，ニッチ保存操作を終了して次ステップに移行す

段の分割表現（右）に相互的に変換可能である．解個体のる．一方で |Pt+1 | + |Fi | > N となる場合は，Fi に対して

移動手段列（左）は．遺伝的アルゴリズムの解個体の保存

リファレンスラインと解の垂直距離を算出し，より多様性のために使用し，PoI と移動手段の分割表現（右）は突然の高い解を N − |Pt+1 | 個選択し，Pt+1 に追加する．

変異のために使用する．
Mode

記号

Path
Walk

Walk

Bus

1-3

3 - 21

…

Bus

Bus

…

Train

Walk

Walk
21 - 62

1

3

21

…

34

62

PoI

図 2

4.3 遺伝的アルゴリズムの詳細
図 3 にアルゴリズムのフローチャートを示す．提案アルゴリズムは初期化処理，変異，非優越ソート，トーナメン
ト選択，ニッチ保存操作のステップより構成されている．

© 2021 Information Processing Society of JapanT

GA の最終世代

N

母集団数 (|Pt | = |Qt | = N )Pt

解個体の経路表現（左）と個体の分割表現（右）― 1184 ―表 1 アルゴリズムで用いる変数とその説明
説明

t 世代目の探索母集団(遺伝子操作により更新)

Qt

t 世代目のアーカイブ母集団

At

Pt と Qt の和集合i

非優越ソートで各個体に与えられる評価値t

アルゴリズムの現在の世代

α

変異確率

𝑷𝟎 = 𝟒のとき

初期化

4
1

10

7

5

トーナメント選択

8

S

11

2

G

出発地

目的地

変異

K-1
12

6

3

9

徒歩15分以内

徒歩15分以内

非優越ソート

図 4 初期解の生成例
ニッチ保存

待できない．そこで，PoI の数が偏らないように，増加変
異と減少変異をそれぞれ変異確率 α に対して 1/2 の確率で

No
最終
世代か？

実行する．
増加変異

Yes

図 5 に増加変異の例を示す．はじめに，既に遺伝子に含終了まれている PoI を除く全ての PoI の中から追加する PoI を
ランダムに 1 つ選択する（図中では PoI の 23）．また，移図 3 遺伝的アルゴリズムのフローチャート

動手段についてもランダムに選択する（Taxi）．次に，新たに PoI を追加する位置をランダムに決定し，決定された

4.4 初期解の生成

PoI の位置から出る方向に対して移動手段を追加する．

初期解の生成は遺伝的アルゴリズムの 1 処理であり，初期探索母集団 P0 に追加する N 個の個体を作成する．本ア
ルゴリズムでは遺伝子操作の交叉を行わないため，経由する PoI や交通手段をランダムに選択すると，解が収束しない可能性が高い．そこで，本アルゴリズムでは出発地から減少変異
図 6 に減少変異の例を示す．削除する PoI をランダムに選択し，PoI と同じ位置にある移動手段を削除する．なお，減少変異は解個体の PoI 数が 2 よりも大きい場合にのみ実行する．

目的地に比較的短い時間で移動できる経路を初期解に設定する．
図 4 に初期解生成の例を示す．はじめに，出発地及び目的

Mode

Walk

Train

Bus

地から徒歩 15 分範囲内の PoI から集合 P oIs と P oIg を作”Taxi”をランダムに選択成する．そして P oIs , P oIg からランダムに PoI を選択し，PoI”23”をランダムに選択

N 組の sd ペア（図中では {1, 10}, {1, 12}, {2, 11}, {3, 11} の

PoI

Mode

Walk

Walk

位置をランダムに決定

1

3

Walk

Bus

21

34

62

Bus

Train

Walk

削除位置をランダムに決定

PoI

1

3

21

34

Walk

Train

Walk

62

4 組）を作成する．この N 組の sd ペアに対して，ダイク
ストラ法を用いて移動時間が最小となる経路を探索する．

Taxi

Train

Walk

求めた N 組の経路に対して，出発地と目的地に移動する経路情報を付与した解を初期解として設定する．

1

4.5 変異

3

図 5

21

23

34

62

増加変異の例

1

3

34

62

図 6 減少変異の例

変異は，解個体が持つ遺伝子の一部を変更することで，新しい解を生成する遺伝的アルゴリズムの処理である．本
アルゴリズムでは，PoI（遺伝子）をランダムに 1 つ追加
する増加変異と，PoI をランダムに 1 つ削除する減少変異

5. 評価実験の設計
5.1 実験目的を用いる．これは，解の多様性を表す指標である PoI の数

本研究で扱う問題は，実際の交通機関を利用するユーザが，多い解あるいは少ない解ばかりに収束しないように考（移動者）を対象とするため，どれくらいの時間で，ユーザ慮するためである．PoI の数がどちらかに収束すると，遺が納得できる解を求められるか明らかにする必要がある．

伝的アルゴリズムの探索が局所的になり，解の多様性が期

そこで，実在する地域を対象にアルゴリズムを適用し，計© 2021 Information Processing Society of Japan― 1185 ―図 7

ならまちのポイントプロット（緑：駅，赤：観光地，青：バス停留所）

算時間と解の多様性を評価することを目的 1 とする．また，実際に利用者に解を提示し，解に対する満足度を評価することを目的 2 とする．

6. おわりに
本稿では，交通機関利用に伴って消費するリソースを抑えつつ，三密を回避するための経路推薦手法について検討し

5.2 評価アプローチ
目的 1 に対しては，シミュレーション実験を行う．評価の観点として，(1) 出力解がそれぞれが優劣してないか，(2) 求めた経路は現実的なルートか，(3) 解の多様性はある
か，(4) 現実的な時間内に終了するかを設定する．そして，遺伝的アルゴリズムの世代数などのパラメータを変化させて複数回実行し，解に対して (1)〜(4) の観点で評価する．
目的 2 に対しては，実証実験を行う．本実験を行うためには，提案アルゴリズムに加え，UI を含む経路推薦システ
ムとして構築する必要がある．評価の観点としては，（1）
推薦経路に対する満足度に加え，（2）経路推薦するまでの時間，（3）ユーザビリティなどを設定する．実験参加者にた．そして，扱う問題の定式化をするとともに，NSGA-III
を用いたアルゴリズムを設計した．今後は設計したアルゴ
リズムに基づいてシステムを構築して評価実験を行い，提案手法の有効性について検討する．また，本研究で扱う問
題の組み合わせ数は多く，NSGA-III による解探索でも実行時間が大きくなることが予想される．そのため，システ
ムの実装に並行して有効な局所探索法などの手法を検討
し，実行時間の短縮を目指す．
参考文献
[1]

経路推薦システムを使用した移動を実際にしてもらい，探索時や移動後の主観的評価をアンケートにより収集する．

[2]

5.3 実験対象エリア
本実験では，アルゴリズムを奈良県奈良市を対象に 33[3]箇所の観光地が存在する地域（図 7）に対して適用することで提案手法を評価する．図の地域は通称「ならまち」と呼ばれ，日本でも有数の観光地であり，観光客が多く訪れ[4]

る．一方で，ならまち付近にはオフィス街や学校も多数存在し，通勤・通学する人も多く存在する．そのため，なら
まちでは電車，バス，タクシーの交通網が発達しており，[5]

図中内に駅は 5 箇所，停留所は 104 箇所存在する．本研究では，これらの観光地，駅，停留所，合計 143 箇所の PoI[6]を含む地域を対象とする．今後，当該エリアを対象に，シミュレーション実験および実証実験を行う．

© 2021 Information Processing Society of Japan― 1186 ―国 土 交 通 省.
令 和 2 年 版 国 土 交 通 白 書.
https://www.mlit.go.jp/hakusyo/mlit/r01/
hakusho/r02/pdf/kokudo.pdf. Accessed: 2020-07-07.
Dea van Lierop, Madhav G. Badami, and Ahmed M.
El-Geneidy. What inﬂuences satisfaction and loyalty inpublic transport? a review of the literature. Transport
Reviews, Vol. 38, No. 1, pp. 52–72, 2018.
T. D. Camacho, M. Foth, and A. Rakotonirainy. Pervasive technology and public transport: Opportunities beyond telematics. IEEE Pervasive Computing, Vol. 12,
No. 1, pp. 18–25, 2013.
World Health Organization. Coronavirus disease (covid19) pandemic. https://www.who.int/emergencies/diseases/novel-coronavirus-2019. Accessed: 202105-01.
Rohit Verma, Surjya Ghosh, Mahankali Saketh, Niloy
Ganguly, Bivas Mitra, and Sandip Chakraborty. Comfride: A smartphone based system for comfortable public
transport recommendation. 2018.
Hao Liu, Yongxin Tong, Panpan Zhang, Xinjiang Lu,
Jianguo Duan, and Hui Xiong. Hydra: A personalized and context-aware multi-modal transportation recommendation system. Association for Computing Machinery, 2019.

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Jingyuan Wang, Ning Wu, Wayne Xin Zhao, FanzhangPeng, and Xin Lin. Empowering a* search algorithms
with neural networks for personalized route recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data
Mining, KDD’19, pp. 539–547, New York, NY, USA,2019. Association for Computing Machinery.
G. Bajaj, G. Bouloukakis, A. Pathak, P. Singh, N. Georgantas, and V. Issarny. Toward enabling convenient urban transit through mobile crowdsensing. In 2015 IEEE
18th International Conference on Intelligent Transportation Systems, pp. 290–295, 2015.
M. Handte, S. Foell, S. Wagner, G. Kortuem, and P. J.
Marrón. An internet-of-things enabled connected navigation system for urban bus riders. IEEE Internet ofThings Journal, Vol. 3, No. 5, pp. 735–744, 2016.
Hao Hu, Xiang Li, Yuanyuan Zhang, Changjing Shang,and Sicheng Zhang. Multi-objective location-routing
model for hazardous material logistics with traﬃc restriction constraint in inter-city roads. Computers &Industrial Engineering, Vol. 128, pp. 861–876, 2019.
Sandra Zajac and Sandra Huber. Objectives and methods in multi-objective routing problems: a survey andclassiﬁcation scheme. European Journal of Operational
Research, Vol. 290, No. 1, pp. 1–25, 2021.
Diclehan Tezcaner and Murat Köksalan. An interactive
algorithm for multi-objective route planning. Journal of
Optimization Theory and Applications, Vol. 150, No. 2,
pp. 379–394, Aug 2011.
Luciano Costa, Thibaut Lust, Raphael Kramer, andAnand Subramanian. A two-phase pareto local searchheuristic for the bi-objective pollution-routing problem.
Networks, Vol. 72, No. 3, pp. 311–336, 2018.
Carlos Fonseca and Peter Fleming. Genetic algorithms
for multiobjective optimization: Formulation discussion
and generalization. the ﬁfth Intl conference on Genetic
Algorithms, Vol. 93, , 02 1999.
J. Horn, N. Nafpliotis, and D.E. Goldberg. A nichedpareto genetic algorithm for multiobjective optimization.
In Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, pp. 82–87 vol.1, 1994.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A
fast and elitist multiobjective genetic algorithm: Nsgaii. IEEE Transactions on Evolutionary Computation,
Vol. 6, No. 2, pp. 182–197, 2002.
Eckart Zitzler, Marco Laumanns, and Lothar Thiele.
Spea2: Improving the strength pareto evolutionary algorithm for multiobjective optimization. Vol. 3242, 01
2001.
Zhihua Cui, Yu Chang, Jiangjiang Zhang, Xingjuan Cai,and Wensheng Zhang. Improved nsga-iii with selectionand-elimination operator. Swarm and Evolutionary
Computation, Vol. 49, pp. 23–33, 2019.
Yodai Hirano, Hirohiko Suwa, and Keiichi Yasumoto.
A method for generating multiple tour routes balancing
user satisfaction and resource consumption. In Proceedings of the International Workshop on Smart Sensing
Systems, IWSSS’19, 2019.
金光勇慈, 立花巧樹, 松田裕貴, 中村優吾, 諏訪博彦, 安本
慶一. ナッジを用いたコロナウイルス接触確認アプリのインストール促進. 第 39 回社会における AI 研究会, pp.
1–6, 2020.

© 2021 Information Processing Society of Japan― 1187 ―