다차원 배낭 문제를 위한 정수계획법 기반 지역 탐색 기법

황준하(Jun-Ha Hwang) 한국컴퓨터정보학회 2012 韓國컴퓨터情報學會論文誌 Vol.17 No.6

정수계획법 기반 지역 탐색은 단순 언덕오르기 탐색을 기반으로 하는 지역 탐색의 일종으로서 기존의 지역 탐색과는 달리 이웃해 생성 시 정수계획법을 활용한다. 기존 연구 [1]에 의하면 정수계획법 기반 지역 탐색은 경영과학 및 인공지능 분야에서 많은 관심을 받아 온 다차원 배낭 문제를 해결하는 데 매우 효과적인 것으로 알려져 있다. 그러나 해당 연구에서는 OR-Library에 있는 다차원 배낭 문제들 중 규모가 가장 큰 문제들만을 대상으로 하여 정수계획법 기반 지역 탐색의 우수성을 검증하였다는 단점이 있다. 본 논문에서는 그 외의 문제들을 대상으로 정수계획법 기반 지역 탐색을 적용함으로써 보다 객관적으로 정수계획법 기반 지역 탐색의 우수성을 검증한다. 아울러 본 논문에서는 기존의 정수계획법 기반 지역 탐색이 단순 언덕오르기 탐색과 정수계획법을 결합한 것과는 달리 언덕오르기 탐색, 타부 탐색, 시뮬레이티드 어닐링과 같은 다른 지역 탐색 기법과 정수계획법을 결합하는 방안을 제시한다. 실험 결과, 정수계획법 기반 지역 탐색은 중소 규모의 다차원 배낭 문제들에 있어서도 기존의 가장 좋은 휴리스틱 탐색 기법에 비해 유사하거나 더 우수한 성능을 발휘함을 확인하였다. Integer programming-based local search(IPbLS) is a kind of local search based on simple hill-climbing search and adopts integer programming for neighbor generation unlike general local search. According to an existing research [1], IPbLS is known as an effective method for the multidimensional knapsack problem(MKP) which has received wide attention in operations research and artificial intelligence area. However, the existing research has a shortcoming that it verified the superiority of IPbLS targeting only largest-scale problems among MKP test problems in the OR-Library. In this paper, I verify the superiority of IPbLS more objectively by applying it to other problems. In addition, unlike the existing IPbLS that combines simple hill-climbing search and integer programming, I propose methods combining other local search algorithms like hill-climbing search, tabu search, simulated annealing with integer programming. Through the experimental results, I confirmed that IPbLS shows comparable or better performance than the best known heuristic search also for mid or small-scale MKP test problems.

혼합정수계획법을 이용한 발전부문 온실가스 감축 잠재력 평가

김용건,구윤모,김동우,이원종,양유경 한국환경정책평가연구원 2019 기후환경정책연구 Vol.2019 No.-

Ⅰ. 연구의 필요성 및 목적 □ 연구의 배경 및 필요성 ㅇ 우리나라는 2030년 온실가스 감축목표를 설정하고 이의 달성을 위한 감축로드맵을 이행 중에 있으나, 발전부문의 감축목표 및 이행계획의 구체성이 부족한 상황임 - 감축로드맵 수정안(관계부처합동, 2018, p.6)은 확정감축량 23.7백만 톤CO₂와 추가감축 잠재량 34.1백만 톤CO₂로 발전부문 감축 계획을 제시하고 있으나, 추가 감축잠재량에 대해서는 2020년 NDC 제출 전까지 결정을 보류함 - 국가 감축목표 달성을 위해서 관련 정책의 구체화가 필요함 ㅇ 발전부문 의사결정의 불확실성을 해소하고 국가 온실가스 감축정책의 투명성을 높이기 위해서는 감축 잠재력의 이행에 따른 경제적 부담에 대한 과학적 분석이 필요함 - 발전부문의 온실가스 감축 잠재력과 비용의 평가에는 화력발전소의 부하추종능력, 전력저장시설의 시간적 연결성 등에 대한 과학적 분석이 요구됨 - 현재까지 우리나라의 온실가스 감축 잠재력 분석은 시간적 해상도가 낮고 시간적 연결성이 결여된 선형계획법과 연산가능일반균형모형 분석 등에 한정되었음 □ 연구의 목적 및 방법 ㅇ 정수적 특성을 반영한 순차적 급전계획의 최적화 모형 개발 및 적용을 통해 발전부문 온실가스 감축 잠재력 및 감축비용을 과학적으로 평가하고 효율적인 국가 감축목표 이행을 위한 정책적 시사점을 제시하고자 함 - 혼합정수계획법이란 최적화 프로그램인 선형계획법의 확장된 개념으로 실수뿐 아니라 정수 형태의 변수를 포함하는 프로그램으로서 발전소 기동 및 정지 등 0-1 혹은 정수적 의사결정 문제를 수리 모형화하는 데 적합한 개념임 Ⅱ. 선행연구 현황 □ 해외에서는 신재생에너지의 보급 잠재력 분석에 신재생에너지의 변동성과 경직성을 세밀하게 반영한 급전결정모형이 활용되고 있음 ㅇ Bistline(2017)은 태양광, 풍력 등 신재생에너지가 대규모로 보급될 경우 전력계통에 미치는 영향과 비용 특성을 혼합정수계획법을 적용한 급전결정모형을 통해 분석함 ㅇ Abrell, Rausch, and Streitberger(2019)는 신재생에너지가 대규모로 보급될 경우 에너지 저장장치(양수 발전 및 ESS)의 적정 보급 용량을 혼합정수계획법을 적용한 급전결정모형을 이용하여 추정하고, 에너지 저장장치의 효과적인 보급 유인을 제공할 수 있는 정책수단을 제시함 □ 국내에서는 온실가스 감축정책의 효과를 분석하기 위해 선형계획법에 기초한 전원구성 모형과 연산가능 일반균형모형이 주로 활용되어 왔음 ㅇ 안영환(2017)은 온실가스 규제 강화에 따른 석탄발전소의 자산 가치 하락 정도를 선형계획법으로 분석함 ㅇ 김진태, 조철흥, 최동현(2019)은 최대부하요금 인상에 따른 경제적 파급효과 및 온실가스 배출 영향을 연산가능 일반균형모형을 이용하여 분석함 ㅇ 안재균(2018)은 혼합정수계획법에 기반한 급전결정모형을 활용하여 비용효과적인 저탄소 전력시스템의 구축을 위한 전력시장제도의 개선방안을 제시하였으나 온실가스 잠재력에 대한 분석은 수행되지 않음 ㅇ Shin et al.(2019)는 혼합정수계획법을 포함하는 다층적 연계 모델링을 통해 석탄발전소 가동률 감소를 위한 최적 급전계획을 유도하는 방법론을 개발하여 2020년에 대한 시범분석을 수행함 Ⅳ. 주요 가정 및 입력 자료 □ 주요 가정 ㅇ 시간 단위를 1시간 단위에서 2시간 단위로 단순화하고, 시뮬레이션 기간을 1년에서 2개월로 단축하여 현실적으로 모형이 해를 구할 수 있도록 문제를 단순화 ㅇ 설비예비력제약은 설비용량구성의 제약 만족 여부 점검 시에만 이용 ㅇ 자료 확보 및 계산상의 어려움으로 열간 기동비용만을 고려 Ⅴ. 시나리오 구성 및 분석 □ 기준시나리오는 『제8차 전력수급기본계획』상의 전원계획을 전제로 한 2030년 경제급전 결과이며, 정책시나리오는 다양한 탄소가격에 대해 연료사용에 따른 이산화탄소 배출계수를 적용하여 추가적인 변동비를 적용한 것임 ㅇ 탄소가격을 2만 5,000원/톤CO₂(CT1), 5만 원/톤CO₂(CT2), 7만 5,000원/톤 CO₂(CT3), 10만 원/톤CO₂(CT4)으로 하는 4개의 시나리오를 구성하고, 필요에 따라 추가적인 탄소가격 시나리오를 구성 □ 분석결과 ㅇ 탄소가격이 2만 5,000원(CT1), 5만 원(CT2), 7만 5,000원(CT3), 10만 원(CT4)으로 증가함에 따라 배출량이 1.8%, 26.7%, 47.9%, 51.0% 감소 ㅇ 석탄 발전의 비중이 기준시나리오 기준 46.2%에서 탄소가격이 5만 원(CT2)인 경우 24.7%로, 10만 원(CT4)인 경우 2.6%로 감소(가스 발전 비중은 26.7%, 48.8%로 증가) ㅇ 탄소가격 인상에 따른 배출량 감소율을 1만 원 단위 변화로 살펴본 결과, 탄소가격이 3만 원에서 4만 원으로 증가하면서부터 큰 폭의 배출량 변화가 시작되었으며. 4만원에서 5만 원으로 증가하는 구간에서 배출 감소율이 9.1%에서 25.9%까지 급격하게 증가함(그림 1 참조). 또한 탄소가격 인상에 따라 전력 공급비용도 증가함을 보임 ㅇ 기동비용 변화에 따른 영향은 배출량과 생산비용의 수준은 물론 탄소가격에 따른 변화 양상에서도 크지 않은 것으로 평가됨. 기동비용을 10배 증가시킬 경우 비용이 다소증가하는 영향이 있는 것을 제외하면 탄소가격 시나리오별 영향에 미치는 영향은 무시할 만한 수준임 ㅇ 열간 기동비용의 10배라는 가정하에 탄소가격 시나리오별 에너지 저장장치의 저장량 변화추이를 살펴본 결과, 저장장치의 역할은 탄소가격이 높아짐에 따라 낮아지다 일정 수준이 지나면 다시 커지는 경향을 보임 ㅇ 출력에 따른 효율변화를 나타내는 비용특성함수를 반영할 경우, 2차식에 대해 구간선형함수로 근사하여 혼합정수계획법 문제로 정식화하여 시뮬레이션을 수행함. 탄소가격 2만 5,000원(CT1), 5만 원(CT2), 7만 5,000원(CT3) 시나리오에서의 이산화탄소 배출량 감소율은 2.6%, 26.1%, 47.2%로 비선형 출력특성함수를 반영하지 않은 경우의 시뮬레이션 결과인 1.8%, 26.7%, 47.9%와 유사한 경향을 보임. 비용(세금 제외)에 있서도 탄소가격 시나리오별로 1.4%, 11.3%, 24.8%의 감소율을 보여 비선형 출력특성 함수를 반영하지 않은 경우의 0.4%, 11.8% 및 25.4%와 큰 차이 없는 것으로 평가됨 ㅇ 720개 시간 구간을 대상으로 최소 가동시간과 최소 정지시간 제약을 적용할 경우, 탄소가격에 따른 감축 잠재력을 살펴본 결과, 이산화탄소 배출량의 변화율이나 비용 상승률이 최소 가동·정지 시간을 반영하지 않은 경우와 비교해 작은 차이를 보임 ㅇ 시나리오별·기간별(1년을 2개월 단위로 6개 기간으로 구분) 석탄 및 LNG 발전량을 살펴본 결과 탄소가격 2만 5,000원 및 5만 원일 때의 배출 감소율은 1년 전체기준 2.7% 및 27.1%로 초기 1,440시간 기준 1.8%, 26.7%와 다소 차이를 보이나 1년 전체를 대표하는 데 큰 무리가 없는 것으로 판단됨 Ⅵ. 결론 및 정책 제언 □ 발전부문의 2030년 국가 온실가스 감축 목표 달성을 위해서는 4만 원/톤CO₂ 이상의 탄소가격이 요구될 전망임 ㅇ 발전부문은 국가 전 부문에 걸친 수요 관리 등의 효과를 제외하고도 2030년 기준 온실가스 배출량을 9.5~23.1% 감축하여야 하며, 이러한 감축을 유도하기 위해서는 4만~5만원/톤CO₂의 탄소가격이 요구됨 □ 탄소가격 3만~7만 원/톤CO₂ 범위에서 발전부문 총 배출의 45%에 상당하는 감축량이 발생할 수 있으며, 발전부문이 배출권 시장의 수급 균형에 결정적인 영향을 미칠 것으로 평가됨 ㅇ 배출권 가격 3만~7만 원 범위에서 발전부문이 연간 1억 톤 수준의 배출권 공급 잠재력(수요 감소 요인)을 담당할 전망임 □ 배출권 가격에 대한 전력시장 반영이 효과적으로 이루어지지 못할 경우 배출권 가격의 심각한 왜곡 현상 발생이 우려됨 ㅇ 배출권 순 매입비용을 평균하여 변동비에 반영할 경우, 동일한 전력수요 만족을 위한 공급비용만 증가시키고 이산화탄소 배출량마저 증가시키는 정반대의 악영향을 초래할 가능성이 높음. 배출권 가격 자체가 기회비용 개념으로 변동비에 반영되어야 하며 이에 따라 급전 우선순위가 결정되어야 함. 무상할당 등에 따른 매몰비용(sunk cost)은 별도의 정산 절차를 통해 발생주의 원칙에 따라 회계적으로 처리될 필요가 있지만, 이러한 매몰비용이 급전 의사결정의 효율성을 훼손하는 역할을 하도록 이용되어서는 안 됨 ㅇ 배출권 초기할당의 유상 경매는 발전부문 원가 상승 영향을 크게 증가시킬 수 있음. 전기의 간접배출량 규제가 병행될 경우 발전부문 직접 배출에 대한 무상할당 유지 필요성이 높음 Ⅰ. Background and Aims of Research □ The study developed a Mixed Integer Linear Programming (MIP) model to evaluate CO₂ mitigation potential in the power sector of Korea. Based on the current capacity plan of the government, we applied the MIP model to find the optimal dispatch (unit commitment) of power units for various carbon pricing scenarios. ㅇ The Korean government set a mid-term GHG mitigation target of 37 percent reduction compared to BAU (Business-As-Usual) emissions in 2030. The power sector is responsible the lion’s share of the reduction burden but the exact amount of its reduction goal is yet to be finalized. Ⅱ. Analysis of Results and Conclusion □ We found out that a carbon price of around 30,000~40,000 Won/tCO₂ triggers a significant reduction of GHG emissions by way of substitution from coal to natural gas. A carbon price of 60,000 Won/tCO₂ can reduce around 40 percent of CO₂ emissions in the power sector. ㅇ To attain solutions in a reasonable amount of time, we ran simulations for the first two months of 2030, aggregating two hours into a single unit of time. We verified, however, that the solution from the two-month time horizon is quite similar to a full-year simulation. We found out that a simulation with an even smaller time horizon of 20 days resembles the full-scale optimization quite well. □ The MIP model for the power sector unit commitment problem has the potential to be applied to evaluate environmental dispatch mechanisms that consider the short-term regional status of air pollution, such as PM concentration, in setting priorities of power units. We can devise an efficient environmental dispatch mechanism as such that maximizes the environmental benefits and minimizes the supply costs at the same time.

혼합정수선형계획법을 이용한 지구관측위성의 촬영 임무 계획 모델링 연구

이기문(Kimoon Lee),김동진(Dongjin Kim),정대원(Daewon Chung),이선호(Seonho Lee) 한국국방우주학회 2023 한국국방우주학회지 Vol.1 No.1

연구의 목적은 지구관측위성의 촬영 임무 계획 문제를 효과적으로 모델링하는 방법을 연구하는 것이다. 이를 위해 혼합정수선형계획법을 이용하여 위성의 촬영 임무 문제를 모델링하였으며, 그 과정에서 정의한 의사결정변수, 목적함수, 그리고 여러 제약조건들을 구체적으로 설명하였다. 모델링 검증을 위해 본 연구팀에서 개발한 수정된 동적계획법을 이용하여 수치 시뮬레이션을 수행하였다. 테스트 시나리오별 임무 계획결과를 도출하였고, 그 결과 위성의 촬영 임무 문제가 혼합정수선형계획법을 통해 효과적으로 모델링되었음을 입증하였다. The study aims to investigate effective methods for modeling the imaging mission planning problems for Earth observation satellites. To achieve this, we model the satellite imaging mission problem using Mixed-Integer Linear Programming(MILP) and provide a detailed explanation of the decision variable, objective function, and various constraints defined in the process. Numerical simulations for validating the proposed model are conducted using a modified dynamic programming algorithm. The mission planning results for various test scenarios are derived, and the analysis results demonstrate that the satellite imaging mission problem is effectively modeled through MILP.

집합 커버링 문제를 위한 정수계획법 기반 지역 탐색

황준하(Jun-Ha Hwang) 한국컴퓨터정보학회 2014 韓國컴퓨터情報學會論文誌 Vol.19 No.10

집합 커버링 문제는 대표적인 조합 최적화 문제들 중 하나로서 n개의 열로부터 일부를 선택하여 m개의 행을 커버하되 비용을 최소화하는 문제로 정의된다. 본 논문에서는 집합 커버링 문제를 해결하기 위한 정수 계획법 기반 지역 탐색의 적용 방안을 제시하고 있다. 정수계획법 기반 지역 탐색은 이웃해를 탐색하여 현재해를 반복적으로 개선하는 지역 탐색 기법의 일종으로서 이웃해를 생성하기 위한 알고리즘으로 정수계획법을 사용한다. 본 논문에서 제시한 기법의 효과를 검증하기 위해 OR-Library의 테스트 데이터를 대상으로 실험을 수행하였다. 실험 결과, 모든 테스트 데이터에 있어서 정수계획법 기반 지역 탐색을 통해 지금까지 알려진 가장 좋은 해를 탐색할 수 있었다. 특히 4개의 테스트 데이터에 대해서는 지금까지 알려진 가장 좋은 해보다 더 좋은 해를 도출할 수 있음을 확인할 수 있었다. The set covering problem (SCP) is one of representative combinatorial optimization problems, which is defined as the problem of covering the m-rows by a subset of the n-columns at minimal cost. This paper proposes a method utilizing Integer Programming-based Local Search (IPbLS) to solve the set covering problem. IPbLS is a kind of local search technique in which the current solution is improved by searching neighborhood solutions. Integer programming is used to generate neighborhood solution in IPbLS. The effectiveness of the proposed algorithm has been tested on OR-Library test instances. The experimental results showed that IPbLS could search for the best known solutions in all the test instances. Especially, I confirmed that IPbLS could search for better solutions than the best known solutions in four test instances.

비선형정수계획법을 이용한 운행전략에 따른 열차운영계획 수립

김기현,서선덕 대한교통학회 2002 대한교통학회지 Vol.20 No.7

Scheduling of regional trains can be developed with many different objectives, such as views of operators, transport users or society as a whole. Planning goals of the society usually determines which perspective should prevail. Different perspec- tives produce different rail operating plans and the results are not usually comparable. Therefore, it is imperative to devise all possible rail operating plans with different perspectives and compare them objectively to select the best alternative for the society. In Korea, a high speed rail HSR service is planned for 2004 and some of the existing line are shared with HSR. It is necessary to include HSR in developing operation plans for existing rail. In this study, three rail operating plans were developed with three different objectives, i.e. cost and time minimization, and profit maximization with mathe- matical integer nonlinear programming(MINLP). The models were applied for the Seoul-Busan corridors and Seoul-Mokpo corridors. Operation plans developed were evaluated with various measure of effectiveness, that is, passenger- km, passenger-hour, trips. They were compared with alternatives which reflect current operating patterns. Further research issues were also identified. 열차운영계획은 수송수요 산정, 운행노선계획, 열차시각표 작성, 기관차 및 인원의 할당 등 광범위한 내용을 포괄하고 있으나, 본 논문에서는 계획의 초기단계에서 결정 가능한 운행노선계획을 대상으로 범위를 설정하였다. 운영목표에 따른 전략은 사용자, 운영자, 사회전체의 입장에서 고려될 수 있는데, 이러한 전략에 의해 운행될 수 있는 열차운행패턴을 운영비용의 최소화, 통행시간의 최소화, 운영자 수익의 최대화 모형으로 해결하고자 하였다. 2004년 이후에 운행이 예상되는 고속철도/기존철도는 운영계획의 변경이 예상되는바, 상기의 목표에 따라 열차운영패턴을 작성하여, 개발된 효과척도의 적용을 통해 정책적인 적용가능성을 평가하였으며 기존 계획된 철도청의 운영계획과도 아울러 비교, 최적대안을 선정하였다. 본 고에서는 수리계획모형인 비선형정수계획모형(MINLP)으로서 국내 철도망에 부합하는 운영계획을 작성하였으며, 이에 따른 열차-km는 수익최대화 모형, 인-km는 철도청의 열차운영계획이 가장 많은 것으로 나타났다. 인-hour는 수익 최대화 모형과 통행시간 최소화 모형이 가장 적은 것으로 나타났는데, 이는 장거리 노선의 편성이 증가된 것으로 사료된다. 이러한 결과를 산출함에 있어, 어려운 점은 각 구간의 기하급수적 증가, 결정변수의 초기값 선정 등이 있으나, 그동안 연구된 각종 경험적 기법의 적용과 실제 편성 가능한 변수의 적용을 통해 이를 해결하였다. 추후, 설정된 모형의 비교에 적합한 효과척도의 개발과 전국적으로 사례구간의 확장 및 모형의 최적대안 선택 시 효과척도의 가중치에 대한 연구가 필요할 것으로 사료된다.본 논문은 과학기술부(한국과학재단)에서 지원한 첨단도로연구센터의 연구수행 결과입니다.

비선형 최적화 문제의 해결을 위한 정수계획법과 이웃해 탐색 기법의 결합

황준하(Jun-Ha Hwang) 한국컴퓨터정보학회 2009 韓國컴퓨터情報學會論文誌 Vol.14 No.2

정수계획법은 조합 최적화 문제의 최적해를 매우 효과적으로 탐색할 수 있는 기법인 반면에 대상 문제가 선형적으로 표현되어야만 적용이 가능하다는 단점이 있다. 본 논문에서는 정수계획 법의 뛰어난 탐색 능력과 이웃해 탐색 기법의 유연성을 결합함으로써 비선형 최적화 문제를 효과적으로 해결하는 방안을 제시하고 있다. 먼저 1단계에서는 주어진 문제로부터 선형적으로 표현 가능한 부문제만을 대상으로 정수계획 법을 적용한다. 2단계에서는 전체 문제를 대상으로 이웃해 탐색 기법을 적용하되 1단계의 결과를 초기해로 설정한 후 탐색을 수행한다. 비선형 최대 커버링 문제를 대상으로 한 실험 결과, 이와 같은 간단한 결합만으로도 이웃해 탐색 기법만을 적용했을 때보다 훨씬 좋은 해를 도출할 수 있음을 확인하였다. 이는 기본적으로 정수계획법의 탁월한 성능에 기인한 것으로 판단된다. Integer programming is a very effective technique for searching optimal solution of combinatorial optimization problems. However, its applicability is limited to linear models. In this paper, I propose an effective method for solving a nonlinear optimization problem by integrating the powerful search performance of integer programming and the flexibility of neighborhood search algorithms. In the first phase, integer programming is executed with subproblem which can be represented as a linear form from the given problem. In the second phase, a neighborhood search algorithm is executed with the whole problem by taking the result of the first phase as the initial solution. Through the experimental results using a nonlinear maximal covering problem, I confirmed that such a simple integration method can produce far better solutions than a neighborhood search algorithm alone. It is estimated that the success is primarily due to the powerful performance of integer programming.

Power-Delay Product Optimization of Heterogeneous Adder Using Integer Linear Programming

곽상훈(Sang-Hoon Kwak),이정근(Jeong-Gun Lee),이정아(Jeong-A Lee) 한국컴퓨터정보학회 2010 韓國컴퓨터情報學會論文誌 Vol.15 No.10

본 논문에서는 이종가산기구조에 근거한 이진가산기의 전력-지연시간곱의 최적화 방법론을 제안한다. 정수선형 계획법(Integer Linear Programming)에 의해 이종가산기의 전력-지연시간곱을 공식화하였다. 정수선형계획법의 사용을 위하여 최초의 전력-지연시간곱의 비선형수식을 선형수식으로 변환하는 기법을 채택하였다. 또한, 제안된 방법이 전력지연시간곱(Power-Delay Product)의 척도에서 기존가산기와 비교해 우월함을 실험결과를 통해 확인하였다. In this paper, we propose a methodology in which a power-delay product of a binary adder is optimized based on the heterogeneous adder architecture. We formulate the power-delay product of the heterogeneous adder by using integer linear programming(ILP). For the use of ILP optimization, we adopt a transformation technique in which the initial non-linear expression for the power-delay product is converted into linear expression. The experimental result shows the superiority of the suggested method compared to the cases in which only conventional adder is used.

잠수함 지원업무 요구일정과 부두 가용자원을 고려한 선석할당계획

최지원(Ji-Won Choi),최인찬(In-Chan Choi) 한국항해항만학회 2020 한국항해항만학회지 Vol.44 No.6

His paper looks more closely at the Republic of Korea’s (ROK) Navy submarine berth-allocation strategies, with the study’s results ultimately resulting in the proposition of an integer programming model. Current submarine berth-allocation planning problems include the need for more minimal berth-shifting and general support service failures, as a lack of efficient submarine berth-allocation often leads to submarines unable to receive the support service they need due to the inadequacy of their assigned berths. Currently, the ROK Navy allocates berths by only taking available reserve resources and the full-capacity limits of support services into account. This paper expands upon this strategy, and proposes a model which would allow for submarine berth allocation planning to also take submarine support service scheduling into account, allowing for more efficient and timely submarine servicing. This proposed model in turn minimizes berth shifting, support service failures, and allows for full coordination with the submarine support service request schedule. The construction of this model was carried out through data gathered on the ROK Navy’s fleets and forces, allowing for a more nuanced analysis of existing issues with submarine berth-allocation planning. 본 논문은 현재 한국 해군 잠수함 선석할당방법을 반영하여 기존의 잠수함 선석 할당계획문제를 확장하고 해당문제를 해결하는 정수계획모형을 제안한다. 기존의 잠수함 선석 할당계획 문제는 정박 중 선석 이동과 지원업무 실패를 최소화하면서, 잠수함이 필요한 지원업무가 가능한 선석에 잠수함을 할당하는 것이다. 반면, 한국 해군에서는 선석이동과 지원업무실패 최소화뿐만 아니라 부두 가용자원을 고려하여 잠수함이 요구하는 지원업무의 일정을 최대한 보장하면서, 선석을 할당한다. 따라서 본 논문은 한국 해군의 운용상황에 맞게 기존의 잠수함 선석 할당계획 문제를 확장하고, 부두가용자원의 특징과 잠수함 지원업무 일정의 조율을 포함하는 모형을 제시한다. 제안하는 모형은 선석 이동 횟수, 지원업무 지원 실패 횟수, 잠수함 지원업무 요구 일정 조율 횟수를 최소화하는 것을 목적으로 한다. 본 모형의 검증을 위해서 한국 해군의 상황을 바탕으로 고려한 가상의 데이터로 실험을 수행하여 기존의 잠수함 선석 할당계획 문제와 비교·분석한다.

부유식 해상풍력발전 유지보수 계획 최적화 모형 개발

상민규(Min-Gyu Sang),이남경(Nam-Kyoung Lee),신용혁(Yong-Hyuk Shin),이철웅(Chulung Lee),오영진(Young-Jin Oh) 한국컴퓨터정보학회 2021 韓國컴퓨터情報學會論文誌 Vol.26 No.12

본 연구에서는 부유식 해상풍력발전의 운영 및 유지보수에 필요한 체계적인 정비계획 수립을 위해 최적화기법을 활용한 수리 모형을 제안하고자 한다. 주간 단위로 선박과 기술자를 운용하는 계획정비와 고장정비 작업의 배정에 혼합정수계획법(Mixed Integer Linear Programming, MILP)을 도입하였다. 본 연구의 최적화 모델을 활용한 사례연구에서는 선박과 기술자의 투입 규모가 유지정비 비용에 미치는 영향을 확인하였으며 1년간 정비계획 수립에서 더 나아가 정비작업별 상세스케줄링까지 연계되는 단계적 최적화 방법론을 함께 제시하였다. 세부적으로는 기상 데이터와 정비 데이터를 활용한 발전량 손실을 비가동 비용으로 반영하여 정비 우선순위를 선정하였으며, 이를 통해 국내 실정에 맞는 해상풍력단지의 유지보수 전략을 제시할 수 있을 것으로 기대한다. In this paper, we propose operations and maintenance (O&M) planning approach for floating offshore wind farm using the mathematical optimization. To be specific, we present a MILP (Mixed Integer Linear Programming that suggests the composition of vessels, technicians, and maintenance works on a weekly basis. We reflect accessibility to wind turbines based on weather data and loss of power generation using the Jensen wake model to identify downtime cost that vary from time to time. This paper also includes a description of two-stage approach for maintenance planning & detailed scheduling and numeric analysis of the number of vessels and technicians on the O&M cost. Finally, the MILP model could be utilized in order to establish the suitable and effective maintenance planning reflecting domestic situation.

자동화 컨테이너 터미널에서 수직형 블록의 이적작업을 위한 할당 및 작업순서

배종욱(Jong-Wook Bae),박영만(Young-Man Park),김갑환(Kap Hwan Kim) 한국항해항만학회 2006 한국항해항만학회지 Vol.30 No.6

이적작업은 적하작업과 반출작업을 신속하게 처리하기 위해 자동화 컨테이너 터미널에서 중요하게 고려하는 운영 전략들 중의 하나이다. 이는 ATC(Automated Transfer Crane) 의 운반시간과 재취급 작업시간을 줄이기 위해 장치장 블록에 산적되어 있는 컨테이너들을 재배치하는 작업이다. 본 논문은 가능한 컨테이너 이동을 최소화하면서 한 수직형 블록 내에 장치된 컨테이너들의 배치 형태를 바람직한 배치 형태로 전환사키기 위한 이적계획 문제를 다룬다. 이 문제는 선후관계를 가지는 2개의 하위 문제 즉, 장치위치 할당문제와 장비 작업순서 문제로 분할된다. 장치위치 할당문제는 운반시간의 관점에서 현재 장치되어 있는 컨테이너들 중에서 어떤 컨테이너를 어느 베이에 옮길 것인가를 결정한다. 이의 결과를 가지고 장비 작업순서 문제는 장치 공간의 제약을 고려하여 ATC 의 이동시간을 최소화하는 작업순서를 정한다. 본 연구에서는 정수계획법과 동적계획법을 이용하여 각 하위문제를 모형화 하였다. 제안된 모형을 이용하여 이적계획 과정을 설명하기 위한 예제를 제시하였다. Remarshalling operation is one of the operations considered important in an automated container terminal to perform quickly loading operations and delivery operations. It arranges the containers scattered at a verticla yard block in order to reduce the transfer time and the rehandling time of ATC(Automated Transfer Crane)s. This paper deals with the remarshalling planning problem minimizing the weighted operation time. This problem can be decomposed into 2 subproblems, storage space assignment problem and operation sequencing problem Storage space assignment problem decides to where containers are transported in terms of transportation time cost... with results of a previous subproblem, operation sequence problem determines the ATC operation sequence, which minimizes the dead-heading of ATC This study formulates each subproblem with mixed integer program and dynamic program To illustrate the proposed model, we propose an instance to explain the process of remarshalling planning.