Google Mapで電気自動車用に充電場所を考慮した経路案内を実現(1/2)

１．Google Mapで電気自動車用に充電場所を考慮した経路案内を実現(1/2)まとめ

・ガソリン駆動車の経路案内時には給油場所は問題にならないが電気自動車は考慮が必要
・充電時間は総移動時間のかなりの部分を占める可能性があり充電率によっても時間が変わる
・最新のGoogleマップは充電場所を経路案内時に考慮し電気自動車の航続距離に関する不安を軽減

２．電気自動車用の経路案内で考慮が必要な事

以下、ai.googleblog.comより「Addressing Range Anxiety with Smart Electric Vehicle Routing」の意訳です。元記事の投稿は2021年1月29日、Kostas KolliasさんとSreenivas Gollapudiさんによる投稿です。

ＥＶ、即ち電気自動車は日本では主流ではありませんが、こういう経路案内が実現されると相当使いやすくなるのだろうな、と思います。過去の同様な地味なGoogle Mapのアップデートには「機械学習を使ってバスの運行情報を予測」があります。

アイキャッチ画像はテスラのEVでクレジットはPhoto by Taneli Lahtinen on Unsplash

道案内に使用されるマッピングアルゴリズムは、多くの場合、グラフ内の最短経路を見つける教科書的な解決法であるダイクストラ(Dijkstra)の基本的なアルゴリズムに依存しています。

ダイクストラのアルゴリズムはシンプルで洗練されています。考えられる全てのルートを考慮する(指数関数的に数が増大して手に負えなくなる)のではなく、初期解を繰り返し改善し、多項式で解決できるように機能します。

元のアルゴリズムとその実用的な拡張機能(A*アルゴリズムなど)は、広範囲に渡る道路網で車両の経路を決定するために1日に何百万回も使用されています。

ただし、ほとんどの車両はガソリン駆動であるため、これらのアルゴリズムは給油の考慮事項を無視します。何故なら、

a）ガソリンスタンドは通常、わずかな迂回をするだけでどこでも利用可能
b）給油に必要な時間は通常数分しかない

なためです。つまり、総移動時間と比較して給油の時間は無視できます。

この状況は、電気自動車(EVs:Electric Vehicles)では異なります。まず、EV充電ステーションはガソリンスタンドほど一般的に利用できないため、充電ステーションに到達する前に車の電力が不足するという不安を引き起こす可能性があります。

この懸念は十分に一般的であるため、EVの普及に対する障壁の1つと見なされています。第2に、EVのバッテリーの充電は、より意思決定を必要とする作業です。充電時間は、総移動時間のかなりの部分を占める可能性があり、充電ステーション、車両モデル、およびバッテリーレベルによって大きく異なる可能性があるためです。更に、充電時間は非線形です。たとえば、バッテリーの充電にかかる時間は、20%から30%に充電するよりも90%から100%に充電する方が長くなります。

EVは示されている範囲までの距離しか移動できません。
それ以上進むには再充電が必要になりますが、経路や充電率が異なれば、充電にかかる時間コストも異なります。目標は、到着までの合計時間を最適化することです。

本日は、電気自動車用に車に組み込まれた最新リリースのGoogleマップに統合された電気自動車の経路案内に関する新しいアプローチを紹介します。これは、充電ステーションの場所を経路に統合することで、電気自動車の航続距離に関する不安を軽減します。

Googleマップは、バッテリーレベルと目的地に基づいて、旅程の合計時間を最小限に抑える充電停止場所と充電レベルを推奨します。

これを実現するために、充電ステーションを通る効率的なルートを推奨するための拡張性の高いソリューションを設計しました。これにより、運転時間と充電時間の合計が最適化されます。

ベルリンからパリへのガソリン燃料自動車の最速ルートを上の図に示します。真ん中の図は、航続距離が400km範囲の場合のEVの最適なルートを示しています。(移動時間のみが示されています。充電時間は含まれていません)。ルートに沿った大きな白い円は充電停止を示しています。下の図は、航続距離が200km範囲の場合のEVの最適ルートを示しています。

充電ステーションを経由する経路案内
経路選択の基本的な制約は、充電場所間の距離を、電気自動車がフル充電時に到達できる距離よりも長くする事はできないということです。

その結果、ルート選択モデルは、各充電ステーションがノードとなり、充電ステーション間の各経路がエッジである充電ステーションのグラフとなります。通常の道路ネットワークの道路グラフとは対照的です。

各EVのさまざまな特性(重量、最大バッテリーレベル、プラグタイプなど)を考慮して、アルゴリズムは、EVに適しているエッジとそうでないエッジを識別します。

ルーティング要求が受信されると、Maps EVルーティングは、実行可能なグラフに起点と終点の2つの新しいノードを加えます。このグラフには出発地から近くの充電ステーション、および近くの各充電ステーションから目的地までの潜在的な移動の概要を示す、複数の新しい(実行可能な)エッジがあります。

このグラフを使ってダイクストラのアルゴリズムまたはA*を使用して経路を作成すれば、充電時間をまったく気にしないドライバー用に移動時間を最適化するのに十分です。(つまり、各充電ステーションで常にバッテリーを完全に充電するドライバー)

ただし、このようなアルゴリズムは、充電時間を考慮するのに十分ではありません。充電時間を考慮するため、アルゴリズムは、各充電ステーションノードを複数回複製することによって新しいグラフを作成します。