Comments
Description
Transcript
将来の混雑状況予測に基づく 混雑回避巡回スケジューリング手法の提案
将来の混雑状況予測に基づく 混雑回避巡回スケジューリング手法の提案 栗山 恭嘉 村田 佳洋 柴田 直樹 † 安本 慶一 伊藤 実 奈良先端科学技術大学院大学情報科学研究科 † 滋賀大学情報管理学科 移動経路，訪問施設での混雑状況を考慮しながら効率よく目的地を巡回するスケジューリング手法の確立は，観 光の満足度や配送計画などのビジネス効率を高めるために重要である．これまで，ユーザ間で経路情報を共有 し互いに重複しない移動経路を選択することで混雑を緩和する方式や，直近の混雑情報から最も混雑していな い地点を次に訪問することで特定の地点へのユーザの集中を防ぐ方式が提案されているが，各移動経路，各地 点での待ち時間の両方を考慮されておらず，観光目的への利用を考える際には不十分である．そこで本研究で は，各移動経路，各地点の混雑を同時に考慮した複数地点巡回スケジューリング手法を提案する．本手法では， 各ユーザの希望巡回地点リストから時刻毎の各地点，各経路の混雑状況を予測し，予測混雑下においてユーザ の要望をできるだけ満足するよう，経路だけでなく巡回順序の変更や巡回地点数の削減を行ったスケジュールを 算出し，各ユーザが混雑を避けて満足度の高い地点をなるべく多く巡回し，希望する時間までに帰還できるよ う，複数のユーザについて同時にスケジューリングを行う．提案手法を実装し，実験を行った結果，各ユーザが 独自の判断で行動した場合に比べて，提案方式では 20-30% 程度高い満足度を達成できることを確認した． Proposal of Congestion Alleviation Scheduling Technique for Car Drivers Based on Prediction of Future Congestion on Roads and Spots Hisaka Kuriyama Yoshihiro Murata Naoki Shibata† Keiichi Yasumoto Minoru Ito Nara Institute of Science and Technology † Shiga University For efficient sightseeing tour and business in urban areas, it is important to establish the scheduling method to visit multiple spots efficiently by taking into account congestion of routes and facilities on those spots. There are some existing studies on a route scheduling method which enables users to select different routes by sharing route information with other users, and a spot scheduling method which stimulates users to select different spots based on the latest congestion situation on the pots. However, these existing studies are not perfect for the purpose of sightseeing tours, since they do not treat congestion of routes and spots at the same time. In this paper, we propose a method for predicting congestion of routes and spots in the future based on the prearranged user schedules indicating in what order users visit spots. Using the predicted results, we adjust each user’s schedule by changing visiting order of spots and reducing the number of visiting spots, satisfying user’s preference as much as possible. We have implemented the proposed method. Through experiments, we confirmed that the proposed method achieves 20 to 30 % higher user satisfaction degree than existing methods. 1 はじめに 計画などのビジネス効率を高めるためにも重要である． さらに，観光地などにおいて特定のサービス施設 (テー 多様な活動が高密度になされる都心部では，交通網に マパーク，水族館，レストラン，駐車場など) へ来訪者 慢性的な混雑が生じており，人々に多大な時間的損失を が集中した際には，サービスの所要時間に加えて，サー もたらしている．また，観光地においては，近年の動向と ビス開始までの待ちが発生するため，来訪者の円滑な活 して，レクリエーション活動の単位が団体から家族，小 動を妨げるだけでなく，近隣交通網の混雑を誘発する要 グループへと変化しており，観光地周辺の道路網では今 因ともなりえる．よって，魅力ある多くの観光スポット 後よりいっそうの自家用車による混雑が予想される [1]． への訪問可能性の向上など，訪問者に快適な観光活動を このような環境下において，移動経路上の混雑状況を考 保証するため，移動経路に加えて，各訪問地における混 慮しながら効率よく目的地を巡回するスケジューリング 雑状況も考慮したスケジューリング手法が切望されてい 手法の確立は，個人移動者が長時間移動により被る不快 る． 感の軽減に留まらず，オンデマンドバス，運送業の配送 1 移動経路の混雑を回避する代表的な手段として，交通 くのユーザが優先度の高い地点を多く巡回できることを 網の渋滞状況を考慮した経路作成，案内を行う車載カー 確認した． ナビの利用が挙げられる．カーナビは従来，起終点間の 2 最短距離経路の算出が目的であったが，センサー技術，通 関連研究 本章では，我々の研究グループが提案した観光用ナビ 信デバイスの高性能化により，その時々の情報を利用し たサービスが可能となった．VICS(Vehicle Information ゲーションシステム，また，文献 [4,5,6,7] で提案された混 and Communication System) [2] はその最たる例であり， 移動者は VICS センターで編集，処理された最新の道路 混雑情報を，路上に設置されたビーコンを介して入手し， 雑回避手法について説明する．本研究では，文献 [4,5,6,7] その情報を基に混雑を回避した経路選択が可能となる． 観光用ナビゲーションシステム P-Tour で提案されるシミュレーションモデルを実験に用いるた め，ここではより詳細に説明を行う． しかし，カーナビは現在の混雑状況に基づいて迂回経路 我々の研究グループは，複数目的地に対する巡回スケ を案内できるが，多数のユーザが同一の情報を利用し迂 ジュールの作成と案内を行う観光用パーソナルナビゲー 回路に流入した際には，新たな混雑を招く恐れがある [3]． ションシステム P-Tour を提案している．これは，観光 この問題を解消する手法として，文献 [4] ではユーザ間 などで多数の目的地があるとき，ユーザの希望を考慮し で経路情報を共有し，互いに重複しない経路を選択する つつ，ユーザが指定した時間内に巡回可能なスケジュー ことで混雑を回避する方式を提案しており，個人の移動 ルを，短時間で求めるものである [8]． 効率向上に加えて，道路網全体としての混雑減少を実現 経路情報共有による混雑緩和手法 している． 文献 [4] では，道路網上を多数の自動車が移動する環 次に，目的地の混雑による待ちを解消する方法として， 境を対象とした混雑回避手法が提案されている．道路網 イベントホール [5]，テーマパーク [6,7] を対象とし，直 を構成する交差点をノード，交差点間の道路をリンクと 近の混雑情報から各来園者が次に訪れるアトラクション し，各車両は道路網上のノードから起点，終点をランダ を調整することで，特定のアトラクションへの来園者の ムに設定し，リンク上を移動し終点ノードに到着した際 集中を防ぐ方式が提案されている． に行動を終了する．リンクはいくつかの固定長のブロッ しかし，既存研究では，訪問地間の移動時間，各地点 クに分割し [9]，末尾ブロックから順番に番号を割り当て での待ち時間の両方を考慮したスケジューリングは行わ る．i 番目のブロックは以下の要素を持つ． れておらず，観光等の目的への利用を踏まえた場合には • Li : ブロック長 • Ni : ブロックに属する車両数 不十分である．また，現実の環境での回遊行動において は，ある特定の時刻までに自宅に帰らなければならない， • Di : 通過密度 • Vi : 通過速度 ブロックの通過密度は といった時間制約を考慮する必要がある．よって，既存 研究のように，動的にスケジューリングを行う方法では， 貪欲に多くの地点を回ろうとした結果，制限時刻に間に Ni Li で定義される．通過速度に ついては，Green Shields[10] が提唱したモデルを利用し 合わない可能性が高く，逆に帰還に要する時間を長めに (1) 式のように定義する． 見積もり，早々に出発地点に向けて移動を開始した場合 は，多くの目的地を巡回することが困難となる． Vi = Vf (1 − 本研究では，各ユーザが希望する巡回地点リストを基 Di ) Dmax (1) に，ユーザが行動を開始し，帰還するまでのより長期的 ここで，Vf は自由流速度 (密度が 0 のときの速度) を， な期間について，時刻毎の各地点，各経路の混雑状況を るだけ満足するよう調整を行うスケジューリング手法を Dmax は最高密度 (速度が 0 となるときの密度) を表す． Vf は 13.89m/s，Dmax は 0.14，Li は Vf で 5 シミュレー ションステップ (1 シミュレーションステップは 1 秒の時 提案する．提案手法では，経路だけでなく巡回する目的 間経過) 移動した距離に等しいとする．各ブロックは (1) 地の順序変更や，巡回地点数の削減を行うスケジューリ 式に基づいてステップ毎に通過速度を更新され，各車両 ングを行うことで，各ユーザが混雑を避けて優先度の高 は自身が現在属するブロック i の通過速度で移動する． い地点をできる限り多く巡回し，希望する時間までに出 移動の計算は先頭ブロックから順に行われる．各車両は 発地点に帰還できるよう調整を行う． 自身が属するブロックの通過速度が更新されると，直ち 本研究では，提案手法を計算機上に実装し，評価実験 に更新後の速度へと変更を行う．また，車両がブロック を行った結果を報告する．実験の結果，千人規模のユー i からブロック i + 1 に移動する際は，通過速度は Vi から ザについて，実際にスケジューリングが可能であり，独 Vi+1 に即座に変更される．隣接するブロック i + 1 に移 る際に移動先のブロックの通過密度 Di+1 が Dmax を超 事前に予測し，予測混雑下においてユーザの要望をでき 自の判断で行動した際と比較して，提案方式ではより多 2 える場合は，現在のブロック i の先頭で停止し，ブロッ サービス中リストはその地点において，サービスを受 ク i + 1 の混雑が解消するまで待機する． けているユーザの行列リストを表す．待ち行列リストに 起終点間の移動経路の選択方法について，最短距離経 はノードに到着した新規ユーザが最初にリストの末尾に 路戦略，最短時間経路戦略，経路情報共有戦略の 3 種類 追加される．先のサービスが終了した際に，待ち行列リ の戦略が提案されている． ストの先頭から ck 人のユーザが同時にサービス中リス 最短距離経路戦略 (Shortest Distance Route, 以下 SD トに遷移し，サービスを開始する．ユーザは，Stk の時 とする) は，目的地間の経路長を最短にする経路を選択 間を消費することでサービスを受け終える． する戦略である． ユーザが各アトラクションの混雑情報を通信ユニット 最短時間経路戦略 (Shortest Time Route, 以下 ST と を介して入手し，最も混雑していないアトラクションを する) を用いる車両は，目的地間を最短時間で移動可能 次に訪問することで，各アトラクションのサービス所要 な経路を選択する．リンク l の期待通過時間 (Expected 時間に偏りがない場合に待ち時間が軽減される [5,6]．こ Passing Time)EP Tl を，リンク l を構成する各ブロック の通過時間の総和として定義し，VICS センターが，一 定時間間隔で ST 車両に対して全リンクの期待通過時間 れに加えて，次に訪れるアトラクションに予約を入れ， を配信する．ST 車両は交差点毎に，各リンクの期待通 これらの関連研究では，目的地間の移動時間，各地点 過時間情報を基に，最短時間経路を検索する． での待ち時間の両方を考慮したスケジューリングは行わ 経路情報共有戦略 (Route Information Sharing, 以下 RIS とする) は，目的地間の所要時間を最短にし，かつ 他の RIS 車両と重複しない経路を選択することで効率的 れておらず，また，直近の混雑情報のみを参照し巡回目 な移動を行う戦略である．ここで, 車両 j のリンク l につ 還するまでの，より広範囲の期間についての混雑予測を いての通過確信度 (Passage Assurance)P Aj ,l を p 個の 行うことで，本問題に対し，より良い解を得ることを目 リンクを含む経路についてスタート地点から順に p p−1 p−2 2 1 , , , ... , (2) p p p p p 標とする． 予約を入れたユーザと入れていないユーザが別々の列に 並ぶことで，より効果的に待ち時間が軽減される [7]． 的地の変更を行う．本研究では，移動時間および待ち時 間の両者を同時に扱い，かつ，ユーザが活動を開始し帰 提案方式 3 と定義し，割り当てを行う．これは，近い将来通過する 提案方式では，まず，各ユーザが訪問を希望する巡回 であろうリンクの通過確率が高く，遠い将来通過する 目的地群，希望する帰着時間情報を収集し，得られた情 であろうリンクの通過確率が低いことを意味する．次 報を基に，全ユーザが希望する経路を巡回したと仮定し に，全 RIS 車両の P A の総和として総通過確信度 (Total Passage Assurance)T P Al を定義する．ここで，RIS 車 両に配信する情報として期待混雑度 (Expected Traffic たシミュレーションを行い，各地点，各経路の混雑状況 Congestion)ET Cl を以下のように定義する． 更や巡回地点数の削減を行い，全ユーザが希望する時間 ET Cl = EP Tl (T P Al + 1.0) をあらかじめ予測する．次に，予想混雑下において，目 的地間の移動経路だけでなく，巡回する目的地の順序変 までに出発地点に帰還でき，かつ各ユーザが優先度の高 (3) い目的地を多く訪問できるよう調整を行う． 各車両は交差点を通過し経路探索を終えた時点で P A 3.1 を経路情報サーバに送信する．サーバは期待混雑度を算 想定環境と仮定 本研究では複数の訪問候補となる地点，及び地点間を 出し，交差点に近づいた車両に対して配信を行う．車両 結ぶ道路で構成される道路網上において，多数のユーザ は交差点毎に全リンクの期待混雑度を受け取り，現地点 が，各々訪問を希望する複数の地点を目的地として選び， から目的地までの期待混雑度が最小となる経路を検索す 各目的地を巡回し最終的には出発地点まで帰還する環境 ることで，他の RIS 車両と重複しない経路を選択する． を想定する．各ユーザは出発地点から道路網上を目的地 目的地の混雑度考慮による混雑回避手法 に向かって移動し，到着した際にサービスを受ける．各地 文献 [5,6,7] では，大規模なイベント会場を，複数の 点には，サービスを受け終えるまでに要する時間が設定 ユーザが移動し各アトラクションにてサービスを受ける されており，ユーザは必要な時間を消費することでサー 環境下における混雑回避手法が提案されている．まず，各 ビスが終了し，次の目的地への移動を再開する．ユーザ アトラクションはパラメータとして，以下の要素を持つ． は希望する全ての目的地を訪れると出発地点に帰還し活 • Lsk : サービス中リスト • Lqk : 待ち行列リスト 動を終了する．各道路，各地点に複数のユーザが集中す • ck : キャパシティ • Stk : サービス所要時間 路においては移動速度が低下する．各地点ではサービス ることで混雑が発生した場合は，その混雑度に応じて道 が開始されるまでの待ち時間が発生する． 3 各ユーザは，広域無線 LAN などの通信機能を備えた の高い地点を巡回し，希望する帰着時間内に出発地点に デバイスを所持すると仮定する．ユーザが活動を行う地 帰還できるような調節を行う．以下，アルゴリズムの概 域には，各ユーザから得られた要望を基にスケジューリ 要を示す． ングを行う情報センター (以下，サーバとする) が存在 （ 1 ） 各ユーザが希望する目的地群に対して，文献 [8] し，ユーザは無線アクセスポイントを経由してサーバと などの発見的手法を用いて，総移動距離が最小と の情報のやり取りが可能とする．各ユーザは活動を開始 なるような巡回経路を求める (取り扱う道路網の する前に，端末上で訪問を希望する巡回目的地群，及び 構造が単純である時は，全探索を行っても良い)． その重要度（その目的地への訪問を希望する強さの程度） （ 2 ） 各ユーザが (1) で求めた経路を巡回したと仮定し， を入力し，サーバに送信する．サーバは，各ユーザから 提案システム上でシミュレーションを行う．目的 入手した情報を基に，全ユーザが希望する経路を巡回し 地間の移動戦略には RIS を用い，目的地での滞在 たと仮定したシミュレーションを行い，時刻毎における は 2 章で述べたモデルに準じる．また，各ブロッ 各地点，各経路の混雑状況を予測し，予測混雑下におい ク，各ノードに存在するユーザ数を 1 シミュレー て各ユーザのスケジュールを調整する．サーバは全ユー ションステップ毎に記憶することで，時刻毎の混 ザのスケジュールが確定後，ユーザにスケジュールを送 雑情報を生成する 信する． （ 3 ） 各ユーザの得点（重要度の総和），帰着するまで に要した時間を求める． 問題設定 3.2 （ 4 ） 巡回目的地を状況に応じて変更する（後述） 各ユーザは，各目的地を訪問しサービスを受けること （ 5 ） (2)∼(4) の処理を全ユーザの巡回目的地変更がな ができれば，自身が設定した重要度に相当する得点が得 くなる，または規定のループ数繰り返し，決定し られるものとする．ただし，ユーザの帰着希望時間以降 たスケジュールを実際に配布する に，目的地を訪問しサービスを受けることができても， 3.6 その目的地の得点は加算しないものとする．本研究では， 全ユーザの得点の合計を最大化することを目的とする． 各経路，目的地で混雑が発生する状況下においては， 各ユーザが自身の希望する全ての目的地を訪問すること 入力 3.3 で希望帰着時間に間に合わない場合がある．そこで，シ 各ユーザが端末デバイス上で入力する情報は以下の 6 ミュレーションにより希望帰着時間を超過したユーザに つから成る． ついては，重要度の低い地点への訪問を諦めるよう変更 • pds : 出発地点 • pre(pds ) : 出発地点に対する重要度 を行うことで対処する． ユーザの巡回希望リストの中から 1 つ目的地を外し， • D : 訪問希望目的地数 • dm (1 ≤ m ≤ D): 訪問を希望する目的地 残った目的地群に対して全ての巡回パターンを算出する． この処理を，巡回希望リストに含まれる全ての目的地に • pre(dm ) : 訪問を希望する目的地 m に対する重要度 • pg : 希望する帰着時間 ユーザは，自身が入力した各目的地の選好度に応じて， ついて順番に行い，最終的に最も総得点が高く，巡回所 要時間が最も短い回り方を，先に生成された混雑情報を 基に選択する．条件に最も合致する巡回スケジュールが それぞれ異なった重要度を設定すると考えられる．ここ 確定すると，ユーザの巡回経路，目的地を変更する．変 では，ユーザは各目的地，及び出発地点の重要度を百分 更後，再び全ユーザがその経路を巡回したと仮定し，提 率における割合で入力する． D ∑ 案システム上でシミュレーションを行い，各ユーザの得 pre(dm ) + pre(pds ) = 100 点，帰着するまでに要した時間を算出し，超過したユー (4) ザについては巡回経路，目的地変更を再び行う．また， m=1 一度目的地の削減を行ったユーザについて，シミュレー 出力 3.4 巡回目的地の変更手順 ションを繰り返す過程で予想混雑状況が変化し，削除し 解となるスケジュールは，提案手法を利用するユーザ数 ′ ′ ′ ′ 分のスケジュールで構成され，S =〈s1 , s2 , ..., sn , ...sU 〉 た地点を訪れても希望帰着時間を超過しないと予測した で表す．sn は，ユーザ un のスケジュールであり，sn =〈 場合は，ユーザの巡回希望リストにその地点を再度追加 d1 , d2 , ..., dm , ...dD , dpd 〉で表す．ここで，dm は m 番目 に訪問する目的地である． する． ′ ′ ′ 3.5 ′ ′ ′ ′ ′ 3.7 タブーリスト 予備実験の結果，前節までに述べたアルゴリズムでは， アルゴリズム概要 同じ目的地の挿入，削除を無為に繰り返すユーザが現れ， 提案アルゴリズムでは，各ユーザができるだけ重要度 解が収束しない場合が発生することが分かった．そこで， 4 タブーリストを用いてこの繰り返しを防止する手法を提 案する． ユーザが，削減したある目的地を再度追加し，その結 果，希望帰着時間を超過した場合は，超過が生じた目的 地毎にその回数を記録する．この回数が一定値を上回っ た目的地はタブーリストに書き込み，以後その目的地の 追加は行わないことで，短時間で戦略変更の繰り返しを 停止させることができる． 3.8 安全率 提案手法について，道路網上に存在する全てのユーザ が提案手法を利用することが理想的であるが，現実環境 においては，提案手法を利用しないユーザが混在する．こ のような環境では，提案手法を利用しないユーザの存在 を考慮せずにスケジューリングを行うため，実際に活動 を行う際にそれらのユーザと経路，目的地が競合するこ とで意図しない混雑に巻き込まれ，パフォーマンスが低 図 1: 放射環状網 下する．そこで，道路網の容量に対して巡回を行うユーザ はサービス施設であり，道路網上のリンク数は 32，ノー が過剰に存在する場合は，道路網上の混雑度の補正を目 ド数は 56，ブロック数は 831，トポロジの全長は 59.3km 的とした，安全率を次のように定義し用いることとする． non user num 安全率 = 1 + ·β (5) user num サーバ上での仮想シミュレーション時に，安全率を各ブ に設定する．各ノードのサービス所要時間は 600-1800 シ ミュレーションステップの範囲でランダムに設定する． 各ノードのキャパシティは 10-30 ユーザの範囲でランダ ロックの通過密度に乗じ，各ノードのキャパシティに対し ムに設定する．この値は，500 人のユーザが全ての目的 ては除算を行うことで，提案手法を利用しないユーザによ 地に均等に割り振られた場合に適度な待ち時間が生じる って生じる混雑をおおよそ見積もったスケジューリングを 程度の値を参考に設定を行った．ユーザ数が 1000 人程 行う．ここで，提案手法を利用するユーザ数を user num， 度では，全てのノードが常時過剰に混雑する状態である． 提案手法を利用しないユーザ数を non user num とす また，本研究では，各ノードにおいてはレストランなど る．提案手法を利用しないユーザの数は，VICS などか の逐次的なサービスが行われると仮定する．よって，各 ら入手可能とする．β は道路網上における user num と ノードにおいて待ちが発生した場合，待ち行列リストに non user num との比率に対する重みである． 並ぶユーザは，サービス中リストに空きができる度に 1 人ずつ追加されるとする． 評価実験 4 4.1 4.3 実験の目的 従来手法の設定 提案手法の有効性を検証するために，先行研究に基づ 提案手法の有効性を確認するために，シミュレーション き以下のように比較モデルを設定する． を用いて従来手法との比較を行う．また，提案手法では， ユーザは各目的地の混雑状況を考慮して，動的に次の システムがユーザに対してスケジュールを提示するが， 訪問目的地を変更する．ここで，ユーザは通信ユニット 提示されたスケジュールを無視したほうがユーザ個人に を所持し，各リンク，各ノードの混雑情報を随時入手可能 とって有利ならば，このシステムを用いるインセンティ であると仮定する．ユーザは現在所属する目的地でサー ブが失われる．そこで，ユーザが提示されたスケジュー ビスを受け終えた後に，巡回希望リスト内の未訪問地点 ルを無視して独自の判断で行動した場合についての実験 の待ち行列リストに含まれるユーザ数，サービス所要時 を行う．さらに，道路網上に提案手法を利用しないユー 間を入手し，(6) 式により見込み所要時間を計算する． ザが混在する，逐次的にユーザが追加される場合など， 不特定要素が混入する場合にも提案手法が有効かどうか predicttime = staym + time(dnow , dm ) を検証する． ここで，time(dnow , dm ) は，現在所属するノード dnow 4.2 (6) から dm への移動に要する時間である．staym は地点 m 道路網構造 の現在の混雑状況に基づき算出された予想サービス所要 既存の研究では，単純な道路網構造を扱ったものが多 時間であり，Lsm · Stm /cm と定義する．ユーザは巡回 い．そこで，本実験では，図 1 に示す，やや複雑な放射環 候補となる全てのノードの見込み時間を算出し，最も予 状トポロジにて実験を行う．各リンクは道路，各ノード 5 想所要時間が小さい地点を次の目的地に設定し直す．さ ないユーザが用いる経路選択戦略，配置方法については らに，ユーザは希望帰着時間からの遅延ができるだけ生 実験設定 1 と同様し，全ユーザにおける，独自の判断で じないよう，ある地点でのサービスを受け終え，次に訪 行動するユーザの割合を 10 から 90 の範囲で 10% 刻み れる目的地を (6) 式により求めた後に，(7) 式に基づき で変化させた． 帰還に要する所要時間を見積もる． 設定 3：道路網上に提案手法を利用しないユーザが混在 returntime = staym +α·time(dnow , dm ) (α ≥ 1)(7) するケースの評価 本実験では，道路網上に提案手法を利用しないユーザ (7) 式により希望帰着時間を超過する場合にはその地 点への訪問をキャンセルし，最終目的地に向けて移動を が混在する場合の提案手法の有効性を検証した．道路網 全体のユーザ数は実験設定 1 と同様とし，それぞれにつ 開始する．α 値が小さい際は，帰還に要する時間を短め いて経路移動戦略に RIS を用い従来手法に従い巡回する に見積もり，値が大きい際は，時間に余裕をもって最終 ユーザの比率を 90:10 から 10:90 まで 10% 刻みで変化さ 目的地への移動を開始する．本実験では，α=1 とする． 4.4 せる． 実験パラメータ設定 予備実験の結果，ユーザ数が 500 人の場合には提案手 本節では，提案手法，従来手法に共通する各種パラメー 法の効果が現れたが，ユーザ数が 1000 人の場合には道路 タの設定を述べる． 網上の各ノードが混雑が過剰となり，提案手法を利用し ユーザは出発地点から行動を開始し，4 つの異なる目 ないユーザから受ける影響が大きくなり，提案手法を用 的地を巡回し最終的に出発地点に帰還する．各目的地， いるだけではパフォーマンスの低下が防止できないこと 及びその重要度はランダムに設定される．希望帰着時間 が分かった．そこで，ユーザ数が 1000 人の場合に 3.9 節 は，ユーザが入力を行った目的地群の巡回に要する総距 で述べた安全率を用いて，混雑を見積もったスケジュー 離の最短を理想速度で移動した際に要する時間に，各目 リングを行った．安全率の具体的な値は現在検討中であ 的地における混雑が生じない際のサービス所要時間の総 るが，ここでは予備実験から，本道路網構造，実験人数 和を加えたものとする． において最もパフォーマンスの低下を抑えることができ タブーリストの許容回数については，1000 ユーザにつ た β=0.5 の値を用いた． いて，値を 1∼5 の範囲で変更し，全ユーザが各々ラン 設定 4：道路網上のユーザが逐次追加される場合の検証 ダムに選択された 5 つの地点への訪問を希望したとして， 本実験では，時間の変化と共に道路網上に新規ユーザ 放射環状トポロジにて実験を行った．その結果，平均得 が随時追加されるモデルを考える．道路網上にはランダ 点，訪問目的地数に大きな差が生ず，許容回数の増加に ムの位置に 600 シミュレーションステップ毎に，新たに 伴いスケジューリングに要する時間も増すため，本実験 100 ユーザが追加される．本実験では，提案手法を用いる ユーザ，経路移動戦略に RIS を用い従来手法に従うユー では許容回数を 1 回とする． 4.5 実験設定 ザについてそれぞれ検証する．追加の上限は 500，1000 提案手法の有効性を検証するために，一般的な PC ユーザと変更して実験を行う． （Core2 Duo 2.4GHz，1024M Memory，WindowsXP 4.6 pro.）上で実験を行った．以下，実験の設定を述べる． 評価指標 提案手法と従来手法について，以下の項目に基づいて 設定 1：従来手法との比較 比較を行い評価する． 本実験では，道路網上で巡回活動を行った全ユーザが 平均得点：全ユーザの得点の平均値 提案手法を用いて巡回を行った際と，従来手法を用いた 平均有効訪問数：各ユーザが実際に訪問した目的地 (以 際の結果を比較した．道路網上には両方式について，各々 下，実訪問数とする) において，希望帰着時間内でサー ユーザ数を 500，1000 人と変更して実験を行った．従来 ビスを受け終えることができた目的地の平均数 手法に従うユーザが利用する経路選択戦略には SD，ST， 超過人数：希望帰着時間を超過したユーザ数 RIS を各実験人数について，それぞれ選択する．本実験 4.7 では，実験開始時に上記設定人数のユーザが同時に道路 実験結果 実験結果 1：従来手法との比較 網上に配置され，巡回を開始する． 提案方式，従来方式について、シミュレーションを行っ 設定 2：インセンティブの検証 た結果の平均値を表 1，2 に示す．平均得点については 本実験では，提案手法を利用しスケジュールを受け取っ 提案方式が従来方式と比べて 20-30% 程度高かった．平 たユーザの数割かが，与えられた結果に従わず，独自の 均実訪問数は従来方式の方が 0.2-0.3 程度高いが，平均 判断で行動する場合を考え，提案手法に従うインセンティ 有効訪問数は多くの場合において提案方式が上回ってい ブを検証する．道路網全体のユーザ数，提案手法に従わ 6 表 1: 実験 1:従来手法との比較結果 (500 ユーザ) 実訪問数 有効 得点 超過 訪問数 従来手法 (SD) 人数 従来手法 (RIS) 3.972 4.024 4.006 3.564 3.638 3.664 72.3 72.8 74.4 123 119 110 提案手法 3.842 3.826 94.7 7 従来手法 (ST) 表 2: 実験 1:従来手法との比較結果 (1000 ユーザ) 実訪問数 有効 得点 超過 訪問数 人数 従来手法 (SD) 3.216 2.641 53.3 364 従来手法 (ST) 3.240 3.287 2.909 2.767 2.927 2.834 55.6 58.2 72.5 290 233 44 従来手法 (RIS) 提案手法 図 2: 実験 2:不利益が生じたユーザの割合 (500 ユーザ) る．ユーザ数が 1000 の場合に，従来方式 (RIS) の方が 若干高いが，これは提案方式では制約時間に間に合うよ う目的地数を適度に削減した結果である．さらに，平均 得点については提案方式がいずれの場合においても他を 上回ることから，提案方式が事前にシミュレーションす ることで，重要度の高い地点を優先的に選択して巡回し 図 3: 実験 2:不利益が生じたユーザの割合 (1000 ユーザ) ていることが分かる．また，提案方式では各ユーザの巡 増加するに連れて，受ける影響も大きくなる．しかし， 回目的地，経路を調整しているため超過人数も少ない． 従来手法を用いるユーザについても同様にパフォーマン スの低下が見られ，図 5 より得点については提案手法を 実験結果 2：インセンティブの検証 独自の判断で行動したユーザについて，得点が提案方 利用するユーザの割合が 4 割を超える程度から従来手法 式により与えられたスケジュールに従った場合に得られ を上回り，超過人数についても多くの場合において従来 ると予想されていた値から改善（低下，または変化がな 手法と比較して少ない値を示すことから，提案手法が優 い）されない，または希望帰着時間を超過した割合を図 位にある． 2，3 に示す．提案方式に従わないことで，得点が改善さ れるユーザも存在するが，全体的には得点が悪化する傾 実験結果 4：道路網上のユーザが逐次追加される場合の 検証 向が強い．図 2 より，ユーザが 500 人の場合は，独自の 計算機上でシミュレーションを行った結果を表 3，4 に 判断で行動するユーザの割合が 0.5 の際に，悪化の割合 示す．道路網上に追加されるユーザの上限が 500 ユーザ が最も低いが，その割合は 85% 程度と十分に高い．図 3 の場合は，提案手法が優位であるが，1000 ユーザの場合 より，ユーザが 1000 人の場合は，改善が見られるユー にはパフォーマンスの低下が著しい． ザは増加するが，最低でも 70% 程度のユーザは改善が 4.8 期待できない．よって，ユーザが独自の判断で行動する 考察 提案手法は，道路網の容量を考慮し，その制限内で最 ことで得をする確率は，最高でも 30% 程度であり，提 も所要時間が短く，得点の高い巡回経路を算出する．実 案手法により得られた結果に従う方が得策である． 験 3，4 の結果より，提案手法を利用しないユーザの混 実験結果 3：道路網上に提案手法を利用しないユーザが 在，逐次的にユーザが追加されるなど，不特定要素が混 混在するケースの評価 入する場合は，道路網の混雑状態が適度な状態では，そ 計算機上でシミュレーションを行った結果を図 4，5 に れらの影響を抑えることができる．しかし，道路網が飽 示す．ユーザ数が 500 人の場合は，道路網上の各ノード 和状態になると，パフォーマンスの低下を防ぐことがで がある程度混雑している状態にある．このケースでは， きない．そこで，そのような要素の存在をあらかじめ考 得点もほぼ低下せず，超過人数も少ない．しかし，ユー 慮し，本研究で提案した安全率などを用いて巡回時間に ザ数が 1000 人の場合には，道路網上の各ノードが常時 多少の余裕を含ませたスケジューリングをすることで， 相当に混雑しており，従来手法を用いるユーザの割合が 妨害が生じた場合においても，時間内での巡回が可能と 7 表 3: 実験 4:従来手法との比較結果 (500 ユーザ) 実訪問数 有効 得点 超過 訪問数 従来手法 (RIS) 提案手法 4.244 4.000 3.820 3.858 人数 76.1 94.2 124 44 表 4: 実験 4:従来手法との比較結果 (1000 ユーザ) 実訪問数 有効 得点 超過 訪問数 図 4: 実験 3:得点，超過人数の分布 (500 ユーザ) 人数 従来手法 (RIS) 4.077 3.850 76.0 140 提案手法 3.954 3.240 80.3 320 参考文献 [1] [2] [3] [4] 図 5: 実験 3:得点，超過人数の分布 (1000 ユーザ) なる．さらに，その余裕を見積もった時間内で，できる だけ得点が高くなる巡回経路を算出するため，従来手法 と比較して高い得点が得られると考えられる．また，逐 [5] 次的にユーザが追加される場合には，新規ユーザが追加 される際に，既に巡回を行っているユーザのスケジュー ルを再計算してやることで，パフォーマンスの低下を軽 [6] 減することができると考えられる． 5 むすび 本稿では，各ユーザの希望巡回地点リストを基に各経 [7] 路，各地点の混雑状況を予測し，各ユーザが帰着時間制 約を満たしつつ可能な限り重要度の高い目的地を巡回で きるよう調整を行う手法を提案した．評価実験の結果， 提案手法は以下の特性を示した．(1) ユーザが同時に配 [8] 置される環境では，従来手法と比較して，多くのユーザ が重要度の高い地点を優先的に巡回し，20-30% 程度高 い満足度を達成できる．(2) 提案手法に従うインセンティ [9] ブが十分に確保されている．(3) 提案手法を利用しない ユーザが混在，逐次的にユーザが追加される場合におい て，ネットワークが過剰に混雑していない状況下におい ては，高いパフォーマンスが得られる．また，巡回時間 [10] に余裕を持たせたスケジューリングを行うことで，ある 程度の過剰な混雑にも対応が可能である． 今後は，提案手法を利用しないユーザが混在する，及 び逐次的にユーザが追加される場合に生じるパフォーマ ンスの低下を軽減する手法を提案する予定である． 8 Mizokami, S., Asakura, Y., Furuichi, E. and Kameyama, M.: “Forecasting System of Sightseeing Travel Demand Considering Area Attraction and Excursion Behavior,” Journal of Infrastructure planning and management, Vol. 639, IV-46, pp. 65-75 (2000). Vehicle Information and Communication System Center: VICS HOME PAGE, http://www.vics.or.jp/. Mahmassani, H. S. and Jayakrishnan, R.: “Systam Performance and User Response under Real-time Information in a Congested Traffic Corridor,” Transportation Research, Vol. 25A, pp. 293-307 (1991) Yamashita, T., Izumi, K., Kurumatani, K. and Nakashima, H.: “Smooth Traffic Flow with a Cooperative Car Navigation System,” Proc. of the fourth international joint conference on Autonomous agents and multiagent systems, pp. 478-485 (2005). Suzuki, R. and Arita T.: “Effects of Information Sharing on Collective Behaviors in Competitive Populations,” Proc. of the Eighth International Symposium on Artificial Life and Robotics, pp. 36-39 (2003). Kawamura, H., Kataoka, T., Kurumatani K. and Ohuchi A.: “Investigation of Global Performance Affected by Congestion Avoiding Behavior in Theme Park Problem,” IEEJ Transactions on Electronics, Information and Systems, Vol. 124, No. 10, pp. 19221929 (2004). Kataoka, T., Kawamura H., Kurumatani, K. and Ohuchi, A.: “Distributed Visitors Coordination System in Theme Park Problem,” Proc. of International Workshop on Massively Multi-Agent Systems, pp. 105-119, (2004). 丸山敦史，柴田直樹，村田佳洋，安本慶一，伊藤 実：PTour：観光スケジュール作成支援とスケジュールに沿った 経路案内を行うパーソナルナビゲーションシステム，情報 処理学会論文誌，No.45，Vol.12，pp.2678-2687，(2004) Horiguchi, R., Kuwahara, M. and Nishikawa, I.: “The Model Validation of Traffic Simulation System for Urban Road Networks: ’AVENUE’,” Proc. of the Second World Congress on Intelligent Transport, Vol. 4, pp. 1977-1982 (1995). Greenshields, B.: “A study of traffic capacity,” Proc. of Highway Research Board, Vol.14, pp. 448-494 (1934).