電気自動車利用促進を目的とした充電設備の多期間設置計画問題
M2014SS003 松井和也
指導教員：佐々木美裕

はじめに

1

本研究は, 電気自動車 (EV) の利用促進のために, 充電設備を多期間にわたって順に設置する際の最適な設置場所, 設置順を求めることを目的とする.
昨今, 日本では EV が普及しつつある. 経済産業省の「自動車産業戦略 2014」では, EV の国内乗用車市場に占める割合を 2020 年に 15%〜20%とすることを目標としている [2]. 2020 年の乗用車販売台数を 2014 年実績と同等の 470 万台と仮定すると, そのうち約 70〜94 万台を EVが占める計算となる. しかし, 2015 年 1 月末までに EV の国内累計販売台数は約 11 万台である. これは, 国内乗用車市場の約 2%しかない. 一方, EV を充電するための充電設備は, 2017 年 2 月末までに急速充電器が約 3,000 基,
2014 年 12 月末までに普通充電器が約 11,000 基設置されている. EV が普及しない理由の 1 つに充電設備の整備が不十分であることが挙げられる. よって, EV の普及には充電設備の整備が急務であると考えられる.
一般にほとんどの地域において十分な数のガソリンスタンドが設置されているので, 従来型自動車を利用する場合, 目的地に向かう際に給油のために遠回りをする必要はない. しかし, EV の場合, 充電設備が十分に整備されていないので遠回りを余儀なくされる可能性が高い. 遠回りは利用者の利便性に影響を与えるので, 遠回りをしなくて済む充電設備の整備が利便性の向上につながり, さらには EV の利用促進につながる. 利便性が低い場合, 利用者は EV を利用しないで従来の自動車を選択することが推測される. よって, EV 利用促進のためには, 利用者の利便性を考慮した充電設備の設置計画の策定が重要である.
設置順の違いによって EV を選択する割合 (EV シェア)の違いの例を 1 つ示す. EV シェアは, 新たに充電設備が設置されたときに, 現在従来型自動車を利用している人がEV に乗り換えると予想される OD の需要の割合である.
図 1 は 4 つの充電設備を, 各期に 1 つずつ設置した時の設置順の違いによる各期の EV シェアの違いを示している. 設置順 (a) で設置した場合, 第 3 期まで設置すると約70%が走行可能となるが, 設置順 (b) で設置した場合, 第3 期まで設置しても 30%程度である. この結果から, 最適な設置順を求めることが重要であることがわかる.

2問題の概要2.1

言葉の定義

以下の記述において, 次のように言葉を定義する.
需要点 対象地域内の市区町村の代表点.
候補点 対象地域内の充電設備の設置候補点.
節点 対象地域内の需要点と候補点.
走行可能 節点間が, 設置されている充電設備をいくつか

設置順 (a)

設置順 (b)

図 1 設置順の違いによる EV シェアの違い
経由して走行できるとき, その節点間は走行可能であるという.
対象の OD ペア 対象地域内の出発地と目的地のペア (需要点のペア). 航続距離以内で走行可能な需要点間は対象の OD ペアに含まない.
最短距離 対象地域内のネットワーク上の最短距離. (従来型自動車を利用して移動したときの距離)
移動距離 対象地域内の候補点を経由したときの距離.
(EV を利用して充電設備を経由したときの距離)
潜在 OD 需要 OD ペア間の潜在的な需要. (従来型自動車を利用している人とし, 所与とする.)

EV シェア 新たに充電設備を設置した時に, 現在従来型自動車を利用している潜在 OD 需要のうち EV に乗り換えると推測される OD の需要の割合.
迂回率 OD ペア間の最短距離に対して移動距離の割合.
(EV に乗り換えたときに従来型自動車に比べての利用者の負担)
利用者割合 OD ペア間の移動距離に対して EV を選択すると予想される人の割合.

2.2 モデルの説明
過去の研究では, 充電設備の配置問題を求めるモデルが提案されている [3, 5]. また, 充電設備を多期間にわたって設置する際の最適な設置順を求めるモデルが提案されている [1, 4]. Chung, Kwon[1], Kuby, Lim[3] の研究では, OD 間が走行可能となるのは充電設備を経由して OD間を最短経路で移動できるときのみとしている. 松井, 森[4], 山之内, 保田 [5] の研究では, OD 間の移動距離に応じた OD 需要の減衰を考慮していない. OD ペア間が走行可能となるのは, 最短経路のみではなく, 出発地からどれだけ遠回りをしても設置されている充電設備を経由して目的地に到着することができるのであれば, その経路も走行可能とする. しかし, 遠回りの距離が長くなればその経路を利用する人は少なくなると考えられる. そこで, 移動距離に応じてその経路を利用する人が少なくなるモデルを提案する.
充電設備が新たに設置されることにより, EV に乗り換えたときの移動距離の負担を減らすことで, 従来型自動車から EV に乗り換える人を増やすことを目的とする. 設
置する充電設備の設置候補は所与とし, 候補の中からいくつかを選択して設置する際の設置順を求める. 設置された候補点を設置済みの候補点, 設置されていない候補点を未設置の候補点とする. 需要点には, 充電設備が完備されていると仮定し, 航続距離内で移動可能な需要点間は対象の OD ペアに含まない. これは, OD ペア間が途中で充電する必要がないからである. EV の航続距離は 180km 前後であり, EV を利用して遠出することは不向きである.
そこで, 利用者の近距離移動を考慮した, 1 ストップモデ
ル, 2 ストップモデルを考える. また, 今後の EV の普及,インフラ整備により遠距離移動に利用する人の割合が増える場合も考慮して, 全ての OD ペアを対象とするマルチストップモデルを考える. 以下に各モデルの対象とする OD ペアを示す.

1 ストップモデル 対象地域内のすべての充電設備が設置されたときに, 充電設備をちょうど 1 回経由して走行可能な OD ペアを対象としたモデル.
2 ストップモデル 対象地域内のすべての充電設備が設置されたときに, 充電設備を高々2 回経由して走行可能な OD ペアを対象としたモデル.
マルチストップモデル 対象地域内のすべての OD ペアを対象としたモデル. 充電設備を高々2 回経由する経路に加え, 3 回以上経由する経路も含まれる.

3解法

1 ストップモデル, 2 ストップモデル, マルチストップモデルの解を求める方法として貪欲算法を提案する. 以下に記号を定義する.
Π: 対象とする OD ペアの集合.
Oπ: OD ペア π ∈ Π の出発地.
Dπ: OD ペア π ∈ Π の目的地.
R: 航続距離.
d(i, j) : 枝 (i, j) の長さ.
i = j の時, d(i, j) = 0.
dπ
OD ペア π の最短距離.
wπ: OD ペア π ∈ Π の潜在 OD 需要.
V: 候補点の集合.
V∗: 設置済みの候補点の集合. V ∗ ⊆ V .
V: 未設置の候補点の集合. V ⊆ V .
V ∗ ∪ V = V, V ∗ ∩ V = ϕ.
mindπ: OD ペア π ∈ Π の移動距離の最小値.
sπ: OD ペア π ∈ Π の利用者割合.
E: 隣接する候補点ペアの集合.
E = {(k, l) | k ∈ V, l ∈ V, d(k, l) ≤ R}.
∗E: E のうち, 走行可能な候補点ペアの集合.
E ∗ = {(k, l) | k ∈ V ∗ , l ∈ V ∗ }. E ∗ ⊆ E.

Bπ:OD ペア π ∈ Π に対して走行可能な候補点ペアのうち, 移動距離が最小となる候補点ペア. Bπ ⊆ E ∗ .
Bπ =arg min ∗ {d(Oπ , u) + d(Dπ , v)+(u,v)∈E

Z(t):d(u, v)}, π ∈ Π.
第 t 期に設置する充電設備番号.

E は, 候補点間の距離が航続距離 R 以内である候補点ペアの集合である. E ∗ は, E の集合のうち, 設置済みである候補点ペアのみの集合である. Bπ は, 出発地 Oπ から設置済みの候補点ペア (u, v) ∈ E ∗ を経由して目的地Dπ に行くことができる候補点ペアのうち, 移動距離が最小となる候補点ペアの集合である. OD ペア π ∈ Π の最短距離に対する移動距離の割合を迂回率 δπ とし,dmin(1)δπ = π − 1dπで定義し, OD ペア π ∈ Π 間の迂回率と呼ぶ. この迂回率を用いて利用者割合を rπ とし,rπ = e−αδπ(2)とする. α はパラメータである. OD ペア π ∈ Π 間の移動に EV を利用すると推測される OD 需要を, rπ wπ とする. パラメータ α は, 利用者の遠回りへの関心度を表し,α が大きい場合, 利用者は迂回率に対して敏感になり, 利用者割合が低くなる. α が小さい場合, 利用者は迂回率に対して鈍感で, 利用者割合があまり低くならない.
2 ストップモデルの貪欲算法を以下に記述する.
[貪欲算法 (2 ストップモデル)]
・ t は期間を表す.
・ ϵ は小さい数とする.
入力： V, E, Π, d(i, j), R
出力： Z(t)ステップ 0 V := V, V ∗ := ϕ, t := 1, Vt := V , E ∗ :=ϕ, sπ := 0 (π ∈ Π), Z := 0, Zprev = 0 とする.
ステップ 1 sπt := sπ (π ∈ Π) とし, v ∈ Vt を 1 つ選択
する.
ステップ 2 Vt∗ := V ∗ ∪{v} , Vt := Vt \{v} とし, 走行可能な候補点ペア Et∗ := {(k, l) | k ∈ Vt∗ , l ∈ Vt∗ , (k, l) ∈E} を見つける.
ステップ 3 OD ペア π ∈ Π 間が走行可能な経路と, その距離を保持する. 経路が複数存在する場合は, 移動距離が最小となるものを保持する. 走行可能な経路が存在しない場合, Bπ := ϕ とする.
Bπ :=arg min ∗ {d(Oπ , u) + d(Dπ , v) + d(u, v)},(u,v)∈Et

dmin:= d(Oπ , k) + d(Dπ , l) + d(k, l), (k, l) = Bπ .
πステップ 4 Bπ = ϕ(π ∈ Π) の時, sπt := 0, そうでない時, 式 (1), (2) を用いて迂回率 δπ , 利用者割合 rπ をそれぞれ求める.
ステップ 5 sπt := max {sπ , rπ }, (π ∈ Π) とする.
∑ステップ 6 OD 需要の合計 z :=sπt wπ を求める.
π∈ΠZ < z の時, Z := z とし, v t := {v} , Et∗ :=Et , s∗π := sπt (π ∈ Π) とする.
ステップ 7 Vt ̸= ϕ の時, ステップ 1 へ戻る. そうでなければ, Z(t) := v t , V ∗ := V ∗ ∪ {v t } , V := V \{v t } , E + := Et∗ , sπ := s∗π (π ∈ Π) とし, ステップ8 へ進む.
ステップ 8 |Z − Zprev | < ϵ の時, Z(t) を出力して終了
する. そうでなければ Zprev := Z, t := t + 1, Z :=0, Vt := V とし, ステップ 1 へ戻る.

1 ストップモデルは, 2 ストップモデルのアルゴリズムにおいて (k, l) ∈ E を k = l とすることにより解くことができる. マルチストップモデルを考える際, 候補点間が走行可能かどうかの判定が難しい. そこで, 設置済みの候補点の隣接行列を掛け合わせることにより, その候補点間が走行可能かを判定する. 設置済みの候補点の隣接行列をA, 候補点数を m, A の (i, j) 要素を aij (A = (aij )) とし,以下に候補点間が走行可能か判定する方法を記述する.
[候補点間の走行可能判定]
候補点 i ∈ V ∗ , j ∈ V ∗ 間が航続距離 R 以内 (d(i, j) ≤ R)
ならば aij = 1 そうでなければ aij = 0 とする隣接行列 Aを作成する. 次に, 隣接行列 A を n 乗する. n = 2 の時,m∑
A2 の (i, j) 要素はaik akj と表すことができる. aik akj
k=1は, 0 または 1 の値をとる. ある k に対して aik akj = 1であることは, (i, j) 間を k を経由して移動できることを表す. したがって, An の (i, j) 要素が 1 の時, 候補点
i ∈ V ∗ , j ∈ V ∗ 間は, n − 1 回以下の経由で走行可能であることを示している.
マルチストップモデルの貪欲算法を以下に記述する.
[貪欲算法 (マルチストップモデル)]Π) とする.
ステップ 7 Vt ̸= ϕ の時, ステップ 1 へ戻る. そうでなければ, Z(t) := t∗ , V ∗ := V ∗ ∪ {t∗ } , V := V \{t∗ } , sπ := s∗π (π ∈ Π) とし, ステップ 8 へ進む.
ステップ 8 |Z − Zprev | < ϵ の時, Z(t) を出力して終了する. そうでなければ Zprev := Z, t := t + 1, Z :=0, Vt := V とし, ステップ 1 へ戻る.

4

計算実験

提案解法は, Microsoft Visual C++ 2010 Express で実装した. 使用した計算機に搭載されている CPU は Intel(R) Core(TM) i7-3770K CPU, メモリは 16GB である.

4.1

データ

提案する解法により得られた解と厳密解を比較することや, 人口分布の違いが設置順に与える影響を分析するためにデータを作成する. 10km 四方の領域内に需要点と候補点をランダムに配置したデータ 1 と, 6km 四方の領域内に格子点上に候補点を配置し, 需要点をランダムに配置したデータ 2 を作成する. データ 2 は, 領域内を 9 つのエリアに分け, それぞれのエリアの中に需要点をランダムに10 個配置する. 需要点の座標を 10 種類（test1〜test10）と, 人口分布を 2 種類 (p1, p2) 作成する. データ 1, デー
タ 2 の需要点数, 候補点数, 需要点の人口, 領域, 各閾値を
表 1 に示す. 潜在 OD 需要は重力モデルに従って, OD の各人口の積に比例し, OD 間の最短距離の 2 乗に反比例すると定める. α= 2, 3, 4, 5 の迂回率における利用者割合のグラフを図 2 に示す.
表 1 実験データ
データ 1
データ 2・ t は期間を表す.
・ ϵ は小さい数とする.

データ 1
データ 2

入力： Π, R, d(i, j), V
出力： Z(t)

需要点数
1590

候補点数
949

領域
10km 四方の正方形
6km 四方の正方形

需要点の人口
10ランダム閾値 (km)3.2
2

ステップ 0 V := V, V ∗ := ϕ, t := 1, Vt := V , sπ :=0 (π ∈ Π), Z := 0, Zprev = 0 とする.
ステップ 1 sπt := sπ (π ∈ Π) とし, v ∈ Vt を 1 つ選択
する.
ステップ 2 Vt∗ := V ∗ ∪ {v}, Vt := Vt \ {v} として, [候補点間の走行可能判定] へ.
ステップ 3 Vt∗ の候補点間の走行判定を用いて, OD ペアπ ∈ Π 間が走行可能ならば dmin
π (π ∈ Π) を求めス
テップ 4 へ進む. そうでなければ rπ := 0(π ∈ Π) とし, ステップ 5 に進む.
ステップ 4 式 (1), (2) を用いて走行可能な OD ペア π ∈ Π間の迂回率 δπ , 利用者割合 rπ をそれぞれ求める.
ステップ 5 sπt := max{sπ , rπ }(π ∈ Π) とする.
∑ステップ 6 OD 需要の合計 z :=sπt wπ を求める.
π∈Π

Z < z の時, Z := z とし, v t := {v} , s∗π := sπt (π ∈図 2 迂回率における利用者割合のグラフ

4.2

提案する解法と厳密解との比較

データ 1 に対して 3 節で述べた解法により得られた目的関数値と厳密な最適値の相対誤差を比較する. 厳密解を求めるために解を全列挙し最適な解を求める. 2 ストップモデルでは α=2, 3, 4, 5 のすべてで相対誤差が 0%となった. 表 2 にマルチストップモデルに対する最適値と目的関数値の比較を示す. α=4, 5 の時, 相対誤差が 0%となった. α=1, 2 の時の相対誤差が 1%以下となり, 提案する解法は高精度な結果を得ることができた. また, すべてのデータで提案する解法は高速に計算することができた.

表 3 人口分布 p1 のときの第 1 期〜第 3 期の設置箇所

表 2 最適値と目的関数値の比較 (マルチストップモデル)

4.3

最適値
目的関数値
相対誤差 (%)

871.74866.42α=2(7.21 秒)(0.01 秒)
0.61

773.65772.10α=3(7.22 秒)(0.01 秒)
0.20

最適値
目的関数値
相対誤差 (%)

704.22704.22α=3(7.26 秒)(0.01 秒)
0.00

648.42648.42α=4(7.39 秒)(0.01 秒)
0.00(a) p1(b) p2

図 3 人口分布p1 の時, 候補点 19 は, 10 個のデータ全てで第 3 期以内に設置されている. また, 候補点 25 と 31 も 9 個のデータで第 3 期以内に設置されている. これは, 左上と右下に人口が多いため左上と右下のエリア間が早期に走行できるように設置されたからだと考える. p2 の時, 候補点 18 と26 は, 10 個のデータのうち 7 個のデータで第 3 期以内に設置されている. また, 候補点 33 は, 半数の 5 個のデータで第 3 期以内に設置されている. この 3 つの候補点は,人口の多い中心のエリアと対象領域の上部の 3 つのエリアが接している箇所である. このことから, 中心と上部のエリアとの最短経路上にある充電設備が早期に設置される結果となった. p2 の結果も, p1 の結果と同様に, 人口の多い中心と上部のエリア間が早期に走行できるように設置されたからだと考える. これらの実験から, 人口が多いエリア間の最短経路に利用されている充電設備が優先して設置される結果になると考える.

test2193032

test33125
19

test4311925

test53125
19

第1期
第2期
第3期

test6193125

test7193125

test8193125

test93125
19

test10193125

表 4 人口分布 p2 のときの第 1 期〜第 3 期の設置箇所

人口分布が設置順に与える影響の分析

人口分布の違いが設置順に与える影響を分析するためにデータ 2 を用いてマルチストップモデルで求めた設置順の傾向を把握する. 2 種類の設定した人口分布を図 3 に示す. 赤色のエリアは人口が全体の 40%, 黄色のエリアは全体の 30%, 緑色のエリアは全体の 10%, 青色のエリアは全体の 5%であることを示している. p1(図 3(a)) は, 人口が多いエリアを 2 つ設定する. p2(図 3(b)) は, 人口が多いエリアを中心に設定し, 対象領域の上部と中心エリアの左のエリアを 10%と設定する. p1, p2 に対して α = 3 として実験を行う. 10 個のデータをマルチストップモデル
を用いて貪欲算法で求め, 第 1 期〜第 3 期に設置される候補点を表 3, 表 4 に示す.

第1期
第2期
第3期

test1
193125

5

第1期
第2期
第3期

test1
26
18
12

test2
1826
33

test3
26
1833

test4
26
24
19

test5
1832
26

第1期
第2期
第3期

test6
1925
32

test7
26
18
34

test8
19
33
17

test926
33
18

test10
18
33
19

おわりに

本研究は, 充電設備を多期間にわたって順に設置する際の設置場所, 設置順を求めるモデルを提案した. さらに,そのモデルを求める解放として貪欲算法を提案した. 提案した解法を用いて小規模のデータで実験を行い厳密な最適解と比較した. その結果, 8 個のデータのうち 6 個のデータで厳密な最適解を求めることができた. 他の 2 個のデータも相対誤差が 1%以下と高精度な結果が得られた. さらに, 実行時間も短く高速に高精度の解を求めることができた. また, 人口分布の違いが候補点の設置順, 設置場所に与える影響の分析を行った.
本モデルでは, 需要点に充電設備が完備されていると仮定した. 今後は, 需要点に充電設備が完備されているところとされていないところの 2 種類に分けたモデルを考える必要がある.

参考文献[1] S.H. Chung and C. Kwon：“Multi-period planningfor electric car charging station locations: A case ofKorean Expresways”, European Journal of Operarional Research 242, pp. 677-687, 2015.
[2] 経済産業省：
http://www.meti.go.jp[3] M. Kuby and S. Lim：“The flow-refueling location problem for alternative-fuel vehicles”, SocioEconomic Planning Sciences 39, pp. 125-145, 2005.
[4] 松井和也, 森龍一郎：「電気自動車専用急速充電器の多期間最適配置計画問題」, 南山大学情報理工学部 2013年度卒業論文, 2014.
[5] 山之内亮介, 保田将弘：「電気自動車専用急速充電器の最適配置問題」, 南山大学数理情報学部 2011 年度卒
業論文, 2012.