電気自動車用充電ステーションの配置最適化に関する研究事例

データ分析
データ分析モビリティ最適化問題論文電気自動車
0

本記事ではEV向けの充電ステーションの配置最適化に関する研究を紹介する。

取り上げる論文を一通り読んで日本語でまとめたものである。

スポンサーリンク

Employing Opportunistic Charging for Electric Taxicabs to Reduce Idle Time

Employing Opportunistic Charging for Electric Taxicabs to Reduce Idle Time | Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies
For electric taxicabs, the idle time spent on cruising for passengers, seeking chargers, and charging is wasteful. Previous works can only save cruising time th...

Publication:

  • Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies
  • March 2018

概要

For electric taxicabs, the idle time spent on cruising for passengers, seeking chargers, and charging is wasteful. Previous works can only save cruising time through better routing, or charger seeking and charging time through proper charger deployment, but not for both. With the advancement of wireless charging techniques, efficient opportunistic charging of electric vehicles at their parked positions becomes possible. This enables a taxicab to get charged while waiting for the next passenger. In this paper, we present an opportunistic wireless charger deployment scheme in a city, which both maximizes the taxicabs’ opportunity of picking up passengers at the chargers and supports the taxicabs’ continuous operability on roads, while minimizing the total deployment cost. We studied a metropolitan-scale taxicab dataset on several factors important for deploying wireless chargers and determining the numbers of the chargers in the regions: the number of passengers, the functionalities of buildings, and the frequency of passenger appearance in a region, and taxicab traffic flows in a city. Then, we formulate a multi-objective optimization problem and find the solution. Our trace-driven experiments demonstrate the superior performance of our scheme over other representative methods in terms of reducing idle time and supporting the operability of the taxicabs.

【全訳】

電動タクシーでは乗客を探す回送、充電器の探索、充電に費やす時間は無駄なものである。既存の研究では、より良いルーティングによって回送時間か、適切な充電ステーションの配置によって探索と充電に費やす時間かどちらかしか節約することはできなかった。無線充電技術の進歩により、停車位置で効率的に気ままに充電することができる。これにより、タクシーは次の乗客を待つ間に充電することが可能となる。本論文では、タクシーが充電しながら乗客を乗せる機会を最大化し、路上でのタクシーの継続的な運用をサポートしながら、全体の展開コストを最小化するような無線充電器の都市への展開戦略を提案する。本研究では、大都市規模なタクシーデータセットを用いて、無線充電器の配備し、地域における充電器の台数を決定する重要な要素である、地域の乗客数・建物の機能性・乗客出現頻度・都市におけるタクシー交通の流れについて検討した。そして、多目的最適化問題を定式化し、その解を求めた。その結果として、他の代表的な手法と比較すると、アイドル時間の短縮やタクシーの運用を支援するという点で優れていることが示された。

目的

電動タクシーの利益を最大化することが最終的な目的である。そのために、

  • アイドルタイムの最小化
    • 乗客を探して巡回する時間
    • 充電器を探す時間
    • 充電時間
  • 無線充電器の配置コスト(配置数)の最小化

これら両方の最適化問題を考え、無線充電器の展開戦略「PickaChu」を提案したことがこの論文の貢献である。

背景

経験豊富なタクシー運転手は乗客を拾うために、巡回するのではなく特定の場所で待機することを好む。
そこで、待機中にタクシーを充電することができれば効率的に充電をすることができる。

無線充電技術を用いればそのような効率的な充電が可能になる。
無線充電とは、送信コイルから磁界を介して非接触で受電コイルに電気エネルギーを送る技術である。

駐車場や信号機の手前などの地面に無線充電器が設置され、EVがその上に駐車するだけで充電できるようになる。

用いたデータセット

タクシーの利用履歴

中国深圳における2015年の15,610台のタクシーの状態(タイムスタンプ、GPS位置、速度、乗務状況など)を30秒ごとに記録したデータセットを用いている。
データはここから入手可能。(サービスプロバイダと交渉して、研究者が公開している。)
深圳の範囲外の位置や冗長な位置のフィルタリングなどのクリーンアップはしている。

タクシーの移動は10分以上停車や乗車状態の変化で分割される「軌跡」で表現する。

道路地図データ

OpenStreetMapから中国深圳の道路地図データを用いている。
深圳市の自治体情報に従い、南西角を座標(緯度22.4450、経度113.7130)、北東角を座標(緯度22.8844、経度114.5270)とした四角形で道路地図をトリミングしている。

交差点や折り返し地点を頂点とし、道路を辺とする道路ネットワークを構築。
GPS位置の全ての点に対して最適化問題の解を求めるのは複雑すぎるため、元のGPS位置をユークリッド距離で最も近い頂点に標準化する。(これは一般的な手法らしい)

充電器の交通量推定と最適化に頂点のみを使用する。(乗客の出現状況の抽出と分析については、元のGPS位置を利用。)

地図は次のように $M=557$ 個の地域に分割して考える。
$$G=\{ g_0, g_1, \dots, g_{M-1} \}$$
メッシュは1つあたり 2000m $\times$ 2000m の大きさになり、深圳のタクシーのおおよその平均時速40kmで、ほとんどの乗客が許容できる待ち時間(約6分以内)で到達できる大きさである。
動的に分割して乗客の出現の地理的な分布に適応させる研究もある。

プラグイン充電ステーションの位置情報

深圳市交通委員会から市内全てのプラグイン充電ステーションの位置を入手。

深圳のデータセットの分析

アイドル時間

まず、そもそもアイドル時間とは何か定義し、どの程度あるのか(1日あたりの平均)を計算する。

巡回時間:
乗客を降ろしてから次の乗客を乗せるまでの走行している時間として定義。
約50%のタクシーが1日に4.17時間以上巡回している。

充電器探索時間:
乗客を降ろしてから充電ステーションで充電するまでの走行していた時間として定義。(充電ステーションに5分以上滞在したとき充電されていたと判断する。)
約50%のタクシーが1日に2.78時間以上充電器を探している。

充電時間:
充電ステーションでの滞在時間として定義した。
約50%のタクシーが1日に0.83時間以上充電している。

これらのアイドル時間を減らすように無線充電器を配置し、充電中であっても素早く乗客を拾える確率が高くなるようにする。

建物と乗客数の相関

OpenStreetMapを用いて、深圳の各建物のクラスと位置を取得。(すでに分類されているわけではなく、手作業が含まれる?)
そして、各建物のクラスの100m以内に現れた乗客の1時間当たりの平均数の重み $w(c)$ も算出。
以下のように分類すると、乗客数は次のような相関があることが分かった。

  • 住宅
    • 乗客数は少ない。(自家用車や公共交通機関を使う人が多いため。)
    • $w(\rm{Residential})=0.9$
  • 商業
    • 乗客数は少ない。
    • $w(\rm{Commercial})=0.7$
  • 市民
    • 図書館、庁舎などの市民が使う建物。
    • 2番目に乗客数が多い。
    • $w(\rm{Civic})=2.0$
  • 基本
    • 駐車場などの公共サービス
    • 乗客数はかなり少ない。(そもそも建物の数が少ないため)
    • $w(\rm{Basic})=0.2$
  • 専門
    • オフィスビル、ビジネスビル、鉄道、地下鉄、空港など特定の用途の建物。
    • 全時間帯において、他のクラスより乗客数が多い。
    • $w(\rm{Professional})=4.4$
  • 観光
    • 乗客数はかなり少ない。(そもそも建物の数が少ないため)
    • $w(\rm{Tourism})=0.2$

したがって、建物の機能性は、地域における乗客出現の可能性を推測するための要因として利用できる。
建物の大きさを考慮すると測定の精度がさらに向上する可能性がある。

$C_i$ を地域 $g_i$ の建物クラスの集合、$B_i$ を地域 $g_i$ に存在する建物の数、 $P_i (c)$ を建物クラス $c$ の割合として、建物の機能性を次のような加重和として算出する。
$$\bar{H}_i = \frac{B_i}{\max_{g_i \in G} B_i} \sum_{c \in C} w(c) P_i (c)$$

乗客の出現頻度

路上にある無線充電器にタクシーが駐車した際に、次の乗客が乗車するまでの待ち時間が小さいことが望ましいため、乗客の出現頻度が高い地域ほど充電器の配備すべきである。

乗客数がラッシュ時に偏っていて、全体の乗客数が大きく見える場合があるので、乗客数は「乗客出現頻度」とはならない。
ラッシュ時だけ乗客数が多い地域に無線充電器を設置しても他の時間は持て余すだけになるためである。
そこで、乗客数の時系列データを以下の2種類を用いて周波数に変換する。

  • 離散フーリエ変換
    • 誤った周波数を返す可能性がある。
  • 自己相関関数
    • 時系列の周波数の誤検出を回避できるが、真の周期の整数倍を返す可能性がある。

しかし、それぞれには欠点があるので、2つの結果を組み合わせて周波数を決定する[24]。

まず、周波数の中には極めて低い振幅を持つものがあるため、閾値を設定する。
地域 $g_i$ における、時系列の乗客出現数 $x_i (n)$ を考える。
99%の信頼度を確保するため、$x_i (n)$ を100回シャッフルし、それぞれの最大振幅の中から99番目の値を閾値とする。
(なぜ時系列のものをシャッフルするのか分からないが[24]に書かれているのかもしれない。)

こうして閾値でフィルタリングされ、離散フーリエ変換から得られた周波数の集合$F_i^{\rm DFT}$ と、自己相関関数から得られた周波数の集合 $F_i^{\rm ADF}$ の積集合 $F_i=F_i^{\rm DFT} \cap F_i^{\rm ACF}$ を最終的な周波数集合とする。

そして、 $F_i = \{f_i^1,f_i^2,\dots,f_i^m\}$ とその振幅の集合 $P_i= \{p_i^1, p_i^2, \dots, p_i^m\}$ を用いて、地域 $g_i$ の乗客出現頻度を次のような加重平均として算出する。
$$\bar{F}_i = \frac{P_i}{||P_i||_1} \cdot F_i $$

乗客の出現しやすさのスコアリング

以上で算出した「建物の機能性」と「乗客出現頻度」を用いて、乗客の出現しやすさを次のようにスコアリングする。
$$\rho(g_i) = \left( \frac{\bar{x}_i}{\bar{x}_\min} \right)^\alpha \cdot \bar{F}_i^\beta \cdot \bar{H}_i^\gamma$$
ここで、 $\bar{x}_i$ は地域 $g_i$ における平均乗客数で、 $\bar{x}_\min$ は全ての地域の中で最小の平均乗客数を表す。
また、 $\alpha, \beta, \gamma$ はそれぞれの指標の影響を調整する定数である。

建物の機能性と乗客頻度の妥当性は結果の章に書かれている。

$\alpha, \beta, \gamma$の最適値を見つけるために、ある範囲で変化させて、無線充電器の配置を決定し、1日の中からランダムに選択された1時間だけ実験を行い、最終的にはアイドル時間を最小化する値の組み合わせを選択する。
その結果、深圳では $\alpha = 1.2, \beta = 2, \gamma=1$ が最適な組み合わせであった。

なお、スコアは乗客出現の尤度を示す最適な方法ではなく、あくまでもヒューリスティックな手法であることに注意が必要である。

電池残量の推定

タクシーの電池残量を推定すると、閾値 $\eta$ を超えないように到達しやすいような充電器の配備を決定することができる。
軌跡の長さはタクシーのエネルギー消費量を決定するため、タクシーの軌跡の長さから電池残量を推定する。

軌跡の長さの確率密度分布はパラメトリック分布を用いてモデル化することはできないため、カーネル密度推定する。(ポアソン分布に従う気もする)
タクシーが長さ $d$ の軌道を取る確率密度分布は、
$$\hat{f}(d) = \frac{1}{Rh} \sum_{t=0}^{R-1} K(\frac{d-d_t}{h})$$
ここで、$R$ はタクシーの軌跡の合計数、 $d_t$ は $t$ 番目の軌跡の長さ、 $h$ は精度を調整するバンド幅でありMISE (Mean Integrated Squared Error) を最小化するような値を選ぶ。
$K(\cdot)$ はカーネル関数であり、ガウス関数を用いている。

電気自動車の電力消費モデルによると消費電力 $\phi$ は、空気抵抗 $E_{\rm air}$ と転がり抵抗 $E_{\rm roll}$ によって算出される。
$$ \phi = \frac{\Delta E_{\rm{air}} + \Delta E_{\rm{roll}}}{\Delta t} = c_w v^3 + c_e \kappa g v $$
ここで、$c_w$ は車両前面積で決まる空気抵抗係数、 $v$ は走行速度(今回は道路地図全体の最大の制限速度)、 $\Delta l$ は移動距離、 $c_e$ は転がり抵抗係数、 $\kappa$ はタクシーの質量、 $g$は重力加速度である。
ここで、各タクシーは同じ電池容量 $E_0$ を持っているとする。

充電器から出発するタクシーが最短経路を通って距離 $d$ だけ走行した地点での電池残量は、次のように推定される。
$${\rm SoC}(d) = \max \left(1 – \frac{c_w v^2 + c_e \kappa g}{E_0}\sum_{t=0}^{R^\prime -1} l_t,~0 \right)$$
ここで、 $R^\prime$ は最短距離で通る道の数であり、 $l_t$ はそれぞれの道の長さである。
地域 $g_i$ に配置する無線充電器の数を $\mu_i$ とする。
$$b_i = \left\{ \begin{array}{l}
0 \quad &\text{if } \mu_i=0 \\
1 \quad &\rm{otherwise~} (\mu_i \ge 1)
\end{array} \right.$$
として、地域 $g_j$ にいるタクシーの推定される電池残量は次のように表せる。
$$\overline{\rm SoC}(g_j) = \sum_{i=0}^{M-1} \hat{f}(d_{i, j}) {\rm SoC} (d_{i, j})b_i $$
ここで、$d_{i,j}$ は地域 $g_i$ から $g_j$ への最短経路距離である。

最適化問題の定式化

次の指標を最適化する。

  • 無線充電器の総配備コストを最小化
  • 充電器がカバーする総地域スコアを最大化

制約条件は、

  • どの地域でも予想される電池残量が閾値 $\eta$ を下回らないこと
  • 無線充電器の総充電電力が電動タクシーの総消費電力を下回らないこと

すなわち、数式で表現すると以下のようになる。

\begin{align}
\text{minimize} \quad &\sum_{g_i \in G} \omega_0 \mu_i \\
\text{maximize} \quad &\sum_{g_i \in G} \rho(g_i)\mu_i \\
\text{subject to} \quad &\overline{\rm SoC}(g_i) \ge \eta, \quad \forall g_i \in G \\
\quad & C\sum_{g_i \in G} \mu_i \ge^{} \phi V \\
\quad & \mu_i \in \mathbb{N}, \quad \forall g_i \in G
\end{align}

ここで、$\omega_0$ は充電器の配置の単位コストを表す定数、 $C$ は充電電力、 $V$ は走行するタクシーの総数である。

出発地と到着地が与えられると、 $\overline{\rm SoC} (g_i)$ が決定され、この最適化問題は古典的な多目的整数計画法問題となる。
その最適解は分岐境界探索の既存のソルバーを使用して解を得ることができる。

最適化問題から地域 $g_i$ の無線充電器の数 $\mu_i$ を得たら、その地域内の頂点を1日平均の乗客リクエスト数でランク付けし、降順に $\mu_i$ 個の頂点に無線充電器を1つずつ割り当てる。

タクシーの配車スキーム

最新のEV用無線充電システムの充電電力は150 kWであるため、電池容量が75 kWhだと約30分で満充電にすることができる。
しかし、満充電でも300km 程度の走行しかできず、大都市圏では1日に800kmの走行が必要であるため、1日に約3回(約2時間)の充電が必要である。
したがって、なるべく長時間運転をさせず、乗客を待っている間に充電させる。

以上の戦略に基づき、空車のタクシーは以下の電池残量に関するルールに従って乗客を探す。

  • 電池残量が $\theta$(例えば、80%)以上の場合
    • 巡回して乗客を探す。
  • 電池残量が $\theta$(例えば、80%)以下の場合
    • 最も近い充電器に移動し、ランダムな時間(通常であれば5分から30分)待機して乗客を乗せる。
  • 電池残量が $\eta$ (例えば、20%)以下の場合
    • 最も近い無線充電器に移動し、フル充電まで充電する。
    • 乗車リクエストは断る。

人気のない地域では充電単価を低く(例:0.11 ドル/kWh)、人気のある地域での充電単価を高く(例:0.22 ドル/kWh)設定し、タクシーが人気のない地域にも留まるように動機づける。

以前の研究のような中央集権型・分散配車型のタクシー配車戦略を採用することができるが、この研究では焦点を当てていない。(古典的な中央集権型で評価している。)

タクシーが充電器の待機列に並ばなければならない可能性があるが、上記の戦略では待機時間はわずかであることが予想され、待ち時間は無線充電器の探索時間に含むこととしている。

シミュレーションの設定

提案している「PickaChu」の性能を評価するため、以下の充電ステーション配置アルゴリズムと比較する。

  • Optimal Charging Station Deployment (OCSD) [15]
    • 最寄りの充電器を探す時間を最小化するように充電器を配置するスキーム。
    • これの配置コストを参考にPickaChuの最適化をする。
    • ピックアップ戦略がないため,タクシーは道路をうろうろして乗客を発見する。
  • Cruising on Purpose (pCruise) [33]
    • 近くのタクシー間で通信して乗客情報を共有し、乗客を見つける確率が最大となるルートを巡回するスキーム。
    • 充電器の配置戦略がないため、OCSDと同じとする。
  • 深圳の既存プラグイン充電ステーションの配置(Baseline)
    • ピックアップ戦略がないため,タクシーは道路をうろうろして乗客を発見する
  • OptPickaChu
    • PickaChuの展開コストからさらに削減された最適化問題の解。
    • PickaChuよりの充電器の数が少なくなる。

すべて同じ無線充電器を使用していると仮定している。
いずれの方法も、タクシーの電池残量が20%以下になると、最寄りの充電器まで移動し満充電になるまで乗客にサービスを提供しない。
いずれも タクシー配車の中央集権型の配車システムを利用している。

都市型モビリティシミュレータ「SUMO」を用い、深圳の道路上で1,000台のタクシーを24時間シミュレーションする。
乗客のリクエストの場所と時間は、2015年7月15日に実際に起こった乗客のリクエストに従う。
道路地図はSUMOのものではなく、OpenStreetMapのものに変換した。
1回の乗車で1人の乗客にしかサービスを提供できないと仮定する。

充電器、車両、電池に関するパラメータはBYD e6という深圳のタクシーの中で広く使われている車両モデルを採用している。

結果

最適化の結果

最適化問題を解くと、

  • OptPickaChu
    • 557地域のうち93地域を選択し、350台の無線充電器を配置する。
  • PickaChu
    • 557地域のうち125地域を選択し、480台の無線充電器を配置する。

PickaChuの無線充電器の配置は、既存の81箇所の充電ステーションの分布と概ね一致しており、現行の充電器配置スキームから拡張可能であることが示唆されている。

評価項目ごとの結果

  • 運行フェーズの比率
    • アイドル時間(巡回・充電器を探す・充電する)と乗車して移動する時間の比率
    • アイドル時間はPickaChuが最も少なく、OptPickaChuがその次に少ない。
      • PickaChuは他の方式に比べて比較的低コストにしても、運行効率の面で優れた性能を発揮できる。
  • コスト
    • 走行の消費電力コスト (0.5ドル/mile) + 充電による機会損失コスト (0.1ドル/hr)
    • 全てほぼ同じ平均コストだった。
  • 1日の平均収益
    • 乗客との走行距離 $\times$ 距離あたりの収入 (1.5ドル/mile)
    • OptPickaChuとPickaChuは、平均収益を約250ドル、500ドル、600ドル以上増加させる。
      • 他の手法はアイドルフェーズに費やす時間が多いため、充電時間が増え利益が減少している。
  • 車両の電池残量
    • 全てほぼ同じ電池残量推移だった。
    • OptPickaChuは充電器の数は少ないが、ほとんどの時間で他の方式と同等の電池残量となった。
  • 全充電器のエネルギー供給オーバヘッド [kWh]
    • 安定したエネルギー供給は電力網への負荷が小さいので、小さいほど良い。
    • PickaChuとOptPickaChuはほぼ同じ推移で、最も小さい。
  • サービスを提供した乗客の数
    • リクエストが少ない1時から8時にかけては多かったが、それ以外ではそこまで良い結果ではなかった。
    • 特にOptPikaChuでは充電器がない地域が多いので、乗客の待ち時間が長くなってしまう。
    • 乗客が少ない地域では、サービス率が高い水準で維持されていた。
    • 逆に多い地域では、相対的に低い結果になった。

地域スコアの妥当性

地域スコア $\rho(g_i)$ の建物の機能性の項 $\bar{H}_i$ と乗客出現頻度の項 $\bar{F}_i$ の妥当性を示すために、それぞれを除いたときの最適化を行った。

平均コストと収益を評価したところ、平均コストはほぼ同等であるが、1台あたりの1日の収益がそれぞれ150ドル、75ドル減ることが分かった。

したがって、この2つの要素を考慮することで、地域スコアが乗客の出現の可能性をより正確に反映することができていることを示せている。

無線充電器の数

最適化によって地域と無線充電器の数が得られるが無線充電器の数が及ぼす影響を調べた。
最適化によって得られた地域をランダムに10から90個を選び、最適化によって得られた無線充電器数だけ配置する。

充電器の総数が増加するにつれて、タクシーの平均収入は増加し続け、タクシーの平均コストは減少し続けていた。
これは、充電器の数が増えると、タクシーが乗客を拾う機会も増え、充電器を探すアイドル時間が減るためである。

感想

乗客数を離散フーリエ変換して乗客発生頻度を求めているが、本当にこれは必要だったのだろうか?
確かにラッシュ時だけ乗客数が多い地域に無線充電ステーションを配置しても、それ以外の時間では持て余すことになるのは理解できる。
結果的に、ラッシュ時に多い地域は全体としても乗客数が多いような気がしているので、相関関係を調べておきたい。

軌跡の長さはパラメトリック分布に従わないとしているが、指数分布に従っているような気もする。

スコアリングはヒューリスティックな手法であるのは仕方ないが、それぞれの指標に相関がありそうなので、本当にそれで良いのか疑問に思われる。
どれかの指標を減らしても問題なさそう。

スポンサーリンク
H-MEMO

コメント