배송 네트워크에서 드론의 유용성 검증

정예림(Yerim Chung),박태준(Taejoon Park),민윤홍(Yunhong Min) 한국경영과학회 2016 한국경영과학회지 Vol.41 No.3

This paper investigates the usefulness of drones in an urban delivery system. We define the vehicle and drone routing problem with time window (VDRPTW) and present a model that can describe a dual mode delivery system consisting of drones and vehicles in the metropolitan area. Drones are relatively free from traffic congestion but have limited flight range and capacity. Vehicles are not free from traffic congestion, and the complexity of urban road network reduces the efficiency of vehicles. Using drones and vehicles together can reduce inefficiency of the urban delivery system because of their complementary cooperation. In this paper, we assume that drones operate in a point-to-point manner between the depot and customers, and that customers in the need of fast delivery are willing to pay additional charges. For the experiment datasets, we use instances of Solomon (1987), which are well known in the Vehicle Routing Problem society. Moreover, to mirror the urban logistics demand trend, customers who want fast delivery are added to the Solomon’s instances. We propose a hybrid evolutionary algorithm for solving VDRPTW. The experiment results provide different useful insights according to the geographical distributions of customers. In the instances where customers are randomly located and in instances where some customers are randomly located while others form some clusters, the dual mode delivery system displays lower total cost and higher customer satisfaction. In instances with clustered customers, the dual mode delivery system exhibits narrow competition for the total cost with the delivery system that uses only vehicles. In this case, using drones and vehicles together can reduce the level of dissatisfaction of customers who take their cargo over the time-window. From the view point of strategic flexibility, the dual mode delivery system appears to be more interesting. In meeting the objective of maximizing customer satisfaction, the use of drones and vehicles incurs less cost and requires fewer resources.

Partial Inverse Traveling Salesman Problems on the Line

Yerim Chung(정예림),Myoung-Ju Park(박명주) 한국컴퓨터정보학회 2019 韓國컴퓨터情報學會論文誌 Vol.24 No.11

부분역최적화는 역최적화의 흥미로운 변형으로, 주어진 최적화문제와 그 문제의 부분해가 주어지면 이 부분해가 최적해에 포함되도록 문제를 최소한으로 수정하는 문제이다. 이 논문은 라인위에서 정의되는 순환외판원문제(TSP)를 다루는데, 이는 배달시스템, 창고 선반에서 물건을 수집하는 것, 등의 많은 응용을 가진다. 라인 위에서 위치하는 n개의 일이 주어지고 이 중 연속적으로 처리해야하는 일 k개가 부분적으로 주어진다. 각각의 일은 라인 위의 특정 장소에 위치하고 라인을 움직이는 서버에 의해 처리되어야 한다. 우리의 임무는 k개의 일이 최적해에서 연속적으로 처리되도록 n개의 일의 위치를 라인 위에서 최소한으로 조정하는 것이다. 이 논문에서 이 문제와 이 문제의 다양한 변종을 다항시간 내에 푸는 알고리즘을 개발한다. 구체적으로, 서버가 특정한 Forward Trip이라는 특정한 내부 알고리즘을 사용하는 경우와 일반적인 최적 알고리즘을 사용하는 경우에 대한 부분역최적화를 다룬다. The partial inverse optimization problem is an interesting variant of the inverse optimization problem in which the given instance of an optimization problem need to be modified so that a prescribed partial solution can constitute a part of an optimal solution in the modified instance. In this paper, we consider the traveling salesman problem defined on the line (TSP on the line) which has many applications such as item delivery systems, the collection of objects from storage shelves, and so on. It is worth studying the partial inverse TSP on the line, defined as follows. We are given n requests on the line, and a sequence of k requests that need to be served consecutively. Each request has a specific position on the real line and should be served by the server traveling on the line. The task is to modify as little as possible the position vector associated with n requests so that the prescribed sequence can constitute a part of the optimal solution (minimum Hamiltonian cycle) of TSP on the line. In this paper, we show that the partial inverse TSP on the line and its variant can be solved in polynomial time when the sever is equiped with a specific internal algorithm Forward Trip or with a general optimal algorithm.

Notes On Inverse Interval Graph Coloring Problems

Yerim Chung(정예림),Hak-Jin Kim(김학진) 한국컴퓨터정보학회 2019 韓國컴퓨터情報學會論文誌 Vol.24 No.10

이 논문에서는 인터벌 그래프 컬러링 역문제 중 다항시간 안에 풀이 가능한 경우에 대해 연구한다. 인터벌 그래프의 컬러링 역문제는 주어진 인터벌 그래프를 K개의 서로 다른 색깔로 색칠할 수 없는 경우를 가정하며, 다음과 같이 정의된다. 주어진 인터벌 그래프가 K개의 색깔을 이용해서 모두 칠해질 수 있도록 인터벌 그래프와 연관되어 있는 인터벌 시스템을 최소한으로 수정하는 문제이다. 인터벌 시스템에서 두 인터벌이 부분적으로라도 서로 겹쳐있는 구간이 있을 경우 두 인터벌에 해당하는 노드들이 엣지로 연결되어 있음을 의미하고, 따라서 이 경우에는 해당 노드들을 같은 색깔을 이용해 칠할 수 없다. 따라서 겹쳐져 있는 인터벌들을 이동시켜 해당 그래프의 chromatic number를 바꿀 수 있다. 본 논문에서는 인터벌의 길이가 모두 1 또는 2이며, 인터벌의 이동이 본래 위치 대비 오른쪽으로만 가능하다는 제한이 있는 경우에 대해 집중 탐구한다. 이 문제를 해결하는 다항시간 알고리즘으로 sorting과 선입선출 방식을 사용하는 2단계 알고리즘을 제안한다. In this paper, we study a polynomially solvable case of the inverse interval graph coloring problem. Given an interval graph associated with a specific interval system, the inverse interval graph coloring problem is defined with the assumption that there is no proper K-coloring for the given interval graph, where K is a fixed integer. The problem is to modify the system of intervals associated with the given interval graph by shifting some of the intervals in such a way that the resulting interval graph becomes K-colorable and the total modification is minimum with respect to a certain norm. In this paper, we focus on the case K=1 where all intervals associated with the interval graph have length 1 or 2, and interval displacement is only allowed to the righthand side with respect to its original position. To solve this problem in polynomial time, we propose a two-phase algorithm which consists of the sorting and First Fit procedure.

정수계획법을 이용한 대학강의 시험시간 및 강의실 배정 문제의 풀이

정예림(Yerim Chung),김학진(Hak-Jin Kim) 한국컴퓨터정보학회 2019 韓國컴퓨터情報學會論文誌 Vol.24 No.9

In this paper, we study the university timetabling problem, which consists of two subproblems, the university course timetabling problem and the examination timetabling problem. Given a set of classrooms, students, teachers, and lectures, the problem is to assign a number of courses (and examinations) to suitable timeslots and classrooms while satisfying the given set of constraints. We discuss the modeling and solution approaches to construct course and examination timetables for one of the largest Korean university. By using binary integer programming formulations, we describe these two complex real-world problems. Then, we propose a solution method, called NOGOOD, to solve the examination timetabling model. The computation results show that NOGOOD finds the optimal examination schedule for the given instance. Although we consider a specific instance of the university timetabling problem, the methods we use can be applicable to modeling and solving other timetabling problems.

소비자 네트워크의 변화 관리 문제

정예림(Yerim Chung),박선주(Sunju Park),정승화(Seungwha Chung) 한국경영과학회 2014 한국경영과학회지 Vol.39 No.2

Customer networks go through constant changes. They may expand or shrink once they are formed. In dynamic environments, it is a critical corporate challenge to identify and manage influential customer groups in a cost effective way. In this context, we apply inverse optimization theory to suggest an efficient method to manage customer networks. In this paper, we assume that there exists a subset of nodes that might have a large effect on the network and that the network can be modified via some strategic actions. Rather than making efforts to find influential nodes whenever the network changes, we focus on a subset of selective nodes and perturb as little as possible the interaction between nodes in order to make the selected nodes influential in the given network. We define the following problem based on the inverse optimization. Given a graph and a prescribed node subset, the objective is to modify the structure of the given graph so that the fixed subset of nodes becomes a minimum dominating set in the modified graph and the cost for modification is minimum under a fixed norm. We call this problem the inverse dominating set problem and investigate its computational complexity.

시뮬레이션을 이용한 성형외과 예약패턴 분석

최지연,정예림,박선주,정승화,Choi, Jiyeon,Chung, Yerim,Park, Sunju,Chung, Seungwha 한국시뮬레이션학회 2018 한국시뮬레이션학회 논문지 Vol.27 No.1

Generally, solutions that can increase patients' satisfaction are in conflict with the solutions that can increase the satisfaction and profitability of the medical personnels. In this paper, we compare appointment patterns using multiple performance measures that take into account both hospital's position and customers' position, and propose the best appointment pattern especially for an efficient scheduling in a plastic surgery clinic. A simulation model using ARENA is designed based on real hospital data. Based on this model, we compare 5 appointment patterns. To check the robustness of the appointment patterns, we have experimented on various appointment situations by considering peak, extreme peak seasons, and peak, off-peak days. We found that Triangle-like pattern turned out to be most efficient regardless of appointment situations. 일반적으로 고객의 만족도를 높이는 방안은 병원의 이익 및 병원 의료진들의 만족도를 높이는 방안과는 상충된다. 이에 본 논문은 병원과 고객을 함께 고려한 평가지표를 사용하여 여러 가지 예약 패턴들을 비교해보고 병원의 효율적인 운영을 위해 성형외과에 적절한 예약 패턴을 제안하고자 한다. 본 논문에서는 도심에 위치한 실제 성형외과의 고객 및 진료 데이터를 이용해 시뮬레이션 모델을 설계하고, 이 모델을 대상으로 5가지 예약 패턴을 비교하였다. 예약 패턴의 강건성을 체크하기 위하여 성수기와 극성수기, 피크 요일과 한적한 요일 등 다양한 상황 하에서 실험을 진행하였다. 실험 결과, 본 연구에서 새롭게 제안하는 Triangle-like Pattern이 예약 수와 관계없이 가장 좋은 결과를 보여주었다.

시뮬레이션을 통한 해군의 복구성 수리부속 재고관리 모형 개발에 관한 연구

김성필,박선주,정예림,Kim, Sungpil,Park, Sunju,Chung, Yerim 한국시뮬레이션학회 2013 한국시뮬레이션학회 논문지 Vol.22 No.1

과학기술의 발전으로 대한민국 해군의 함정 등의 무기체계는 첨단화, 과학화 되면서, 무기체계를 도입 및 운영, 유지하는 비용도 크게 증가한 반면, 이를 위한 국방비는 한정되어 있다. 따라서, 최적화된 예산을 사용하면서 적절한 가용도를 유지하기 위해 함정 가동에 영향을 주는 수리부속에 대한 효율적이고 과학적인 관리가 필요하다. 이를 위해 본 연구에서는 복구성 수리부속의 재고수준에 따른 가용도를 산출하는 시물레이션 재고관리 모형을 제시하였다. 제시된 모델은 기존의 복구성 수리부속의 다단계 재고관리모형인 METRIC 모형을 바탕으로 계획정비, 재생율, 전환보급, 동류전용 등의 현실적인 개념을 순차적으로 반영한 5개의 모델로 구성되어 있다. 실험은 각 모델에 같은 재고수준량을 입력하여 가용도의 결과값을 산출하도록 진행하였으며, 추가적인 민감도 분석을 실시하였다. 실험결과 각 모델별 가용도의 차이가 있었으며, 따라서, 해군의 운영특성을 반영한 재고관리 모델의 개발이 필요함을 확인하였다. Recent development in science and technology has modernized the weapon systems of ROKN (Republic Of Korea Navy). Although the cost of purchasing, operating, and maintaining the cutting-edge weapon systems has been increased significantly, the national defense expenditure is under a tight budget constraint. In order to maintain the availability of ships with low cost, we need an efficient and scientific method for managing repairable parts. In this study, we propose a simulation model that computes the availability of ship's repairable parts. Our model is based on the METRIC (Multi Echelon Technique Repairable Item Control) model and extends to five sub-models to reflect the realistic situations that arise in the navy, such as planned maintenance, condemnation, lateral transshipment, and cannibalization. We have performed simulations to compute the availability of repairable parts while setting the part-level consistent throughout the five models and carried out two sensitivity analyses. The simulation results show the differences in the part availability in different models. The experiments confirm our claim that ROKN needs an inventory management system that captures the operational characteristics of the navy.

코로나19가 가져온 오프라인 소비 패턴의 변화: 2020년 신용카드 데이터 분석

최지혜(Jihae Choi),정예림(Yerim Chung),박선주(Sunju Park),박태준(TaeJoon Park) 연세대학교 경영연구소 2021 연세경영연구 Vol.58 No.3

2020년 유행한 COVID-19 바이러스(이하, 코로나19로 표기)로 인한 외부 활동 제약과 심리적인 위축으로 소비가 위축되었을 거란 예상과 달리 국내 소비 총액은 전년과 비슷한 수준을 유지하고 있다. 하지만 이는 온라인 시장의 성장이 오프라인 시장의 매출 하락을 상쇄하면서 발생한 착시로, 오프라인 비중이 큰 업종들은 사회적 거리두기와 방역 활동으로 인해 매출에서 큰 타격을 입었다. 이는 온ㆍ오프라인간의 양극화를 심화시켰다. 이러한 가운데 2020년 5월, 국민의 생계를 지원하고 소비를 진작시키고자 정부는 14.2조 원 상당의 1차 긴급재난 지원금을 국민들에게 배포하였다. 이 정책은 일시적인 소비를 이끌어냈지만 특정 업종에만 소비가 집중되는 현상이 발생하였다. 본 연구는 신한카드사의 서울 시 오프라인 신용카드 결제 데이터를 사용하여 2020년 오프라인 소비에서의 변화를 분석하고, 이를 통해 (1) 코로나19가 가져온 오프라인 소비 변화를 확인하고 나아가 (2) 오프라인에서 업종별로 다른 코로나19의 영향을 확인하였다. 마지막으로 (3) 시계열 군집화를 사용하여 긴급재난 지원금 사용 가능 기간에 대해 오프라인에서 업종별 긴급재난지원금의 영향을 분석하였다. 그 결과 코로나19로 인한 오프라인 소비 변화가 소비 주체 별로 상이했다는 점과 오프라인에서 업종 간의 매출 변화에 유의미한 차이가 있다는 점을 확인하였다. 또 시계열 군집화를 통해서는 긴급재난지원금의 오프라인 사용에 업종 별 차이가 발생하였음을 확인하고, 이를 통한 향후 정책적 보완점이 필요함을 확인하였다. Contrary to expectations that consumer spending would decrease in 2020 due to the COVID-19 pandemic, domestic consumption maintained the level of the previous year. However, this is an illusion that occurred because the growth of the online market offset the decline in sales in the offline market. Offline consumption decreased due to quarantine activities, and the stores that mainly rely on the offline customer took a direct hit. This circumstance intensifies the in-balance between online consumption and offline consumption. In May 2020, the government distributed the first emergency disaster relief fund worth 14.2 trillion KRW to stimulate consumption. Although this policy led to a temporary consumption increase, it did not overcome the consumption bias in that customer spending was concentrated in a few industries. This study analyzed the changes in offline consumption patterns using the payment data in Seoul provided by Shinhan credit card company. In this study, we confirm the actual offline consumption pattern changes via consumer group and verify the different impacts of COVID-19 via the industry sector. At last, using the time series clustering, we divided industries into 3 different groups based on the effect of the emergency disaster relief fund.

역최적화를 활용한 물류거점 통합 유도

유건식 ( Geonsik Yu ),정예림 ( Yerim Chung ),박선주 ( Sunju Park ) 한국로지스틱스학회 2016 로지스틱스연구 Vol.24 No.3

본 연구는 업체 간 공동 물류화를 유도함으로써, 복잡해진 물류 구조를 조율하여 이로 인한 부정적인 외부효과를 줄이려는 정부 정책의 효율성을 높이기 위한 연결망 모형을 제시하고, 역최적화 알고리즘을 적용하여 탐색한 해를 어떻게 해석하고 활용할지에 대한 예시를 보였다. 특히 기존에 역최적화 알고리즘이 적극적으로 적용된 바 없는 정책 의사결정 분야에 방법론을 적용하여 다수의 의사결정자가 연관된 정책 설계에 수리적인 최적화를 도입할 수 있음을 보였다. 선행 물류 연구들에 의해 공동 물류화의 효과성과 활용 방안에 대한 심도있는 고찰이 이루어졌기 때문에, 본 연구는 역최적화 수리모형을 활용하여 공동 물류화 문제를 효율적으로 정책화하기 위한 모형과 계량적인 해법을 제시하는 데에 초점을 두었다. 연구의 목적을 위해 기존에 알려진 물류 대안을 개별 업체가 당면한 의사결정 대상으로 가정하고 시장 상황을 모형화하였다. 개별 업체가 갖는 물류 대안은 자사 물류 거점을 사용하는 것과 더불어, 공동 물류화와 리스등을 포함하는 것을 가정하였다. 해당 모형은 조합 최적화 이론에서 고안한 연결망 모형을 응용하였으며, 해당연결망의 접점은 기업의 의사결정 대안을 표현하도록 하고 접점 간의 연결에는 해당 대안에 관련된 비용을 할당하였다. 구성한 연결망 모형에 대해서 기존의 해법을 사용하여 정책 구성에 활용 가능한 비용 조정값을 도출할 수 있음을 보였다. 이 때 연결의 조정값이 양수일 경우, 이를 해당 경제 행위에 대한 과세 등으로 해석할 수있으며, 반대로 음수일 경우에는 보조금 지급 등으로 해석할 수 있다. 도출한 해로부터 발생 가능한 다양한 경우에 해의 특성에 대한 분석을 수행했으며, 추가적으로 이를 현실적인 제약 조건을 고려한 정책 상황에 어떻게 적용할 수 있을지에 대해 논했다. 이는 과세할 수 없는 행위 혹은 정책적 지원을 할 수 없는 행위가 고려될 경우에 어떻게 모형을 수정하여야 하는지에 대한 답이 될 수 있다. 본 연구는 역최적화라는 수리적 기법이 의사결정 및 정책 관련 분야에도 실용적으로 적용될 수 있음을 보였다. 특히, 우리가 제시한 방법은 최소한의 예산으로 시장에 효율적인 개입을 수행할 수 있는 방향을 도출함으로써 여러 의사결정자가 존재하는 공동 물류화유도 상황을 수리적으로 해결한다. 나아가, 본 연구가 제시한 모형은 공동 물류화 상황이 아니더라도 그 외 정부의 개입으로 시장을 조율하고자 하는 다양한 정책 문제나 3자에 의한 조율이 필요한 다른 문제에도 역최적화가 수리적인 해법이 될 수 있음을 보일 것으로 기대한다. This study suggests a network model that describes a product distribution service market with multiple decision makers or companies in order to minimize the negative externalities when inducing integrated distribution system. We apply the inverse optimization algorithm to the network model to minimize the cost of inducement policy and provide application examples for the methods we used. Different from preceding researches on distribution system integration issues that cover the practical usage and location selection for distribution centers, this paper focuses on suggesting a quantitative method for efficient policy design related to distribution market. To solve the problem, we suppose that each distribution company in the market can have several well­known alternatives for their distribution processes and formulate the whole decision making of the market with a network model. We assume that each company has following alternatives for their product distributions: utilizing their own distribution centers, leasing a warehouse from a competitor and using a joint distribution center with a competitor. Applying the network theory and the combinatorial optimization theory, we describe in the network model the companies and their decision alternatives as nodes and assign the cost of their decisions to the related link. By using the inverse optimization algorithm, we compute the optimal solution that can be applied to the policy making for distribution center integration by means of fine­tuning the distribution industry or the monetary inducement on joint distribution center. When the value of the given solution is positive, we can interpret it as additional taxation on a certain economic decision. On the other hand, if the value is negative, we can interpret the result as government subsidies. We analyze the characteristics of our optimization solution for different possible situations and consider practical constraints of formulating efficient inducement policy. By extending our linear programming model, we also show that our model can handle and optimize the market situations containing upper bounds or lower bounds of cost modifications. For example, situation including a limited amount of subsidies, taxation not allowed and etc. The mathematical method we proposed in this research can be used to design an efficient inducement policy for distribution system integration with minimum budget. And furthermore, our method can also be applied to other policy-related problems including market adjustment concepts.

경쟁적 문제 해결 과정에서 피드백 순서와 문제 해결 경험

문희진(Hee Jin Mun),정예림(Yerim Chung),박경민(Kyung Min Park) 한국경영과학회 2013 한국경영과학회지 Vol.38 No.1

This study suggests that as receiving feedback is moved back, the effectiveness of problem-solving increases. Utilizing data from innovation contests in which a number of problem solvers compete with each other, we answer questions such as whether the order of receiving first feedback affects problem-solving effectiveness and how problem-solving experience moderates the relationship between the first feedback order and problem-solving effectiveness. Empirical results based on data collected from Kaggle, an online platform for innovation contests, showed that the order that contest participants receive the first feedback increases problem-solving effectiveness. Furthermore, the more prior experience of contest participants accentuates the suggested relationship between the order of receiving the first feedback and problem-solving effectiveness.