近年，次世代の自動車として電気自動車が注目を浴びている．電気自動車は，ガソリン車と違い，走行中に地球温暖化の原因となるとされる二酸化炭素や，大気汚染を引き起こす有害なガス（NOxなど)を排出しないため，地球環境の悪化の抑制に繋がると期待されている．

しかし，電気自動車が長距離を走るためには電気の充電が必要不可欠である．更に，ガソリンの補給と比べて充電には時間がかかることから，電気自動車のユーザーが取る経路は街中に配置された充電所の利用を考慮されたものでなくてはならない．そこで，クラウド・コンピューティングを中心として近年急速に高度化が進む情報技術を利用し，現在の道路状況や充電状況，充電所の利用などの情報を考慮した経路をユーザーに提示するナビゲーションシステムの開発を行う．

そこで，電気自動車の環境配慮性を最大限に活かすために，ただ単にユーザーにとって都合の良い経路を提示するだけではなく，電気自動車の消費電力が最小になる経路をユーザーに提示するシステムを考える．このとき，できる限りユーザーが自ら望んで低消費電力の経路を選択することが望ましい．そこで，システムはユーザーが希望した出発地と目的地，出発時刻を踏まえた経路を複数導出し，更に各経路のコストにインセンティブを付与することで，ユーザーが低消費電力の経路を選択する確率を操作することができるシステム[1]が提案されている．ユーザーは一般的に，目的地までの所要時間が少なく，コストが小さい経路を選択する傾向にあるので，消費エネルギーは少ないが所要時間が大きく，コストもかかる経路と，消費エネルギーが大きいが所要時間，コスト共に小さい経路の2つが提示された場合，ユーザーが後者を選択するのは自然であり，このように経路社会の利益と個の利益は相反してしまうことが珍しくない．しかし，提案されているインセンティブを用いた手法を用いれば，この2つの要素を同時に満たすことができ，ユーザーの自由意志を尊重しつつ，電気自動車の消費電力を最小化することができるのである．

しかし，このシステムは，急な事故などで，現在地から目的地までの経路を再び導出し，インセンティブを付与しなければならなくなった場合，当然システムはインセンティブの再計算をしなければならないが，そういった問題に対しての考慮が全くなされていない．そこで本研究では，先行研究に再計算に対する枠組みを追加し，道中で再計算を行った場合でも，合理的にインセンティブを再計算できるシステムの開発を行う．

最短経路問題

候補経路の導出のためには，このシステムは，急な事故などで，現在地から目的地までの経路を再び導出し，インセンティブを付与しなければならなくなった場合，当然システムはインセンティブの再計算をしなければならないが，そういった問題に対しての考慮が全くなされていない．出発地から目的地までの最短経路を求めるアルゴリズムが必要となる．そのようなアルゴリズムとしては，Dijkstra法[2],Bellman-Ford法[3]，A*アルゴリズム[4]が知られており，今回はシンプルであるために比較的拡張が容易そうなDijkstra法をベースに必要な経路探索あるごリズムの拡張を行う．Dijkstra法は，エッジとノードから構成されるグラフ構造について最短経路を求めるアルゴリズムで，出発地からの距離が近いノードから順に最短経路を一つずつ確定させていき，確定した情報を用いて次に出発地に近いノードまでの最短距離を決定していくアルゴリズムである．Dijkstra法は重みが距離のような定数について適用できるものであるが，本研究では距離ではなく所要時間，すなわち定数ではなく時変の値を重みとして最短経路問題を解くことが必要である．

Dijkstra法の改良として，ゴールノードへの到着時刻が早い順に任意の数の複数経路を導出する実装[5]，任意の2ノード間のエッジの重みがエッジを出発する時刻の関数になっているグラフについて最短経路を導出する実装[6]が提案されている．通常のダイクストラ法では時不変の定数を重みとして用い，1つの経路を導出していたが，先行研究を踏まえて本研究では15分毎の各交差点間の所要時間のデータが与えられているとし，それを用いて経由する交差点に車が到着する（という仮定）度に適切な所要時間を計算して重みとして用い，更に空間的に二次元であったグラフに時間軸を追加し三次元的なグラフとみることで，時刻による道路状況の変化を考慮し，かつ複数の経路を導出するDijkstra法の拡張を実現する．これにより，空間を表す二次元のグラフにおいて最短経路を求めるDijkstra法のアルゴリズムに小さな変更を行うことで，Dijkstra法の効率を損なうことなく三次元的なグラフにおいても最短経路が探索できることを確認することができる．

ユーザーに提案する経路の選別

　上記のように拡張されたDijkstra法を用いて経路を複数導出し，導出された経路をクラスタリングすることでユーザーに提案する経路を決定する手法[1]が提案されている．まず，決められた出発地と目的地，出発時刻について拡張Dijkstra法により十分な数の経路を導出する．ここで，経路の中で1番消費電力の小さい経路を選び，その経路と同じようなコストと所要時間である経路を全て同一の経路と満たす（クラスタリング）．基準の経路と同一とみなすコストと所要時間の範囲は適当に設定する．クラスタリングが終わったら次に所要時間の小さい経路について再びクラスタリングを行い，これを時間最短の経路とコスト最小の経路が決定されるまで繰り返す．全てのクラスタリングが終わったら，意味のない経路を除外する．具体的には，ある経路よりもコストも所要時間も大きい経路をユーザーは選択しないとし，そのような経路を除外する．このようにして選別された経路についてインセンティブを付与していく．また，選別された経路には事前のアンケート等により，ユーザーがそれぞれを選択する確率が決定できるとする．

　選別された経路とそれらをユーザーが選択する確率に基づき設定された目的関数を制約条件の下で最小化する計算を行うことで，各経路を通ったときにユーザーに付与されるインセンティブを計算することができる手法が提案されている[7]．具体的には，目的関数をインセンティブ付与後の各経路の消費電力の期待値の総和とし，それをインセンティブを変数として最小化する．また，得られたインセンティブの値が不自然な値にならないような式，そして1人のユーザーに付与するインセンティブの期待値をκとする式をもって制約条件とする．ここで，先行研究では，先述したように，急な事故などでインセンティブの再計算を行わなければならなくなった場合に合理的にインセンティブを再計算する枠組みが用意されていない．そこで，1人のユーザーに付与するインセンティブの期待値を表すκを，現在地から目的地までのクラスタリングされた経路の消費電力の期待値に比例する関数とすることで，再計算時にも合理的なインセンティブを求めることが可能となる．このとき，κの消費電力の期待値に対する比例定数は適当に設定するとする．

　提案した手法により求めたインセンティブを，どのようなタイミングで付与すれば合理的なのかを検討する．また，提案手法は1組の出発地と目的地についてインセンティブを計算するものであるが，異なる複数の出発地と目的地を考慮したインセンティブを計算するシステムを検討する．