数理最適化セミナーのご案内

2.11 pセンター問題

　前節のpメディアン問題は，需要点と施設点の間の（重み付き）総移動距離を最小にするという目的で作られた問題でした．このため，需要点から施設点までの平均的な移動距離を最小にするような解を期待できます．しかし，解の中に需要点と施設点の間が極端に離れている組み合わせが含まれている可能性があります．この点，この節で扱うpセンター問題は，（重み付き）移動距離が極端に大きい組み合わせを作らないように配置をする問題と見ることができます．

　ここで，センターとは最も遠い需要点からの（重み付き）距離を最小にする施設点のことで，この点を求める問題のことをセンター問題といいます．また，p箇所に施設を配置するような場合にpセンター問題と呼び，消防署のような施設を配置するような場合に用いられています．

例題

　ある企業は，A市からF市までの6市の中から2つの市に新たにデパートを出店しようと考えています．この時，都市から出店地までの重み付き移動距離の最大値を最小にするためにはどの市に出店すると良いでしょうか．なお，各市の人口は左下の表のようになっています．また，2市間の距離は右下の図のようになっています．なお，直接結ばれていない2都市間の距離は他の都市を経由したときの最短距離を採用します．

都市 人口
A市 800
B市 550
C市 780
D市 600
E市 1020
F市 360

　

　前節の例題との違いは目的関数の部分だけです．このため，前節の例題での変数と制約条件についてはこの例題でもそのまま使用しますので詳細は前節を参照してください．

　目的関数については，都市から出店地までの重み付き移動距離の最大値ということになります．まず，都市iから都市jまでの重み付き移動距離を求めます．これは$x_{ij} = 1$の時に意味を持つものですからi-j間の距離，iの人口そして$x_{ij}$の3つを掛け合わせたものとなります．なお，$i = j$の時にはこの積は常に0になりますので計算には含めないことにします．次に，今回のようなミニマックス問題の定式化での一つのテクニックとして変数vを新たに導入します．この時，重み付き移動距離がそれぞれv以下であるという制約条件を加えることでvに重み付き移動距離の最大値という意味を持たせることができます．よって，変数v自身が目的関数となります．

　以上のことから，次のように定式化できます．

0-1変数
$x_{AA}$, $x_{AB}$, $x_{AC}$, $x_{AD}$, $x_{AE}$, $x_{AF}$, $x_{BA}$, $x_{BB}$, $x_{BC}$, $x_{BD}$, $x_{BE}$, $x_{BF}$, $x_{CA}$, $x_{CB}$, $x_{CC}$, $x_{CD}$, $x_{CE}$, $x_{CF}$, $x_{DA}$, $x_{DB}$, $x_{DC}$, $x_{DD}$, $x_{DE}$, $x_{DF}$, $x_{EA}$, $x_{EB}$, $x_{EC}$, $x_{ED}$, $x_{EE}$, $x_{EF}$, $x_{FA}$, $x_{FB}$, $x_{FC}$, $x_{FD}$, $x_{FE}$, $x_{FF}$ 0または1をとる出店するのかと最も近い出店地はどこなのかを表す変数
　
連続変数
$v$ 重み付き移動距離の最大値
　
目的関数（最小化）
$v$ 重み付き移動距離の最大値
　
制約条件
$v \ge 800 \times 7x_{AB}$, $v \ge 800 \times 2x_{AC}$, $v \ge 800 \times 13x_{AD}$, $v \ge 800 \times 19x_{AE}$, $v \ge 800 \times 17x_{AF}$, $v \ge 550 \times 7x_{BA}$, $v \ge 550 \times 8x_{BC}$, $v \ge 550 \times 6x_{BD}$, $v \ge 550 \times 12x_{BE}$, $v \ge 550 \times 10x_{BF}$, $v \ge 780 \times 2x_{CA}$, $v \ge 780 \times 8x_{CB}$, $v \ge 780 \times 14x_{CD}$, $v \ge 780 \times 20x_{CE}$, $v \ge 780 \times 18x_{CF}$, $v \ge 600 \times 13x_{DA}$, $v \ge 600 \times 6x_{DB}$, $v \ge 600 \times 14x_{DC}$, $v \ge 600 \times 7x_{DE}$, $v \ge 600 \times 4x_{DF}$, $v \ge 1020 \times 19x_{EA}$, $v \ge 1020 \times 12x_{EB}$, $v \ge 1020 \times 20x_{EC}$, $v \ge 1020 \times 7x_{ED}$, $v \ge 1020 \times 3x_{EF}$, $v \ge 360 \times 17x_{FA}$, $v \ge 360 \times 10x_{FB}$, $v \ge 360 \times 18x_{FC}$, $v \ge 360 \times 4x_{FD}$, $v \ge 360 \times 3x_{FE}$ 各重み付き移動距離は最大値を越えない
$x_{AA} + x_{BB} + x_{CC} + x_{DD} + x_{EE} + x_{FF} = 2$ 2都市に出店
$x_{AA} + x_{AB} + x_{AC} + x_{AD} + x_{AE} + x_{AF} = 1$ A市は1箇所に配分
$x_{BA} + x_{BB} + x_{BC} + x_{BD} + x_{BE} + x_{BF} = 1$ B市は1箇所に配分
$x_{CA} + x_{CB} + x_{CC} + x_{CD} + x_{CE} + x_{CF} = 1$ C市は1箇所に配分
$x_{DA} + x_{DB} + x_{DC} + x_{DD} + x_{DE} + x_{DF} = 1$ D市は1箇所に配分
$x_{EA} + x_{EB} + x_{EC} + x_{ED} + x_{EE} + x_{EF} = 1$ E市は1箇所に配分
$x_{FA} + x_{FB} + x_{FC} + x_{FD} + x_{FE} + x_{FF} = 1$ F市は1箇所に配分
$x_{AB} \le x_{BB}$, $x_{AC} \le x_{CC}$, $x_{AD} \le x_{DD}$, $x_{AE} \le x_{EE}$, $x_{AF} \le x_{FF}$, $x_{BA} \le x_{AA}$, $x_{BC} \le x_{CC}$, $x_{BD} \le x_{DD}$, $x_{BE} \le x_{EE}$, $x_{BF} \le x_{FF}$, $x_{CA} \le x_{AA}$, $x_{CB} \le x_{BB}$, $x_{CD} \le x_{DD}$, $x_{CE} \le x_{EE}$, $x_{CF} \le x_{FF}$, $x_{DA} \le x_{AA}$, $x_{DB} \le x_{BB}$, $x_{DC} \le x_{CC}$, $x_{DE} \le x_{EE}$, $x_{DF} \le x_{FF}$, $x_{EA} \le x_{AA}$, $x_{EB} \le x_{BB}$, $x_{EC} \le x_{CC}$, $x_{ED} \le x_{DD}$, $x_{EF} \le x_{FF}$, $x_{FA} \le x_{AA}$, $x_{FB} \le x_{BB}$, $x_{FC} \le x_{CC}$, $x_{FD} \le x_{DD}$, $x_{FE} \le x_{EE}$ 出店している都市に配分

　この結果をC++SIMPLEで記述すると次のようになります．

// 変数の宣言
IntegerVariable 
     x_AA(type = binary), x_AB(type = binary), x_AC(type = binary),
     x_AD(type = binary), x_AE(type = binary), x_AF(type = binary),
     x_BA(type = binary), x_BB(type = binary), x_BC(type = binary),
     x_BD(type = binary), x_BE(type = binary), x_BF(type = binary),
     x_CA(type = binary), x_CB(type = binary), x_CC(type = binary),
     x_CD(type = binary), x_CE(type = binary), x_CF(type = binary),
     x_DA(type = binary), x_DB(type = binary), x_DC(type = binary),
     x_DD(type = binary), x_DE(type = binary), x_DF(type = binary),
     x_EA(type = binary), x_EB(type = binary), x_EC(type = binary),
     x_ED(type = binary), x_EE(type = binary), x_EF(type = binary),
     x_FA(type = binary), x_FB(type = binary), x_FC(type = binary),
     x_FD(type = binary), x_FE(type = binary), x_FF(type = binary);
Variable v;

// 重み付き移動距離の最大値の最小化
Objective max_distance(type = minimize);
max_distance = v;
v >= 800 * 7 * x_AB;   v >= 800 * 2 * x_AC;   v >= 800 * 13 * x_AD;
v >= 800 * 19 * x_AE;  v >= 800 * 17 * x_AF;  v >= 550 * 7 * x_BA;
v >= 550 * 8 * x_BC;   v >= 550 * 6 * x_BD;   v >= 550 * 12 * x_BE;
v >= 550 * 10 * x_BF;  v >= 780 * 2 * x_CA;   v >= 780 * 8 * x_CB;
v >= 780 * 14 * x_CD;  v >= 780 * 20 * x_CE;  v >= 780 * 18 * x_CF;
v >= 600 * 13 * x_DA;  v >= 600 * 6 * x_DB;   v >= 600 * 14 * x_DC;
v >= 600 * 7 * x_DE;   v >= 600 * 4 * x_DF;   v >= 1020 * 19 * x_EA;
v >= 1020 * 12 * x_EB; v >= 1020 * 20 * x_EC; v >= 1020 * 7 * x_ED;
v >= 1020 * 3 * x_EF;  v >= 360 * 17 * x_FA;  v >= 360 * 10 * x_FB;
v >= 360 * 18 * x_FC;  v >= 360 * 4 * x_FD;   v >= 360 * 3 * x_FE;

// 出店と配分に関する制約条件
x_AA + x_BB + x_CC + x_DD + x_EE + x_FF == 2;
x_AA + x_AB + x_AC + x_AD + x_AE + x_AF == 1;
x_BA + x_BB + x_BC + x_BD + x_BE + x_BF == 1;
x_CA + x_CB + x_CC + x_CD + x_CE + x_CF == 1;
x_DA + x_DB + x_DC + x_DD + x_DE + x_DF == 1;
x_EA + x_EB + x_EC + x_ED + x_EE + x_EF == 1;
x_FA + x_FB + x_FC + x_FD + x_FE + x_FF == 1;
x_AB <= x_BB; x_AC <= x_CC; x_AD <= x_DD; x_AE <= x_EE; x_AF <= x_FF;
x_BA <= x_AA; x_BC <= x_CC; x_BD <= x_DD; x_BE <= x_EE; x_BF <= x_FF;
x_CA <= x_AA; x_CB <= x_BB; x_CD <= x_DD; x_CE <= x_EE; x_CF <= x_FF;
x_DA <= x_AA; x_DB <= x_BB; x_DC <= x_CC; x_DE <= x_EE; x_DF <= x_FF;
x_EA <= x_AA; x_EB <= x_BB; x_EC <= x_CC; x_ED <= x_DD; x_EF <= x_FF;
x_FA <= x_AA; x_FB <= x_BB; x_FC <= x_CC; x_FD <= x_DD; x_FE <= x_EE;

　このままでは大変分かりにくいですので，前節と同様にC++SIMPLEでの記述を簡潔なものにしていくことにします．この際，定式化については次のようなものにします．

集合
$City = \{ A, B, C, D, E, F \}$ 都市の集合
　
0-1変数
$x_{ij}, i \in City, j \in City$ 0または1をとる出店するのかと最も近い出店地はどこなのかを表す変数
　
連続変数
$v$ 重み付き移動距離の最大値
　
定数
$distance_{ij}, i \in City, j \in City$ 都市iから都市jまでの距離
$population_i, i \in City$ 都市iの人口
　
目的関数（最小化）
$v$ 重み付き移動距離の最大値
　
制約条件
$v \ge population_i \cdot distance_{ij} \cdot x_{ij}, \forall i, j \in City, i \ne j$ 各重み付き移動距離は最大値を越えない
$\displaystyle \sum_{i \in City} x_{ii} = 2$ 2都市に出店
$\displaystyle \sum_{j \in City} x_{ij} = 1, \forall i \in City$ 各都市は1箇所に配分
$x_{ij} \le x_{jj}, \forall i, j \in City, i \ne j$ 出店している都市に配分

　すると，C++SIMPLEでは次のような簡潔な記述になります．

// 集合と添字
Set City;
Element i(set = City), j(set = City);

// パラメータ
Parameter distance(name = "2 都市間の距離", index = (i, j));
Parameter population(name = "都市の人口", index = i);

// 変数
IntegerVariable x(index = (i, j), type = binary);
Variable v;

// 目的関数
Objective max_distance(type = minimize);
max_distance = v;

// 制約条件
v >= population[i] * distance[i, j] * x[i, j];
sum(x[i, i], i) == 2;
sum(x[i, j], j) == 1;
x[i, j] <= x[j, j], i != j;

// 求解
solve();

// 結果出力
simple_printf("%s 市に出店する．\n", i, x[i,i].val == 1);

　実行する際には，前節の例題と同様に次の2都市間の距離を表すcsvファイル（左）と各都市の人口を表すdatファイル（右）を与えます．

2 都市間の距離, A, B, C, D, E, F
A, 0, 7, 2, 13, 19, 17
B, 7, 0, 8, 6, 12, 10
C, 2, 8, 0, 14, 20, 18
D, 13, 6, 14, 0, 7, 4
E, 19, 12, 20, 7, 0, 3
F, 17, 10, 18, 4, 3, 0
都市の人口 =
[A] 800 
[B] 550 
[C] 780 
[D] 600 
[E] 1020 
[F] 360
;

　このモデルを実行すると，前節のpメディアン問題の時の結果とは異なり，A市とF市に出店すると良いことがわかります．

2.10 pメディアン問題
2.12 巡回セールスマン問題

 

 

上に戻る