将来の増設を考慮した電気自動車用充電施設の配置問題について
名古屋大学大学院・工学研究科 柴田敬太(Keita Shibata) 今堀慎治(Shinji Imahori) Graduate SchoolofEngineering, Nagoya University 概要
低炭素社会の実現へ向け二酸化炭素を排出しない電気自動車が注目されている．しかし，現在
電気自動車は普及しておらず，その理由の一つとして充電インフラが整備されていないという課
題が存在する．そこで，本稿では利用者の近くに充電施設が存在する配置が望ましい配置と考え，
利用者と充電施設問の距離の二乗和を最小とする配置を求めることを目的とした，電気自動車用
充電施設の配置問題を考える．施設の配置に際し，本稿ではクラスタリングの代表的手法である
$k$-means 法を用いる．また，実社会において施設配置は今回，次回，さらに将来と逐次的に行わ
れる．
$k$-means 法は
1
度に全ての施設配置を行う場合では良い解が得られるが，段階的に設置す
る場合では工夫が必要である．そこで，本稿では各施設に必要度に応じた重みを付加する重み付
き $k$-means 法を用いた解法を提案する．提案法により，今回，将来のように
2
段階で施設配置が
行われる際に，各段階を通じて不便を感じない配置が得られることを示す．1
はじめに
地球環境問題の中でも社会に大きな影響をもたらすものとして地球温暖化が挙げられる．この
地球温暖化の原因となる温室効果ガスの中で大きな割合を占めるものが二酸化炭素である．二酸
化炭素の排出が少ない社会を「低炭素社会」と呼び，この実現が必要とされている．日本の各部門
における二酸化炭素排出量に注目すると，二酸化炭素総排出量
12
億
4100
万トンの
2
割を運輸部
門が占めており，この運輸部門の
9
割を自動車による排出量が占めている．そこでこの自動車を二
酸化炭素を排出しない電気自動車に置き換えることで，二酸化炭素排出削減につながると考えた．
しかし，日本国内においてハイブリツド自動車が約
200
万台保有されているのに対し，電気自
動車は約
3
万台程度しか保有されておらず普及課題を抱えている．電気自動車の普及課題として
価格，航続距離，充電インフラの整備の3
つの課題が挙げられる．つまり，普通自動車やハイブリッド自動車に比べ電気自動車が高価であること，1 充電当たりの走行距離が短いため長距離移動
が困難であること，充電インフラが十分に整っていないため，バツテリー切れの懸念を抱きなが
らの走行を強いられることが課題となっている．これらの課題のうち，最適化問題として扱うこ
とのできる課題として充電インフラの整備の課題に取り組む．充電インフラの整備として，充電
施設の数を増やす，充電施設を利用しやすい地点に配置することが挙げられる．本稿では新設す
る充電施設数は固定し，利用しやすい地点に充電施設を配置することを目的とした施設配置問題
について考える．充電施設の施設配置問題に関する研究は大きく分けて
2
種類の方法で行われている．
1
つは設置
候補地を表す「ノード」や道路の情報である「りンク」からネットワークを形成し，ネットワーク
上でシミュレーションを行うことにより配置候補を検討する研究である．この種類の研究は，た とえば笠井[6] や日渡ら [9]
により行われている．
2
つ目は人口や交通量などを平面に分布させ，こ
の
2
次元平面内のどの点に目的の施設を配置するかを求める研究である．小柳ら
[8]や石亀ら [4] による研究は，このタイプにあたる．このタイプの代表的な手法としてはボロノイ図を利用した 方法が用いられている．ボロノイ図とは，いくつかの点 (母点と呼ぶ) が平面上に配置されている とき，平面内の点をどの母点に最も近いかによって分割してできる図を示す．既存研究では平面 上の候補点のうち，どの点の組合せを用いれば平均距離の最小化を達成する配置が得られるかを 検討している． 現在電気自動車の充電施設は，市役所，大型量販店，ガソリンスタンド，高速道路のサービス エリアなど様々な場所に設置されている．そこで本研究では設置候補点に自由度を持たせた施設 配置を行いたいと考え，2 つ目の方法である 2 次元平面上に施設を配置する問題を扱う． 実社会における施設配置では，ある年に施設を何基か設置し，その翌年にまた施設を何基か追 加設置するというように逐次的に設置されることがある．各年度を独立したものと考えると，対 象とする年度の既存施設数と新設施設を考慮した配置を求めればよい．既存施設を不動点，新設 施設数を入力とした $k$-means
法を用いることでこの年度における良い配置を得ることが可能であ る．しかし，これにより得られる配置は対象年度における運用しか考慮していないため，対象外 の年度では悪い配置となってしまう可能性がある．つまり，対象とした一つの年度に偏った配置が 得られる．実社会での運用を考えた場合，各段階において良い施設の配置を得たい．そこで，将 来必要であると考えられる総施設数を見積もり，その施設数を入力として得た配置から影響の少 ないものを引いていくという考えが挙げられる．この方法が現実的であると考えられるが，燃料 電池車の台頭もあり今後電気自動車がどれほど普及するかの予測は困難である．ゆえに，将来に 必要な総施設数を見積もること自体が困難となる．しかし，充電施設を設置しなければ電気自動 車の普及は実現しない．そこで，本稿では今年度，来年度のように近い将来までの設置する施設 数がわかる場合において，各年度において良い配置となる施設の配置方法を検討する．提案法と して，各施設に重み付けを行った重み付き $k$-means
法を用いることで，各年度を独立として考え た場合の一つの年度に偏った配置ではなく，各年度において偏りの少ない配置を求める．2
問題のモデル
2.1
充電施設の施設配置問題 施設の利用者が分布している平面上に充電施設を設置する．既に存在する施設は既存施設とし， 新たに設置する新設施設とは区別する．利用者は複数の施設が存在する場合，より近くの施設を 利用するものとし，各利用者を最も近くにある1つの充電施設に割り当てる．このとき，施設と 利用者の問の距離によって定まる目的関数を小さくする施設の設置をしたい．施設を設置する対 象となる平面をルールに従いメッシュに区切り，セル単位で利用する施設を決定する．この仮定 のもと，愛知県をモデルに配置問題の検討を行う．対称となる愛知県のデータとして，総務省統 計局の国勢調査の人ロメッシュデータ [10]を利用する．lkm
四方のメッシュに分割されたデータ に座標を加工し，各セルに座標と人口を与える．電気自動車の利用者数は人口に比例すると仮定 し，各セルの人口を利用者数とする．既存施設の配置は日産リーフ関連情報ポータルサイト [11] における愛知県の急速充電スポットのデータを利用する．愛知近郊における人口分布図を図1, 本 稿で用いる既存施設の配置図を図2に示す．図1: 愛知近郊の人口分布図 図 2: 既存施設の配置図
2.2
問題の定式化 各利用者にとって利便度の高い施設の配置を求める．ここでの利便度とは施設への近さを表す が，これには目的に応じて様々な評価方法が存在する．主に総移動距離の最小化，最大距離の最 小化，距離の二乗和の最小化の三種類である．それぞれの特徴を順に述べていく．まず総移動距離の最小化を目的とした問題について述べる．この問題は
p一メディアン問題 [7] とも呼ばれ，施設までの総移動距離を最小にするように $P$個の施設を配置する問題である．特徴 としては，全体で必要となる移動距離を最小にできるが，利用者が多い領域に施設が密集する傾 向があるため，利用者が少ない領域の移動距離が増大する性質がある． 次に最大距離の最小化を目的とした問題について述べる．これを目的とした問題は $p-$センター 問題[7]とも呼ばれ，施設までの距離が最も遠い利用者が施設までの距離を最小にするように
$p$個 の施設を配置する問題である．特徴としては，施設までの距離が遠い最も不便を被る利用者の負担 を軽減することができる反面，利用者の密集した領域から孤立した点に強く依存する性質がある． 最後に距離の二乗和の最小化を目的とした問題について述べる．この問題は同一施設を利用す る利用者集合内の分散の和を最小化する問題である．これより得られる施設の配置は各集合の重 心となり，集合内の各利用者に対する依存度が平等になる性質がある． 本稿では特定の利用者が得をする配置ではなく，各利用者が平等にある程度の負担を負う配置 を得るため，分散の和を最小とすることを目的とした距離の二乗和を最小とする配置を求める．こ の問題の入出力を以下に示す． 入力愛知県近郊における人口のメッシュデータ 既存施設の配置 設置する充電施設数 出力利用者の座標と充電施設までの距離の二乗和が最小となる配置 目的関数$\sum_{i=1}^{N}\min_{1\leq j\leq k}\{||g_{j}-x_{i}||^{2}\}$ (1)
$x_{i}$ : 利用者の座標$(1\leq i\leq N)$ $gj$ : 施設の座標 $(1\leq i\leq k)$
2.3
問題の種類 本稿では2種類の問題を扱う．実社会における施設配置は今年度にいくつ，来年度にいくつと いうように段階に分けて逐次的に施設配置が行われる．段階的な施設配置を考える前に，まず段 階的に配置するという制約を緩和させ，配置したい施設を一度にすべて配置する施設配置問題を 扱う．この問題を，一段階の施設配置問題と呼ぶ．つまり，既存施設が存在する平面上に新設施設 を一度に設置する場合，どのように配置するのが良いかを考察する問題である．本稿における施 設配置問題では，利用者は最も近い施設を利用することから，どの施設を利用するかにより利用 者集合をグループ分けすることができる．このグループ分けを適切に行うことで，利用者にとっ て便利な配置を得ることができる．この配置を得るため，代表的なクラスタリングアルゴリズム である $k$-means法を適用した解法を述べる． 次に，各年度ごとに施設を段階的に配置していくことを考えた施設配置問題を扱う．本稿では， 段階分けを今回，将来の二段階に分けた施設配置を考える．各段階で必要な新設施設数は決まっ ており，それぞれの段階で必要となる施設数を今回必要数，将来必要数と呼ぶ．また，今回の段 階で得られた施設の配置は将来の段階を考察する際には既存施設となる．一段階の施設配置問題 の解法を応用すると，下記の2種類の標準的解法が考えられる． 今回を重視する方法:
今回必要数で$k$-means
法を実行し (今回の配置を得る), 結果を既存施設と して固定したうえで将来必要数で$k$-means
法を再度実行する (将来の配置 を得る). 将来を重視する方法:
全必要数で$k$-means
法を実行し (将来の配置を得る), 新設施設の中で目的 関数値への寄与の小さいものから将来必要数分を除く (今回の配置を得る). この問題では，各段階において良い配置となるような配置方法を求める．3
一段階の施設配置問題
ここでは段階分けを行わず，一度に全ての充電施設を配置する施設配置問題に対するアルゴリ ズムを述べる．本稿では，代表的なクラスタリング手法である $k$-means
法を用いる．k-means法 により，既存施設が存在する平面上で新設施設を入力としたときの設置候補点を考察する．3.1
k-means
法 k-means法は非階層型クラスタリングの一種であり，クラスタリング手法として広く使われる手法である．この手法は目的関数
$\sum_{i=1}^{N}\min_{1\leq j\leq k\{||gjx_{i}||^{2}\}}-$ を最小化するクラスタの中心を求めることで，データ $N$ を任意の$k$ 個のクラスタに分割する．クラスタとは，ある集合をグルー
プに分割するときのグループを表す．
$N$はデータの総数，
$x_{i}(i\in\{1,2, \ldots, N\})$は各データ，
$gj$$(i\in\{1,2, \ldots, k\})$
はクラスタの中心，
$N^{(j)}$ はデータ $N$ 内のクラスタ $i$ に属するデータの集合を表す．各データ点から最も近いクラスタの中心との距離の二乗和が最小となるクラスタの中心を 求めることでクラスタリングを行う．この手法で得られる解は局所最適解である．$k$
-means
法のアルゴリズムについて述べる．まず
$k$個のクラスタの中心をランダムに配置する (Stepl). 次に，けを行う (Step2). このとき得られる配置図はボロノイ図 [5]
となる．それぞれのクラスタ内で重
心: $gj= \frac{1}{(j)}\sum_{i\in N}x$を計算し，座標が変化した場合その重心へとクラスタの中心を再配置
$|N$ する $(Step3)$.
$k$-means
法はこの手順を繰り返し行う反復計算である．反復の途中で全てのクラス
タの中心に変化が現れなければ終了する (Step4). この手順をまとめたものを以下のアルゴリズム k-means法に示す． アルゴリズム $k$-means
法 Step 1. $k$個のクラスタの中心をランダムに設定． Step 2. 各データを最も近いクラスタの中心に割り当てる． Step 3.クラスタごとに重心を計算し，新たに得られた座標ヘクラスタの中心を移動する．
Step 4.全てのクラスタの中心が変化しなければ終了．それ以外は
Step2へ戻る． クラスタの中心を充電施設，データ集合を利用者集合とすることで，利用者と充電施設問の距離の二乗和を最小とするような局所最適解が得られる．充電施設の配置問題に
$k$-means
法を適用した場合の手順を図
3
に示す．まず，新設施設をランダムに配置する
(Stepl). 平面内の各利用者を，最も近い施設に割り当てる
(Step2).各施設の占める領域ごとに重心を計算し，充電施設
を新たな重心へと移動する (Step3).この動作を繰り返し，全施設が移動しなくなった時点でア
ルゴリズムを終了する．図3
では，施設が占める領域ごとに色分けしている． 図3: $k$-means法のアルゴリズムしかし，一般的な
$k$-means 法をそのまま適用する場合，利用者の座標のみで人口の数を考慮し
ていない．そこで，本稿では人口を重みとして導入することで，人口を考慮した距離の二乗和の最小化を試みる．データ
$x_{i}$の人口を$w_{i}$とする．計算方法としては，アルゴリズムの
Step3において重心ではなく加重平均 : $g_{j}’= \frac{\Sigma_{l\in N(j)^{wx}}:i}{\Sigma_{i\in N(j)}w_{l}}$
を用いることで求めることができる．
k-means
法にお$\sum_{i=1}^{N}\min_{1\leq j\leq k}\{w_{i}||g_{j}-x_{i}||^{2}\}$ (2)
$\ovalbox{\tt\small REJECT}$ : 利用者の座標 $(1\leq i\leq N)$
$gj$ : 施設の座標 $(1\leq j\leq k)$ $w_{i}$ : 重み (人口)$(1\leq i\leq N)$
3.2
既存施設の有無による違い k-means法は初期解依存度の強い解法であり，初期解設定手法に関する研究が行われている
[3].今回の施設配置問題ではさらに既存施設の有無による影響も受けるため，この影響につぃて述べ
る．まず既存施設が存在しない場合では，本稿での数値実験においては初期配置にょる依存は見
られるが，極端な初期配置が与えられない限り悪い解が現れにくいという結果が得られた．
既存施設が存在しない場合に対して，既存施設が存在する場合では二つの違いが存在する．ま
ずアルゴリズムにおける違いとして，アルゴリズム内で既存施設は不動点としてふるまう．ある
施設が占める領域内の重心を計算する際に，既存施設は利用者の割り当てのみを行い，新設施設
が占める領域のみ重心計算と重心への施設移動を行うという違いが存在する．また，不動点であ
る既存施設により初期配置として与えた$k$個の新設施設の移動が制限され，初期解依存度が強く
なる傾向がある．図 4 にこの例を示す． 図 4: 既存施設の影響による初期解依存度 図4
の三角形の10
点が既存施設を表している．左の図は新設施設が平面内の左右両端におかれた 状態を初期解として$k$-means
法を実行した結果，中心の図は左側に新設施設が集中して配置され
た状態を初期解として実行した結果，右の図は右側に新設施設が集中して配置された状態を初期
解として実行した結果を表す．
$k$-means法の初期解をランダムに与える場合，図
4
のように初期
解において施設の置かれた領域から抜け出せず，強く初期解に依存する配置が得られることがあ
る．ゆえに既存施設が存在する状況では，初期配置の決定方法を詳細に検討する必要がある．3.3
施設の初期配置方法
初期配置の決定方法に関して
3
種類の方法を検討する．それぞれ，ランダムに配置，各既存施
設が占める領域内で人□が多い領域内に配置，各既存施設が占める領域内で目的関数値への寄与
が大きい領域内に配置である．まず，ランダムに配置する方法を述べる．初期配置として必要な新
設施設数を他の施設と重なることの無いように平面内のランダムな地点に設置する．次に，人口
が多い領域内に配置する方法を述べる．あらかじめ既存施設が存在するので，各既存施設が占め
る領域を求め，各領域内の人口を計算する．人口が最も大きい領域を選択し，その領域内に初期
配置として新設施設を 1 基設置する．このとき，設置地点は領域内からランダムに決定する．領
域内の充電施設 1 基における人口の寄与は，既存施設が占める領域内の施設数に反比例すると考
える．ある領域に
$n$基の充電施設を新設する場合，この領域には
1
基の既存施設と
$n$基の新設施設が存在することから，施設 1 基に対する人口の寄与は
$1/(1+n)$となる．1 基の設置領域を決定
することに，設置された領域の施設
1
基に対する人口の寄与の値を更新し，最も値の大きい領域
を次の設置候補領域とする．この手順を必要な数の新設施設を配置するまで繰り返すことで初期
配置が得られる．また，目的関数値への寄与が大きい領域内に設置する場合では，施設
1
基に対
する目的関数値への寄与を人口の場合と同様の方法で求めることで初期配置の決定を行う．3.4
初期配置の違いによる解の変化既存施設が 10 基ある状態で，新設する充電施設数を 1 基から 10 基とした場合について，3 種類
の初期配置決定法に基づく $k$-means
法を各
20
回実行した．新設する充電施設数ごとに得られた計
20
個の局所最適解のうち，最大値，最小値，およびこれらの平均値を図5
から図7
に示す． $\langle xt0^{8})$ $19-$ ◆$m$ax 17 ’.average 働 ◆ $u 15 A\mathfrak{m}\mathfrak{n}$ 麟13,2
◆◆蓄盤
11 -l ◆ ◆ ◆ ◆ 皿 9.
$A\bullet$ $\bullet$ $\bullet$ ▲ $\bullet$ 7 ‘ ▲ $\bullet$ $35arrow\wedge$ $\bigwedge_{\tau}$ ▲ $A\bullet|$ $\bullet\wedge$ $\bullet$ ▲$\underline{1}$ ’$1011 0 4 5 6 7 91011$
新設する充電施設数 新設する充電施設数 図5: ランダムに配置図 6: 人口の多い領域に配置 新設する充電施設数の増加に伴いクラスタ数が増えるため，各利用者がより近くの施設を利用す ることが可能となる．したがって，目的関数値は充電施設数の増加に伴い減少する．しかし，図5 のランダムに初期配置を設定した場合ではこの通りになっていない．8
基新設する場合と7
基新設 する場合に注目すると，8 基新設する場合における目的関数値の最大値が 7 基の場合よりも上回っ ている．最小値や平均値に関しては7
基の場合よりも減少しているため，20
回の試行のうち7
基 の場合を上回る最大値が得られた回に限り，ランダムな配置決定による極端な初期配置が得られ たことで，既存施設の制限を受けてアルゴリズムが上手く機能しなかったことが原因として考えられる．一方，人口や目的関数値への寄与が大きい領域に配置する場合では，施設数の増加に伴
$(x{\} 0^{\epsilon}\rangle$ $g{\}\alpha mN11131517197953$ $|..$ $\ovalbox{\tt\small REJECT}$ ’ $\ovalbox{\tt\small REJECT}_{\dagger}*$ $*\mathscr{A}$ $\mathscr{A}*$ $\ovalbox{\tt\small REJECT}$ $\$ $\mathscr{Q}$ $0$ 2 4 5 \’o 7 $S$ 9 1011 新設する充電施設数 1 2 3 4新設する充電蕊設数5 6 7 8 9 10 図 7: 目的関数値の寄与の大きい領域に配置 図8: 各初期配置決定法における最小値 い安定的に目的関数値が減少している．また，各初期配置方法による最小値の値を図8に示す．3 基以上を新設する場合において，ランダムに比べ人口や目的関数値を考慮した方法で良い解が得 られている．しかし，1基や2基を新設する場合ではランダムより劣り，3基以上においても人口 と目的関数値のどちらを対象とした方法が優れた解を得るかについてはばらつきがみられる．し たがって，人口や目的関数値の一方を考慮するだけでは常に良い解を得ることはできない．人口 や目的関数値の寄与を同時に考慮できる指標や，これらと異なる新たな評価方法を考案する必要 がある．
4
二段階の施設配置問題
実社会における段階的施設配置について，本稿では今回と将来の二段階で施設配置を行う場合 を考える．この問題に対し前節まで述べてきた標準的な方法を用いて考えると，2通りの方法が考 えられる． 今回を重視する方法:
今回必要数で$k$-means
法を実行し (今回の配置を得る), 結果を既存施設と して固定したうえで将来必要数で$k$-means法を再度実行する (将来の配置 を得る). 将来を重視する方法:
全必要数で$k$-means法を実行し (将来の配置を得る), 新設施設の中で目的 関数値への寄与の小さいものから将来必要数分を除く (今回の配置を得る). この問題では，各段階において良い配置となるような配置方法を求める事を目的としている．し かし，これら標準的な方法は段階的施設配置において有効ではない場合がある．つまり，ある段 階での良い配置が，別の段階でも良い配置であるとは限らない．例として，人口が均一に分布し ている正方形の平面を考える．新設施設を1基から4基とした場合における各新設施設数での良 い配置を図9に示す．このときの良い配置とは，施設と利用者間の距離の二乗和の総和が最小と なる配置を指す．どの段階においても良い配置とはならない例として，今回 1 基，将来 2 基という二段階に分けて計
3
基設置する場合を考える．今回を重視してまず
1
基を置く場合，図
9
の
(1) より中心に設置するのが良い配置となる．すると，次の 2 基を設置する場所を考えるとき，すで に中心に 1 基設置した状態で設置場所を考えなければならない．このとき，すでに設置された中心の
1
基は動かせないため，図
9
の
(3)のような 3 基の良い配置となるように配置することはでき(1)1 基の良い配置 (2)2基の良い配置 (3)3 基の良い配置 (4)4 基の良い配置 図9: 新設施設数が1基から4基の場合における良い配置 ない．ゆえに，今回の段階では良い配置となるが，将来の段階では良い配置にはならない．同様
に，将来を重視してまず 3 基の配置を考えると，図 9 の
(3)が得られる．次に，今回の段階の配置
を得るため将来に必要となる 2 基を除く必要がある．このとき，3 基のうちどの 2 基を除いても図 9 の (1)の配置は得られない．したがって，将来の段階では良い配置となるが，今回の段階では良
い配置にはならない．以上より，標準的な方法を用いた場合，今回または将来のどちらかは好ま しくない配置で運用しなければならない．このことから，一方の段階に偏らない配置を得るため には標準的な方法以外の解法を新たに提案する必要がある．4.1
各段階での運用を考慮した配置方法 今回または将来のどちらか一方を重視するのではなく，各段階での運用を考慮した配置を得た い．今回と将来の配置を包括的にとらえるため，今回の配置を求める際に今回，将来に設置する 全ての施設数で設置場所の検討を行う必要があると考えられる．次に，設置後すぐに運用を開始 するのは今回設置する施設における配置であるため，これらを優先的に需要がある場所へ設置し たい．ゆえに，今回設置する施設と将来設置する施設とで利用者への影響力に差を持たせた状態 で設置場所を考察することが解決策として挙げられる．そこで，本稿では各施設に優先度により 重み付けを行う方法を提案する．目的関数として施設と利用者間の距離の二乗和を扱うため，こ の重みを余分に必要となる距離として扱うことで，施設ごとに通常の距離に加え重み分の距離を 課すことができる．これにより，施設ごとに利用しやすさを変化させることが可能となる．この 方法を用いて，今回設置する施設が将来設置する施設よりも利用しやすくなるように重み付けす ることで，将来の配置を考慮しつつ今回設置する施設を優先した配置が得られると考えた．した がって，本稿では施設ごとの優先度に合わせた重み付けを行う重み付き $k$-means
法を用いた解法 を提案する．4.2
重み付きk-means
法を用いた提案法重み付き $k$
-means
法を用いた提案法について述べる．重み付き$k$-means
法は $k$-means
法において距離の判定をする際に，各施設の重みを考慮した判定を行う方法である．重み付き $k$-means法
を用いた提案法を以下に示す．
関数値への寄与が小さいものから順に将来設置する施設の数だけ除く (今回の配置を得る). その後，全ての重みを無くした状態で先ほど得た配置を既存施設とし，将来設置する施設 の数の新設施設を入力として $k$
-means
法を実行する (将来の配置を得る). 上記の提案法を用いることで，標準的な解法のように今回または将来のどちらかに偏った解を得 るのではなく，表1に示すようにどの段階においてもある程度良質の解を得ることを目的とする． 表 1: 解法の性質 計算手法今回の配置 将来の配置 $\overline{\overline{今回を重視する方法\fcircle\fcircle\cross}}$ 将来を重視する方法 $\cross$ 提案法4.3
重みの種類 k-means 法で得られる図はボロノイ図になっており，重み付けを行った場合も同様に重み付きボロノイ図が得られる．まず，利用者
$x$から充電施設$g_{j}(i\in\{1,2, \ldots, k\})$ までの距離を$d_{E}(x, gj)$,施設のの重みを吻とすると，重みの付け方により
3
種類の距離を定義することができる
[1]. それぞれの距離の表し方により
3
種類のボロノイ図が得られる．まず，乗法的重み付き距離
$d_{MW}$ による乗法的重み付きボロノイ図 (Multiplicatively Weighted Voronoi Diagram)
について述べる．乗
法的重み付きボロノイ図では重み付き距離$d_{MW}$を，
$d_{MW}(x, g_{j})= \frac{1}{w_{j}}d_{E}(x, g_{j})$ (3)
と定める．この距離によって得られるボロノイ図を図 $1O$ に示す．このとき境界線が円の一部と
なる．次に，加法的重み付き距離
$d_{AW}$ による加法的重み付きボロノイ図 (Additively WeightedVoronoi Diagram) について述べる．ここでは重み付き距離$d_{AW}$ を，
$d_{AW}(x, g_{j})=d_{E}(x, g_{j})-w_{j}$ (4) のように定める．これにより得られるボロノイ図を図11に示す．このとき境界線が双曲線の一部 となる．この重み付けを行うと，施設の領域が消えてしまうことがある．具体的には，重み付けを
行った施設問の距離が短い場合，重さの差が大きい場合などにこの状況が起こることがある．最後
に，加法的重み付きべき乗距離
$d_{PW}$ による加法的重み付きべき乗ボロノイ図(Power Diagram[2] または Additively Weighted Power Voronoi Diagram)について述べる．重み付き距離
$d_{PW}$ を，$d_{PW}(x, g_{j})=d_{E}^{2}(x, g_{j})-w_{j}$ (5) と定める．この距離によって得られるボロノイ図を図 12 に示す．境界線が隣り合う 2 点の垂直二 等分線に平行な直線の一部となる．この重み付けも加法的重み付き距離の場合と同様に，重みの 小さい点の領域は空集合になる場合がある． それぞれ特徴のある図が得られるが，本稿では予備実験を行った結果，目的関数値の良い解が 得られたことや，施設までの距離が重みに左右されることを直感的に判断しやすい配置図が得ら れることから，加法的重み付き距離，加法的重み付きべき乗距離の2種類の重み付けを採用する．
図10: 乗法的重み付きボロノイ図 図11: 加法的重み付きボロノイ図 図 12: 加法的重み付きべき乗ボロノイ図 4.3.1 重み付き k-means 法を用いた提案法のアルゴリズム 重み付き$k$-means 法を用いた提案法のアルゴリズムについて説明する．重み付きk-means法に ついては基本的なアルゴリズムは標準的な$k$
-means
法と同じであるが，各利用者を施設に割り当 てる部分が異なる．利用者の割り当てについては，各施設ごとに設定された重みを考慮した割り当 てを行う．加重平均の計算や計算により新たに得られた座標への移動は新設施設に対してのみ行 う．ここで，既存施設を$m$基，新設施設を$k$基，このうち今回設置する施設数を $k-n$基，将来 設置する施設数を$n$基とする．重み付き $k$-means
法を用いた提案法のアルゴリズムを以下に示す． アルゴリズム 重み付き k-means法を用いた提案法 Step 1. 既存施設が$m$基存在する状態に新設施設$k$基を入力として通常の$k$-means
法を実行し， $m+k$基の施設の配置を得る． Step 2. 新設施設である $k$基の施設が占める領域の目的関数値を比較し，目的関数値への寄与が
大きい $k-n$基を今回設置する施設とし，既存施設とともに重み付けを行う． Step 3. 各利用者を重みを考慮した距離で最も近い施設に割り当てる． Step 4.新設施設が占める領域内の加重平均を計算し，新たに得られた座標へと施設を移動する．
Step 5. 全施設の座標が変化しなければStep6へ．それ以外は Step3へ戻る．
Step 6.
新設施設が占める領域内の目的関数値を比較し，目的関数値への寄与が小さい
$n$基を除く．今回設置する施設である $k-n$基の施設を既存施設として固定．(今回の配置が得られる．) Step 7.
全ての施設の重みを取り除き，新設する
$n$基はStep5. で取り除いた地点に配置する．既存施設$m+(k-n)$
基の状態に，
$n$基を新設施設として$k$-means
法を実行する．5
数値実験
重み付き k-means法を用いた提案法にょって得られる配置を評価する．提案法を用いることに
より今回，将来の各段階で標準的な 2 つの解法の悪い配置よりも良い配置を求めることを目的と
する．実在する既存施設の配置を利用し，今回または将来の各段階を重視した標準的な解法と提
案法を比較する．比較のため，以下の問題例を用いた数値実験を行う．
この問題に対し今回を重視する方法，将来を重視する方法の標準的な
2
種類の解法と提案法を
比較する．それぞれ
20
回の実験を行い，各手法の最小値を比較することで提案法の有効性を検証
する．提案法で用いる重み
$w$については，予備実験の結果表 2 に示したものを用いる．
表2: 各施設の重み$\overline{\frac{\hat{\neg}\fbox_{\overline{\overline{\overline{i}}}}\#\ovalbox{\tt\small REJECT} する\mathbb{E}^{--}-arrow\theta の\ovalbox{\tt\small REJECT} み J_{\backslash }^{\urcorner}\backslash \neq^{-}\ovalbox{\tt\small REJECT}^{\underline{\underline{-}}}*\ovalbox{\tt\small REJECT} する M_{\overline{\overline{\overline{i}}}}\#の\ovalbox{\tt\small REJECT} み\Re\Gamma\neq E^{\vec{-}}\overline{-}\ovalbox{\tt\small REJECT} の\ovalbox{\tt\small REJECT} み_{}D}{加法的重み付き 10010}}$
加法的重み付きべき乗
3000300
上記の問題例に対し，以下の表
3
に示した計算機環境で実験を行った．
表3: 計算機環境
CPU Intel Core i7-2600s $(2.80GHz)$
メモリ $8GB$
5.1
将来を重視する方法と提案法の比較
将来を重視する方法と提案法の比較を行う．ここではまず既存施設が
$1O$基ある状態で，設置す
る全施設(10 基)を新設として追加し，目的関数値への寄与が少ない施設を将来設置する施設数分
だけ除外した場合の配置と，提案法にょって得られた配置を比較する．今回設置する施設数が
6
基
から9
基の場合の結果を以下に示す．$65\langle x\{\phi)$ $\kappa^{\backslash }\xi^{55}$ $\check{g\aleph lR}$ 将来重視の解(10-4) 加法的重み(10-4) $m$ 5 45
$1\alpha 1$ $1\alpha 2$ 10-3 $1\alpha 4$
配置方法の種類 加法的重みべき乗 (10-4) 今回重視の解$(k=6)$ 図13: 目的関数値の比較 図14:6基新設する場合の配置図 表 4 は，各行が配置方法の種類として設置する全施設数から将来設置する施設数の差をとった 今回設置する施設数を表し，各列は用いた解法を表しており，重み付きが今回の提案法を用いた 結果である．また，参考として表4の最後列には，今回設置する施設である6基から9基の配置を 重視した際に得られる現時点での暫定解を示す．将来を重視した標準的な解法に比べ，重みを用 いた提案法の解が目的関数値の小さい良い解が得られている．これは提案法が将来を重視した標 準的な解法を用いる場合よりも，今回の配置において良い解が得られることを示している．しか し，図13の配置方法の種類10–1, 10–2において提案法が今回重視の解よりも良い解を得てい る．提案法では今回設置する施設と将来設置する施設を含む設置する全施設数で設置した後に将 来設置する施設数を除くことで今回の配置を得ている．したがって，今回を重視した標準的な解 法による解よりも良い解は得られないと考えていた．このような結果が得られた要因として，今 回を重視する標準的な解法における初期解設定が十分でなく，必要な地点に初期解がうまく置か れていない可能性がある．他にも提案法では重みを用いるため，この重みの作用により重みなし では得られない配置が得られたことによる影響も考えられる．ゆえに，初期解設定の方法や重み の作用についてさらに考察する必要がある．また，図14に示した配置図は今回設置する施設数を 6基とした場合の結果を示す．基本的に中心部の既存施設付近に新設施設は存在せず，既存施設の ある領域の周りに新設施設を配置するような配置図が得られている．
5.2
今回を重視する方法と提案法の比較 今回を重視する標準的な解法と提案法の比較を行う．今回設置する施設数6基から9基にそれ ぞれ将来設置する施設数を追加し，既存施設を含め全 20 基の配置を比較したものを以下に示す．表 5: 今回を重視する方法と提案法の比較 今回重視の解(6$+$4)
$9+1 8+2 7+3 6+4$
配置方法の種類 加法的重みべき乗(6$+$4) 将来重視の解$(k=10)$ 図 15: 目的関数値の比較 図16:6基配置後4基配置した配置図 表5は，各行が配置方法の種類として今回設置する施設をいくつか設置した後に，将来設置す る施設を設置をいくつ設置したかを表し，各列は用いた解法を表す．また，参考として表5の最後 列には，10 基を一度に全て設置した場合の現時点での暫定解を示す．このときの目的関数値の値 を図 15 内にラインで示す．実験の結果，今回を重視する標準的な解法と比べ提案法が良い解を得 ている．図 15 を観察すると解の改善度合にも差があり，将来設置する施設数が多いほど，提案法 による解の改善が顕著に表れた．これは設置する全施設数内で占める割合が今回設置する施設数 に対して将来設置する施設数の方が小さい場合，将来設置する施設の設置場所を考える際に今回 設置する施設が既存施設として存在するため設置候補地が絞られることから，提案法と標準的解 法とで設置場所にあまり変化が見られないことで改善度合いが少なくなると考えられる．一方で， 将来設置する施設数の割合が大きい場合，今回設置する施設による既存施設が少なく，将来設置す る施設の設置候補地に自由度があることから，提案法による改善が顕著に見られたと考えられる． 配置図の結果として既存施設10基に対し，今回設置する施設6基を設置した後に，将来設置す る施設として 4 基追加する場合$(6+4)$の配置図を図
16
に示す．今回重視の解のように中心の既存
施設を囲うような配置ではなく，提案法を用いた2種類の解法のように中心部にも新設するよう な配置が $k=10$における暫定解にも近い配置が得られ，目的関数値においても良い解が得られて いる．
6
まとめ
本稿では，電気自動車用の充電施設の整備について，二段階で施設を配置する場合に対して重 み付き $k$-means
法を適用し，今回または将来のそれぞれの場合において不便を感じない配置を求 める手法を提案した．提案法のベースとなる$k$-means
法は，ランダムな初期解から実行すると解 の安定性を欠くことを示した．そこで，人口や目的関数値の値を考慮した初期解を用いることに より，解の安定性を向上させた．次に，二段階の施設配置問題を取り扱った．標準的解法である 今回を重視する場合の方法では，今回の配置は良い配置が得られるが，将来の配置が悪い配置と なってしまう．また，同様に将来を重視する場合の方法では将来の配置は良いが，今回の配置が悪 いものとなってしまう．つまり，これらの配置方法を用いた場合では今回または将来の一方に偏っ た解が得られる．そこで，将来設置する施設と比べ今回設置する施設と既存施設に大きな重み付 けを行うことで，各施設の影響力に差を持たせる方法を提案した．数値実験の結果，今回または 将来を重視した標準的解法において，重視しなかった段階において目的関数値の大きな悪い解が 得られるのに対し，提案法ではそれぞれの段階においてもある程度質の良い解が得られた．ゆえ に，本稿における提案法が段階を問わずある程度質の良い配置を得るという目的に対して有効で あることが示された． しかし，課題として重みの定義や二段階を超える多段階の場合における配置方法についてさら に検討していく必要がある．また，技術的な課題として現時点では海をまたぐ移動を利用者に強 いる配置が得られる可能性が存在する．この課題に対して，道路情報を取り込んで形成するネッ トワークボロノイ図の応用が有効であると考えられる．これらの課題を解決していくことにより， 実社会で有効な電気自動車用充電施設の配置が得られる解法を求めていきたい．参考文献
[1] ElenaDeza, Michel Deza
:
Dictionary ofDISTANCES, pp. 255-256, 2006, ELSEVIER. [2] Herbert Edelsbrunner: Algorithms in Combinatorial Geometry, pp. 327-328, 1987,Springer-Verlag.
[3] DouglasSteinley, Michael J. Brusco: Initializing$k$-meansBatchClustering:A Critical
Eval-uation ofSeveral Techniques, Journal of Classification, Vol.24, No.1, pp. 99-121, 2007.
[4] 石亀篤司，松田真典
:
充電インフラの適正配置に関する検討，オペレーションズ・リサーチ2011 年 7 月号，pp. 388-394.
[5] 岡部篤行，鈴木敦夫著
:
最適配置の数理，2000, 朝倉書店．[6] 笠井雄亮: 電気自動車用充電器の設置場所評価システムの研究，二次電池による社会システ ムイノベーション第8回フォーラム，2011.
[7] 加藤直樹著: 数理計画法，2008, コロナ社．
[8] 小柳文子，瓜生芳久
:
重み付きボロノイによる電気自動車用充電設備の適正配置の検討，電 学論$B$, Vol.119-B, No. 12, pp. 1412-1419,1999.
[9] 日渡良爾，岡野邦彦，池谷知彦
:
充電インフラ検討用次世代自動車交通シミュレータの開発， 電力中央研究所，研究報告L10011,2011.[10] 政府統計の総合窓口($e$-Stat). http://www.e-stat.go.jp
