유전자 알고리즘을 이용한 시간제약 차량경로문제

전건욱(Geon-Wook Jeon),이윤희(Yoon-Hee Lee) 한국산업경영시스템학회 2006 한국산업경영시스템학회지 Vol.29 No.4

The main objective of this study is to find out the shortest path of the vehicle routing problem with time window constraints by using both genetic algorithm and heuristic. Hard time constraints were considered to the vehicle routing problem in this suggested algorithm. Four different heuristic rules, modification process for initial and infeasible solution, 2-opt process, and lag exchange process, were applied to the genetic algorithm in order to both minimize the total distance and improve the loading rate at the same time. This genetic algorithm is compared with the results of existing problems suggested by Solomon. We found better solutions concerning vehicle loading rate and number of vehicles in R-type Solomon’s examples R103 and R106.

유전 알고리즘을 이용한 다용량 차량경로문제

전건욱 ( Geon Wook Jeon ) 국방대학교 안보문제연구소 2004 국방연구 Vol.47 No.1

차량경로문제는 지리적으로 분산된 고객에게 재화와 서비스를 효율적으로 수송 및 배송하는 차량 할당 및 운행 경로를 결정하는 문제이며 우편 시스템, 택배 시스템, 제품사후 서비스 시스템, 물류유통 시스템 및 군 수송 분야 등 다양한 분야에 적용이 가능하다. 일반적인 차량경로문제의 목표는 가용 차량의 대수와 적재용량, 수요지점의 수요량 및 차량에 대한 각종 운행조건 등의 제약 조건 하에 운행 거리를 최소화하는 것이며 차량경로문제가 최초 제기된 이후 체약 조건들을 다양화하여 광범위한 연구가 진행되고 있다. 최근에 이르러서는 물류와 관련한 수송비 절감의 필요성에 대한 인식으로 그 중요성을 더해 가고 있는 실정이다. 일반적인 차량경로문제는 차량의 적재 용량과 차량대수, 운행거리의 제약 조건 하에 적재용량이 동일한 다수의 차량을 이용하여 차량의 총 운행거리를 최소화하는 문체를 다루고 있다. 해법에 있어 차량경로문제는 최적해 산출시 매우 많은 계산량을 필요로 하므로 일반 최적기법의 적용이 곤란하나, 본 연구에서는 단일 창고에서 각 수요지점의 수요량을 충족시킨 후 다시 창고로 되돌아오는 차량에 대해 운행경로를 최소화하는 수리모형의 구축과 이에 대한 해법으로 기존의 유전자 표현을 일부 수정하고 차량 적재용량을 다양화한 다용량 차량경로문제의 새로운 발견적 알고리즘을 제시한다. 다용량 차량경로문제는 기존 연구에 비해 현실성을 고려한 것으로 상위수준의 발견적 기법 중 하나인 유전 알고리즘을 적용하여 최적해를 산출함으로써 유전자 표현의 효율적인 구성이 최적해 산출에 미치는 영향을 관찰하였다. The primary idea of vehicle routing problem is to transport goods or services efficiently to the customers. The main objective is to minimize total service distance and transportation cost with identical vehicles under the following constraints, number of available vehicles, loading capacity, and service distance. And more extensive works by manipulation of these constraints are currently studying so far. Vehicle routing problem can be applied for the various areas such as post delivery, home delivery system, distribution center, and military transportation etc. A modified genetic algorithm, an efficient gene representation which assigns each vehicle to the demand point, with various capacities for each vehicle is suggested in this study. An example with twenty demand points and six different vehicles is provided and analyzed an optimal solution.

신뢰도 분석모델을 이용한 대함유도탄 검사주기 결정에 관한 연구

김대익,전건욱,Kim, Dae-Ik,Jeon, Geon-Wook 한국국방경영분석학회 2006 한국국방경영분석학회지 Vol.32 No.2

무기체계는 최근 고도의 신기술과 막대한 비용이 투자되어 첨단화, 정밀화, 장사정화, 은밀화, 복합 기능화의 특징을 가진 고비용 무기체계로 변화하고 있다. 이에 따라 유도무기체계의 경우도 경제적인 운용과 사용자의 안전성을 보장하는 측면에서 고도의 신뢰성이 보장되어야 한다. 따라서 유도무기 체계를 개발하고 생산하는 단계에서의 신뢰도 평가뿐만 아니라 주어진 저장 환경조건이나 운용환경에서의 일정한 저장 신뢰도의 유지를 위한 기준이 제시 되고 이를 유지하기 위한 최적화된 검사주기가 필요하다고 할 수 있다. 본 연구는 현재 해군에서 운용중인 대함 유도탄(Harpoon Block 1)을 대상으로 검사주기 간 고장건수 및 정비현황을 기초로 수학적 기법과 신뢰도 분석 S/W를 활용하여 저장고장률과 MTBF를 도출하고 이를 바탕으로 체계 운용유지를 위한 최적 검사주기를 결정하여 향후 대함 유도무기체계 신뢰도 예측 및 평가를 통한 검사주기 개선방안을 제시하였다. The main purpose of this study is to determine the optimal periodic inspection for Anti-Ship-Missile(Harpoon Block 1) fielding on Korea Navy Ship. In order to perform this study, the data from the Korea Navy (Harpoon maintenance & storage reliability) were collected from 1984 to 2004. Storage failure rate & MTBF for Harpoon block 1 were analysed by using mathematical model & reliability analysis software(Relex) and finally determined optimal periodic inspection. The suggested methodology will be used to determine and reevaluate the periodic inspection of Anti-Ship-Missiles for the Korea Navy.

하이브리드 유전자알고리즘을 이용한 엄격한 시간제약 차량경로문제

백정구,전건욱,Baek, Jung-Gu,Jeon, Geon-Wook 한국국방경영분석학회 2007 한국국방경영분석학회지 Vol.33 No.2

The main purpose of this study is to find out the best solution of the vehicle routing problem with hard time window by using both genetic algorithm and heuristic. A mathematical programming model was also suggested in the study. The suggested mathematical programming model gives an optimal solution by using ILOG-CPLEX. This study also suggests a hybrid genetic algorithm which considers the improvement of generation for an initial solution by savings heuristic and two heuristic processes. Two heuristic processes consists of 2-opt and Or-opt. Hybrid genetic algorithm is also compared with existing problems suggested by Solomon. We found better solutions rather than the existing genetic algorithm. 본 연구는 엄격한 시간제약 차량경로문제에 대하여 유전자알고리즘과 휴리스틱 기법을 이용하여 최적해를 산출하는 것이다. 문제해결을 위해 수리적 모형을 구성하고, ILOG-CPLEX를 이용하여 최적해를 산출하였다. 임의 생성방법과 세이빙 휴리스틱을 적용한 초기해 생성, 실행불가능해의 교정과 유전자 알고리즘 종료 후 2-opt, Or-opt 등 해교정 및 해개선을 위한 과정이 추가된 하이브리드 유전자 알고리즘을 구축하여 엄격한 시간제약이 있는 차량경로 문제에 적용하여 솔로몬 예제와 비교하고, 제안한 알고리즘의 해공간탐색능력, 수렴성, 휴리스틱 기법의 효과를 확인하였다.

ARIMA를 이용한 항공기 수리부속의 수요 예측

박영진,전건욱,Park, Young-Jin,Jeon, Geon-Wook 한국국방경영분석학회 2008 한국국방경영분석학회지 Vol.34 No.2

신형/장기 운영 무기체계 수리부속의 불균형적 수요발생에 따른 항공기 불가동을 해소하기 위한 수요예측기법 개선의 필요성이 대두되고 있다. 항공기 수리부품들은 고단가이고, 청구에 소요되는 기간이 길어 사전에 예측하지 못한다면 작전지원에 문제가 발생하게 된다. 신뢰성 있는 수요 예측은 과보유로 인한 재고비용을 줄일 수 있으며, 수요를 예측하기 위한 방법은 회귀분석, 단/다변량 시 계열분석, 데이터 마이닝 기법 등이 있다. 항공기 부품의 수요 예측은 그 부품의 수가 8만 가지 이상이며 각 부품간의 관계를 분석하기에 어려움이 있어 시간에 종속적인 단변량 시계열 분석을 통해 수요예측을 실시하였다. 본 연구에서는 이러한 문제점을 해결하기 위하여 첫째, 자료를 기존 AMMIS 체계에서 고장 자료를 실수요로 가정하여 수집하였다. 고장이나 주기 검사, 시한성 기술지시 등으로 부품을 장 탈착하게 되면 정비부서에서 이를 전산프로그램인 AMMIS에 입력하도록 하고 있다. 따라서 실제 정비부서에서 부품을 사용한 현황을 실수요라고 인정할 수 있다. 둘째, 1999년 1월부터 2007년 2월까지의 월별 자료(98개)를 수집하였다. 자료의 수가 충분하므로 예측 정확성 향상을 위하여 ARIMA기법에 적용이 가능하다. 고장빈도가 높은 부품 50여개를 추출하여 Box-Jenkins의 ARIMA기법을 적용하여 예측을 실시하였다 실시 결과 적합한 모형식을 도출하였으며, 현용기법보다 예측 정확성이 높다는 결론을 얻었다. This study is for improvement of repair part demand forecasting method of Republic of Korea Air Force aircraft. Recently, demand prediction methods are Weighted moving average, Linear moving average, Trend analysis, Simple exponential smoothing, Linear exponential smoothing. But these use fixed weight and moving average range. Also, NORS(Not Operationally Ready upply) is increasing. Recommended method of Box-Jenkins' ARIMA can solve problems of these method and improve estimate accuracy. To compare recent prediction method and ARIMA that use mean squared error(MSE) is reacted sensitively in change of error. ARIMA has high accuracy than existing forecasting method. If apply this method of study in other several Items, can prove demand forecast Capability.

탄도미사일의 비행특성을 고려한 요격미사일 소요 알고리즘

김흥섭,김기태,전건욱,Kim, Heung-Seob,Kim, Ki-Tae,Jeon, Geon-Wook 한국군사과학기술학회 2011 한국군사과학기술학회지 Vol.14 No.6

A Ballistic Missile(BM) is a missile that follows a sub-orbital ballistic flightpath with the objective of delivering one or more wardheads to a predetermined target and An Anti-Ballistic Missile(ABM) is a missile designed to destroy a ballistic missile before reaching its target. The main objective of this study is to assess the requirement of ABM by considering both flight characteristic of the SCUD-B/C, Nodong missiles and intercept performance of ABM in the Lower tier Ballistic Missile Defense(BMD). The Ballistic Missile's flight characteristics, such as trajectory, velocity etc., are estimated by simulation using the physical motion equations. The requirement of ABM is calculated by evaluating whether the BMD forces can defend those when the ballistic missiles attack prime facilities.

운영유지비용을 고려한 신뢰도 할당 모형의 선정

박종화,김기태,전건욱,Park, Jong-Hwa,Kim, Ki-Tae,Jeon, Geon-Wook 한국국방경영분석학회 2009 한국국방경영분석학회지 Vol.35 No.3

시스템의 성능과 안전성을 보장하기 위해서는 개발 초기부터 신뢰도에 대한 연구가 이루어져야 한다. 시스템의 목표 신뢰도를 수립하고, 이를 달성하기 위하여 하부시스템 및 부분품에 신뢰도를 할당해야 한다. 시스템의 획득 및 개발에 있어서 성능이 우수하고 비용이 저렴하더라도 고장이 빈번하게 발생한다면 원활한 임무 수행에 많은 영향을 미치고, 막대한 운영유지비용이 소요될 것이다. 본 연구에서는 신뢰도 할당 모형과 운영 유지비용과의 관계를 알아보기 위하여 기존의 알려진 신뢰도 할당 모형들을 검토 및 평가하였다. 신뢰도 할당모형의 평가는 차기 개발 함정용 디젤 엔진을 대상으로 하였으며, 다양한 신뢰도 할당 모형에 목표 신뢰도를 고려하여 신뢰도를 할당하고, 현재 운영하는 함정용 디젤 엔진의 자료를 바탕으로 시뮬레이션을 수행하여 운영유지비용을 최소화하는 신뢰도 할당 모형을 선정하였다. Reliability should be done from the initial stage of development to secure performance and safety of system. To establish and achieve target reliability of a system, reliability should be allocated into the subsystems. In the acquisition and development of a system, frequent failures will cause a negative effect on performing mission and occurs increasing operating cost. This study reviewed and evaluated the existing reliability allocation models using operation and maintenance costs to find the correlation between reliability allocation models and its operating cost. A target system reliability on the diesel engine to be developed for naval vessels is allocated into its subsystem based on the existing reliability allocation models. A selection methodology for reliability allocation models was made to minimize operating cost by using simulation based on the given operating diesel engine data for naval vessels.

잠수함 생존율 극대화를 위한 최적 이동경로 계획

김기태,박세훈,조성진,전건욱,Kim, Ki-Tae,Park, Se-Hoon,Cho, Sung-Jin,Jeon, Geon-Wook 한국국방경영분석학회 2010 한국국방경영분석학회지 Vol.36 No.3

잠수함은 수중에서 임무를 수행하며, 은밀성을 강점으로 하는 매우 위협적인 무기 체계이다. 하지만 잠수함 센서에 의해 탐지되거나 수면 위로 부상하여 노출될 경우 적으로부터 공격을 받을 수 있는 위협에 직면하게 된다. 본 연구는 적 수상함정의 탐색활동과 잠수함의 잠항능력을 고려하여 생존율을 극대화하는 최적의 이동경로를 계획하였다. 잠수함의 생존율을 극대화하기 위한 이동경로 계획 수리모형을 구축하고, ILOG CPLEX를 이용하여 수리모형을 검증하였다. 잠수함의 생존율을 보장하고, 목표지점으로 이동하기 위한 휴리스틱 알고리즘을 이용하여 이동경로, 이동 단위시간(거리), 생존율, 계산시간을 도출하였다. The submarine is very threatening and secretive weapon system that achieves missions under the sea. However, the submarine is faced with danger that can be attacked from the enemy when is detected by sensor or rose to the surface. This study will be planned optimal path to maximize the survival rate that considers submarine navigation capability in underwater and search activity of hostile warships. A mathematical programming model and a heuristic algorithm will be suggested in this study. The mathematical programming model is verified by using ILOG CPLEX. The submarine path, unit time(distance) of navigation, survival rate, and computation time is computed by using a heuristic algorithm.

Hybrid 유전자 알고리즘을 이용한 서비스 가능 시간대가 존재하는 차량경로문제

김기태 ( Ki Tae Kim ),전건욱 ( Geon Wook Jeon ) 한국경영공학회 2011 한국경영공학회지 Vol.16 No.2

The main purpose of this study is to find out the shortest path(minimize total travel distance) of the vehicle routing problem with possible service time windows. This study suggests a mathematical programming model and verifies the suggested mathematical programming model by using CPLEX 11.1. This study also suggests a hybrid genetic algorithm which considers the generation for an initial solution by random and saving algorithm, the process of solution improvement by 2-Opt. The suggested algorithm is compared by Solomon`s examples considering possible service time windows. We found the better solutions concerning total travel distance rather than best-known solutions in R/RC-type Solomon`s examples.

다품종 배달과 수거를 동시에 고려한 항공기경로문제

김각규 ( Gak Gyu Kim ),전건욱 ( Geon Wook Jeon ) 한국항공경영학회 2013 한국항공경영학회지 Vol.11 No.3

최근 역물류 관점의 물류 시스템 필요성이 대두되면서 배달과 수거를 동시에 고려한 차량경로 문제 (Vehicle Routing Problem with Simultaneous Deliveries and Pickups, VRPSDP)가 활발히 연구되고 있다. 하지만 기존 연구들을 보면 독립적재 공간이 필요한 여러 품종의 제약조건을 무게로만 한정함으로써, 항공 수송의 발달로 수많은 인원과 물자들이 동시에 배·수송되는 현실에서 이 수리모형의 적용은 한계가 있었다. 따라서 본 논문에서는 적재공간의 독립성을 고려한 항공기 경로문제(Aircraft Routing Problem, ARP)를 제시하여 모기지(depot)에 위치한 항공기가 각 수요지로 인원과 물품을 수송/배달하고, 수요지로부터 복귀/수거하는 독립적인 적재공간을 갖는 다품종(heterogeneous products) 문제에 대한 최적해를 구하는 수리모형을 제안한다. 본 연구에서는 수리적 최적해를 찾기 위하여 IBM에서 제공하는 소프트웨어 ILOG CPLEX 버전 12.4를 사용하였다. As generalization of the well-known traveling salesman problem (TSP), the vehicle routing problem (VRP) can be described as a problem to find the optimum pick-up or delivery routes from one or several depot(s) to a number of geographically scattered customers, given a set of constraints. An aircraft routing problem with heterogeneous products pick-up and delivery at the same time which is one of the special topics of vehicle routing problem is suggested in this study. It is a variation of the capacitated aircraft routing problem, in which both pickup and delivery tasks occur at customer`s locations simultaneously. The main objective is to design a set of minimum distance routes for the aircraft routing assignment with independent capacity for heterogeneous products. The past studies have mainly dealt with capacity as a weight constraint for heterogeneous products. However, this study classifies into independent categories of each capacity according to product characteristics. In order to solve the optimal solution of the suggested mathematical programming model, the ILOG CPLEX 12.4 provided by IBM company were used.