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

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

・グラフを改良する事でダイクストラで充電時間を考慮した経路を求める事が可能になった
・しかし充電ステーションの密度が非常に高い場所ではグラフが巨大になり効率が悪化
・グラフに小さいエッジを追加してグラフをまばらにする事で計算量を削減した

２．グラフの効率的な処理

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

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

複製したノードの半分は、部分的に充電されたバッテリーでステーションに入る事に対応し、充電量xは0％～100%の範囲です。残りの半分は、わずかに充電してy(ここでも0%～100%)でステーションを出ることに対応します。充電量xの入口ノードから充電量yの出口ノード(y> xの制約を持つ)にエッジを追加し、xからyに到達するための対応する充電時間を表現させます。

充電ステーションAから充電ステーションBへの移動でバッテリー充電の一部(z)が消費された場合、ステーションAのすべての出口ノードとステーションBの対応する入口ノードの間にエッジ(充電量x-z)を導入します。

このグラフ変換を実行した後、ダイクストラまたはA*を使用すると充電時間を考慮した経路を求める事ができます。

ノード/エッジ複製手法の例
この場合、アルゴリズムは充電せずに最初のステーションを通過することを選択し、2番目のステーションで20%から80%のバッテリーを充電します。

グラフを疎(スパース化)にする
充電に関する不安に自信を持って対処しながら上記の操作を実行するには、アルゴリズムは充電ステーション間の各行程のバッテリー消費量を高精度で計算する必要があります。このため、マップは、各タイプのEVの属性を考慮して、任意の2つの充電ステーション間の行程に沿った道路特性に関する詳細情報(行程間の各距離、標高、勾配など)を保持します。

保持が必要な情報量が多いため、多数のエッジを維持することは、メモリを大量に消費するタスクになる可能性があります。EV充電ステーションが少ない地域では問題ありませんが、世界にはステーションの密度が非常に高い場所(北欧など)が存在します。このような場所では、EVが移動できるステーションのペアごとにエッジを追加すると、可能なエッジは数十億に急速に拡大します。

左の図は、北ヨーロッパの高密度に充電ステーションが存在する地域を示しています。異なる色は異なるプラグタイプに対応します。右の図は、ステーションの密度が高くなるにつれて、ルーティンググラフのサイズが非常に速く拡大する理由を示しています。互いに範囲内に多数のステーションがある場合、誘導案内グラフは、各エッジの詳細情報を格納する完全グラフになります。

ただし、この高密度は、比較的離れた2つのステーション間を移動する際に、間違いなく複数のステーションを通過することを意味します。この場合、長いエッジに関する情報を維持することは冗長であり、グラフに小さいエッジ(スパナ:spanner)を追加するだけで、グラフがまばらになり、計算が容易になります。

スパナ構築アルゴリズムは、貪欲幾何スパナ(greedy geometric spanner)を直接一般化したものです。

充電ステーション間の移動は、速いものから遅いものの順に並べ替えられ、この順序で処理されます。ポイントaとbの間の各行程について、アルゴリズムは、スパナにすでに含まれている小さなサブ行程が直接行程を含むかどうかを調べます。そのために、スパナにすでにあるサブ行程を使用して達成できる行程時間とバッテリー消費量を、直接a-bルートの同じ量と比較します。

それらが小さなエラーしきい値内にあることがわかった場合、aからbへの直接行程はスパナに追加されません。それ以外の場合は追加されます。このスパース化アルゴリズムを適用すると、顕著な影響があり、ユーザーの道案内要求に応答する際にグラフを効率的に提供できます。

左側：元の道路網(EVステーションは明るい赤)です。
中央：ステーショングラフには、ステーション間のすべての実行可能な行程のエッジがあります。
右側：まばらなグラフは、はるかに少ないエッジで距離を維持しています。

概要
本研究では、グラフのスパース化と標準ルーティングアルゴリズムの新しい枠組みを使用して、充電ステーションへのアクセスを含む、電気自動車の長距離経路案内用の規模拡大可能なソリューションを設計しました。アルゴリズムのアイデアとテクニックをGoogleマップユーザーの手に渡せることを嬉しく思います。世界中の電気自動車ドライバーにストレスのない経路が提供出来るようになる事を楽しみにしています。

謝辞
協力者のDixie Wang, Xin Wei Chow, Navin Gunatillaka, Stephen Broadfoot, Alex Donaldson, Ivan Kuznetsovに感謝します。