ロジスティックネットワーク設計システム MEta Logistic network Optimization System

簡易システムビデオ

MELOS (MEta Logistic Optimization System)

MEta Logistic network Optimization System-GF (Green FIeld)

YouTubeVideo("x9c0UQo699g")
YouTubeVideo("ae6Yqish4uM")

連続施設配置問題

平面上に施設が配置可能と仮定した施設問題に対する近似解法を考える。

施設数が1つの場合には、Weiszfeld法と呼ばれる反復法で近似解が得られることが知られている。 複数施設に対しては、k-means法と似た反復解法が考えられる。ここでは、重み付き複数施設配置問題に対するWeiszfeld法を構築する。

以下では、1つの施設を洗濯するためのWeiszfeld法について解説する。

各顧客 $i$ は平面上に分布しているものとし,その座標を $(X_i,Y_i)$ とする. 顧客は重み $w_i$ をもち,目的関数は施設と顧客の間の距離に重みを乗じたものの和とする. 顧客と施設間の距離は $\ell_p$ ノルム($1 \leq p$)を用いて計算されるものとする. 東京都市圏の道路ネットワークでは $p \approx 1.8901$ と推定されており, 実務的には Euclidノルム($p=2$)に迂回係数($1.3$ 程度) を乗じたものを使う場合が多い.

顧客の集合 $I$ に対して,単一の倉庫の配置地点 $(X,Y)$ を決定する問題は, $$ f(X,Y) = \sum_{i \in I} w_i \left\{ (X-X_i)^p +(Y-Y_i)^p \right\}^{1/p} $$ を最小にする $(X,Y) \in \mathbf{R}^2$ を求める問題になる. これは,以下の Weiszfeld法を拡張した解法を用いることによって容易に求解できる.

上の関数は凸関数であるので, $(X,Y)$ が最適解である必要十分条件は,$(X,Y)$ が $$ \frac{\partial f(X,Y)}{\partial X} =0 $$ および $$ \frac{\partial f(X,Y)}{\partial Y} =0 $$ を満たすことである. $$ \frac{\partial f(X,Y)}{\partial X} =  \sum_{i \in I} w_i (X-X_i) \frac{ |X-X_i|^{p-2}}{\left\{ (X-X_i)^p +(Y-Y_i)^p \right\}^{(p-1)/p} } =0 $$ は陽的に解くことができないが, 以下の $X$ に対する繰り返し式を示唆している. $$ X^{(q+1)}= \frac{ \sum_{i \in I} w_i |X^{(q)}-X_i|^{p-2} X_i/ \left\{ (X^{(q)}-X_i)^p +(Y^{(q)}-Y_i)^p \right\}^{(p-1)/p} }{ \sum_{i \in I} w_i |X^{(q)}-X_i|^{p-2}/ \left\{ (X^{(q)}-X_i)^p +(Y^{(q)}-Y_i)^p \right\}^{(p-1)/p} } $$

$Y$ についても同様の式を導くことができる.

これらの式を利用した解法は,一般に不動点アルゴリズムとよばれ, $1 \leq p \leq 2$ のとき大域的最適解に収束する.

以下のコードでは移動距離は大圏距離distanceを用いる。これはgeopyから読み込んであると仮定する。 顧客の重みは、年間の製品需要量に製品の重量を乗じたものとする。

引数:

  • cust_df : 顧客データフレーム;緯度経度情報を利用する。
  • weight : 顧客の重み;重み付きの大圏距離の和を最小化するものとする。
  • num_of_facilities : 平面上に配置する施設の数を指定する。
  • epsilon : 誤差上限
  • max_iter : 反復回数の上限

返値:

  • X : 施設の緯度のリスト
  • Y : 施設の経度のリスト
  • partition : 顧客の割り当てられた施設の番号を格納したリスト

weiszfeld_numpy[source]

weiszfeld_numpy(cust_df, weight, num_of_facilities, epsilon=0.0001, max_iter=1000)

Weiszfeld法; 複数施設の連続施設配置問題の近似解法 (NumPy version)

weiszfeld[source]

weiszfeld(cust_df, weight, num_of_facilities, epsilon=0.0001, max_iter=1000)

Weiszfeld法; 複数施設の連続施設配置問題の近似解法

weiszfeld関数の適用例

cust_df = pd.read_csv(folder + "Cust.csv", index_col=0) #read customer data for using Lat/Lng
cust_df.head()
name lat lon
id
1 札幌市 43.06417 141.34694
2 青森市 40.82444 140.74000
3 盛岡市 39.70361 141.15250
4 仙台市 38.26889 140.87194
5 秋田市 39.71861 140.10250
prod_df = pd.read_csv(folder + "Prod.csv", index_col=0) #read product data (for using weight)
prod_df.head()
name weight volume cust_value dc_value plnt_value fixed_cost average_demand standard_deviation inv_cost lot_size safety_inventory target_inventory initial_inventory
0 A 1 0 8 1 1 18 1015.153846 367.846749 0.005769 2516.855181 606.947136 3123.802316 1865.0
1 B 4 0 6 1 1 11 480.596154 169.345187 0.005769 1353.762658 279.419559 1633.182217 956.0
2 C 5 0 6 1 1 16 456.557692 162.361706 0.005769 1591.343248 267.896815 1859.240063 1063.0
3 D 2 0 7 1 1 16 165.230769 47.416591 0.005769 957.329619 78.237375 1035.566994 556.0
4 E 3 0 9 1 1 14 390.846154 134.714885 0.005769 1377.282348 222.279560 1599.561908 910.0
total_demand = pd.read_csv(folder + "total_demand.csv")
total_demand.head()
prod cust demand
0 A さいたま市 261.72
1 A 京都市 102.28
2 A 仙台市 81.22
3 A 佐賀市 145.40
4 A 前橋市 255.70
weight_of_prod ={p:w for (p,w) in zip(prod_df.name, prod_df.weight) } #prepare weight dic.
weight_of_cust = defaultdict(int)
for row in total_demand.itertuples():
    weight_of_cust[row.cust] += weight_of_prod[row.prod]*row.demand 
weight = [weight_of_cust[row.name] for row in cust_df.itertuples()] 

# 関数呼び出し
X, Y, partition = weiszfeld_numpy(cust_df, weight, num_of_facilities = 10)
error= 0 554.0992750051812
error= 1 277.15171860025305
error= 2 211.82887657130394
error= 3 111.12403409848025
error= 4 93.74103979625383
error= 5 98.78085812692669
error= 6 98.78085812692686
error= 7 98.78085812692669
error= 8 98.78085812692686
error= 9 98.78085812692669
error= 10 98.78085812692686
error= 11 98.78085812692669
error= 12 98.78085812692686
error= 13 98.78085812692669
error= 14 98.78085812692686
error= 15 98.78085812692669
error= 16 98.78085812692686
error= 17 98.78085812692669
error= 18 98.78085812692686
error= 19 98.78085812692669
error= 20 98.78085812692686
error= 21 98.78085812692669
error= 22 98.78085812692686
error= 23 98.78085812692669
error= 24 98.78085812692686
error= 25 98.78085812692669
error= 26 98.78085812692686
error= 27 98.78085812692669
error= 28 98.78085812692686
error= 29 98.78085812692669
error= 30 98.78085812692686
error= 31 98.78085812692669
error= 32 98.78085812692686
error= 33 98.78085812692669
error= 34 98.78085812692686
error= 35 98.78085812692669
error= 36 98.78085812692686
error= 37 98.78085812692669
error= 38 98.78085812692686
error= 39 98.78085812692669
error= 40 98.78085812692686
error= 41 98.78085812692669
error= 42 98.78085812692686
error= 43 98.78085812692669
error= 44 98.78085812692686
error= 45 98.78085812692669
error= 46 98.78085812692686
error= 47 98.78085812692669
error= 48 98.78085812692686
error= 49 98.78085812692669
error= 50 98.78085812692686
error= 51 98.78085812692669
error= 52 98.78085812692686
error= 53 98.78085812692669
error= 54 98.78085812692686
error= 55 98.78085812692669
error= 56 98.78085812692686
error= 57 98.78085812692669
error= 58 98.78085812692686
error= 59 98.78085812692669
error= 60 98.78085812692686
error= 61 98.78085812692669
error= 62 98.78085812692686
error= 63 98.78085812692669
error= 64 98.78085812692686
error= 65 98.78085812692669
error= 66 98.78085812692686
error= 67 98.78085812692669
error= 68 98.78085812692686
error= 69 98.78085812692669
error= 70 98.78085812692686
error= 71 98.78085812692669
error= 72 98.78085812692686
error= 73 98.78085812692669
error= 74 98.78085812692686
error= 75 98.78085812692669
error= 76 98.78085812692686
error= 77 98.78085812692669
error= 78 98.78085812692686
error= 79 98.78085812692669
error= 80 98.78085812692686
error= 81 98.78085812692669
error= 82 98.78085812692686
error= 83 98.78085812692669
error= 84 98.78085812692686
error= 85 98.78085812692669
error= 86 98.78085812692686
error= 87 98.78085812692669
error= 88 98.78085812692686
error= 89 98.78085812692669
error= 90 98.78085812692686
error= 91 98.78085812692669
error= 92 98.78085812692686
error= 93 98.78085812692669
error= 94 98.78085812692686
error= 95 98.78085812692669
error= 96 98.78085812692686
error= 97 98.78085812692669
error= 98 98.78085812692686
error= 99 98.78085812692669
error= 100 98.78085812692686
error= 101 98.78085812692669
error= 102 98.78085812692686
error= 103 98.78085812692669
error= 104 98.78085812692686
error= 105 98.78085812692669
error= 106 98.78085812692686
error= 107 98.78085812692669
error= 108 98.78085812692686
error= 109 98.78085812692669
error= 110 98.78085812692686
error= 111 98.78085812692669
error= 112 98.78085812692686
error= 113 98.78085812692669
error= 114 98.78085812692686
error= 115 98.78085812692669
error= 116 98.78085812692686
error= 117 98.78085812692669
error= 118 98.78085812692686
error= 119 98.78085812692669
error= 120 98.78085812692686
error= 121 98.78085812692669
error= 122 98.78085812692686
error= 123 98.78085812692669
error= 124 98.78085812692686
error= 125 98.78085812692669
error= 126 98.78085812692686
error= 127 98.78085812692669
error= 128 98.78085812692686
error= 129 98.78085812692669
error= 130 98.78085812692686
error= 131 98.78085812692669
error= 132 98.78085812692686
error= 133 98.78085812692669
error= 134 98.78085812692686
error= 135 98.78085812692669
error= 136 98.78085812692686
error= 137 98.78085812692669
error= 138 98.78085812692686
error= 139 98.78085812692669
error= 140 98.78085812692686
error= 141 98.78085812692669
error= 142 98.78085812692686
error= 143 98.78085812692669
error= 144 98.78085812692686
error= 145 98.78085812692669
error= 146 98.78085812692686
error= 147 98.78085812692669
error= 148 98.78085812692686
error= 149 98.78085812692669
error= 150 98.78085812692686
error= 151 98.78085812692669
error= 152 98.78085812692686
error= 153 98.78085812692669
error= 154 98.78085812692686
error= 155 98.78085812692669
error= 156 98.78085812692686
error= 157 98.78085812692669
error= 158 98.78085812692686
error= 159 98.78085812692669
error= 160 98.78085812692686
error= 161 98.78085812692669
error= 162 98.78085812692686
error= 163 98.78085812692669
error= 164 98.78085812692686
error= 165 98.78085812692669
error= 166 98.78085812692686
error= 167 98.78085812692669
error= 168 98.78085812692686
error= 169 98.78085812692669
error= 170 98.78085812692686
error= 171 98.78085812692669
error= 172 98.78085812692686
error= 173 98.78085812692669
error= 174 98.78085812692686
error= 175 98.78085812692669
error= 176 98.78085812692686
error= 177 98.78085812692669
error= 178 98.78085812692686
error= 179 98.78085812692669
error= 180 98.78085812692686
error= 181 98.78085812692669
error= 182 98.78085812692686
error= 183 98.78085812692669
error= 184 98.78085812692686
error= 185 98.78085812692669
error= 186 98.78085812692686
error= 187 98.78085812692669
error= 188 98.78085812692686
error= 189 98.78085812692669
error= 190 98.78085812692686
error= 191 98.78085812692669
error= 192 98.78085812692686
error= 193 98.78085812692669
error= 194 98.78085812692686
error= 195 98.78085812692669
error= 196 98.78085812692686
error= 197 98.78085812692669
error= 198 98.78085812692686
error= 199 98.78085812692669
error= 200 98.78085812692686
error= 201 98.78085812692669
error= 202 98.78085812692686
error= 203 98.78085812692669
error= 204 98.78085812692686
error= 205 98.78085812692669
error= 206 98.78085812692686
error= 207 98.78085812692669
error= 208 98.78085812692686
error= 209 98.78085812692669
error= 210 98.78085812692686
error= 211 98.78085812692669
error= 212 98.78085812692686
error= 213 98.78085812692669
error= 214 98.78085812692686
error= 215 98.78085812692669
error= 216 98.78085812692686
error= 217 98.78085812692669
error= 218 98.78085812692686
error= 219 98.78085812692669
error= 220 98.78085812692686
error= 221 98.78085812692669
error= 222 98.78085812692686
error= 223 98.78085812692669
error= 224 98.78085812692686
error= 225 98.78085812692669
error= 226 98.78085812692686
error= 227 98.78085812692669
error= 228 98.78085812692686
error= 229 98.78085812692669
error= 230 98.78085812692686
error= 231 98.78085812692669
error= 232 98.78085812692686
error= 233 98.78085812692669
error= 234 98.78085812692686
error= 235 98.78085812692669
error= 236 98.78085812692686
error= 237 98.78085812692669
error= 238 98.78085812692686
error= 239 98.78085812692669
error= 240 98.78085812692686
error= 241 98.78085812692669
error= 242 98.78085812692686
error= 243 98.78085812692669
error= 244 98.78085812692686
error= 245 98.78085812692669
error= 246 98.78085812692686
error= 247 98.78085812692669
error= 248 98.78085812692686
error= 249 98.78085812692669
error= 250 98.78085812692686
error= 251 98.78085812692669
error= 252 98.78085812692686
error= 253 98.78085812692669
error= 254 98.78085812692686
error= 255 98.78085812692669
error= 256 98.78085812692686
error= 257 98.78085812692669
error= 258 98.78085812692686
error= 259 98.78085812692669
error= 260 98.78085812692686
error= 261 98.78085812692669
error= 262 98.78085812692686
error= 263 98.78085812692669
error= 264 98.78085812692686
error= 265 98.78085812692669
error= 266 98.78085812692686
error= 267 98.78085812692669
error= 268 98.78085812692686
error= 269 98.78085812692669
error= 270 98.78085812692686
error= 271 98.78085812692669
error= 272 98.78085812692686
error= 273 98.78085812692669
error= 274 98.78085812692686
error= 275 98.78085812692669
error= 276 98.78085812692686
error= 277 98.78085812692669
error= 278 98.78085812692686
error= 279 98.78085812692669
error= 280 98.78085812692686
error= 281 98.78085812692669
error= 282 98.78085812692686
error= 283 98.78085812692669
error= 284 98.78085812692686
error= 285 98.78085812692669
error= 286 98.78085812692686
error= 287 98.78085812692669
error= 288 98.78085812692686
error= 289 98.78085812692669
error= 290 98.78085812692686
error= 291 98.78085812692669
error= 292 98.78085812692686
error= 293 98.78085812692669
error= 294 98.78085812692686
error= 295 98.78085812692669
error= 296 98.78085812692686
error= 297 98.78085812692669
error= 298 98.78085812692686
error= 299 98.78085812692669
error= 300 98.78085812692686
error= 301 98.78085812692669
error= 302 98.78085812692686
error= 303 98.78085812692669
error= 304 98.78085812692686
error= 305 98.78085812692669
error= 306 98.78085812692686
error= 307 98.78085812692669
error= 308 98.78085812692686
error= 309 98.78085812692669
error= 310 98.78085812692686
error= 311 98.78085812692669
error= 312 98.78085812692686
error= 313 98.78085812692669
error= 314 98.78085812692686
error= 315 98.78085812692669
error= 316 98.78085812692686
error= 317 98.78085812692669
error= 318 98.78085812692686
error= 319 98.78085812692669
error= 320 98.78085812692686
error= 321 98.78085812692669
error= 322 98.78085812692686
error= 323 98.78085812692669
error= 324 98.78085812692686
error= 325 98.78085812692669
error= 326 98.78085812692686
error= 327 98.78085812692669
error= 328 98.78085812692686
error= 329 98.78085812692669
error= 330 98.78085812692686
error= 331 98.78085812692669
error= 332 98.78085812692686
error= 333 98.78085812692669
error= 334 98.78085812692686
error= 335 98.78085812692669
error= 336 98.78085812692686
error= 337 98.78085812692669
error= 338 98.78085812692686
error= 339 98.78085812692669
error= 340 98.78085812692686
error= 341 98.78085812692669
error= 342 98.78085812692686
error= 343 98.78085812692669
error= 344 98.78085812692686
error= 345 98.78085812692669
error= 346 98.78085812692686
error= 347 98.78085812692669
error= 348 98.78085812692686
error= 349 98.78085812692669
error= 350 98.78085812692686
error= 351 98.78085812692669
error= 352 98.78085812692686
error= 353 98.78085812692669
error= 354 98.78085812692686
error= 355 98.78085812692669
error= 356 98.78085812692686
error= 357 98.78085812692669
error= 358 98.78085812692686
error= 359 98.78085812692669
error= 360 98.78085812692686
error= 361 98.78085812692669
error= 362 98.78085812692686
error= 363 98.78085812692669
error= 364 98.78085812692686
error= 365 98.78085812692669
error= 366 98.78085812692686
error= 367 98.78085812692669
error= 368 98.78085812692686
error= 369 98.78085812692669
error= 370 98.78085812692686
error= 371 98.78085812692669
error= 372 98.78085812692686
error= 373 98.78085812692669
error= 374 98.78085812692686
error= 375 98.78085812692669
error= 376 98.78085812692686
error= 377 98.78085812692669
error= 378 98.78085812692686
error= 379 98.78085812692669
error= 380 98.78085812692686
error= 381 98.78085812692669
error= 382 98.78085812692686
error= 383 98.78085812692669
error= 384 98.78085812692686
error= 385 98.78085812692669
error= 386 98.78085812692686
error= 387 98.78085812692669
error= 388 98.78085812692686
error= 389 98.78085812692669
error= 390 98.78085812692686
error= 391 98.78085812692669
error= 392 98.78085812692686
error= 393 98.78085812692669
error= 394 98.78085812692686
error= 395 98.78085812692669
error= 396 98.78085812692686
error= 397 98.78085812692669
error= 398 98.78085812692686
error= 399 98.78085812692669
error= 400 98.78085812692686
error= 401 98.78085812692669
error= 402 98.78085812692686
error= 403 98.78085812692669
error= 404 98.78085812692686
error= 405 98.78085812692669
error= 406 98.78085812692686
error= 407 98.78085812692669
error= 408 98.78085812692686
error= 409 98.78085812692669
error= 410 98.78085812692686
error= 411 98.78085812692669
error= 412 98.78085812692686
error= 413 98.78085812692669
error= 414 98.78085812692686
error= 415 98.78085812692669
error= 416 98.78085812692686
error= 417 98.78085812692669
error= 418 98.78085812692686
error= 419 98.78085812692669
error= 420 98.78085812692686
error= 421 98.78085812692669
error= 422 98.78085812692686
error= 423 98.78085812692669
error= 424 98.78085812692686
error= 425 98.78085812692669
error= 426 98.78085812692686
error= 427 98.78085812692669
error= 428 98.78085812692686
error= 429 98.78085812692669
error= 430 98.78085812692686
error= 431 98.78085812692669
error= 432 98.78085812692686
error= 433 98.78085812692669
error= 434 98.78085812692686
error= 435 98.78085812692669
error= 436 98.78085812692686
error= 437 98.78085812692669
error= 438 98.78085812692686
error= 439 98.78085812692669
error= 440 98.78085812692686
error= 441 98.78085812692669
error= 442 98.78085812692686
error= 443 98.78085812692669
error= 444 98.78085812692686
error= 445 98.78085812692669
error= 446 98.78085812692686
error= 447 98.78085812692669
error= 448 98.78085812692686
error= 449 98.78085812692669
error= 450 98.78085812692686
error= 451 98.78085812692669
error= 452 98.78085812692686
error= 453 98.78085812692669
error= 454 98.78085812692686
error= 455 98.78085812692669
error= 456 98.78085812692686
error= 457 98.78085812692669
error= 458 98.78085812692686
error= 459 98.78085812692669
error= 460 98.78085812692686
error= 461 98.78085812692669
error= 462 98.78085812692686
error= 463 98.78085812692669
error= 464 98.78085812692686
error= 465 98.78085812692669
error= 466 98.78085812692686
error= 467 98.78085812692669
error= 468 98.78085812692686
error= 469 98.78085812692669
error= 470 98.78085812692686
error= 471 98.78085812692669
error= 472 98.78085812692686
error= 473 98.78085812692669
error= 474 98.78085812692686
error= 475 98.78085812692669
error= 476 98.78085812692686
error= 477 98.78085812692669
error= 478 98.78085812692686
error= 479 98.78085812692669
error= 480 98.78085812692686
error= 481 98.78085812692669
error= 482 98.78085812692686
error= 483 98.78085812692669
error= 484 98.78085812692686
error= 485 98.78085812692669
error= 486 98.78085812692686
error= 487 98.78085812692669
error= 488 98.78085812692686
error= 489 98.78085812692669
error= 490 98.78085812692686
error= 491 98.78085812692669
error= 492 98.78085812692686
error= 493 98.78085812692669
error= 494 98.78085812692686
error= 495 98.78085812692669
error= 496 98.78085812692686
error= 497 98.78085812692669
error= 498 98.78085812692686
error= 499 98.78085812692669
error= 500 98.78085812692686
error= 501 98.78085812692669
error= 502 98.78085812692686
error= 503 98.78085812692669
error= 504 98.78085812692686
error= 505 98.78085812692669
error= 506 98.78085812692686
error= 507 98.78085812692669
error= 508 98.78085812692686
error= 509 98.78085812692669
error= 510 98.78085812692686
error= 511 98.78085812692669
error= 512 98.78085812692686
error= 513 98.78085812692669
error= 514 98.78085812692686
error= 515 98.78085812692669
error= 516 98.78085812692686
error= 517 98.78085812692669
error= 518 98.78085812692686
error= 519 98.78085812692669
error= 520 98.78085812692686
error= 521 98.78085812692669
error= 522 98.78085812692686
error= 523 98.78085812692669
error= 524 98.78085812692686
error= 525 98.78085812692669
error= 526 98.78085812692686
error= 527 98.78085812692669
error= 528 98.78085812692686
error= 529 98.78085812692669
error= 530 98.78085812692686
error= 531 98.78085812692669
error= 532 98.78085812692686
error= 533 98.78085812692669
error= 534 98.78085812692686
error= 535 98.78085812692669
error= 536 98.78085812692686
error= 537 98.78085812692669
error= 538 98.78085812692686
error= 539 98.78085812692669
error= 540 98.78085812692686
error= 541 98.78085812692669
error= 542 98.78085812692686
error= 543 98.78085812692669
error= 544 98.78085812692686
error= 545 98.78085812692669
error= 546 98.78085812692686
error= 547 98.78085812692669
error= 548 98.78085812692686
error= 549 98.78085812692669
error= 550 98.78085812692686
error= 551 98.78085812692669
error= 552 98.78085812692686
error= 553 98.78085812692669
error= 554 98.78085812692686
error= 555 98.78085812692669
error= 556 98.78085812692686
error= 557 98.78085812692669
error= 558 98.78085812692686
error= 559 98.78085812692669
error= 560 98.78085812692686
error= 561 98.78085812692669
error= 562 98.78085812692686
error= 563 98.78085812692669
error= 564 98.78085812692686
error= 565 98.78085812692669
error= 566 98.78085812692686
error= 567 98.78085812692669
error= 568 98.78085812692686
error= 569 98.78085812692669
error= 570 98.78085812692686
error= 571 98.78085812692669
error= 572 98.78085812692686
error= 573 98.78085812692669
error= 574 98.78085812692686
error= 575 98.78085812692669
error= 576 98.78085812692686
error= 577 98.78085812692669
error= 578 98.78085812692686
error= 579 98.78085812692669
error= 580 98.78085812692686
error= 581 98.78085812692669
error= 582 98.78085812692686
error= 583 98.78085812692669
error= 584 98.78085812692686
error= 585 98.78085812692669
error= 586 98.78085812692686
error= 587 98.78085812692669
error= 588 98.78085812692686
error= 589 98.78085812692669
error= 590 98.78085812692686
error= 591 98.78085812692669
error= 592 98.78085812692686
error= 593 98.78085812692669
error= 594 98.78085812692686
error= 595 98.78085812692669
error= 596 98.78085812692686
error= 597 98.78085812692669
error= 598 98.78085812692686
error= 599 98.78085812692669
error= 600 98.78085812692686
error= 601 98.78085812692669
error= 602 98.78085812692686
error= 603 98.78085812692669
error= 604 98.78085812692686
error= 605 98.78085812692669
error= 606 98.78085812692686
error= 607 98.78085812692669
error= 608 98.78085812692686
error= 609 98.78085812692669
error= 610 98.78085812692686
error= 611 98.78085812692669
error= 612 98.78085812692686
error= 613 98.78085812692669
error= 614 98.78085812692686
error= 615 98.78085812692669
error= 616 98.78085812692686
error= 617 98.78085812692669
error= 618 98.78085812692686
error= 619 98.78085812692669
error= 620 98.78085812692686
error= 621 98.78085812692669
error= 622 98.78085812692686
error= 623 98.78085812692669
error= 624 98.78085812692686
error= 625 98.78085812692669
error= 626 98.78085812692686
error= 627 98.78085812692669
error= 628 98.78085812692686
error= 629 98.78085812692669
error= 630 98.78085812692686
error= 631 98.78085812692669
error= 632 98.78085812692686
error= 633 98.78085812692669
error= 634 98.78085812692686
error= 635 98.78085812692669
error= 636 98.78085812692686
error= 637 98.78085812692669
error= 638 98.78085812692686
error= 639 98.78085812692669
error= 640 98.78085812692686
error= 641 98.78085812692669
error= 642 98.78085812692686
error= 643 98.78085812692669
error= 644 98.78085812692686
error= 645 98.78085812692669
error= 646 98.78085812692686
error= 647 98.78085812692669
error= 648 98.78085812692686
error= 649 98.78085812692669
error= 650 98.78085812692686
error= 651 98.78085812692669
error= 652 98.78085812692686
error= 653 98.78085812692669
error= 654 98.78085812692686
error= 655 98.78085812692669
error= 656 98.78085812692686
error= 657 98.78085812692669
error= 658 98.78085812692686
error= 659 98.78085812692669
error= 660 98.78085812692686
error= 661 98.78085812692669
error= 662 98.78085812692686
error= 663 98.78085812692669
error= 664 98.78085812692686
error= 665 98.78085812692669
error= 666 98.78085812692686
error= 667 98.78085812692669
error= 668 98.78085812692686
error= 669 98.78085812692669
error= 670 98.78085812692686
error= 671 98.78085812692669
error= 672 98.78085812692686
error= 673 98.78085812692669
error= 674 98.78085812692686
error= 675 98.78085812692669
error= 676 98.78085812692686
error= 677 98.78085812692669
error= 678 98.78085812692686
error= 679 98.78085812692669
error= 680 98.78085812692686
error= 681 98.78085812692669
error= 682 98.78085812692686
error= 683 98.78085812692669
error= 684 98.78085812692686
error= 685 98.78085812692669
error= 686 98.78085812692686
error= 687 98.78085812692669
error= 688 98.78085812692686
error= 689 98.78085812692669
error= 690 98.78085812692686
error= 691 98.78085812692669
error= 692 98.78085812692686
error= 693 98.78085812692669
error= 694 98.78085812692686
error= 695 98.78085812692669
error= 696 98.78085812692686
error= 697 98.78085812692669
error= 698 98.78085812692686
error= 699 98.78085812692669
error= 700 98.78085812692686
error= 701 98.78085812692669
error= 702 98.78085812692686
error= 703 98.78085812692669
error= 704 98.78085812692686
error= 705 98.78085812692669
error= 706 98.78085812692686
error= 707 98.78085812692669
error= 708 98.78085812692686
error= 709 98.78085812692669
error= 710 98.78085812692686
error= 711 98.78085812692669
error= 712 98.78085812692686
error= 713 98.78085812692669
error= 714 98.78085812692686
error= 715 98.78085812692669
error= 716 98.78085812692686
error= 717 98.78085812692669
error= 718 98.78085812692686
error= 719 98.78085812692669
error= 720 98.78085812692686
error= 721 98.78085812692669
error= 722 98.78085812692686
error= 723 98.78085812692669
error= 724 98.78085812692686
error= 725 98.78085812692669
error= 726 98.78085812692686
error= 727 98.78085812692669
error= 728 98.78085812692686
error= 729 98.78085812692669
error= 730 98.78085812692686
error= 731 98.78085812692669
error= 732 98.78085812692686
error= 733 98.78085812692669
error= 734 98.78085812692686
error= 735 98.78085812692669
error= 736 98.78085812692686
error= 737 98.78085812692669
error= 738 98.78085812692686
error= 739 98.78085812692669
error= 740 98.78085812692686
error= 741 98.78085812692669
error= 742 98.78085812692686
error= 743 98.78085812692669
error= 744 98.78085812692686
error= 745 98.78085812692669
error= 746 98.78085812692686
error= 747 98.78085812692669
error= 748 98.78085812692686
error= 749 98.78085812692669
error= 750 98.78085812692686
error= 751 98.78085812692669
error= 752 98.78085812692686
error= 753 98.78085812692669
error= 754 98.78085812692686
error= 755 98.78085812692669
error= 756 98.78085812692686
error= 757 98.78085812692669
error= 758 98.78085812692686
error= 759 98.78085812692669
error= 760 98.78085812692686
error= 761 98.78085812692669
error= 762 98.78085812692686
error= 763 98.78085812692669
error= 764 98.78085812692686
error= 765 98.78085812692669
error= 766 98.78085812692686
error= 767 98.78085812692669
error= 768 98.78085812692686
error= 769 98.78085812692669
error= 770 98.78085812692686
error= 771 98.78085812692669
error= 772 98.78085812692686
error= 773 98.78085812692669
error= 774 98.78085812692686
error= 775 98.78085812692669
error= 776 98.78085812692686
error= 777 98.78085812692669
error= 778 98.78085812692686
error= 779 98.78085812692669
error= 780 98.78085812692686
error= 781 98.78085812692669
error= 782 98.78085812692686
error= 783 98.78085812692669
error= 784 98.78085812692686
error= 785 98.78085812692669
error= 786 98.78085812692686
error= 787 98.78085812692669
error= 788 98.78085812692686
error= 789 98.78085812692669
error= 790 98.78085812692686
error= 791 98.78085812692669
error= 792 98.78085812692686
error= 793 98.78085812692669
error= 794 98.78085812692686
error= 795 98.78085812692669
error= 796 98.78085812692686
error= 797 98.78085812692669
error= 798 98.78085812692686
error= 799 98.78085812692669
error= 800 98.78085812692686
error= 801 98.78085812692669
error= 802 98.78085812692686
error= 803 98.78085812692669
error= 804 98.78085812692686
error= 805 98.78085812692669
error= 806 98.78085812692686
error= 807 98.78085812692669
error= 808 98.78085812692686
error= 809 98.78085812692669
error= 810 98.78085812692686
error= 811 98.78085812692669
error= 812 98.78085812692686
error= 813 98.78085812692669
error= 814 98.78085812692686
error= 815 98.78085812692669
error= 816 98.78085812692686
error= 817 98.78085812692669
error= 818 98.78085812692686
error= 819 98.78085812692669
error= 820 98.78085812692686
error= 821 98.78085812692669
error= 822 98.78085812692686
error= 823 98.78085812692669
error= 824 98.78085812692686
error= 825 98.78085812692669
error= 826 98.78085812692686
error= 827 98.78085812692669
error= 828 98.78085812692686
error= 829 98.78085812692669
error= 830 98.78085812692686
error= 831 98.78085812692669
error= 832 98.78085812692686
error= 833 98.78085812692669
error= 834 98.78085812692686
error= 835 98.78085812692669
error= 836 98.78085812692686
error= 837 98.78085812692669
error= 838 98.78085812692686
error= 839 98.78085812692669
error= 840 98.78085812692686
error= 841 98.78085812692669
error= 842 98.78085812692686
error= 843 98.78085812692669
error= 844 98.78085812692686
error= 845 98.78085812692669
error= 846 98.78085812692686
error= 847 98.78085812692669
error= 848 98.78085812692686
error= 849 98.78085812692669
error= 850 98.78085812692686
error= 851 98.78085812692669
error= 852 98.78085812692686
error= 853 98.78085812692669
error= 854 98.78085812692686
error= 855 98.78085812692669
error= 856 98.78085812692686
error= 857 98.78085812692669
error= 858 98.78085812692686
error= 859 98.78085812692669
error= 860 98.78085812692686
error= 861 98.78085812692669
error= 862 98.78085812692686
error= 863 98.78085812692669
error= 864 98.78085812692686
error= 865 98.78085812692669
error= 866 98.78085812692686
error= 867 98.78085812692669
error= 868 98.78085812692686
error= 869 98.78085812692669
error= 870 98.78085812692686
error= 871 98.78085812692669
error= 872 98.78085812692686
error= 873 98.78085812692669
error= 874 98.78085812692686
error= 875 98.78085812692669
error= 876 98.78085812692686
error= 877 98.78085812692669
error= 878 98.78085812692686
error= 879 98.78085812692669
error= 880 98.78085812692686
error= 881 98.78085812692669
error= 882 98.78085812692686
error= 883 98.78085812692669
error= 884 98.78085812692686
error= 885 98.78085812692669
error= 886 98.78085812692686
error= 887 98.78085812692669
error= 888 98.78085812692686
error= 889 98.78085812692669
error= 890 98.78085812692686
error= 891 98.78085812692669
error= 892 98.78085812692686
error= 893 98.78085812692669
error= 894 98.78085812692686
error= 895 98.78085812692669
error= 896 98.78085812692686
error= 897 98.78085812692669
error= 898 98.78085812692686
error= 899 98.78085812692669
error= 900 98.78085812692686
error= 901 98.78085812692669
error= 902 98.78085812692686
error= 903 98.78085812692669
error= 904 98.78085812692686
error= 905 98.78085812692669
error= 906 98.78085812692686
error= 907 98.78085812692669
error= 908 98.78085812692686
error= 909 98.78085812692669
error= 910 98.78085812692686
error= 911 98.78085812692669
error= 912 98.78085812692686
error= 913 98.78085812692669
error= 914 98.78085812692686
error= 915 98.78085812692669
error= 916 98.78085812692686
error= 917 98.78085812692669
error= 918 98.78085812692686
error= 919 98.78085812692669
error= 920 98.78085812692686
error= 921 98.78085812692669
error= 922 98.78085812692686
error= 923 98.78085812692669
error= 924 98.78085812692686
error= 925 98.78085812692669
error= 926 98.78085812692686
error= 927 98.78085812692669
error= 928 98.78085812692686
error= 929 98.78085812692669
error= 930 98.78085812692686
error= 931 98.78085812692669
error= 932 98.78085812692686
error= 933 98.78085812692669
error= 934 98.78085812692686
error= 935 98.78085812692669
error= 936 98.78085812692686
error= 937 98.78085812692669
error= 938 98.78085812692686
error= 939 98.78085812692669
error= 940 98.78085812692686
error= 941 98.78085812692669
error= 942 98.78085812692686
error= 943 98.78085812692669
error= 944 98.78085812692686
error= 945 98.78085812692669
error= 946 98.78085812692686
error= 947 98.78085812692669
error= 948 98.78085812692686
error= 949 98.78085812692669
error= 950 98.78085812692686
error= 951 98.78085812692669
error= 952 98.78085812692686
error= 953 98.78085812692669
error= 954 98.78085812692686
error= 955 98.78085812692669
error= 956 98.78085812692686
error= 957 98.78085812692669
error= 958 98.78085812692686
error= 959 98.78085812692669
error= 960 98.78085812692686
error= 961 98.78085812692669
error= 962 98.78085812692686
error= 963 98.78085812692669
error= 964 98.78085812692686
error= 965 98.78085812692669
error= 966 98.78085812692686
error= 967 98.78085812692669
error= 968 98.78085812692686
error= 969 98.78085812692669
error= 970 98.78085812692686
error= 971 98.78085812692669
error= 972 98.78085812692686
error= 973 98.78085812692669
error= 974 98.78085812692686
error= 975 98.78085812692669
error= 976 98.78085812692686
error= 977 98.78085812692669
error= 978 98.78085812692686
error= 979 98.78085812692669
error= 980 98.78085812692686
error= 981 98.78085812692669
error= 982 98.78085812692686
error= 983 98.78085812692669
error= 984 98.78085812692686
error= 985 98.78085812692669
error= 986 98.78085812692686
error= 987 98.78085812692669
error= 988 98.78085812692686
error= 989 98.78085812692669
error= 990 98.78085812692686
error= 991 98.78085812692669
error= 992 98.78085812692686
error= 993 98.78085812692669
error= 994 98.78085812692686
error= 995 98.78085812692669
error= 996 98.78085812692686
error= 997 98.78085812692669
error= 998 98.78085812692686
error= 999 98.78085812692669
cust_df["weight"] = weight
cust_df.to_csv(folder + "melos-gf.csv")

連続施設配置の可視化関数

引数:

  • cust_df : 顧客データフレーム
  • X : 施設の緯度のリスト
  • Y : 施設の経度のリスト
  • partition : 顧客の割り当てられた施設の番号を格納したリスト

返値:

  • fig: Plotlyの図オブジェクト

show_optimized_continuous_network[source]

show_optimized_continuous_network(cust_df, X, Y, partition)

連続施設配置の可視化関数

fig = show_optimized_continuous_network(cust_df, X, Y, partition)
#fig.show()
Image("../figure/weiszfeld.png")

インスタンス生成

日本の郵便番号データの読み込み

read_data[source]

read_data(filename='../data/zipcode.csv')

ランダムに地点をサンプリング

sample_locations[source]

sample_locations(df, n_locations, rnd_stat)

インスタンスを1つ生成する関数 mk_instance

mk_instance[source]

mk_instance(df, n_plants, n_dcs, n_custs, n_prods, seed)

複数のインスタンスを生成するジェネレータ関数 make_instances

mk_instances[source]

mk_instances()

インスタンス生成のテスト

class TestInstances(unittest.TestCase):
    def test_one(self):
        df = read_data()
        for n in [10, 100, 1000]:
            print(f"testing location sample, n:{n}")
            for seed in range(1,11):
                print(f"instance {n}:{seed}")
                (province, town, address, latitude, longitude) = sample_locations(df, n, seed)
                nout = 0
                for i in province:
                    print(i, latitude[i], longitude[i], town[i])
                    nout += 1
                    if nout >= 3:
                        print("...")
                        break

    def test_two(self):
        for (weight, cust, plnt, dc, dc_lb, dc_ub, demand, plnt_ub, name) in mk_instances():
            for dic in [cust, plnt, dc]:
                nout = 0
                for i in dic:
                    print(i, dic[i], name[i])
                    nout += 1
                    if nout >= 3:
                        print("...\n")
                        break
test = TestInstances()
#test.test_one()
#test.test_two()

lnd

  • lnd: Gurobi models for logistic network design

There are two models:

  • lnd_ms, for multiple-source supply

  • lnd_ss, for single-source supply

The aim is to select a predefined number of places for implementing a distribution center. Data are:

  • customer locations

  • potential distribution center locations

  • plant locations

  • demand, bounds and costs

複数ソース問題

lnd_ms(weight, cust, dc, dc_lb, dc_ub, plnt, plnt_ub, demand, tp_cost, del_cost, dc_fc, dc_vc, dc_num)[source] Logistics network design, multiple source

Gurobi model for multiple-source LND

Return type object of class Model, as defined in gurobipy

Weight weight[p] -> unit weight for product p

Cust dict associating a customer id to its location as (latitute, longitude)

Dc dict associating a distribution center id to its (latitute, longitude)

Dc_lb dc_lb[k] -> lower bound for distribution center k [not used]

Dc_ub dc_ub[k] -> upper bound for distribution center k

Plnt dict associating a plant id to its (latitute, longitude)

Plnt_ub plnt_ub[k] -> upper bound for plant k

Demand demand[k,p] -> units of p demanded by customer k

Tp_cost unit transportation cost (from the plant)

Del_cost unit delivery cost (from a dc)

Dc_fc fixed cost for opening a dc

Dc_vc unit (variable) cost for operating a dc

Dc_num (maximum) number of distribution centers to open

lnd_ms[source]

lnd_ms(weight, cust, dc, dc_lb, dc_ub, plnt, plnt_ub, demand, tp_cost, del_cost, dc_fc, dc_vc, dc_num)

Logistics network design, multiple source

Gurobi model for multiple-source LND

:rtype: object of class Model, as defined in gurobipy :weight: weight[p] -> unit weight for product p :cust: dict associating a customer id to its location as (latitute, longitude) :dc: dict associating a distribution center id to its (latitute, longitude) :dc_lb: dc_lb[k] -> lower bound for distribution center k [not used] :dc_ub: dc_ub[k] -> upper bound for distribution center k :plnt: dict associating a plant id to its (latitute, longitude) :plnt_ub: plnt_ub[k,p] -> upper bound for plant k for p :demand: demand[k,p] -> units of p demanded by customer k :tp_cost: tp_cost[i,j] -> unit transportation cost from plant i to dc j :del_cost: tp_cost[i,j] -> unit delivery cost from dc i to customer j :dc_fc: fixed cost for opening a dc :dc_vc: unit (variable) cost for operating a dc :dc_num: (maximum) number of distribution centers to open

単一ソース問題

lnd_ss(weight, cust, dc, dc_lb, dc_ub, plnt, plnt_ub, demand, tp_cost, del_cost, dc_fc, dc_vc, dc_num)[source] Logistics network design, single source

Gurobi model for single-source LND

Return type object of class Model, as defined in gurobipy

Weight weight[p] -> unit weight for product p

Cust dict associating a customer id to its location as (latitute, longitude)

Dc dict associating a distribution center id to its (latitute, longitude)

Dc_lb dc_lb[k] -> lower bound for distribution center k [not used]

Dc_ub dc_ub[k] -> upper bound for distribution center k

Plnt dict associating a plant id to its (latitute, longitude)

Plnt_ub plnt_ub[k] -> upper bound for plant k

Demand demand[k,p] -> units of p demanded by customer k

Tp_cost unit transportation cost (from the plant)

Del_cost unit delivery cost (from a dc)

Dc_fc fixed cost for opening a dc

Dc_vc unit (variable) cost for operating a dc

Dc_num (maximum) number of distribution centers to open

lnd_ss[source]

lnd_ss(weight, cust, dc, dc_lb, dc_ub, plnt, plnt_ub, demand, tp_cost, del_cost, dc_fc, dc_vc, dc_num)

Logistics network design, single source

Gurobi model for single-source LND

:rtype: object of class Model, as defined in gurobipy :weight: weight[p] -> unit weight for product p :cust: dict associating a customer id to its location as (latitute, longitude) :dc: dict associating a distribution center id to its (latitute, longitude) :dc_lb: dc_lb[k] -> lower bound for distribution center k [not used] :dc_ub: dc_ub[k] -> upper bound for distribution center k :plnt: dict associating a plant id to its (latitute, longitude) :plnt_ub: plnt_ub[k] -> upper bound for plant k :demand: demand[k,p] -> units of p demanded by customer k :tp_cost: tp_cost[i,j] -> unit transportation cost from plant i to dc j :del_cost: tp_cost[i,j] -> unit delivery cost from dc i to customer j :dc_fc: fixed cost for opening a dc :dc_vc: unit (variable) cost for operating a dc :dc_num: (maximum) number of distribution centers to open

lnd_ss_modified[source]

lnd_ss_modified(weight, cust, dc, dc_lb, dc_ub, plnt, plnt_ub, demand, tp_cost, del_cost, dc_fc, dc_vc, dc_num)

Logistics network design, single source

del_cost and tp_cost may not be full! just modify the constraint!

Gurobi model for single-source LND

:rtype: object of class Model, as defined in gurobipy :weight: weight[p] -> unit weight for product p :cust: dict associating a customer id to its location as (latitute, longitude) :dc: dict associating a distribution center id to its (latitute, longitude) :dc_lb: dc_lb[k] -> lower bound for distribution center k [not used] :dc_ub: dc_ub[k] -> upper bound for distribution center k :plnt: dict associating a plant id to its (latitute, longitude) :plnt_ub: plnt_ub[k] -> upper bound for plant k :demand: demand[k,p] -> units of p demanded by customer k :tp_cost: tp_cost[i,j] -> unit transportation cost from plant i to dc j :del_cost: tp_cost[i,j] -> unit delivery cost from dc i to customer j :dc_fc: fixed cost for opening a dc :dc_vc: unit (variable) cost for operating a dc :dc_num: (maximum) number of distribution centers to open

費用生成のための関数

mk_costs[source]

mk_costs(plnt, dc, cust)

Instantiate costs to a given set of plants, dc's and customers

To be adpted to more realistic settings

:rtype: tuple with transportation costs :plnt: dict associating a plant id to its (latitute, longitude) :dc: dict associating a distribution center id to its (latitute, longitude)

最適化のテスト関数

class TestSolving(unittest.TestCase):
    def test_one(self):
        """
        Test optimizing the location of a small number of dc's from set of candidates
        """
        TIME_LIM = 300 # allow gurobi to use 5 minutes
        import time
        from mk_instances import mk_instances
        from clustering import preclustering

        models = {
            "multiple source":lnd_ms,
            "single source":lnd_ss
            }

        for k in models:
            for (weight, cust, plnt, dc, dc_lb, dc_ub, demand, plnt_ub, name) in mk_instances():
                print(f"* using {k} model *")
                print(f"*** new instance, {len(plnt)} plants + {len(dc)} dc's + {len(cust)} customers ***")
                start = time.process_time()
                (tp_cost, del_cost, dc_fc, dc_vc) = mk_costs(plnt, dc, cust)
                dc_num = (20 + len(dc))//10
             
                model = models[k](weight, cust, dc, dc_lb, dc_ub, plnt, plnt_ub, 
                                  demand, tp_cost, del_cost, dc_fc, dc_vc, dc_num)
                # model.write("lnd_ss.lp")
                model.setParam('TimeLimit', TIME_LIM)
                model.optimize()
             
                EPS = 1.e-6
                for x in model.getVars():
                    if x.X > EPS:
                        print(x.varName, x.X)
             
                end = time.process_time()
                print(f"solving MIP used {end-start} seconds")
                print()

clustering

Use scikit-learn models for clustering a set of distribution centers.

The aim is to select a predefined number of candidates for implementing a distribution center. Data are:

number of candidates to select

customer locations

potential distribution center locations

plant locations

See TestSolving below for examples of usage.

preclustering(cust, dc, prods, demand, n_clusters)

Clustering as a predecessor for optimization, to be used in logistics network design

Return type list of selected dc’s (a subset of dc)

Cust dict associating a customer id to its location as (latitute, longitude)

Dc dict associating a distribution center id to its (latitute, longitude)

Prods list (set) of products

Demand demand[k,p] -> units of p demanded by customer k

N_clusters number of clusters to use

preclustering[source]

preclustering(cust, dc, prods, demand, n_clusters)

Clustering as a predecessor for optimization, to be used in logistics network design

:rtype: list of selected dc's (a subset of dc) :cust: dict associating a customer id to its location as (latitute, longitude) :dc: dict associating a distribution center id to its (latitute, longitude) :prods: list (set) of products :demand: demand[k,p] -> units of p demanded by customer k :n_clusters: number of clusters to use

クラスタリングのテスト

class TestClustering(unittest.TestCase):
    def test_one(self):
        """
        Test optimizing the location of a small number of dc's from set of candidates
        """
        from mk_instances import mk_instances
        import time
        for (weight, cust, plnt, dc, dc_lb, dc_ub, demand, plnt_ub, name) in mk_instances():
            start = time.process_time()
            prods = weight.keys()
            n_clusters = (10 + len(dc))//5
            cluster_dc = preclustering(cust, dc, prods, demand, n_clusters)
            end = time.process_time()
            print("clustered dc's, used {} seconds".format(end-start))
            print("selected", len(cluster_dc), "dc's out of", len(dc.keys()), "possible positions")

クラスタリング後にソルバーで解を求めるテスト

class TestClusteringAndSolving(unittest.TestCase):
    def test_one(self):
        """
        Test clustering a set of potential dc's, then optimizing the location of a small number of them
        """
        TIME_LIM = 300 # allow gurobi to use 5 minutes
        import time
        from mk_instances import mk_instances
        from clustering import preclustering

        models = {
            "multiple source":lnd_ms,
            "single source":lnd_ss
            }

        for (weight, cust, plnt, dc, dc_lb, dc_ub, demand, plnt_ub, name) in mk_instances():
            # prepare costs for optimization part
            (tp_cost, del_cost, dc_fc, dc_vc) = mk_costs(plnt, dc, cust)

            # clustering part
            prods = weight.keys()
            n_clusters = (10 + len(dc))//5
            cluster_dc = preclustering(cust, dc, prods, demand, n_clusters)

            # optimization part
            start = time.process_time()
            dc_num = (90 + len(cluster_dc))//50
         
            for k in models:
                print(f"*** new instance, {len(plnt)} plants + {len(dc)} dc's + {len(cust)} customers ***")
                print(f"***** dc's clustered into {len(cluster_dc)} groups, for choosing {dc_num} dc's")
                print(f"* using {k} model *")
                model = models[k](weight, cust, cluster_dc, dc_lb, dc_ub, plnt, plnt_ub,
                                  demand, tp_cost, del_cost, dc_fc, dc_vc, dc_num)
                model.setParam('TimeLimit', TIME_LIM)
                model.optimize()
                # model.write("lnd.lp")
             
                EPS = 1.e-6
                for x in model.getVars():
                    if x.X > EPS:
                        print(x.varName, x.X)
             
                end = time.process_time()
                print(f"solving MIP used {end-start} seconds")
                print()