1. 서 론

기업들은 기업 내의 경영 및 물류효율화를 통한 비용절감이 실효를 거둠에 따라 기업외부로 눈을 돌려 여러 기업을 아우르는 통합된 공급사슬관리(Supply Chain Management)를 통한 비용절감에 관심을 가지게 되었다. 본 연구에서도 하나의 스토어 내의 효율적인 재고관리를 통한 비용절감이 아니라 여러 개 스토어들의 재고를 통합하여 관리하는 중앙창고를 세워 비용절감을 꾀하는 방안에 대해 알아보았다.

특히 본 연구에서는 다품종과 예산(budget)의 제약이 있는 경우 재고관련비용과 운송비용을 고려하여 적정한 수의 중앙창고들을 적정한 장소에 배치하는 중앙창고입지선정문제에 관심을 두었다. 중앙창고입지선정문제란 여러 곳의 스토어와 그 스토어들에 제품을 공급하는 중앙창고로 이루어지는 공급사슬에서 각 중앙창고는 연속적재고조사정책(continuous review policy)을 따를 때 비용을 최소화하는 최적의 중앙창고 개수와 어느 중앙창고가 어느 스토어들에게 제품을 공급할 지를 정하는 문제이다. 연속적 재고조사정책인 (Q, r)재고 모형은 재고수준을 항상 알 수 있고 제품 수요가 불확실한 경우, 재고가 재주문점인 r 이하가 되면, Q만큼 주문하는 것이다[6].

중앙창고 입지 선정문제는 연속적 재고 문제와 설비위치결정 문제를 포괄하는 문제이다. 먼저 연속적 재고 조사 정책에 대한 연구를 살펴보면, Das[1]는 단품종 연속적 재고 모형에서 Q와 r을 반복적으로 풀지 않고 추정하는 방법을 제안하였다. Lee et al.[9]과 Ghalebsaz-Jeddi et al.[2]은 (Q, r) 재고모형에 예산제약(budget constraint)이라는 하나의 제약식이 있는 문제에 대해 연구하고, 반복없이 Q와 r을 구하는 추정을 통한 해법과 Hadley Whitin 기법(HW)을 이용한 최적해를 찾는 해법을 제안하였다. Hariga[4]는 단품종 연속적 재고 관리 문제에서 창고 크기에 제약이 있는 경우의 최적해를 푸는 기법과 EOQ에 기반한 기법을 제시하였다. Tajbakhsh[12]는 단일 창고를 가진 연속적 재고 관리 문제에 충족률(fill rate)이 제약식으로 있는 경우에 수요의 분포가 일반적으로 고려하는 정규분포가 아닌 어떠한 분포라도 풀 수 있는 분포와 무관한 해법(Distribution Free Approach)을 제시하였다.

Pasandideh[10]는 2단계를 가진 공급사슬에서 각 단계는 연속적 재고 관리 모형을 가지고 예산의 제약이 있는 문제에 대해 유전자 알고리듬(Genetic Algorithm)을 이용한 해법을 제시하였다. Purnomo et al.[11]은 보유재고량(on hand inventory), 리드타임동안의 수요를 감당하기 위한 재고량, 연속적 재고 모형과 주기적 재고 모형 등을 고려한 하모니 검색(Harmony Search)을 이용한 해법을 제안하였다. 하모니 검색 알고리듬은 음악연주자의 실력이 향상되게 하여 결국 하모니를 만들어 내는데 착안한 휴리스틱 기법이다. 살펴본 연구들은 Q와 r의 최적화를 통한 비용최소화를 꾀했는데, 본 연구에서는 Q와 r의 최적화 뿐 아니라 중앙창고의 위치도 선정해야 하므로 이들의 연구와는 차이가 있다.

한편, 설비위치결정문제에 대한 연구들을 살펴보면, Holmberg[5]는 운송비가 convex 함수인 경우의 설비위치결정문제를 Benders decomposition과 Dual ascent기법을 이용한 최적해를 찾는 기법을 제시하였다. Hackness[3]는 생산비가 convex 함수인 경우의 설비위치결정문제를 분지한계법(Branch and Bound)을 이용한 해법을 제시하였다.

Lee et al.[8]은 단품종을 고려한 중앙창고입지선정문제에 대한 시뮬레이티드 어닐링(Simulated Annealing)기법을 제안하고 이를 전체나열법(total enumeration)으로 구한 최적해와 비교하여 우수성을 입증하였다. 이들 연구에서는 단품종을 고려하였으며 중앙창고의 예산의 제약을 고려치 않았다. 본 연구에서는 좀 더 실제적인 경우를 고려하기 위해 다품종이며 중앙창고에 예산의 제약이 있는 경우를 고려하였다. 본 연구는 이 문제에 대한 최초의 연구로 그 의의가 있으며, 본 연구를 통해 다양한 제품을 공급하는 용량제약이 있는 중앙창고를 어디에 몇 개를 설치해야 하며 이때의 Q와 r은 얼마인지 구하는 해법을 제시하려 한다.

제 2장에서는 본 논문에서 고려한 문제의 수학모형을 설명하고, 제 3장에서는 Q와 r을 반복 없이 추정하는 해법을 살펴보고 이를 이용한 SA를 적용한 해법을 제시한다. 제 4장에서는 예제를 통해 제안된 해법의 성능을 살펴보았다. 제 5장에서는 결론과 미래연구에 대해 알아보았다.

2. 수학모형

특정 중앙창고에서 제품을 공급하는 스토어들의 모임을 연합(coalition)이라고 정의하고 다음의 가정을 가진다. 먼저 중앙창고의 위치는 미리 정해져 있지 않고, 기존의 스토어의 위치 중 연간평균총비용을 최소로 하는 곳으로 정한다. 또한, 스토어들은 그 스토어를 담당하는 하나의 중앙창고로부터 모든 제품을 공급받고, 각 스토어들과 연합들은 연속적 재고조사정책을 따른다. 각 연합들의 중앙창고는 각 제품에 대해 동일한 주문비용(setup cost) A, 재고유지비용(holding cost) h, 유실판매 벌과 비용(penalty cost) p를 가진다.

본 연구에서 다루는 문제의 기호와 수학모형을 소개하면 다음과 같다.

기호

Ak : 제품 k의 고정 발주비

hk : 제품 k의 연간 단위당 재고유지비

pk : 제품 k의 연간 단위당 벌과비용

Ck : 제품 k의 단위당 가격

W : 중앙창고의 예산

Z : 표준정규분포의 확률변수 N(0, 1)

N : 스토어 수

U : 전체 스토어들의 집합, {1, 2, 3, …, N}

S : 전체 연합의 집합

sj : 중앙창고 j에서 제품을 공급받는 스토어들의 집합

dij : 중앙창고 j로부터 스토어 i로의 운송거리, 단 dii=0.

uk : 제품 k의 하물당 km당 운송비

tijk = ukdij : 제품 k에 대해 중앙창고 j로부터 스토어 i로의 운송비

Dik : 스토어 i에서 제품 k의 연간 기대수요

Djk : 스토어 i∈sj에 제품을 공급하는 중앙창고 j에서 제품 k의 연간 기대 수,

μik, σik : 선행기간(lead time) 동안의 스토어 i의 제품 k에 대한 수요의 평균과 표준편차.

μjk, σjk : 스토어 i∈sj에 제품을 공급하는 중앙창고 j에서 제품 k에 대한 선행기간동안의 수요의 평균과 표준편차,

Vjk : 평균이 μjk이고 표준편차가 σjk인 중앙창고 j에서 제품 k에 대한 선행기간동안의 총 수요에 대한 확률변수.

Ljk(rjk) : 스토어 i∈sj에 제품을 공급하는 중앙창고 j에서 제품 k에 대한 주기말의 기대부족수요,

단, (Vjk-rjk)+=max[0, Vjk-rjk]이며 gjk(vjk)는 리드타임동안의 중앙창고 j에서 제품 k의 수요의 확률밀도함수이다.

의사결정변수

Qjk : 중앙창고 j에서 제품 k에 대한 주문량, Q :={Qjk:∀j, ∀k}

rjk : 중앙창고 j에서 제품 k에 대한 재주문점. R :={rjk:∀j, ∀k}

xij : 스토어 i가 중앙창고 j에서 모든 제품을 공급받으면 1 아니면 0, X :={xi:∀i, ∀j}

yj : 중앙창고 j에 스토어가 할당되면 1 아니면 0, Y :={yj:∀j}

본 연구에서 고려한 비용은 중앙창고 j를 대상으로 한 경우 다음과 같다.

연간 주문비 :

연간재고유지비 :

연간유실판매벌과비 :

운송비 :

이들 비용을 목적식으로 하며 예산의 제약을 가진 다품종 중앙창고입지선정 문제의 수학 모형(F1)은 다음과 같다.

subject to

식 (1)은 목적식으로 재고관련 비용과 운송비용의 최소화이다. 식 (2)는 주문품을 수령할 때 비용을 지불하는 경우 중앙창고 j에서 보유한 모든 제품의 총가격이 예산(W)이내에 있을 확률이 γ보다 크게 하는 제약식이다. 여기서 P(·)는 확률이다. Ck를 제품 k의 크기라 하고, W를 창고의 크기라 한다면 이 제약식으로 창고의 용량제약이 있는 경우를 나타낼 수도 있다.

식 (3)은 중앙창고 창고 j가 사용되지 않으면 스토어들은 창고 j로부터 제품을 받을 수 없도록 한다. 식 (4)는 각 스토어는 하나의 창고로부터 제품을 받을 수 있도록 한다. 식 (5)~식 (7)은 의사결정변수가 이진정수 혹은 비음(non- negative)임을 나타낸다. F1은 현재 상태로는 풀 수가 없다. 왜냐하면, Qjk와 rjk의 값이 구해지지 않았고 기대부족수요를 구하기 위해서는 정규분포의 기댓값을 구해야 하기 때문이다.

Lee et al.[8]은 F1에서 제약식 (2)가 없고 단품종인 경우를 풀 수 있는 SA(Simulated Annealing)기법을 제시하였다. 또한, Ghalebsaz-Jeddi et al.[2]과 Lee et al.[8]은 식 (1)을 목적식으로 하고 식 (2)와 식 (7)을 제약식으로 하는 하나의 창고 혹은 스토어가 있는 문제를 풀 수 있는 기법을 제시하였다. 본 논문에서는 이 논문들에서 제시한 기법들을 이용하여 2가지의 해법을 개발하고자 한다.

3. 제안된 알고리듬

3.1 Subproblem과 2가지 해법들

수학 모형 F1에서 오픈할 중앙창고(j)와 그 중앙창고가 담당할 스토어(i)가 정해져 있다고 하고, 첨자 i와 j를 이번 절에서는 생략하고자 한다. 이때의 운송비용은 Qk와 rk의 결정에 영향을 미치지 않으므로 제외할 수 있다. 이 문제는 예산의 제약이 있는 연속적 재고관리문제와 동일한데, 즉, 오픈할 중앙창고 j의 비용을 최소화 하는 Qk와 rk를 구하는 Subproblem은 다음과 같다.

Subproblem (S1)

subject to 첨자 j를 생략한 식 (2)와 식 (7)

이라고 할 때 Y~N 이다. 식 (2)는 다음과 같이 나타낼 수 있다.

위 수학 모형(S1)은 비선형계획법 문제로 라그랑쥐함수를 도입하면 다음과 같다.

위 라그랑쥐함수를 Qk, rk, λ에 대해 각각 편미분하고 0으로 두고 풀면

여기서, F(·)는 누적정규분포이다.

식 (11)에서

이라 두면 Qk, rk는 λ에 영향을 받으므로 g(λ)라 둘 수 있다. 만약 g(λ) > 0이면 제약식 (2)를 위반하고 g(λ) < 0이면 제약식 (2)를 만족한다.

따라서, 수학모형(S1)의 최적해는 식 (9)~식 (11)을 동시에 만족하는 변수 Qk, rk, λ를 구하면 된다. 하지만 세 식에 Qk, rk, λ가 모두 있으므로, 세 식을 만족하는 Qk, rk, λ를 구하기가 간단하지 않다. 즉, Qk, rk, λ가 모두 수렴할 때까지 세 식을 반복적으로 풀어주어야 한다. 이러한 문제를 푸는 대표적인 해법으로는 Hadley and Whitin(HW) 해법과 Lee et al.[9]이 제시한 해법이 있다.

Hadley and Whitin의 해법(HW)

단계 1 : g(λ1)>0이고 g(λ2)<0인 λ1, λ2≥0를 구한다.

단계 2 : λ =λ1일 때 , λ=λ2일 때 를 구한다. 식 (9)와 식 (10)을 동시에 만족할 때까지 반복적으로 풀어 와 를 각각 구한다.

단계 3 : λ3 = (λ1+λ2)/2라고 할 때 식 (9)와 식 (10)을 반복적으로 풀어 를 구한다. 만약 g(λ3) > 0이면 λ1=λ3, 이다. 만약 g(λ3) < 0이면 λ2=λ3, 이다.

단계 4 : ε은 임의로 정한 작은 수라고 할 때, g(λ1)-g(λ2) <ε이면 종료한다. 아니면 단계 3으로 돌아간다.

HW 해법은 반복적이고 복잡한 계산이 필요하므로 Lee et al.[9]은 다음과 같은 추정 해법을 제시하였다.

G(z)=1-F(z)라할 때 Das[1]는 L(z)를 G(z)에 대한 2차 식으로 추정하였다.

여기서 a = 0.79838, b = 0.39694, c = -0.0000044이다.

식 (10)을 식 (9)에 대입하고 식 (12)를 이용하면 다음의 식을 구할 수 있다.

여기서

이다.

G(z)를 이용하여 z를 다음과 같이 추정할 수 있다.

G(z) > 0.0132일 때

0.0014 ≤ G(z) ≤ 0.0132일 때에는 G(2.2) = 0.0132, G(2.6) = 0.0047, G(3.0) = 0.0014를 이용하여 보간법으로 z를 구하고, G(z) < 0.0014일 때에는 z = 3.0으로 둔다.

Lee et al.[9]이 제안한 추정 해법은 다음과 같다.

단계 2 : λ=λ1일 때 , λ=λ2일 때 를 구한다. 식 (13)을 이용하여 G(z)를 구한다. G(z)를 이용하여 위에서 소개한 방법으로 z를 추정한다. 와 식 (9)를 이용하여 와 를 각각 구한다.

단계 1, 3, 4는 HW와 동일하다.

3.2 SA 해법

SA는 Kirkpatrick et al.[7]이 제시한 메타휴리스틱 기법으로 “uphill move”라는 개념을 도입하여 목적함수를 증진시키지 못하는 해에 대하여도 교체 확률 함수 하에 받아들이므로 국부최적해(local optimal)을 극복하여 전체최적해(globlal optimal)를 탐색해 가는 기법이다. SA 기법에 제 3.1절에서 알아본 중앙창고에 예산의 제약이 있는 문제(S1)에서 Q와 r을 구하는 두 가지해법을 도입한 SA 기법은 다음과 같다.

단계 1 : (초기화) 초기온도 T0와 최종온도 Tf를 정한다. 초기해 s를 구하고 그에 따른 초기해의 비용 C(s)를 HW나 추정해법을 이용하여 구한다. iter=0, best=x, Cbest=C(x)으로 정한다.

단계 2 : (1) (이동) 현재의 해에서 임의의 스토어 j를 선택한다. 현재 오픈된 중앙창고의 수를 no_ware라고 할 때, j가 속하지 않은 중앙창고 중 CWm(1≤ m≤no_ware+1)를 임의로 선택하였을 때 k= no_ware +1이면 새로운 중앙창고 CWno_ware+1= {j} open하고 아니면 CWm에 j를 추가한다. 이러한 이동에 의해 얻어진 새로운 해를 y로 정한다. HW나 추정해법을 이용하여 각 중앙창고의 Qk, rk와 수학모형 F1의 목적식 값 C(y)를 계산한다.

(2) (Metropolis 기준) △C = C(y)-C(s)를 계산하고, 이동을 수락 혹은 거절한다.

∙△C ≤ 0이고 C(y) < Cbest이면 이동을 수락하고, 최상의 해를 갱신한다. 즉, best = y, Cbest = C(y)으로 두고, x = y, C(x) = C(y)로 둔다. iter = 0으로 둔다.

∙△C ≤ 0이고 C(y) > = Cbest이면 이동을 수락한다. x = y, C(x) = C(y)로 둔다.

∙△C > 0이면, 확률 exp(-△C/Titer)으로 x = y, C(x)= C(y)로 둔다(uphill move). 아니면 이동을 거절한다. 즉, x = x로 둔다.

단계 3 : (종료조건) 만약 iter ≤ max_iter이고 Tf < Titer이면 iter=iter+1, Titer+1=α×Titer로 갱신하고 단계 2로 가고 아니면 종료한다.

4. 실험조건 및 결과

50개의 스토어가 있는 10개의 예제와 100개의 스토어가 있는 10개의 예제를 생성하였다. 모든 스토어는 3개의 제품을 취급하고 선행기간(lead time)은 모든 스토어들에 대해 3주이며 제품단위당 운송비는 50km에 $1로 간주하여 0.02$/km이다. 각 스토어의 창고와 중앙창고는 제품별 단위가격(Cj), 주문당 주문비용(Aj, setup cost), 제품단위당 재고유지비용(hj, holding cost), 유실판매 벌과비용(pj, penalty cost)을 가진다고 가정하였다. 물론 같은 제품인 경우에는 모든 스토어에 대해 이들 비용은 동일하다. 또한, 각 제품의 선행기간 동안의 수요의 평균 (μi)와 표준편차(σi)는 스토어와 제품에 따라 각각 다르다고 가정하였다. 각 데이터의 값들은 <Table 1>과 같이 일양분포(U, Uniform Distribution)를 이용하여 랜덤하게 생성하였다. 모든 창고들에 대해 W=400,000, γ=0.903, 즉 z1-γ=-1.3으로 하였다. 각 스토어간의 거리는 2차원 평면으로 가정하여 x축, y축 각각에 대해 U[0km, 50km]이다.

제안된 알고리듬은 ‘C 언어’로 구현되었으며 Intel Core i3(2.10GHz) CPU가 탑재된 PC로 실행되었다. SA에 쓰인 패러미터들의 값은 다음과 같다.

∙max_iter : 100,000

∙T0 : 초기온도. 5000(수락율이 90% 이상이 되도록 정함).

∙Tf : 최종온도 1,

∙α : 0.95

각 데이터별로 10번의 반복수행을 하여 총비용의 평균(Average)과 표준편차(S.D., Standard Deviation), 평균시간(Time), 평균호출횟수(Call Counts)를 구하였는데, <Table 2>와 <Table 3>에 주어져 있다. 평균호출횟수는 주문량(Qjk)과 재주문점(rjk)을 계산하기 위해 관련 함수를 호출한 총 횟수이다.

SA-Approx.는 SA 기법과 Lee 등이 제안한 추정기법을 사용한 경우로 반복 없이 주문량과 재주문점을 계산한다. 또한, SA-HW는 SA 기법과 HW 기법을 사용하는데 언급하였듯이 HW는 식 (9)와 식 (10)이 수렴할 때까지 반복한다. 스토어 수가 50개인 경우에는 6,636,013/2,938,932 = 2.26회의 평균 반복수를 가지며, 스토어 수가 100개인 경우에는 18,407,348/8,675,812 = 2.12회의 평균 반복수를 가진다. 즉, HW는 약 2회가 넘는 반복을 통해 주문량과 재주문점을 계산하는 것으로 나타났다.

총비용의 평균을 살펴보면, 스토어 수가 50개인 경우에는 데이터 3과 8을 제외하고는 모두 SA-HW가 나은 것으로 보이지만 큰 차이가 없는 것으로 보인다. 평균오차율 = [(SA-Approx.)-(SA-HW)]/(SA-HW) = 0.57%로 거의 차이가 없는 것으로 보인다. 스토어 수가 100개인 경우에는 모든 경우에 SA-HW가 나은 해를 보이지만 평균오차율이 1.12%로 역시 차이가 크지 않은 것으로 나타났다.

총비용의 표준편차는 스토어 수가 50개와 100개인 겨우 모두 SA-Approx.가 평균적으로 작게 나타났지만 거의 차이가 없는 것으로 보인다. 특히, 변동계수(CV, Coefficient of Variation)는 평균대비 표준편차의 비인데 스토어수가 50개인 경우 SA-Approx.와 SA-HW는 각각 0.0114, 0.0119이며 스토어 수가 100개인 경우에는 각각 0.0084, 0.0089로 나타나 아주 작은 것으로 나타났다. 즉, 제시한 두 알고리즘은 모두 안정적으로 해를 찾는 것으로 보인다.

계산시간(CPU time, 초)은 스토어 수가 50개인 경우와 100개인 경우 모두 SA-Approx.가 약 절반가까이 빠른 것으로 나타났다. 각 데이터별로 10번의 반복을 하였는데, 계산시간의 편차는 거의 없는 것으로 나타났다. 즉, 스토어수가 50개이며 SA-Approx.를 사용한 경우. 데이터 2는 9번의 반복에서는 6초, 1번은 7초였다.

5. 결론 및 미래연구

기존에는 단품종의 중앙창고입지선정 문제에 대한 해법에 대한 연구들이 있었고, 예산의 제약이 있는 다품종 연속적 재고 모형에 대한 연구들이 있었다. 본 연구는 다품종과 예산의 제약이 있는 경우의 중앙창고입지선정문제에 대한 최초의 연구로 그에 대한 해법을 제시한 데 의의가 있다고 하겠다. 본 연구에서 제시한 두 해법은 SA-HW와 SA-Approx. 인데 SA-HW는 주문량(Q)과 재주문점(r)을 계산하기 위해 Hadley-Whitin(HW) 기법을 적용한 SA알고리듬이며, SA-Approx.는 반복 없이 추정을 통해 Q와 r을 계산하는 Lee 등이 제안한 기법을 SA에 적용한 것이다. 본 연구의 실험을 통해 살펴본 제안한 두 SA 해법의 결과를 요약하며 다음과 같다.

∙SA-HW는 약 2회가 넘는 반복을 통해 Q와 r을 계산하는 것으로 나타났다.

∙계산시간도 SA-HW는 SA-Approx.보다 약 2배 정도 시간이 더 걸리는 것으로 나타났다.

∙SA-HW가 SA-Approx.보다 약간 나은 결과를 보이나 1% 남짓의 총비용의 차이로 그 차이는 거의 없는 것으로 보인다.

∙SA-HW와 SA-Approx.는 총비용의 표준편차가 거의 없는 것으로 나타나 안정적으로 해를 찾는 기법으로 보인다.

본 연구에서는 고려한 문제는 결정해야할 변수가 중앙창고들의 위치, 중앙창고별 주문량(Q), 중앙창고별 재주문점(r) 등 많은 복잡한 문제로 좀 더 효율적인 해법에 대한 앞으로의 연구가 필요하다. 또한, 트럭 용량의 제약이 있는 경우 등의 좀 더 현실적인 사항들을 고려한 문제들에 대한 연구가 필요하다.