Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.44 No.1 pp.26-36
DOI : https://doi.org/10.11627/jkise.2021.44.1.026

A Mixed-Integer Programming Model for Effective Distribution of Relief Supplies in Disaster

Heungseob Kim†

Department of Industrial and Systems Engineering/Department of Smart Manufacturing Engineering Changwon National University

^†Corresponding Author : heungseob79@cwnu.ac.kr

Received 22/12/2020 Finally Revised 30/12/2020 Accepted 04/01/2021

Abstract

The topic of this study is the field of humanitarian logistics for disaster response. Many existing studies have revealed that compliance with the golden time in response to a disaster determines the success or failure of relief activities, and logistics costs account for 80% of the disaster response cost. Besides, the agility, responsiveness, and effectiveness of the humanitarian logistics system are emphasized in consideration of the disaster situation’s characteristics, such as the urgency of life-saving and rapid environmental changes. In other words, they emphasize the importance of logistics activities in disaster response, which includes the effective and efficient distribution of relief supplies. This study proposes a mathematical model for establishing a transport plan to distribute relief supplies in a disaster situation. To determine vehicles’ route and the amount of relief for cities suffering a disaster, it mainly considers the urgency, effectiveness (restoration rate), and uncertainty in the logistics system. The model is initially developed as a mixed-integer nonlinear programming (MINLP) model containing some nonlinear functions and transform into a Mixed-integer linear programming (MILP) model using a logarithmic transformation and piecewise linear approximation method. Furthermore, a minimax problem is suggested to search for breakpoints and slopes to define a piecewise linear function that minimizes the linear approximation error. A numerical experiment is performed to verify the MILP model, and linear approximation error is also analyzed in the experiment.

Key Words : Humanitarian Logistics , Disaster Response , Mixed-Integer Programming Model , Linear Approximation , Weapon-Target Assignment

재난 구호품의 효과적 분배를 위한 혼합정수계획 모형

김 흥 섭†

창원대학교 산업시스템공학과/스마트제조융합협동과정

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

Changwon National University(CWNU)

1. 서 론

2014년 4월 세월호 참사를 비롯해 경북 경주/포항지역 의 지진, 충북 제천과 경남 밀양의 대형 화재사고 등으로 우리나라 국민들은 재난의 위협이 실생활에 상존함을 다 시금 느끼고 있다. 특히, 2016년 9월, 경북 경주지역의 규 모 5.8의 지진을 시작으로 포항지역에서 2017년 11월 규모 5.5, 2018년 2월 규모 4.6의 지진이 발생한 후 약 100회 이상의 여진이 계속되었다. <Figure 1(a)>에서 확인할 수 있듯이 우리나라가 지진을 관측하기 시작한 1978년부터 규모 3.0 이상의 지진발생 횟수는 매년 지속적으로 증가해 왔으며, <Figure 1(b)>에 제시된 진앙분포도로부터 최근 지진이 발생한 경북 경주/포항지역뿐만 아니라 전국이 지 진으로부터 안전할 수 없음을 확인할 수 있다. 이에 따라 국민들에게 재난에 대한 걱정을 넘어 공포의 대상이 되고 있다. 또한, 기상청의 2019년 지진연보[13]에 따르면, 한반 도 및 주변해역에서 발생한 지진은 총 1,045회로 규모 2.0 이상의 지진은 88회, 미소지진은 957회 발생하였다. 규모 2.0 이상의 지진의 경우 2018년(115회)보다 발생횟수는 적으 나, 디지털 관측 기간(1999~2018년) 연평균 69.9회보다 많 이 발생하였다. 규모 3.0 이상의 지진은 디지털관측 연평 균(10.9회) 보다 많은 14회가 발생하였으나 사람이 진동을 느낀 유감지진은 16회 발생하였다. 따라서 우리나라도 지진 등으로 인한 대형 재난에 대한 대비가 절실한 시점이다.

세계적으로도 21세기에 발생한 재난들의 규모가 과거 대비 상대적으로 커지고, 발생횟수도 증가함에 따라 재난 대응(Disaster response)을 위한 여러 연구와 활동들이 주목 받고 있다. 재난 대응을 위한 연구에서 대표적인 분야 중 하나가 인도주의적 물류(Humanitarian logistics)이다. Choi and Ha[6]는 인도주의적 물류를 ‘위기에 처한 사람들을 도 와주기 위해 발송지에서 소비지까지 구호물품을 보급하고 보관하는 일을 효율적으로 계획하고, 실행하고, 통제하는 활동’으로 정의하고 있다. 즉, 기존의 상업적 물류(Commercial logistics)는 물류비용 절감 등을 통한 수익 최대화, 비용 최소화 등을 목적으로하고 있으나, 재난대응을 위한 인도주의적 물류는 재난지역에 있는 피해자들에 대한 생 명유지, 기본생활 보장 등을 위한 구호활동을 효과적이고, 효율적으로 제공하는 것을 주요 목적으로 한다[5, 17]. 기존 연구들[3, 22, 23]은 재난대응 시 골든타임(Golden time) 준 수가 구호활동의 성패를 좌우하며, 물류비용이 재난대응 비용의 80%를 차지한다고 밝히고 있다. 또한, 인명구호의 시급성, 급격한 환경변화 등 재난상황의 특성을 고려하여 물류체계의 민첩성(Agility), 반응성(Responsiveness), 그리 고, 효과성(Effectiveness)을 강조하고 있다[21]. 즉, 재난대 응 물류체계에서는 의사결정의 시간과 정확성이 상당히 중요하게 고려되어야 한다. 따라서 본 연구는 재난 발생 시, 물류 환경의 불확실성을 고려하여 재난지역에 구호품 을 민첩하고 효과적으로 분배하기 위한 수리계획 모형 (Mathematical programming model)을 제시한다.

재난지역에 구호품을 분배하는 문제는 기존의 차량경 로계획 문제(VRP : Vehicle routing problem)와 동일하다고 할 수 있다. 다만, 재난대응이라는 목적, 재난 규모와 피해 의 불확실성(Uncertainty) 등 재난상황에 대한 환경적 차이 가 있어, 재난대응 물류를 위한 연구들은 기존의 VRP에 이러한 부분들을 반영하여 수정․보완하는 형태로 수행되 고 있다. Chang et al.[4]은 시나리오 기반의 비상물류 대비 문제(Emergency logistics preparation problem)를 다루었으 며, 대만 타이베이의 홍수(Flood) 상황의 시나리오에 대해 지형 정보를 바탕으로 예측된 피해 정도와 구호 자원의 수요를 통해 제안된 모형을 검증하였다. Yi and Özdamar [25]는 재난지역에 구호자원을 지원하고, 재난지역의 환자 들을 외부로 수송하는 문제를 다루었으며, 이는 VRPPD (VRP with pickup and delivery)와 유사한 개념의 문제이다. 또한, Yi and Kumar[24]은 이러한 문제의 해(Solution) 탐색 에 개미집단최적화(ACO : Ant Colony Optimization) 알고 리즘을 적용하였다. Cao et al.[2]는 지진이 발생한 상황을 가정하고, 지리정보시스템(GIS : Geographic Information System)을 통해 도로의 안전도를 평가하고, 수송시간, 거 리, 안전도를 고려하는 경로계획(Path planning) 문제를 제 안하였다. Parragh et al.[18]은 수요발생 후 가능한 한 빠르 게 배송하기 위한 차량의 배차와 경로문제(DARP : Diala- Ride Problem)에 대한 연구이며, 재난대응 물류체계의 반응성 향상을 위한 연구에 응용될 수 있다. Han et al.[10] 은 일반적인 VRP에서 재방문(Re-visit)의 허용, 방문 기한 준수의 개념을 추가한 재난 구호품의 수송 경로계획 문제 를 다루었으며, 복수의 재난 시나리오를 기반으로 수치실 험을 수행하였다.

또한, 재난대응과 관련된 시설의 입지 문제(FLP : Facility Location Problem)도 활발히 연구되고 있다. Balcik and Beamon[1]은 인도주의적 공급체인(Humanitarian supply chain)을 구성하기 위한 입지선정 문제를 제안하였으며, 최 대지역 커버링 문제(MCP : Maximum covering problem)를 활용하였다. Roh et al.[19]은 계층 분석적 의사결정법 (AHP)를 통해 재난 구호물자의 창고 입지 선정의 영향 요 인들을 확인하였으며, Huang et al.[12]은 피해지역에 공급 부족 상황 발생 시 공급 우선순위와 형평성 간 균형을 맞추 어 인명구조 효과, 지연비용, 그리고 형평성을 고려한 다목 적 최적화 모형을 제시하였다. 이때, 인명구조 효과는 효용 곡선을 통해 반영하고, 긴급성과 공급지연으로 인한 인적 고통을 지연비용으로 고려하였다. Ryu and Hwang[20]은 재난 구호물자 저장 창고의 입지선정 문제를 연결성을 고 려한 최대지역 커버링 문제로 고려하여 제안하였다.

본 연구는 재난발생 후 긴급 구호품을 재난지역에 빠르 고 효과적으로 분배하기 위한 수송계획 문제를 다룬다. 이 때, Huang et al.[12]이 제안한 바와 유사하게 임의 재난지역 의 재난 규모와 거주 인구 수를 고려하나 지원 긴급도를 반영하고, 구호품 지원에 따른 효과, 즉, 복구율(Restoration rate)을 고려하였다. 또한, 지진, 홍수 등과 같은 재난상황에 서 도로 등의 물류 기간망의 유실 등의 재난 상황의 불확실 성(Uncertainty)을 반영한 수리계획(Mathematical programming) 모형을 제안한다. 또한, 구호품 지원에 따른 효과와 물류망 소실 확률 등을 고려하기 위한 비선형계획(NLP : Nonlinear programming) 모형을 선형화․선형근사를 통해 선형계획(LP : Linear programming) 모형으로 변환하는 절 차를 제안하고, 수치실험을 통해 근사 오차(Approximation error)를 분석하여 선형근사 절차의 유용성을 검증한다.

본 연구의 제 2장에서는 재난상황에서의 구호품 분배에 대한 문제를 정의하고, 다수의 재난지역으로의 구호품 수송 계획 수립을 위한 비선형 혼합정수계획(MINLP : Mixedinteger nonlinear programming) 모형을 제시한다. 제 3장에 서는 대수변환(Logarithmic transformation)과 부분선형근사 (Piecewise linear approximation) 기법을 기용하여 2장에서 제시된 MINLP를 선형 혼합정수계획(MILP : Mixed-integer linear programming) 모형으로 변환하는 절차를 제시한다. 제 4장에서는 선형근사 MILP를 검증하기 위한 수치실험 결과를 제시하고, 제 5장에서는 결론 및 향후 연구방향을 제시한다.

2. 문제정의 및 수리모형

2.1 문제정의

본 연구는 지진 등의 재난 발생 후 피해지역에 구호품을 빠르고 효과적으로 분배하기 위한 수송계획 문제를 다룬 다. 일반적인 재난관리주기(Disaster management cycle)는 <Figure 2>와 같이 재난관리 시점을 기준으로 사전 활동 개념의 완화(Mitigation)와 대비(Preparedness), 그리고 사 후 활동 개념의 대응(Response)과 재건(Reconstruction)으 로 구분된다[3, 7]. 따라서 본 연구에서 다루는 문제는 재 난관리주기 상에서 재난발생 이전에 재난에 대한 대비 단계와 재난발생 후 대응 단계에 관련된다고 할 수 있다.

또한, 본 연구도 기존 연구들과 유사하게 재난대응이라 는 목적과 <Figure 3>과 같이 재난상황에서 물류체계에 내재 되는 불확실성을 고려하여 기존의 VRP를 수정․보완한다. 본연구의기반이 되는 VRP 계열의모형으로는 MDHVRPTW (Multi-depot heterogeneous VRP with time windows)가 적 용되며, 기존 MDHVRPTW 모형의 수정․보완을 위한 주 요 고려사항은 다음과 같다. 첫째, 재난은 넓은 지역에 걸 쳐 피해를 줄 수 있다. 따라서 재난의 유형과 규모, 재난지 역의 인구밀집도 등에 따라 단위 지역별 피해 규모가 상이 할 수 있다. 둘째, 재난지역 내 주민들의 생명유지를 위한 인명구호가 최우선적인 활동 목표이나, 재난 구호품의 보 유량이 부족한 상황에서는 구호품 지원의 효과성을 고려하여 분배 계획을 수립할 필요가 있다. 셋째, 재난 구호품 지원 은 재난 발생 이후에 수행되며, 구호품 지원을 위한 물류 체계는 지진, 홍수 등 재난에 의한 물류 인프라 파괴와 같 은 불확실성이 내재된 환경으로 고려한다[8, 9, 11]. 이때, 임의의 재난으로 인한 물류 인프라의 파괴 가능성 등의 불확실성 요소는 Chang et al.[4], Cao et al.[2]과 같이 지형 정보시스템(GIS)을 활용한 시뮬레이션(Simulation) 등의 사전 연구를 통해 확률적으로 추정될 수 있는 것으로 가정한다.

2.2 비선형 혼합정수계획(MINLP) 모형

본 절에서 다루는 문제의 환경은 다음과 같다. 재난 구 호품을 저장하고 있는 복수의 구호품 저장 센터가 존재하 고, 각 구호품 센터는 재난발생 시 구호품을 재난지역을 수송하기 위한 차량들을 운영하고 있다. 또한, 지원 대상 지역의 인구밀집도 등의 사전 정보를 보유하고 있으며, 재 난발생 후 각 지역의 피해 규모에 대한 정보를 획득할 수 있다. 물류 인프라의 활용 가능성, 즉, 물류 네트워크 상의 노드(Node) 간의 차량 운행 가능성은 확률 정보로 제공되며, 각 운행구간의 운행 가능성은 확률적으로 독립(Independent) 인 것으로 가정한다. 또한, 현실적인 상황을 묘사하기 위 해 구호품 지원량과 재난지역의 복구율은 비선형적인 관 계에 있으며, 구호품의 지원량 증가에 따라 복구율이 포화 (Saturation)되는 현상이 발생하는 것으로 모델링하였다. 보다 상세한 모델링 환경은 식 (1)부터 식 (24)까지와 같이 제시되는 재난 구호품 수송계획 수립을 위한 비선형 혼합 정수계획(MINLP) 모형의 목적함수(Objective function)와 제약식(Constraints)에 대한 기술에 포함되어 있다. 본 연구 에서 제안하는 MINLP 모형에서 사용되는 표기(Notation) 와 결정변수(Decision variables)는 다음과 같다.

<표기(Notation)>

∙D : 구호품 센터들의 집합; i∈D
∙C : 재난지역들의 집합; i∈C
∙N : 전체 노드들(Nodes)의 집합; N= D∪C
∙K : 구호품 수송차량들의 집합; k∈K
∙h_i : 재난지역 i의 재난지수(재난의 정도)
∙m_i : 재난지역 i의 거주 인구 수
∙ W_i : 구호품 지원의 긴급도 지수; W_i = h_im_i
∙ D_i : 재난지역 i의 구호품 수요량
∙ G_i : 재난지역 i의 구호품 지원 골든타임
∙d_ij : 재난지역 i와 j간의 거리
∙p_ij : 재난지역 i와 j간 이동 가능 확률
∙Q_k : 수송차량 k의 최대 적재량
∙μ_k : 수송차량 k의 평균 운행 속도
∙
∙θ : 재난지역 복구율 산정 함수 R_i 의 보정계수
∙M : 충분히 큰 수(Big-M)

<결정변수(Decision variables)>

∙
∙y_i : 재난지역 i에 지원된 구호품 양
∙t_i : 재난지역 i에 도착하는 시간
∙ Z_i : 재난지역 i에 도착 가능 확률; ln Z_i = ln( Z_i)
∙ R_i : 재난지역 i의 복구 가능율
∙S_ki : 차량 k가 재난지역 i까지 지원한 구호품 양
∙a_i : 부분순회경로방지를 위한 결정변수

Maximize \sum_{i \in C} W_{i} \cdot Z_{i} \cdot R_{i}

(1)

s.t. :

\begin{matrix} \sum_{i \in N} \sum_{k \in K} x_{k i j} \leq 1, & \forall j \in C \end{matrix}

(2)

\begin{matrix} \sum_{j \in N} \sum_{k \in K} x_{k i j} \leq 1, & \forall i \in C \end{matrix}

(3)

\begin{matrix} \sum_{i \in N} x_{k i p} - \sum_{j \in N} x_{k p j} = 0, & \forall k \in K, \forall p \in C \end{matrix}

(4)

\begin{matrix} \sum_{j \in C} x_{k i j} \leq H_{i k}, & \forall k \in K, \forall i \in D \end{matrix}

(5)

\begin{matrix} \sum_{i \in D} \sum_{j \in C} x_{k i j} - \sum_{i \in C} \sum_{j \in D} x_{k i j} = 0, & \forall k \in K \end{matrix}

(6)

\begin{matrix} a_{i} - a_{j} + | N | x_{k i j} \leq | N | - 1, & k \in K, \forall i, j \in N (i \neq j) \end{matrix}

(7)

t_{i} = 0, \forall i \in D

(8)

\begin{matrix} t_{j} \geq t_{i} + (d_{i j} / υ_{k}) - M (1 - x_{k i j}), & k \in K, \forall i \in N, \forall j \in C \end{matrix}

(9)

t_{i} \leq G_{i}, \forall i \in C

(10)

y_{j} - D_{j} \sum_{k \in K} \sum_{i \in N} x_{k i j} \leq 0

(11)

S_{k i} = 0, \forall k \in K, \forall i \in D

(12)

\begin{matrix} S_{k j} \geq S_{k i} + y_{j} - M (1 - x_{k i j}) = 0, & \forall k \in K, \forall i \in N, \forall j \in C \end{matrix}

(13)

S_{k i} \leq Q_{k}, \forall k \in K, \forall i \in C

(14)

R_{i} = tanh (θ \frac{y_{i}}{D_{i}}), \forall i \in C

(15)

Z_{i} = 1, \forall i \in D

(16)

\begin{matrix} Z_{j} \leq Z_{i} \cdot p_{i j} + (1 - x_{k i j}), & \forall i \in N, \end{matrix} \forall j \in C (j \neq i)

(17)

\begin{matrix} x_{k i j} \in {0, 1}, & \forall k \in K, \end{matrix} \forall i \in N, \forall j \in C

(18)

\begin{matrix} y_{i} \geq 0 and Integer, & \forall i \in C \end{matrix}

(19)

\begin{matrix} t_{i} \geq 0, & \forall i \in N \end{matrix}

(20)

\begin{matrix} Z_{i} \in [0, 1], & \forall i \in N \end{matrix}

(21)

\begin{matrix} R_{i} \in [0, 1], & \forall i \in C \end{matrix}

(22)

\begin{matrix} S_{k i} \geq 0 and Integer, & \forall k \in K, \forall i \in N \end{matrix}

(23)

\begin{matrix} a_{i} \geq 0, & \forall i \in N \end{matrix}

(24)

수리모형의 목적함수 식 (1)은 재난지역들의 구호품 지 원 긴급도, 구호품 도착 가능 확률, 그리고 구호품 지원에 따른 복구 가능률의 곱(Product)을 최대화하는 것이며, 지 역별 긴급도와 확률적 복구 가능성을 고려하고 있다. 이러 한 목적함수는 상대의 피해(Damage)를 최대화하기 위해 자원(무기)을 할당하는 무기-표적 할당(WTA : Weapon- Target Assignment) 문제의 목적함수를 반대개념에서 고려 하여 설정하였다. 식 (2)부터 식 (7)까지는 구호품 수송차량 들의 경로 생성에 대한 제약식들이다. 식 (2)와 (3)은 각 재난지역에 대한 구호품 지원을 1회 이내로 제한하고 있다. 식 (4)는 수송차량 운행경로의 연속성(Route continuity)을 보장하기 위한 제약이다. 현실적으로, 임의의 수송차량 k 는 현재 위치하고 있는 곳에서 출발하여야 한다. 따라서 식 (5)는 차량 k가 운행을 시작할 때, 현재 위치하고 있는 구호품 센터 i에서 출발하여야 함을 나타낸다. 식 (6)은 구 호품 수송을 위해 운행을 시작한 차량들은 구호품 지원을 마친 후 구호품 센터들 중 1곳으로 복귀하여야 하며, 이때 출발한 구호품 센터와 복귀하는 구호품 센터가 다를 수 있도록 하였다. 이는, 재난상황에서 수송차량들이 보다 안 전한 구호품 센터로 복귀하는 현실적인 상황을 고려하였 다. 단, 구호품 물류 정책에 따라 차량들의 출발과 복귀하 는 구호품 센터를 동일하게 유지하여야 한다면, 식 (6)은 식 (25)와 같이 적용될 수 있다. 식 (7)은 수송차량들의 운행 경로 상의 부분순회경로 생성을 방지하기 위한 제약(SECs : Sub-tour Elimination Constraints)이다.

\sum_{j \in C} x_{k i j} - \sum_{i \in C} x_{k i j} = 0, \forall k \in K, \forall i \in D

(25)

식 (8)부터 식 (10)까지는 각 수송차량의 운행시간에 대 한 제약식들이다. 식 (8)은 수송차량들이 수송을 시작하는 시간을 0으로 초기화하고 있다. 식 (9)는 각 수송차량이 지정된 경로에 따라 구호품을 배송할 때, 각 재난지역에 도착하는 시간을 산정하기 위한 제약이며, 식 (10)은 재난 지역 i를 지원하기 위한 구호품은 사전에 검토된 골든타임 (Golden time) 이전에 도착하여야 함을 나타내고 있다.

식 (11)부터 식 (15)까지는 각 재난지역에 대한 구호품 지원량을 결정하기 위한 제약식들이다. 식 (11)은 수송차량 의 운행경로와 구호품 지원을 연동하기 위한 제약으로, 수 송차량 k는 운행경로 상에 포함된 재난지역 j에 대해 구호 품 수요량(D_j) 이내에서 지원할 수 있음을 나타내고 있다. 식 (12)는 구호품 센터를 출발하는 수송차량의 구호품 지원 누적량을 0으로 초기화한다. 식 (13)은 수송차량 k가 운행 경로에 따라 방문하는 재난지역에 지원하는 구호품의 누적 량을 산정하며, 식 (14)는 차량 k가 지원하는 모든 재난지 역에서 구호품의 누적량이 차량의 적재능력(Q_k)을 초과할 수 없음을 나타낸다. 즉, 임의 차량의 구호품 최대 지원량 이 적재능력 이내가 되도록 수송계획을 수립한다. 식 (15) 는 재난지역 i의 구호품 수요량 대비 지원량(y_i )에 따라 복구율( R_i )을 산정 함수이다. 본 연구에서는 구호품의 지 원량이 증가됨에 따라 복구율이 포화(Saturation) 되는 현상 을 묘사하기 위해 <Figure 4>와 같은 Hyperbolic tangent (tanh ) 함수로 고려하였다. 이때, tanh 함수에서 완전 복 구, 즉, 복구율이 1.0으로 평가되기 위해서는 수요량 대비 지원량(y_i/ D_i )이 무한대(∞)가 되어야 하는 비현실적 현상 이 발생한다. 따라서 본 연구에서는 수요량 대비 지원량이 1.0이 될 때, 복구율도 1.0에 근사되도록 하기 위해 보정계 수 θ (= 3.5)를 적용하였다.

식 (16)과 식 (17)은 운행경로 상에 계획된 재난지역에 도착할 수 있는 확률을 산정하고 있다. 즉, 식 (16)은 구호품 센터를 출발 시의 도착 확률을 1.0으로 초기화하고, 식 (17) 은 운행경로에 따라 각 재난지역에 도착할 수 있는 확률을 산정한다. 여기서, 본 연구에서는 운행경로 상의 재난지역 들의 방문순서가 중요하며, 이는 본 연구와 기존 VRP와의 차별점이다 예시적으로, <Figure 5>(복구율 = 1.0 가정)가 설명하는 바와 같이 두 재난지역의 방문순서가 변경될 때, 최종 목적함수의 변화가 확인된다. 식 (18)부터 식 (24)까지 는 각 결정변수의 종류(이진형, 실수형, 정수형 등)와 범위 를 지정하고 있다.

3. 선형근사 혼합정수계획(MILP) 모형

2.2절에서 제시된 모형은 목적함수인 식 (1), 제약식 (15) 와 (17)으로 인해 비선형 혼합정수계획(MINLP)으로 정의 된다. 따라서 본 절에서는 대수변환(Logarithmic transformation) 과 부분선형근사(Piecewise linear approximation) 기 법을 활용하여 선형근사 혼합정수계획(MILP) 모형으로의 변환 절차를 제시한다.

3.1 목적함수의 대수변환

본 절에서는 목적함수 식 (1)과 식 (15)에 대한 선형화 및 선형근사 절차를 제시한다. 식 (1)은 결정변수 Z_i 와 R_i 의 곱으로 인해 비선형으로 정의된다. 따라서 첫 번째 단 계로 목적함수를 대수변환하면, 식 (26)과 같이 표현된다. 이때, 비선형 원 함수(Original function) 식 (1)과 대수변 환된 식 (26)은 일대일(1:1) 대응관계가 있어 목적함수로 서의 동등한 효과를 갖는다. 단, 식 (1)에서는 구호품이 지원되지 않는 재난지역에 대해서는 복구율(R_j)이 0이 되 기 때문에 긴급도 지수( W_j)가 목적함수에 반영되지 않는 다. 하지만, 식 (1)의 대수변환 직후의 식에서는 모든 재 난지역의 긴급도 지수가 반영되게 된다. 따라서 수송차량 이 방문하는 재난지역에 한해 긴급도 지수가 반영되도록 보완하였다. 또한, 목적함수가 식 (26)으로 변경됨에 따라 제약식 (15)도 식 (27)과 같이 변형되어야 한다.

Max. \sum_{j \in C} [ln (Z_{j}) + ln (R_{j}) + ln (W_{j}) \sum_{k \in K} \sum_{i \in N} x_{k i j}]

(26)

ln (R_{i}) = ln [tanh (θ \frac{y_{i}}{D_{i}})], \forall i \in C

(27)

3.2 ln(R_i)의 부분선형근사

본 절에서는 3.1절의 대수변환에 의해서도 비선형 함수 로 나타나고 있는 식 (27)에 대해 부분선형근사 기법을 적 용한다. 본 연구에서는 근사 오차(Approximation error)를 최소화하기 위한 부분선형함수 탐색을 최대최소화(Minmax) 문제로 고려하였다. 즉, 부분선형함수의 각 구간 (Interval)에서 나타나는 본 함수와의 최대 오차를 최소화 하기 위한 중단점들(Breakpoints)을 탐색한다. <Figure 6> 에 제시된 바와 식 (28)의 arc tanh(x)의 정의에 따라 임의 구간 [χ_n, χ_n₊₁)에서의 최대 오차 $\in_{χ_{n}, χ_{n + 1})}^{*}$ 가 나타나는 지 점 $χ_{χ_{n}, χ_{n + 1})}^{*}$ 은 식 (29)와 같이 도출된다. 따라서 N개의 구 간을 갖는 부분선형함수에서, 각 구간에서의 최대 오차를 최소화하기 위한 중단점들을 탐색하기 위한 최대최소화 문제는 식 (30)과 같이 정의된다.

arctanh (x) = \frac{1}{2} ln (\frac{1 + x}{1 - x})

(28)

\begin{array}{l} χ_{[χ_{n}, χ_{n + 1})}^{*} \\ = \frac{1}{2 θ} \ln (\frac{2 θ - α_{[χ_{n} {,χ}_{n+1})} + \sqrt{α_{_{[χ_{n} {,χ}_{n+1})}}^{2} + 4 θ^{2}}}{2 θ + α_{[χ_{n} {,χ}_{n+1})} - \sqrt{α_{_{[χ_{n} {,χ}_{n+1})}}^{2} + 4 θ^{2}}}) \end{array}

(29)

\begin{array}{l} Min . max [max {\in_{χ_{n} {,χ}_{n+1})} (χ)}] \\ = max [\in (χ_{{[χ}_{n} {,χ}_{n+1})}^{*}); n \in {1, \dots, N - 1}] \end{array}

(30)

본 연구에서 활용하기 위한 ln( R_i )에 대한 부분선형근 사 함수의 중단점들은 MATLAB 2012b의 ‘fmincon()’ 함 수를 이용하여 탐색되었다. 먼저, 탐색에 적합한 알고리 즘을 선정하기 위해 ‘active-set’, ‘interior-point’, ‘sqp’ 그 리고 ‘trust-region-reflective’ 알고리즘을 이용해 예비 실 험을 수행하였으며, 예비 실험에서 가장 좋은 결과를 보 인 ‘sqp’ 알고리즘을 이용하여 모든 중단점들을 탐색하 였다. 이때, R_i가 0으로 접근하면 ln( R_i )가 - ∞로 발산 하기 때문에 R_i∈ [0.05, 1.0]에서 근사 함수를 생성하였 다. 부분선형근사 함수의 구간(Interval)을 2개 구간부터 20개 구간까지 달리하면서 중단점을 탐색한 결과는 <Figure 7>과 같다. <Figure 7>에서 (a)는 부분선형함수의 구간 수를 증가시킬 때, 전체 구간에서의 최대 오차의 변화를 보여주고 있으며, (b), (c), (d)는 각각 3, 7, 10개의 구간 을 갖는 부분선형함수의 최적 중단점들을 표현하고 있 다. 시각적으로도 구간의 수가 증가할수록 본 함수에 대 한 근사도가 향상됨을 확인할 수 있다. <Table 1>은 5, 7, 10개의 구간으로 부분선형함수를 구성할 때, 중단점(Breakpoints) 과 각 구간에서의 기울기(Slope)를 제시하고 있다. 본 연구의 수치실험(4장)에서는 최대 오차가 0.02(오차율 2.41%)로 나타난 <Figure 7(c)>의 7개 구간 부분선형함수 를 사용하였다.

3.3 도착가능확률(Z_i) 산정식 변환

본 절에서는 임의의 수송차량이 재난지역 i에 구호품을 지원할 수 있을 확률을 산정하기 위한 식 (16)과 식 (17)에 대한 변환을 제시한다. 변환의 초점은 3.1절에서 대수변환 된 목적함수 식 (26)에서의 ln( Z_i)를 산정하고, 식 (17)에서 비선형 항인 Z_i‧p_ij를 선형화하는 것이다. 두 가지 초점은 대수변환에 의해 충족될 수 있다. 즉, 대수변환을 통해 제 약식 (16)은 식 (31)과 같이 변경된다. 또한, 제약식 (17)은 식 (32)로써 동등한 효과를 얻을 수 있으며, 직접적으로 ln( Z_i )를 산정할 수 있게 된다.

ln Z_{i} = ln (Z_{i}) = 0 \forall i \in D

(31)

\begin{array}{l} ln Z_{i} \leq ln Z_{i} + ln (p_{i j}) + M (1 - \sum_{k \in K} x_{k i j}), \\ \forall i \in N, \forall j \in C (j \neq i) \end{array}

(32)

4. 수치실험 및 결과

본 장에서는 제 3장에서 제시된 선형근사 혼합정수계획 (MILP) 모형을 검증하고, 부분선형근사로 인한 오차의 영 향도를 분석하기 위한 수치실험 결과를 제시한다. 수치실 험을 위한 예제(Example)는 구호품 센터 2개소가 수송차량 5대로 재난지역 10개소를 지원하는 상황을 묘사하도록 구 성하였으며, 수치실험을 위한 입력 데이터(Input parameters) 는 <Table 2>와 같다. 수치실험은 Windows 10 운영체제, 2.1GHz Intel Xeon Silver 4116 CPU, 그리고 64GB RAM 환경에서 수행되었으며, IBM사의 ILOG CPLEX 12.8.0.0 소프트웨어를 이용하여 실험예제의 최적해(Optimal solution) 를 탐색하였다.

실험예제의 최적해 탐색 결과 중 수송차량별 운행경로 는 <Figure 8>과 같이 시각화된다. 운행경로 이동 가능성 에 대한 불확실성을 거리에 반비례하도록 설정하여 운행 거리를 최소화하는 경로와 유사하게 도출되었다. 하지만, 운행거리 최소화를 목적으로 하는 VRP와의 중요한 차이 점은 최적해에서 지정한 재난지역의 방문순서가 준수되 어야 한다는 것이다. 즉, 일반적인 VRP에서는 계획된 경 로를 반대로 운행하는 것이 허용된다.

수치실험의 세부적인 결과는 <Table 3>과 같다. 수송차 량의 적재 용량, 구호품 수요량 대비 지원량에 따른 복구 율 등 수리모형의 제약들이 정확하게 작동하고 있음을 확 인할 수 있다. 예시적으로, Vehicle #1의 운행경로 불확실 성( Z_i)을 검증해보면, 대수변환된 lnZ₃ = -0.08103, lnZ₂ = -0.12605로 산정되었으며, 지수변환하면 Z₃ = 0.9222, Z₂ = 0.8816이 된다. 또한, 실험예제에서 $P (\bar{B_{1} C_{3}})$ = 0.9222, $P (\bar{C_{3} C_{2}})$ = 0.9560이므로, $P (\bar{B_{1} C_{3} C_{2}})$ 는 0.8816으로 정확 하게 산정되고 있음을 확인할 수 있다.

다음으로는, 부분선형근사 기법의 근사 오차를 분석하 여 MINLP 모형의 선형근사 MILP 모형으로의 변환에 대 한 실용성을 검증한다. 검증방법은 선형근사 MILP 모형 의 최적해를 바탕으로 재계산된 MINLP 모형의 실제 목 적함수 값(True value)과 선형근사 MILP 모형의 목적함수 값을 비교한다. 이때, 근사 오차는 부분선형근사 기법이 활용된 구호품 수요량 대비 지원량에 의한 복구율( R_i )에 서만 나타난다. 따라서 목적함수 간의 차이는 부분선형근 사 기법의 근사 오차로 간주될 수 있다. 근사 오차는 식 (33)과 같이 산정되었다. 선형근사 MILP 모형의 근사 오 차에 대한 분석 결과는 <Table 4>에 제시되었다. 재난지 역별 오차는 최대 약 1.68%, 최소 약 0.03% 수준으로 나 타났으며, 최종적인 목적함수의 근사 오차는 0.3457%로 상당히 작게 나타났다. 따라서 부분선형근사 기법을 통한 MINLP 모형의 선형근사 MILP 모형으로의 변환은 실무 적으로도 활용 타당성이 있다고 할 수 있다.

Approx. Error \frac{MINLP -MILP}{MINLP} × 100 (%)

(33)

5. 결론 및 향후 연구방향

최근 우리나라에서 지진, 화재, 선박 침몰 등의 재난과 사고가 지속적으로 발생함에 따라 국민들의 불안감이 증 폭되고 있다. 특히, 한반도는 안전지대라고 여겨졌던 지 진에 있어 2016년 경주, 2017년 포항 지진을 비롯하여 한반도와 주변해역에서의 지진의 규모와 발생빈도가 증 가는 대형 재난의 발생 우려를 증폭시키고 있다. 따라서 우려되는 대형 재난에 있어 우리나라의 특성에 맞는 대 비가 절실한 시점이다. 또한, 대형 재난상황에서 인명구 호, 기본생활 유지 등을 위한 재난대응 물류의 중요성이 여러 연구들을 통해 부각되고 있다.

이에 따라 본 연구는 재난구호 활동의 80%를 차지하 는 재난대응 물류 분야에서 수리적인 방법론을 통해 실 현가능(Feasible)하고, 효과성을 담보할 수 있는 재난 구 호품의 공급체인에 대한 문제를 다루었다. 기존의 상업 물류 환경에서 활발히 연구되어온 VRP 계열의 문제를 기반으로 재난대응 물류의 목적과 물류 시스템에 내재된 불확실성을 고려하여 수정․보완된 구호품 수송계획 모 형을 제안하였다. 이때, 구호품 지원에 따른 재난지역의 복구율, 물류 인프라의 파괴 등의 불확실성을 반영하기 위해 비선형 함수로 모델링된 MINLP 모형을 제안하고, 이에 대해 대수변환과 부분선형근사 기법을 이용하여 선 형근사 MILP 모형으로 전환하는 절차를 제안하였다. 또 한, 수치실험을 통해 선형근사 MILP 모형을 검증하고, 근사 오차에 대한 분석을 통해 현실 문제에의 적용 가능 성에 대해서도 확인하였다.

또한, 본 연구는 기업물류 분야에도 응용이 가능하다. 즉, 물류 인프라의 파괴 등으로 인해 기업물류도 재난에 자유로울 수 없으며, 특히, 글로벌화로 인해 기업물류의 공급체인도 환율, 원자재 조달, 품질 및 리드타임, 수송시 간, 정치․경제적 상황 등의 불확실성에 직면하고 있다 [14-16]. 이러한 불확실성에 의한 위험은, 일본의 1995년 과 2011년 대지진으로 인한 물류기능 마비로 식료품 공 급 차질과 아이패드 출시 지연, 미국의 9.11 사태 이후 검 문 강화로 인한 포드 자동차의 부품운송 지연 등과 같은 실례로도 확인되었다[26].

향후 연구방향으로는, 첫째는, 재난대응 물류의 효율 성, 효과성 등과 같은 성과지표의 개발이다. 본 연구는 전 통적인 WTA 문제의 목적함수를 벤치마킹하여 재난지역 의 지원 긴급도, 복구율, 도착 가능성을 고려하였으나, 재 난대응 물류에서는 비용 외에도 다양한 고려요소가 포함 될 수 있다. 둘째로는, 재난상황은 예측이 불가능한 경우 가 많고, 재난발생 시에는 인명구호를 위해 가능한 한 빠 른 대응이 필수적이다. 이는, 재난상황에 따라 민첩한 대 응이 필요함을 의미한다. 따라서 재난상황에 대비하기 위 한 최적화 문제들에 있어서는 현실 적용에 문제가 없는 수준의 합리적인 해를 빠르게 탐색할 수 있어야 한다. 합 리적인 수준의 해를 빠른게 탐색하기 위한 방안으로는, 유전자 알고리즘(Genetic algorithm), 개체군집최적화(Particle swarm optimization) 알고리즘 등과 같은 메타 휴리스틱 (Meta-heuristic) 알고리즘을 적용될 수 있으며, 최근에는 강화학습(Reinforcement learning)과 같은 기계학습(Machine learning) 방법론을 적용한 연구가 나타나고 있다. 셋째로는, 본 연구에서 표현한 재난지역 복구율, 물류 시스템 내 불 확실성 요소들에 대한 현실적인 모델링이 필요하다. 이는 우리나라의 재난 유형, 지형 등을 고려하여 Chang et al. [4], Cao et al.[2]과 같은 연구들의 방법론을 적용해볼 수 있다.

Acknowledgements

This research was supported by Changwon National University in 2019~2020.

Figure

<Figure 1>.

Eearthquakes in Korea(1978~2019)[13]

<Figure 2>.

Disaster Management Cycle[7]

<Figure 3>.

Logistics Environment for Disaster Response

<Figure 4>.

Restoration rate function

<Figure 5>.

Importance of a Route Direction

<Figure 6>.

Searching the Maximum Error Point at Each Interval

<Figure 7>.

Piecewise Linear Approximation for ln[tanh(θ_χ)]

<Figure 8>.

Visualization of Vehicles’ Routes

Table

<Table 1>.

Breakpoints and Slopes of Piecewise Linear Function

<Table 2>.

Input Parameters for a Numerical Experiment

<Table 3>.

Experimental Results

<Table 4>.

Approximation Error Analysis

Reference

Balcik, B. and Beamon, B.M., Facility location in humanitarian relief, International Journal of Logistics, 2008, Vol. 11, No. 2, pp. 101-121.
Cao, Z., Wang, W., Ma, D., Su, J., Gao, Z., and Han, Y., Optimum path analysis of post-earthquake transportation considering multi-objective based on GIS, In International Conference on Transportation Engineering 2009, 2009, pp. 1104-1109.
Celik, M., Ergun, O., Johnson, B., Keskinocak, P., Lorca, A., Pekgun, P., and Swann, J., Humanitarian Logistics, INFORMS Tutorials in Operations Research, 2012, Vol. 9, pp. 18-49.
Chang, M.S., Tseng, Y.L., and Chen, J.W., A scenario planning approach for the flood emergency logistics preparation problem under uncertainty, Transportation Research Part E : Logistics and Transportation Review, 2007, Vol. 43, No. 6, pp. 737-754.
Cheng, W. and Lu, J., Operational analysis on emergency logistics system and emergency response model, In 2008 IEEE International Conference on Service Operations and Logistics, and Informatics, 2008, Vol. 1, pp. 1323-1328.
Choi, H. and Ha, H., The Priority of Supply Chain Designs for Humanitarian Relief with AHP(Analytic Hierarchy Process), Korean Journal of Logistics, 2013, Vol. 21, No. 3, pp. 121-134.
Cozzolino, A., Humanitarian Logistics : Cross-Sector Cooperation in Disaster Relief Management, Springer Science & Business Media, 2012.
Dudin, A. and Semenova, O., A stable algorithm for stationary distribution calculation for a BMAP/SM/1 queueing system with Markovian arrival input of disasters, Journal of Applied Probability, 2004, Vol. 41, No. 1, pp. 547-556.
Economou, A., The compound Poisson immigration process subject to binomial catastrophes, Journal of Applied Probability, 2004, Vol. 41, No. 1, pp. 508-523.
Han, S., Jeong, H., Kim, K., and Park J., A Research on the Vehicle Routing Problem in the Disaster Scene, Korean Management Science Review, 2016, Vol. 33, No. 1, pp. 101-117.
Hsieh, P.H., A data-analytic method for forecasting next record catastrophe loss, The Journal of Risk and Insurance, 2004, Vol. 71, No. 2, pp. 309-322.
Huang, K., Jiang, Y., Yuan, Y., and Zhao, L., Modeling multiple humanitarian objectives in emergency response to large-scale disasters, Transportation Research Part E : Logistics and Transportation Review, 2015, Vol. 75, pp. 1-17.
Korea Meteorological Administration, Annual Earthquake, 2020.
Kumar, S.K. and Tiwari, M.K., Supply chain system design integrated with risk pooling, Computers & Industrial Engineering, 2013, Vol. 64, No. 2, pp. 580-588.
Lima-Junior, F.R. and Carpinetti, L.C.R., Quantitative models for supply chain performance evaluation : A literature review, Computers & Industrial Engineering, 2017, Vol. 113, pp. 333-346.
Meixell, M.J. and Gargeya, V.B., Global supply chain design : A literature review and critique, Transportation Research Part E : Logistics and Transportation Review, 2005, Vol. 41, No. 6, pp. 531-550.
Ozdamar, L., Ekinci, E., and Kucukyazici, B., Emergency logistics planning in natural disasters, Annals of Operations Research, 2004, Vol. 129, pp. 217-245.
Parragh, S.N., Doerner, K.F., Hartl, R.F., and Gandibleux, X., A heuristic two-phase solution approach for the multi-objective dial-a-ride problem, Networks : An International Journal, 2009, Vol. 54, No. 4, pp. 227-242.
Roh, S.Y., Jang, H.M., and Han, C.H., Warehouse location decision factors in humanitarian relief logistics, The Asian Journal of Shipping and Logistics, 2013, Vol. 29, No. 1, pp. 103-120.
Ryu, K. and Hwang, T., Optimal Locations of Disaster Relief Warehouses Based on Connected Maximum Covering Problem, Journal of the Korea Society of Supply Chain Management, 2019, Vol. 19, No. 1, pp. 19-30.
Tatham, P., Pettit, S., Charles, A., Lauras, M., and Van Wassenhove L., A model to define and assess the agility of supply chains : building on humanitarian experience, International Journal of Physical Distribution & Logistics Management, 2010, Vol. 40, pp. 722-741.
Trunick, P.A., Logistics when it counts, Logistics Today, 2005, Vol. 46, No. 2, p. 38.
Van Wassenhove, L.N., Humanitarian aid logistics : supply chain management in high gear, Journal of the Operational research Society, 2006, Vol. 57, No. 5, pp. 475-489.
Yi, W. and Kumar, A., Ant colony optimization for disaster relief operations, Transportation Research Part E : Logistics and Transportation Review, 2007, Vol. 43, No. 6, pp. 660-672.
Yi, W. and Ozdamar, L., A dynamic logistics coordination model for evacuation and support in disaster response activities, European Journal of Operational Research, 2007, Vol. 179, No. 3, pp.1177-1193.
Yoon, K., Kim, J., and Yang. C., A study of Innovational Logistics System’s Preferential Order Decision for Disaster Response, using AHP, Korea Logistics Review, 2015, Vol. 25, No. 2, pp. 1-12.