修士論文 要旨

災害時の電源車巡回経路の最適化

1 はじめに
本研究では需要点の最大遅延コストを最小化する配数理情報学専攻 48216209

大中 亮磨

指導教員

岩田 覚 教授を満たすと仮定する. 経路 r とは頂点の列であり, 最初の 1 要素はデポで, その他の要素は相異なる需要点であるようなものと定義する. 経路 r の経路長 cr を∑送計画問題を新しく導入すると共に, 厳密解法を提案

cr =する.

要素である. 経路の集合 R であって, 各デポと需要点が配送計画問題 (VRP) とは複数の車両が複数の需要点

i τ (ri , ri+1 ) で表す.

ここで ri は r の i 番目の1 回ずつ出現するようなもののうち, 総経路長∑r∈R crを周回する経路を最適化する問題であり, 配送業務等を最小化するものを求める問題を (VRP) と表すことにで応用される重要な問題である. VRP には様々なバリする.

エーションが存在するが, その多くが NP 困難であるこ(VRP) に対する既存の厳密手法としては, 分枝限定とが知られている [2]. そのため実用上高速に厳密解を法と列生成法を用いた手法 [1] が実用上高速に厳密解を求めることが焦点となる.

得られるという意味で大きく成功を収めている. これは配送業務等の文脈における VRP では総経路長の最小元問題を整数計画問題として定式化すると共に, その線化が目的関数とされることが主である. しかし災害支援

形緩和を列生成法で解く操作を, 制約の追加による分枝等の場においては異なる目的関数を考慮したい場合がを行いながら反復するものである.

ある. 例として, 災害時の通信事業会社の電源供給が挙

ここでは主に整数計画問題への定式化部分についてげられる. 災害によって停電が発生した際, 各ビルは非紹介する. まず経路 r に対応する経路ベクトル δ r を,常用電源に切り替えて電力の維持を行う. 各ビルごとにD ∪ S に対応する成分を持ち, r が訪れる頂点に対応す

非常用電力の残量は異なり, 電力が枯渇すると電源断にる成分は 1 であり, それ以外は 0 であるようなものと定よる被害が生じる. そのため, 発電機と燃料を搭載した義する. この時 (VRP) は整数計画問題

電源供給車が各ビルを巡回し, 電力の供給を行うという場面が存在する. ここで各ビルに対し電源断が生じる前(IP)

mins.t.に電源供給が行われることが理想であるが, 不可能な場∑∑r∈R cr xrr∈R xr δ r = 1xr ∈ {0, 1} ∀r ∈ R合は電源供給が遅れた時間に比例した被害が生じる. まに定式化される. ここで R は実行可能な経路全体であたビルによってその重要度は異なり, 重要なビルにおいり, xr を 1 にすることが経路 r を選択することに対応て電源断が起きると多大な被害が生じることとなる.

する. すなわち (IP) の解釈としては, 全ての経路からい

上記のような災害支援での想定では全員の被害を小くつかを選択して各頂点を 1 回ずつ訪問するような選さく留めることが重要となる. このような背景から,び方のうち, 総経路長最小のものを求める問題と考える

本研究では目的関数を最大遅延コストの最小化としたことができる. この整数計画問題の線形緩和を列生成法

VRP を Bottleneck VRP (BVRP) として新しく導入によって計算し, 下界の出力を分枝限定法に利用する.

する. また, BVRP に対する厳密手法を提案すると共列を生成する際に生じる部分問題として, 頂点重みと辺に, 追加の想定として人員割当を伴う場合のヒューリス重みが与えられたグラフ上での最大重み閉路を求める

ティックな手法を提案する.

問題が発生する. この問題は NP 困難であるが, ラベリ

2 既存研究ングと呼ばれる手法を用いて実用上高速に計算できる

VRP の定式化には様々なバリエーションが存在するが, ここでは最も一般的な総経路長最小化 VRP のモデルを以下に紹介する.

D, S をそれぞれデポの集合と需要点の集合とする.
任意の 2 頂点の組 i, j ∈ D ∪ S に対してその間の移動時間 τ (i, j) ∈ Z>0 が与えられている. τ は三角不等式ことが知られている.

災害時の電源車巡回経路の最適化 (大中 亮磨)

3 本研究で提案するモデルとアルゴリズム
以上の背景を踏まえ，本研究では最大遅延コスト最小出力が不可能である場合があるため,(DBFP′ )maxs.t.

化を目的関数とする VRP を新しく導入し, その厳密解法を提案した．モデルを以下に記述する.
デポ集合 D と需要点集合 S, 任意の 2 頂点の組 i, j ∈D ∪ S に対する移動時間 τ (i, j) > 0 が与えられる. 各n⊤ yy⊤ δr ≤ 0y≤1∀r ∈ Rλの最適値が正であるか否かという同値な問題に変形することで, 双対解の出力及び列生成法の適用を可能としている.

需要点 i ∈ S に対してその電源供給時間 pi ≥ 0 と同時必要車両数 ni が与えられる. 同時必要車両数が 2 以上の需要点には複数の車両が同時に仕事を開始する必要がある. また, 各需要点 i ∈ S に対して, その重要度

v i > 0 と電源断時刻 ℓi ≥ 0 が与えられる. また車両が周回できる需要点の上限数 u が与えられる. 経路集合

R に対して各需要点 i の仕事開始時刻 ai には電源供給と移動の時間分以上の余裕がある必要がある, すなわち経路長最小化に対する既存手法
整数計画問題として定式化
下界の計算
列生成法によるLP緩和の計算
部分LP計算ラベリング

出力に応じて分枝or限定操作で表される. 実現可能な経路集合の上で, 需要点に対定式化
下界の計算

ari+1 ≥ ari + pri + τ (ri , ri+1 )である. 各需要点 i の遅延コスト c′i は c′i = v i (ai − ℓi )

遅延コストmin-maxに対する提案手法

遅延コスト𝜆を二分探索
列生成法による実行可能性判定
部分FP判定ラベリング
出力に応じて分枝or限定操作する遅延コストの最大値が最小の経路を求める問題を(BVRP) と表すことにする.

図 1. 既存手法と提案アルゴリズム．

(BVRP) の同期制約を緩和した定式化は,(BIP)

mins.t.

′max∑ r∈R cr xrr∈R xr δ r = nxr ∈ {0, 1} ∀r ∈ R

また本研究では人員の割当を伴う場合についても想定し, ヒューリスティックな手法を提案した. 人員の割当を伴う場合, 人員が搭乗している間のみ車両の移動とのようになる. ここで生じる問題として, (VRP) の場合電源供給が可能となる. これに対する提案手法として,と異なり目的関数が min-max の形であるため制約を線各人員が搭乗できる車両を同駐在所出発の車両 1 台の形緩和しても線形計画問題に帰着できない点が挙げらみに固定した上で, 上記と同様の分枝限定法と列生成法れる. この課題を解決するために, 遅延コストが λ 以下を適用し, 列の生成に伴うラベリング時に人的制約を加で周回可能かという実行可能性問題を解くと共に, 実行味しながら探索を行う手法を提案した. 本手法は人的制可能となる最小の λ を二分探索で求めることを考える.

約を加味しながら経路選択を行うことができるという

すなわち, 遅延コストが λ 以下の経路全体を Rλ と表す

点で, 人員を無視して経路選択を行ったのち人員割当をとき, 実行可能性問題行うような手法と比較して最終的な出力解の改善が期(BFP)

ﬁnds.t.

x∑r

待される.
r∈Rλ xr δ r = n0 ≤ xr

∀r ∈ Rλを解くことを考える. ここで(DBFP)

ﬁnds.t.

yy⊤ δr ≤ 0n⊤ y > 0∀r ∈ Rλとおくと, Farkas の補題 [3] より (BFP) と (DBFP) のいずれか片方のみが実行可能である. ここで (DBFP)
は不等式制約と非有界性により単体法による双対解の参考文献[1] M. Desrochers, J. Desrosiers, and M. Solomon. A new
optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40:342–354, 04 1992.
[2] S. Kumar and R. Panneerselvam. A survey on thevehicle routing problem and its variants. Intelligent
Information Management, 4:66–74, 2012.
[3] J. Matoušek and B. Gärtner. Understanding and Using Linear Programming. Springer Berlin, Heidelberg,2007.