비대칭차량경로문제의 경로분할모형에 관한 연구

강성민(Sungmin Kang) 한국생산관리학회 2007 韓國生産管理學會誌 Vol.18 No.4

  차량경로문제의 Set-Partitioning모형에 적용된 열생성과정에서 차량경로를 생성하는 하위문제는 순회외판원문제와 같은 조합구조를 가지므로 연산상의 어려움이 크다. 본 논문은 각 차량경로를 분할하여, 하위문제에서 분할된 부분경로를 생성하고 주문제에서 다시 결합하는 경로분할모형을 소개한다. 열생성이 용이해지는 반면 주문제는 복잡해진다. 실험예제로 모형의 LP하한값을 비교분석하였으며, 분지열생성을 통하여 최대 100개 수요지의 비대칭차량경로문제의 최적화실험을 수행하였다.   The Capacitated Vehicle Routing Problem (VRP) is to determine a set of feasible vehicle routes. one for each vehicle. such that each customer is visited exactly once and the total distance travelled by the vehicles is minimized. A feasible route is defined as a simple circuit including the depot such that the total demand of the customers in the route does not exceed the vehicle capacity. We introduce a new modelling approach. termed route-splitting. for the VRP that allows us to address problems whose size is beyond the current computational range of the Set-Partitioning model. The route-splitting model splits each vehicle route into segments. and results in more tractable subproblems. Lifting much of the burden of solving combinatorially hard subproblems. the route-splitting approach puts more weight on the LP master problem Recent advances in solving LP problems bode well for our approach. The route-splitting model can deal with non-identical vehicles. Given the ability of the route-splitting model to address a wider range of applications and its good performance on asymmetric instances. we find the model promising and valuable for further research.

맵리듀스를 이용한 효율적인 kNNTA 질의 처리 방법

강성민(Sungmin Kang),김홍연(Hongyeon Kim),이석주(Seok-Joo Lee),민준기(Jun-Ki Min) 한국정보과학회 2015 한국정보과학회 학술발표논문집 Vol.2015 No.12

인지 무선 네트워크에서 하향 링크 전송을 위한 경로 선택 기법

강성민(Sungmin Kang),민지연(Jiyeon Min),김지용(Jiyong Kim),장나윤(Nayoon Jang),황호영(Ho Young Hwang) 한국통신학회 2014 한국통신학회 학술대회논문집 Vol.2014 No.11

맵리듀스를 이용한 다중 중심 기반의 K-Means 클러스터링 기법

강성민(Sungmin Kang),이석주(SeokJoo Lee),민준기(Jun-ki Min) 한국정보과학회 2014 한국정보과학회 학술발표논문집 Vol.2014 No.12

분화성 갑상선암 환자에서 방사성 옥소 치료 시 악화되어 치명적인 경과를 보였던 4증례

강성민 ( Sungmin Kang ),이상우 ( Sang-woo Lee ),안병철 ( Byung Cheol Ahn ),이재태 ( Jaetae Lee ) 대한갑상선학회 2009 International Journal of Thyroidology Vol.2 No.1

Radioiodine therapy of differentiated thyroid cancer patient has been widely used for the treatment of recurrent or metastatic lesions after appropriate surgery. It requires thyroid stimulating hormone (TSH) stimulation to facilitate radioiodine uptake into cancer tissue. Traditional TSH stimulation method is thyroid hormone withdrawal for certain period, but it causes overt hypothyroidism and rarely results in tumor progression. We here report four cases of abrupt aggravation of pre-exsting thyroid cancer during thyroid hormone withdrawal for preparation and eventually lead to death after radioiodine therapy.

맵리듀스를 이용한 다중 중심점 집합 기반의 효율적인 클러스터링 방법

강성민(Sungmin Kang),이석주(Seokjoo Lee),민준기(Jun-ki Min) 한국정보과학회 2015 정보과학회 컴퓨팅의 실제 논문지 Vol.21 No.7

데이터 사이즈가 증가함에 따라서 대용량 데이터를 분석하여 데이터의 특성을 파악하는 것이 매우 중요해졌다. 본 논문에서는 분산 병렬 처리 프레임워크인 맵리듀스를 활용한 k-Means 클러스터링 기반의 효과적인 클러스터링 기법인 MCSK-Means (Multi centroid set k-Means)알고리즘을 제안한다. k-Means 알고리즘은 임의로 정해지는 k개의 초기 중심점들의 위치에 따라서 클러스터링 결과의 정확도가 많은 영향을 받는 문제점을 가지고 있다. 이러한 문제를 해결하기 위하여, 본 논문에서 제안하는 MCSK-Means 알고리즘은 k개의 중심점들로 이루어진 m개의 중심점 집합을 사용하여 임의로 생성되는 초기 중심점의 의존도를 줄였다. 또한, 클러스터링 단계를 거친 m개의 중심점 집합들에 속한 중심점들에 대하여 직접 계층 클러스터링 알고리즘을 적용하여 k개의 클러스터 중심점들을 생성하였다. 본 논문에서는 MCSK-Means 알고리즘을 맵리듀스 프레임워크 환경에서 개발하여 대용량 데이터를 효율적으로 처리할 수 있도록 하였다. As the size of data increases, it becomes important to identify properties by analyzing big data. In this paper, we propose a k-Means based efficient clustering technique, called MCSKMeans (Multi centroid set k-Means), using distributed parallel processing framework MapReduce. A problem with the k-Means algorithm is that the accuracy of clustering depends on initial centroids created randomly. To alleviate this problem, the MCSK-Means algorithm reduces the dependency of initial centroids using sets consisting of k centroids. In addition, we apply the agglomerative hierarchical clustering technique for creating k centroids from centroids in m centroid sets which are the results of the clustering phase. In this paper, we implemented our MCSK-Means based on the MapReduce framework for processing big data efficiently.

복수순회외판원문제 경로분할모형의 최적화연구

강성민(Kang Sungmin) 한국생산관리학회 2008 한국생산관리학회지 Vol.19 No.2

  복수 순회외판원문제(이하 mTSP)는 단일의 출발지를 떠나 여러 도시를 방문하고 다시 출발지로 되돌아오는 복수의 외판원의 경로를 선정하는 문제로, 모든 도시는 각각 단 1인의 외판원에 의해 방문되며, 목표는 외판원들의 방문경로의 총 길이를 최소화하는 것이다. TSP에 비해서 mTSP는 복수의 외판원을 가정하는 보다 현실적인 모형으로, 이와 같은 상황은 다양한 경로탐색문제 및 일정계획문제에서 발생한다. 한편, mTSP는 보다 더 일반적인 로지스틱스모형 해법알고리듬의 하위문제로도 중요한 역할을 한다. 예를 들어 mTSP구조는 다양한 VRP모형의 공통분모이며 VRP의 해법개발을 위해서 mTSP모형 및 문제구조에 대한 연구가 유용하다.<BR>  본 연구의 목적은 mTSP문제의 경로분할모형을 소개하고, 분지열생성 알고리듬에 기반을 둔 최적화 프로세스의 실험을 통해, 특히 Kara와 Bektas의 MTZ유형의 제약식(이하 KB cut)에 관한 분석을 수행하는데 있다. 제한적인 규모의 연산실험에서 KB-cut은 LP하한값을 평균 0.8% 상승시켰으나, 연산시간을 증가시켰다. 결론적으로, 본 연구의 실험에서 KB-cut은 mTSP의 경로분할모형의 최적화를 촉진하지 못했다. 그러나 하한값 평균 0.8%의 상승은 하한값이 98%를 상회하는 상황에서 하한값이 99% 가까이 도달한다는 것을 뜻하므로 그 의미가 작지 않다고 판단된다. 또한 현재 LP 최적화 알고리듬은 여전히 진화중이며 향후 LP 최적화 속도가 충분히 빨라질 경우 하한값 상승의 효과가 나타날 것을 기대할 수 있다. 또한 향후 다양한 cut이 시도될 수 있을 것이다. 본 연구는 사전에 추가되는 제약식에 의한 경로분할모형의 최적화 촉진에 관한 이론적 토대를 제공한다.   The multiple traveling salesman problem (mTSP) consists of determining a set of routes for multiple salesmen each of whom starts from and returns to a home city (depot) after visiting a group of other intermediate cities, such that each intermediate city is visited exactly once and the total distance of visiting all cities is minimized.<BR>  Compared to the TSP, the mTSP is more adequate to model real life situations, since it is capable of handling more than one salesman. These situations arise mostly in various routing and scheduling problems. The mTSP is also important in that it arises as a subproblem in the solution of more general problems. For example, the VRP instances arising in practice can be extremely difficult to solve, since the underlying mTSP is also complex in nature. This provides the need to efficiently solve the mTSP in order to attack large-scale VRPs arising in real-life situations.<BR>  The route-splitting model of the mTSP is introduced, and the exact solution algorithm based on the branch-and-price process is developed. Computational analysis shows that the Kara and Bektas" constraints improve LP lower bounds by about 0.8%. Even though Kara and Bektas" constraints" effect to expedite our branch-and-price optimization process developed for the route-splitting model of the mTSP was not confirmed in our experimentation, we expect to try other cuts afterwards. This work provides the theoretical framework of enhancing bounds with various pre-installed cuts in the route-splitting approach.

초기 승온이 박막 고체산화물 연료전지에 끼치는 전기화학적 영향 연구

강성민(Sungmin Kang),장익황(Ikwhang Chang),지상훈(Sanghoon Ji),박태현(Taehyun Park),차석원(Suk Won Cha) 대한기계학회 2014 대한기계학회 춘추학술대회 Vol.2014 No.4-3

유비쿼터스 컴퓨팅의 미들웨어 테스트 응용 구현

강성민(Sungmin Kang),황기태(Kitae Hwang),이재문(Jaemoon Lee),김남윤(Namyun Kim) 한국통신학회 2003 한국통신학회 학술대회논문집 Vol.2003 No.11

가동준비비용 및 시간이 작업순서에 종속하는 생산일정계획의 연속시간 모형

강성민(Sungmin Kang) 한국생산관리학회 2005 한국생산관리학회지 Vol.15 No.3

본 연구는 가동준비가 작업순서에 종속하는 단일기계에서의 로트결정 및 일정계획 문제의 새로운 연속시간 모형을 제시한다. 유한한 계획시평동안 확정적인 동적 수요를 갖는 다수 제품의 생산량 및 생산시기를 결정하는 문제로서 가동준비비용과 재고비용의 합을 최소화하는 목적을 갖는다. 생산능력은 제한적이며 추후납품은 허용되지 않는다. 본 모형의 특징은 첫째, 연속시간의 모형으로서 가동준비 및 생산이 다음 기간으로 단절 없이 연속될 수 있다는 점, 둘째, 가동준비비용 및 가동준비시간이 작업순서에 종속한다는 점, 셋째, 가동준비상태가 다음 기간으로 이전되며 유휴 기간동안 가동준비상태가 보존된다는 점을 들 수 있다. 생산일정을 짧게 나누는 생산연쇄 분할기법으로 모형화 하였으며, 열생성 프로세스 기반의 휴리스틱을 사용하여 실험 연산한 결과를 제시한다. We propose a new model for the continuous-time capacitated lot-sizing and scheduling problem with sequence-dependent setup times and setup costs that addresses the problem of simultaneously determining production quantities and timings of several products on a single, capacitated machine such that the sum of inventory holding costs and setup costs is minimized and known deterministic, dynamic demands in a finite number of planning periods are satisfied without delays. Setups and production lots are allowed to span two consecutive periods and setup states are preserved over idle periods. The solution technique designed is based on a column generation process coupled with the sequence-splitting in which the entire schedule is broken up into sub-sequences. This scheme is embedded into an optimizationbased heuristic and tested on a set of benchmark problem instances.