近年，次世代の自動車として電気自動車が注目を浴びている．地球温暖化の主要因は温室効果ガスの増加であると考えられている．電気自動車はガソリンを燃料とする一般の自動車のように走行中は温室効果ガスを排出することがないため，地球温暖化の抑制へ繋がると期待されている．
　電気自動車は一般の自動車と異なり，移動手段としての役割のほか，蓄電池の役割を持ち合わせる．蓄電池の役割として，例えば，災害発生などによる停電時に用いる電力供給源が挙げられる．さらに現在，電気自動車と住宅との間で電力を相互供給するシステムの開発が進行している．これにより HEMS(家庭のエネルギーを効率よくコントロールするシステム)[1]を利用して太陽光発電，家電，蓄電池，電気自動車を連携させ電力を適切に制御することが可能になることが期待されており，具体的には電気自動車に貯められている電力を活用した家庭内使用電力のピークシフトなどが見込まれている ．電気自動車をこのように利用するには，帰宅時の電気自動車内の電力がある程度残っていることが要求される．これを踏まえると，帰宅時の電気自動車の残電力量をユーザが決定できることが望ましい．
　ユーザによる残電力量の決定を実現するためには，電気自動車が持つ従来の自動車とは異なる問題を考慮する必要がある．例えば，充電時間が長いこと，充電スタンド数が少ないことが挙げられる．そのため従来の自動車とは異なり，あらかじめ出発時点で目的地に到着するまでに必要となる充電スタンドを探索し，充電量と充電時間をユーザーに知らせるシステムの開発が不可欠である．
　現在設置されている急速充電スタンドには，予約システムを取り入れているものもある．このような充電スタンドとスマートフォンやカーナビゲーションシステムを連動させ，ユーザーが充電スタンドの位置や予約状況の確認，および予約を行うことを可能にするシステムサービスがある[2]．このシステムは先客の利用による待ち時間をなくしたり，あらかじめ待ち時間を知ることを可能にする．今後電気自動車の普及が進むにつれ，充電スタンド予約システムの必要性も高まると考えられている．あらかじめ利用充電スタンドと充電スタンド到着時刻を知ることで，利用する予定の充電スタンドを予約できるという利点も生じる．
　一方，経路を探索するシステムを開発するに当たり，どのような経路をユーザーに提示するかが問題となる．一般に自動車の利用者は時間または金額を重要視することが多いと考えられるため，目的地までの所要時間と所要金額（有料道路通行料・充電料金）のトレードオフを考慮した経路の提示が望ましい．特に，所要時間が最小の経路でも所要金額が大きい経路と，所要時間が2番目に小さく所要金額も小さい経路では，後者の経路を選択するユーザも存在する．このような経路は，所要時間が短い順に複数の経路を出力することで得られると考えられる．
　以上の事柄を踏まえ本研究では，走行中の電力の消費とそれに伴い必要となる充電スタンドでの充電を含めた，目的地到着時の残電力量の制約条件付き経路探索を行うシステムの開発を行う．このシステムでは所要時間が短い複数の経路をユーザに提示する．各経路の詳細として，利用充電スタンド，充電量，充電時間および，充電料金と有料道路通行料を合わせた所要金額をユーザに選択候補として示す．これに加え，出発時刻をユーザが選択可能にし，各出発時刻での道路の混雑度および充電スタンドにおける待ち時間を考慮する．

最短経路問題の解法

　出発地から目的地までの最短経路を求める，すなわち最短路問題を解くアルゴリズムの研究がなされている．エッジとノードから構成されるグラフ構造について最短路問題を解くアルゴリズムとしては，Dijkstra法[3]，Bellman-Ford法[4]，A*アルゴリズム[5]が知られている．Dijkstra 法は，全てのエッジの重みが非負のグラフについて，明らかな出発地からの最短距離を確定し，その確定した情報をもとにさらに遠くまで最短距離を確定していくアルゴリズムである．Bellman-Ford法は，エッジの重みが負であるグラフに対しても最短経路を求めることができるが，重みがすべて非負のグラフに対してはDijkstra法の方が計算量は少ない．A*アルゴリズムは，目的地までの所要コストの推定値を求める関数(heuristic 関数)を導入することで，少ない計算量で最短経路を求めるアルゴリズムである．また，出発地と目的地の双方から探索を行うアルゴリズムがある．双方から同一のノードを探索したときに一度探索を終了し，その後繋がりのあるノード同士の組み合わせを調べることで最短経路を求める．文献[6]では双方向探索にDijkstra法を，[7][8]ではA*アルゴリズムを用いている．

電気自動車の経路探索法

　電気自動車の経路の探索法も研究がなされている．文献[9]では，勾配や走行距離を考慮した消費電力モデルを導出し，複数地点を巡回するときの最適経路を，金属工学の原理の応用であり大域的な最適解への収束を促すシミュレーテッド・アニーリング法[10]を用いて求めている．文献[11]では，電気自動車が減速エネルギーを電気に換え，バッテリーとして使用できることを考慮したグラフについて，バッテリー容量についての制約（走行中にバッテリーが0にならず，かつ最大容量を下回る）を満たす，消費電力が最小の経路を求めるシステムの開発を行っている．また，充電を含めた経路探索法として，充電スタンドにおいて満充電したときの所要時間が最小の経路を求める，Dijkstra法を変形させたアルゴリズム[12]や，出発地から到達しうる範囲と目的地に到達しうる範囲の相互関係を考えることで，充電回数により場合分けを行い，利用しうる充電スタンドを絞る方法[13]などが提案されている．電気自動車の文献[14]では，道中の充電を含めたときの消費電力が最小となる経路を，動的計画法を応用して解くアルゴリズムを提案している．

現在非公開

現在非公開

　本研究で開発したシステムでは，所要時間順に経路を並べているため，所要時間，所要金額のいずれも第2・第3経路よりも第1経路の方が小さい場合もある． このとき，第2・第3経路はユーザーに選択されることはない，すなわち提示することの意味をなさない経路であると考えられる． したがって，ユーザーに何らかのインセンティブを与えるような経路を必ず出力する方法を考案することが課題である． 例えば，第1経路が所要時間が最小の経路，第2経路が有料道路を使用しない（所要金額が小さい）経路，第3経路がその中間の経路，などが挙げられる． このとき，中間の経路の決定方法についても考える必要があり，今後の課題となる．