最適化セミナーのご案内

2.13.4 施設配置問題

 ここでは,どこに施設を配置するかを決定する問題を取り上げます.次の例題を考えます.

例題

 施設を候補地のどこに建てるかを決定します.施設として緊急時の収容所を考えます.つまり,火事での火傷や脳卒中の患者の受け入れ等を考慮するため,エリアの合計人数を考慮するのではなく,各エリアの対象予想数をカバーできればよく,例えば施設1がエリアA,B,Cを担当するときには,施設1の容量に関する制約はA,B,Cの合計人数ではなく,A,B,Cエリアのそれぞれの人数をカバーできればよいということになります.これは,異なるエリアで同時に事象が起こりえないモデルとして考えることを意味します.問題を以下に整理します.

  • 緊急時の収容を考慮する(異なる地域を同時に収容しない)
  • 各施設は受け入れ容量を持っている
  • 各地域は最寄の施設に対応づけられる
  • 容量をオーバーする場合は距離に比例するコストを支払えば3人まで超過することができる
  • 施設を建設するにはコストがかかる
  • 施設の建設候補地は7地点である
  • 地域は5 × 5の25地点である

 このとき,容量超過コストと施設建設コストの和を最小化するような建設場所を決定したいとします.

 以上を踏まえて,以下のように定式化することができます.但しMは大きな定数とします.

集合
$I = \{1 \ldots 7\}$ 施設の集合
$J = \{1 \ldots 25\}$ 地域の集合
 
0-1変数
$x_i, i \in I$ 施設$i$を建設するならば$x_i = 1$,そうでないならば$x_i = 0$とする
 
離散変数
$y_j, j \in J$ エリア$j$に対しての超過人数.0 ... 3の値をとる
 
定数
$dist_{ij}, i \in I, j \in J$ 施設$i$から地域$j$までの距離.今回は座標を与え直線距離をモデル内で求める
$num_j$ 地域$j$で発生する緊急患者数
$capa_i$ 施設$i$が受け入れることのできる人数
$cost_i$ 施設$i$の建設コスト
 
目的関数(最小化)
$\displaystyle \sum_i cost_i x_i  + \sum_j y_j \min \left( dist_{ij} + M\left( 1 - x_i \right), i \right)$ コストの総和
 
制約条件
下記参照  

 制約式は「各地域は最寄の施設に収容される」ということと,「施設の収容には容量があり,3人までは容量の超過が認められる」ということです.これはWCSP特有の関数であるargmin関数を用いることによって1つの制約式で表現することができます.これは実際にモデルで確認をしてください.

 今回は定数に関してはファイルからデータを与えてみます.モデル部分は以下のようになります.

// 施設の集合
Set I;
Element i(set = I);
// 地域の集合
Set J;
Element j(set = J);
IntegerVariable x(index = i,type = binary,name = "x");

Set S = "0 ... 3"; // 離散変数用の集合
DiscreteVariable y(dom = S,index = j,name = "y");

// dist はモデル内で計算する
Parameter dist(index = (i,j),name = "dist");

// 実際には以下の座標を入力する
Parameter pos_xi(index = i,name = "pos_xi");
Parameter pos_xj(index = j,name = "pos_xj");
Parameter pos_yi(index = i,name = "pos_yi");
Parameter pos_yj(index = j,name = "pos_yj");
// 距離は直線距離を考える
dist[i,j] = sqrt(pow((pos_xi[i] - pos_xj[j]),2)
               +pow((pos_yi[i] - pos_yj[j]),2));

Parameter num(index = j,name = "num");
Parameter n(index = (i,j),name = "n");
Parameter capa(index = i,name = "capa");
Parameter cost(index = i,name = "cost");
Parameter M;
M = 100;

// 施設の容量超過分のための計算
n[i,j] = capa[i] - num[j];

Objective total_cost(type = minimize);
total_cost = sum(cost[i]*x[i],i) + 
sum(y[j]*min(dist[i,j]+ M*(1 - x[i]),i),j);

// 制約式,超過人数 y についての記述
n[argmin((1 - x[i])*M + dist[i,j],i),j] + y[j] >= 0;

options.maxtim = 5;
options.method = "wcsp";
solve();

 以下がcsv形式の入力ファイルです.施設に関してと地域に関しての二種類のファイルを用意する必要があります.

i,pos_xi,pos_yi,capa,cost
1,13,18,6,24
2,14,4,9,20
3,19,15,7,41
4,3,10,5,13
5,18,11,7,23
6,7,5,10,18
7,6,1,7,20
j,pos_xj,pos_yj,num
1,0,0,3
2,0,5,6
3,0,10,1
4,0,15,7
5,0,20,3
6,5,0,5
7,5,5,8
8,5,10,12
9,5,15,3
10,5,20,4
11,10,0,5
12,10,5,9
13,10,10,2
14,10,15,1
15,10,20,11
16,15,0,3
17,15,5,4
18,15,10,5
19,15,15,9
20,15,20,1
21,20,0,5
22,20,5,7
23,20,10,8
24,20,15,2
25,20,20,11

 このように,WCSP特有の関数を用いると煩雑な制約式でも簡単に記述できる場合があります.次にこの問題で「最寄の施設まで10.5以上距離がある地域は10地域までしか許さない」という制約を記述することを考えてみます.これはWCSP用のcount関数を用いれば簡単に記述することができます.この場合どの施設がどのエリアを担当するという変数zを加えて以下のように記述することができます.(FacilityLocation2.smp参照)

  IntegerVariable z(index = (i,j),type = binary);
  selection(z[i,j],i);
  Element ii(set = I);
  sum(dist[i,j]*z[i,j],i) <= min(dist[ii,j]+(1 - x[ii])*M,ii);
  semiHardConstraint();
  count( 10.5 <= z[i,j]*dist[i,j],(i,j)) <= 10;

 ここでsemiHardConstraintを用いたのは万が一10地域以内でおさまらなかった場合に「なるべく10地域以内で」ということを表現するためです.


 

 

上に戻る