電気自動車専用急速充電器の多期間最適配置計画問題
2009SE154 松井和也 2010SE127 森龍一郎
指導教員：佐々木美裕

る. 前述の研究では, 静岡県, 岐阜県, 愛知県, 三重県におけ• 需要点同士の中に EV が急速充電器を経由せずに往復可能である場合, その需要点同士は OD ペアの集合に含めない. すなわち, ある需要点同士が 50km 以内にある場合, その需要点同士は OD ペアの集合に含めない.

る電気自動車 (EV) 専用急速充電器の配置問題について考この問題の急速充電器の最適な設置順を求める. また,えている. 求めたすべての配置箇所の急速充電器を同時に急速充電器の設置予定箇所を利用する需要量は重力モデ設置することは, 予算の都合上難しいことが多い. そこで,

ルを用いて推測する. 重力モデルは各需要点の人口の積に急速充電器を多期間に分けて設置することを考える. 最適比例し, 需要点間の距離の 2 乗に反比例する. 出発地 i のな設置順を考える際に利用者の利便性の高い順番に設置す

人口を pi , 目的地 j の人口を qj , OD ペア (i, j) の距離をる. 利便性が高い箇所ほど必要性があると考え, 低い箇所

dij とするとき, 出発地 i と目的地 j の需要量を wij とし,
p i qjwij = 2 とする.
dij

1

はじめに
本研究では山之内, 保田 [5] が求めた結果を用いて, 配置する急速充電器の最適な設置順を決めることを目的とすに比べて早く設置することが望ましい. 本研究では急速充電器を利用することができる人数が多いほど利便性が高いとする. つまり, 急速充電器の設置予定箇所を利用する量が多いほど設置される優先順位が高い.

2モデルの説明
以下の記述において, 次のように言葉を定義する.

需要点 : 市区町村の代表点.
充電器 : 急速充電器の設置予定箇所.
節点 : 需要点と充電器.

OD ペア : 出発地と目的地のペア.
1 ストップモデル：すべての充電器が設置されたときに 1回の充電で目的地に到達できる OD ペアを対象としたモデル.
2 ストップモデル：すべての充電器が設置されたときに最大 2 回の充電で目的地に到達できる
OD ペアを対象としたモデル.
マルチストップモデル：すべての OD ペアを対象としたモデル.
需要点 i を出発地, 需要点 j を目的地とする OD ペアを(i, j) と表し, 節点 i と節点 j を結ぶ枝を ⟨i, j⟩ と表す.
EV を利用して遠出をすることは不向きであると考える. そこで, 充電器を利用する人が近場を行き来する場合を考えて充電器を 1 度または, 2 度まで経由して往来できる OD ペアを対象とする 1 ストップモデル, 2 ストップモ
デルを考える. また, 今後の EV の普及により, 遠出する人の割合が増える場合も考慮して, すべての OD ペアを対象とするマルチストップモデルを考えた.

3

定式化

3.1

1 ストップモデル

この問題をハブ空港の配置モデルの 1 つである P -ハブ
メディアン問題の定式化 [4] を参考にして 1 ストップモデルの定式化を行う. 以下に記号を定義する.
M: 設置する充電器の添字集合.

T∏::::期間の集合.

OD ペアの添字集合.
1 期間に設置する急速充電器の個数.
需要点 i と充電器 k の距離が閾値以内ならば1, それ以外ならば 0.
wij: OD ペア (i, j) の需要量.
xijkt : 第 t 期に OD ペア (i, j) の需要量のうち充電器 k を経由して往来する割合.
ykt: 第 t 期に充電器 k を設置するならば 1, それ以外ならば 0.
以上の記号を用い, この問題を以下のように定式化する.
∑ ∑ ∑max.
wij xijkt(1)αaikt∈T (i,j)∈Π k∈Ms.t.

xijkt ≤ ykt ,(i, j) ∈ Π, k ∈ M, t ∈ T(2)yk(t+1) ≥ ykt ,∑xijkt ≤ 1,k ∈ M, t ∈ T(3)(i, j) ∈ Π, t ∈ T(4)t∈T(5)k∈M∑

ykt ≤ αt,k∈M

以下の記述において, 次のようにこの問題を仮定する.

• 需要点を経由することができない.
• OD ペアの出発地と目的地はすべて需要点のみとする.
• OD ペアは対称性を考えて, 出発地と目的地の区別をしない.

xijkt ≤ aik ,(i, j) ∈ Π, k ∈ M, t ∈ T(6)xijkt ≤ ajk ,(i, j) ∈ Π, k ∈ M, t ∈ T(7)xijkt ≥ 0,(i, j) ∈ Π, k ∈ M, t ∈ T(8)ykt ∈ {0, 1},k ∈ M, t ∈ T(9)目的関数および各制約条件の意味は以下の通りである.

を示している. (14) は各 OD ペアの需要量はいずれかの充(1) は全期間での充電器を利用することができる EV 利用者の数の合計を最大化することを示している. (2) は充電器 k に急速充電器が設置してある場合, OD ペア (i, j)は k を経由して往来できることを示している. (3) は急速充電器は一度設置されたらその後の期間, 使用可能であることを示している. (4) は各 OD ペアの需要量はいずれかの充電器を経由して往来することを示している. (5) は第 t期に設置できる充電器の数は αt 個までであることを示している. (6) は枝 ⟨i, k⟩ が使用不可能であれば, 出発地 i と充電器 k は走行できないことを示している. (7) は枝 ⟨j, k⟩が使用不可能であれば, 目的地 j と充電器 k は走行できないことを示している. (8) は xijkt の非負制約であることを示している. (9) は ykt のバイナリ制約であることを示している.

電器を経由して往来することを示している. (15) は第 t 期

モデル 1
この問題をハブ空港の配置モデルの 1 つである P -ハブ

3.2

メディアン問題の定式化 [4] を参考にして 2 ストップモデルの定式化を行う. 1 ストップモデルに次の記号を新たに追加する.

bkl:

充電器 k, l 間の距離が閾値以内ならば 1, それ以外ならば 0.
他の記号は 1 ストップモデルと同様である. 以上の記号を用い, この問題を以下のように定式化する.

max.

∑ ∑ ∑ ∑

wij xijklt(10)t∈T (i,j)∈Π k∈M l∈Ms.t.

xijklt ≤ ykt ,(i, j) ∈ Π, k, l ∈ M, t ∈ T(11)xijklt ≤ ylt ,(i, j) ∈ Π, k, l ∈ M, t ∈ T(12)yk(t+1) ≥ ykt ,k ∈ M, t ∈ T∑ ∑xijklt ≤ 1,(i, j) ∈ Π, t ∈ T

(13)
(14)

k∈M l∈M∑ykt ≤ αt,t∈T(15)に設置できる充電器の数は αt 個までであることを示している. (16) は枝 ⟨i, k⟩ が使用不可能であれば, 出発地 i と充電器 k は走行できないことを示している. (17) は枝 ⟨j, l⟩が使用不可能であれば, 目的地 j と充電器 l は走行できないことを示している. (18) は枝 ⟨k, l⟩ が使用不可能であれな, 充電器 k, l 間は走行できないことを示している. (19)は xijklt の非負制約であることを示している. (20) は yktのバイナリ制約であることを示している.
モデル 2
この問題を Ernst ら [2] を参考にして 2 ストップモデル

3.3の定式化を行う. 以下に記号を定義する.
V: 需要点の集合.

MTαaik::::

設置する充電器の集合.
期間の集合.

1 期間に設置する急速充電器の個数.
需要点 i と充電器 k の距離が閾値以内ならば1, それ以外ならば 0.
bkl: 充電器 k, l 間の距離が閾値以内ならば 1, それ以外ならば 0.
cij: 需要点 i, j 間の距離が閾値以内ならば 0, それ以外ならば 1.
wij : OD ペア (i, j) の需要量.
xiljt : 第 t 期に需要点 i を出発地とし, 充電器 l を経由して需要点 j へ流れるフロー量.
iyklt : 第 t 期に需要点 i を出発地とし, 充電器 k, l 間を経由するフロー量.
zikt : 第 t 期に需要点 i から充電器 k へ流れるフロー量.
hkt : 第 t 期に充電器 k を設置するならば 1, それ以外ならば 0.
以上の記号を用い, この問題を以下のように定式化する.
max.

k∈M

∑∑ ∑∑

xiljt

(21)

i∈V l∈M j∈V t∈T

xijklt ≤ aik ,(i, j) ∈ Π, k, l ∈ M, t ∈ T(16)xijklt ≤ ajl ,(i, j) ∈ Π, k, l ∈ M, t ∈ T(17)xijklt ≤ bkl ,(i, j) ∈ Π, k, l ∈ M, t ∈ T(18)xijklt ≥ 0,(i, j) ∈ Π, k, l ∈ M, t ∈ T(19)ykt ∈ {0, 1},k ∈ M, t ∈ T

(20)

s.t.

∑zikt ≤xiljt ≤ wij cij ,(22)i ∈ V, j ∈ V, t ∈ T(23)l∈M∑

iyklt+∑

xikjt −j∈Vl∈M

目的関数および各制約条件の意味は以下の通りである.

(10) は全期間での充電器を利用することができる EV 利用者の数の合計を最大化することを示している. (11) は充電器 k に急速充電器が設置してある場合, OD ペア (i, j)
は k を経由して往来できることを示している. (12) は充電器 l に急速充電器が設置してある場合, OD ペア (i, j) は lを経由して往来できることを示している. (13) は急速充電器は一度設置されたらその後の期間, 使用可能であることi ∈ V, t ∈ T

wij ,j∈Vk∈M∑∑∑iylkt− zikt = 0, (24)l∈Mi ∈ V, k ∈ M, t ∈ Tzikt ≤∑wij aik hkt ,i ∈ V, k ∈ M, t ∈ T (25)j∈Vxiljt ≤ wij ajl hlt ,iyklt≤∑
j∈Vi, j ∈ V, l ∈ M, t ∈ T(26)

wij aik bkl hkt , i ∈ V, l, k ∈ M, t ∈ T (27)

hk(t+1) ≥ hkt ,∑hkt ≤ αt,k ∈ M, t ∈ T(28)t∈T(29)k∈Mixiljt , yklt, zikt ≥ 0, i, j ∈ V, k, l ∈ M, t ∈ T(30)

hkt ∈ {0, 1} k ∈ V, t ∈ T(31)

目的関数および各制約条件の意味は以下の通りである.

(21) は全期間での充電器を利用することができる EV 利

計算実験

5最適化計算には IBM ILOG CPLEX 12.4 を用いる. 使用したコンピュータの CPU は Intel(R) Core(TM)2 i73770k CPU , メモリは 16GB である. 実験をするにあた
り 5 つのデータを用いる. 5 つのデータの需要点数, 充電器数, 需要点の人口, 領域, 需要点-充電器間閾値, 充電器間閾値を表 1 に示す.
表 1 実験データ用者の数の合計を最大化することを示している. (22) は需要点 i のフローはいずれかの充電器 k へ流すことを示して

データ 1いる. (23) は需要点 j における流量保存則を示している.

データ 2

ただし, i, j 間の距離が閾値以内である場合は充電器 l からデータ 3フローは流さない. (24) は充電器 k における流量保存則を

データ 4示している. (25) は枝 ⟨i, k⟩ が走行不可能であり, 充電器k に設置されていないならば, 出発地 i からのフローを充電器 k に流すことができないことを示している. (26) は枝⟨l, j⟩ が走行不可能であり, 充電器 l に設置されていないな
らば, 出発地 i からのフローを充電器 l を経由して需要点 jに流すことができないことを示している. (27) は枝 ⟨i, k⟩と枝 ⟨k, l⟩ が走行不可能であり, 充電器 k に設置されていないならば, 出発地 i からのフローを充電器 k, l 間に流すことができないことを示している. (28) は急速充電器は一度設置されたらその後の期間, 使用可能であることを示している. (29) は第 t 期に設置できる充電器の数は αt 個まiでであることを示している. (30) は xiljt , yklt, zikt における非負制約であることを示している. (31) は hkt におけるバイナリ制約であることを示している.

データ 5デルで考える. 記号はモデル 2 と同様であり, これを用い

データ 1
データ 2
データ 3
データ 4
データ 55.1iyklt≤wij bkl hkt ,48202020

2 箇所を 100, それ以外を 1010101010i ∈ V, l, k ∈ M, t ∈ T(32)

他の制約条件はモデル 2 と同様である. 制約条件の意味は以下の通りである.

(32) は枝 ⟨k, l⟩ が走行不可能であり, 充電器 k にが設置されていないらば, 出発地 i からのフローを充電器 k, l 間に流すことができないことを示している.

示す.

3. 2 で求めた結果より, 充電器を利用することができる人数が最大となる充電器を設置する. 1 へ戻る.

1.5
3.2404040

2.0
3.2505050

表 2 計算時間と変数の数の比較
データ 1モデル 1

データ 2変数

計算時間 (秒)0.51 1425
1.03 1978

モデル 2

データ 3変数

計算時間 (秒)1.09 29761
2.32 22867

データ 4変数

1.54 912401
12.25 326766

データ 5

計算時間 (秒)変数

計算時間 (秒)

変数

1.12
4.63

9364013272091.81
17.40

896401327357モデル 2

次にモデル 1 での貪欲算法と厳密解法との目的関数値,計算時間の比較を行い表 3 に示す. また, 貪欲算法で求めた解と厳密解法で求めた解との相対誤差を求める. 相対誤差は以下の式で求めた.
相対誤差 =| 最適値 − 近似値 |× 100(％)| 最適値 |

表 3 モデル 1 の比較
データ 1

目的関数値
計算時間 (秒)する. 以下に貪欲算法のアルゴリズムを示す.

2. 各未設置の充電器を設置した時に EV 利用者が充電器を利用できる人数を求める.

閾値 (km)モデル 1 とモデル 2 の厳密解法での計算時間と変数の大規模な問題では変数の数が多くなりコンピュータの計

1. すべての充電器が設置されているかどうかを確認す
る. すべての充電器が設置されている場合終了する.

充電器間間閾値 (km)数の比較を行う. 全てのデータを用いた計算結果を表 2 に

貪欲算法算時間が長くなる. そこで, 貪欲算法に基づく解法を提案

需要点-充電器

4km 平方の正方形
10km 平方の正方形
150km 平方の正方形
150km 平方の正方形
150km 平方の正方形

モデル 1j∈V

4915202020

計算結果の比較

てこの問題をモデル 2 の制約条件 (27) の式を以下に変更∑

需要点の人口

計算時間 (秒)この問題を Ernst ら [2] を参考にしてマルチストップモする.

充電器数領域

マルチモデルストップ

3.4

需要点数

データ 2

目的関数値
計算時間 (秒)

データ 3

目的関数値
計算時間 (秒)

データ 4

目的関数値
計算時間 (秒)

データ 5

目的関数値
計算時間 (秒)

厳密解法

貪欲算法

相対誤差 (%)

2386.250.51
1091.01
1.09
48.99
1.54
50.13
1.12
50.16
1.81

2386.250.02
1082.58
0.02
48.94
0.06
49.93
0.06
46.50
0.06

0.00
0.77
0.10
0.40
7.31

次に 1 ストップモデル, モデル 1, マルチストップモデ
ルの厳密解法での計算実験結果の比較を行い表 4 に結果を示す.

表 4 厳密解法での計算実験結果の比較
データ 1

計算時間 (秒)変数
目的関数値

1 ストップモデル
0.02
289
14687.50

モデル 1

マルチストップモデル

0.51
1425
2386.251.03
2021
2451.88

1 ストップモデル
0.56
1760
812.92モデル 1

マルチストップモデル

1.09
29761
1091.01

4.34
23078
1273.28

1 ストップモデル
0.70
22223
35.82

モデル 1

マルチストップモデル

1.54
91240148.99

4507.49
32840154.70

1 ストップモデル
0.85
18636
29.29

モデル 1

マルチストップモデル

1.12
93640150.13

530.6232830855.80

1 ストップモデル
0.88
19170
31.61

モデル 1

マルチストップモデル

1.81
89640150.16

5542.5632839757.00

データ 2
計算時間 (秒)
変数
目的関数値

データ 3
計算時間 (秒)
変数
目的関数値

データ 4
計算時間 (秒)変数
目的関数値

図 1 実行結果

データ 5
計算時間 (秒)
変数
目的関数値

今後の課題
本研究では充電器の設置順を決定する際の評価尺度として EV 利用者が充電器を利用できる数を用いました. 今

実データ

5.2

6

山之内, 保田 [5] で用いた岐阜県, 愛知県, 静岡県, 三重県の実データを使用して, 2 ストップモデルを貪欲算法で計算する. 需要点の人口は平成 22 年国勢調査 [3] から取得す
る. 需要点の数は岐阜県 15 点, 静岡県 18 点, 愛知県 16 点,三重県 13 点であり, 候補点の数は岐阜県 15 点, 静岡県 15

後は, 評価尺度に利用者の移動距離を考慮したモデルを検討する必要があると考える. また, マルチストップモデルを貪欲算法で解くことができなかったので, マルチストップモデルに対する貪欲算法を考えることが今後の課題である.

点, 愛知県 17 点, 三重県 15 点である. 使用したデータの参考文献

需要点数は 62, 候補点数は 62, OD ペア数は 889 である.

[1] 地理情報分析支援システム MANDARA,http://ktgis.net/mandara/index.php

充電器を利用できる需要量の実行結果を表 5 に示す. 28個以上充電器を設置しても充電器を利用できる需要量が増加しないという結果となった. また, 設置順を地理情報分
析支援システムの MANDARA[1] を用いて図 1 に示す.
表 5 累積獲得需要量
設置期間

充電器を利用できる需要量

設置期間

充電器を利用できる需要量

12345678910111213
14211345150.47402069514.78
529371022.65
613957410.80
687012904.90764807624.15
785740780.85
802851427.97833851794.36849257513.34
864274822.66
868486727.49871396529.55874336969.91

1516171819202122232425
26
27〜62876762843.50
878214659.84
879059594.56
879772750.25
880237243.72
880483614.30
880555571.81
880592675.74
880606950.73
880614777.96
884233110.30
884246445.15
884253418.47[2] Ernst, A.T., and Krishnamoory M., Exact andheuristic algorithms for the uncapacitated multiple
allocation p-hub median problem, European Journalof Operational Research 104, pp. 100-112, 1998.
[3] 平成 22 年国勢調査 総務省統計局[4] J.F. Campbell, Integer programing formulations of
discrete hub location problems, European Journal ofOperational Research 72 pp. 387-405, 1994.
[5] 山之内亮介, 保田将弘, 電気自動車専用急速充電器の最適配置問題, 2011 年度南山大学情報システム数理学科
卒業論文, 2012.