配置可能な観測地点の集合を𝐼 とする. 本論文では, 地点𝑖 ∈
𝐼 は出動要請が発生する可能性のある地点でもある.
警備車両の最適配置問題
警備車両は出動要請を受けたならば, 迅速に現場へとたど
り着く必要がある. そのため, 時間内に到達可能な距離を𝐷
Optimal location-allocation problems
for traffic police patrol vehicles
とし, 地点𝑖 から到達可能距離内にある地点の集合𝑁𝑖 を
𝑁𝑖 = { 𝑗 ∈ 𝐼 | 𝑑𝑖𝑗 ≤ 𝐷 }
と定義する. ここで, 𝑑𝑖𝑗 は地点𝑖, 𝑗 間の距離とする. ある地
点𝑗 ∈ 𝑁𝑖 に警備車両が配置されており, その警備車両が地点𝑖
公共システムプログラム
11-11428 佐藤裕輝 Hiroki Sato
の出動要請に対応するならば, 「地点𝑖 は地点𝑗 に配置された
警備車両によってカバーされている」という.
指導教員 松井知己 Adviser Tomomi Matsui
2.2 警備車両配置問題
1 はじめに
東京都の 1 世帯あたりの乗用車台数は 0.461 台と, 47 都道
府県中 47 位である. しかし, 乗用車密度は 1411.10(台/km2 )
配置分配問題における典型的な問題として, set-covering
problem (P1)と maximum covering location problem (P2)
の 2 つのタイプの問題がある.
であり 2 位となっている. このため, 東京都は愛知県, 大阪
問題 P1 は Toregas ら [4] によって提案された. この問題
府, 福岡県に次いで 4 番目に交通事故が多く, 平均旅行速度
では, すべての観測地点は配置された警備車両のうち少なく
は最も遅く渋滞頻度も高いことがうかがえる
とも 1 台にカバーされなければならない. その上で, 警備車
交通警察は, これらの被害に対応・防止するために二つの
両の配置費用を最小化する問題である. 決定変数
反の防止などが含まれる. もう一つは, 動的な役割として直
1 (地点𝑗 に警備車両が配置されている),
𝑥𝑗 = {
0 (その他),
を導入する. 地点𝑗 に警備車両を配置するのに必要な費用を
接的な違反の取締り, 交通事故の対応などが挙げられる. 上
𝑐𝑗 とすると, P1 は以下のような整数計画問題
記二つの役割を果たすために, 交通警察は警備車両を配置し
P1: minimize
役割を担う. 一つは, 静的な役割である. これには, 主要交差
点での交通整理や, 運転手の目に付くことによる間接的な違
ている.
subject to
∑𝑗∈𝑁𝑖 𝑥𝑗 ≥ 1 (∀𝑖 ∈ 𝐼),
𝑥𝑗 ∈ {0, 1}
警備車両を配置するためには人的資源や資金が必要であ
り, 配置台数が制限される. しかしながら, どの地点からの
∑𝑗∈𝐼 𝑐𝑗 𝑥𝑗
(∀𝑗 ∈ 𝐼),
として記述される問題である.
出動要請にも迅速に対応する必要がある. したがって, 警備
問題 P2 は Church and Revelle [3] によって定式化され
車両の最適な配置場所を求めることは重要となる. 本論文で
た. この問題は, 限られた警備車両数𝑃 の下で, カバーされ
は, 警備車両の配置問題を[2] [3] [4] によって定式化された
ている地点𝑖 の重要度を表す正の重みℎ𝑖 の総和を最大化する
複数の整数計画問題として記述する. また, 定式化された整
問題である. 決定変数として新たに
数計画問題を東京都市郡部に適用して, 計算実験を行う. こ
の際, 警備車両の数や速度などを変更しながら各問題の結果
を考察する.
今回用いた整数計画問題はいずれも NP 困難であり, 多項
𝑧𝑖 = {
1 (地点𝑖 がカバーされている),
0 (その他),
を導入すると, P2 は以下のような整数計画問題
P2: maximize
∑𝑖∈𝐼 ℎ𝑖 𝑧𝑖
ーを用いることで即座に解くことができる. しかしながら,
∑𝑗∈𝑁𝑖 𝑥𝑗 ≥ 𝑧𝑖 (∀𝑖 ∈ 𝐼),
∑𝑗∈𝐼 𝑥𝑗 ≤ 𝑃,
実務においては経済的な理由等から IP ソルバーを用意でき
𝑥𝑗 ∈ {0, 1}
(∀𝑗 ∈ 𝐼),
𝑧𝑖 ∈ {0, 1}
(∀𝑖 ∈ 𝐼),
式時間解法の存在は絶望視されているが, 商用の IP ソルバ
ない状況も考えられる. そこで, IP ソルバーを使用せず, 短
時間で質の良い解を求める近似アルゴリズムについても議論
する.
subject to
として記述される問題である.
問題 P1, P2 はともに NP 困難な問題であり, 多項式時間
解法の存在は絶望視されている.
2 定式化
次に, Adler ら [2] によって提案された問題 P3, P4, P5 を
本節では, 警備車両の配置問題を定式化する. その際, 典
記す. これらの問題では, 警備車両の影響力を測る指標とし
型的な配置分配問題のアプローチと, 交通量と出動要請を考
て, 配置された警備車両が実際に観測する交通量に着目する.
慮したアプローチを行う.
まず, 各警備車両がカバーする範囲を区別する. 任意の地点𝑖
に対して, ある地点に配置された警備車両 1 台のみにカバー
2.1 用語の定義
され, 他の地点に配置された車両にはカバーされていないと
今回扱う警備車両の配置分配問題では, 道路上の交差点等
する. 問題 P3 はすべての観測地点がカバーされているとい
に観測地点を設け警備車両を配置する. そこで, 警備車両を
う制約の下で, 警備車両が観測する交通量を最大化する問題
圏央道以西も含めた一般国道, 主要地方道上の 158 地点を用
である. 新たに決定変数
𝑧𝑖𝑗 = {
1 (地点𝑗 の警備車両で地点𝑖 がカバーされている),
意した. 交通量データとして, 国土交通省「平成 22 年度全
0 (その他),
を導入する. 地点𝑗 における 1 時間あたりの交通量を𝑈𝑗 とす
国道路・街路交通情勢調査（道路交通センサス）
」を使用し
るならば, P3 は
警備車両配置問題
P3: maximize
subject to
∑𝑗∈𝐼 𝑈𝑗 𝑥𝑗
実験 A, 実験 B において, 車両速度, 警備車両数, 期間数
∑𝑗∈𝐼 𝑥𝑗 = 𝑃 ,
を変更しながら 5 つの整数計画問題を解いた. 本稿では詳細
∑𝑗∈𝑁𝑖 𝑧𝑖𝑗 = 1 (∀𝑖 ∈ 𝐼),
𝑧𝑖𝑗 ≤ 𝑥𝑗
た. 計算には商用ソフトウェア CPLEX を用いた.
(∀𝑖 ∈ 𝐼; 𝑗 ∈ 𝑁𝑖 ),
𝑥𝑗 ∈ {0, 1}
(∀𝑗 ∈ 𝐼),
𝑧𝑖𝑗 ∈ {0, 1}
(∀𝑖, 𝑗 ∈ 𝐼),
を略す.
近似解法
実験 A, 実験 B において, 警備車両数を変更しながらアル
ゴリズム 1 を実行した. また問題 P2 の結果と比較した一部
を表 1 に記す.
と定式化される問題である.
問題 P4 では, 問題 P3 に加えて出動要請を考慮する. 具体
的には, すべての地点𝑖 で警備車両への出動要請があり, 警備
表 1 実験 A における問題 P2 の最適解とアルゴリズム 1 に
車両はカバーしている地点で要請があった場合必ず行かなけ
よる近似解との比較
ればならない. 簡単化のために要請を処理した後は, はじめ
に配置された地点に戻るとする. このとき, 警備車両は往復
時間𝑡𝑖𝑗 と, 要請があった地点でイベントを処理するのにかか
速度
問題 P2 の
近似解での
近似比率
最適値
カバー数
[％]
2
112
108
96.429
る時間𝐸𝑖 の間は交通量を観測することができない. そのた
3
129
127
98.45
め, 地点 j に配置された警備車両が観測できる時間は, 1 日
4
132
129
97.727
2
126
121
96.032
3
132
127
96.212
のシフト時間𝐻 からカバーしているすべての地点𝑖 への往復
30km/h
車両数
40km/h
時間𝑡𝑖𝑗 とイベントの処理時間𝐸𝑖 を引くことで求めることが
できる. そこで, 問題 P3 の目的関数のみを
∑𝑗∈𝐼 𝑈𝑗 (𝐻𝑥𝑗 − ∑𝑖∈𝐼(𝑡𝑖𝑗 + 𝐸𝑖 )𝑧𝑖𝑗 )
5 まとめ
に変更したものが問題 P4 である.
車両速度が大きい場合は到達可能範囲が十分にとれるた
問題 P5 は複数期間にわたる警備車両の最適配置問題であ
め, 警備車両の配置場所が交通量の多い地点に集中してしま
る. 本稿では詳細を略す.
うことがあった. また近似解法の結果と問題 P2 の結果には
3 近似アルゴリズム
分に有意性があるといえる.
大きな差異は見受けられず, 今回提案したアルゴリズムは十
本節では, 前節で定式化した maximum covering location
5 つの整数計画問題はそれぞれ目的や条件が異なっており,
problem (P2)を解く, Hochbaum [1] によって提案された貪
警備車両を配置する自治体が意図に応じて選ぶことが可能で
欲解法による近似アルゴリズムを記述する.
ある. もしくは, 複数の問題を比較し, その自治体にとって
貪欲解法とは, 地点𝑖 から到達可能距離内にある地点の集
より有益な地点に警備車両を配置することも可能である.
合𝑁𝑖 のうち, まだカバーされていない地点𝑗 の重み𝑤𝑗 の総和
本論文では, 警備車両の配置問題を扱った. しかし, 警備
が最大の地点に警備車両を配置する解法である. 配置可能な
車両以外にも, 他の救急車両や公的施設等の配置問題にも適
車両数を𝑃, すでにカバーされている地点の集合を𝐺 とする
用することができると考えられる.
と, 貪欲解法のアルゴリズムは以下のようになる.
アルゴリズム 1
参考文献
Step 0 : 𝐺 ← ∅, 𝑘 ← 1 とする.
[1] D. S. Hochbaum, Approximation Algorithms for NP-
Step 1 : ∑𝑗∈𝑁𝑖 ∖𝐺 𝑤𝑗 を最大にする𝑖 を選ぶ.
Hard Problems, PWS Publishing Company, 1997.
Step 2 : 𝐺 ← 𝐺 ∪ 𝑁𝑖 とする.
[2] N. Adler, A. S. Hakkert, J. Kornbluth, T. Raviv, and
Step 3 : 𝑘 = 𝑃 ならば終了. それ以外ならば 𝑘 ← 𝑘 + 1 とし
M. Sher, “Location-allocation models for traffic police
て Step 1 へ戻る.
定理１
patrol vehicles on an interurban network," Annals of
1
Operations Research, 221 (2014), pp. 9–31.
𝑒
[3] R. Church and C. Revelle, “The maximal covering
このアルゴリズムは近似比(1 − ) を達成する.
4 計算実験
第 2 節で記した整数計画問題と第 3 節で記した近似アルゴ
location
problem,"
Papers of the Regional Science
Association, 32 (1974), pp. 101–118.
リズムを用いて計算実験を行う. 実験の対象は東京都市郡部
[4] C. Toregas, R. Swain, C. Revelle, and L. Bergman, “The
とする. 警備車両を配置可能な観測地点として, [実験 A] 圏
location of emergency service facilities," Operations
央道以東の一般国道, 主要地方道上の 132 地点と, [実験 B]
Research, 19 (1971), pp. 1363–1373.
© Copyright 2024 ExpyDoc
