크리티컬 패스를 활용한 에너지-흐름 네트워크 문제의 해법 개발

Abstract

에너지-흐름 네트워크 문제는 마디 간 에너지 차이가 호의 흐름을 발생시키는 네트워크 상에서 흐름균형, 에너지균형, 흐름 및 에너지 상하한 등의 제약조건을 만족시키면서 비용함수를 최소화하는 문제를 의미한다. 본 논문에서는 다양한 현실문제를 포함하는 에너지-흐름 네트워크 문제를 수리적으로 정의하고 그 문제가 NP-Hard에 속함을 보인다. 그리고 몇 가지 관찰을 통해 하한과 가능해를 동시에 제시하는 알고리듬을 제안한다. 몇 가지 문제에 적용한 결과 실험적으로는 대체로 하한과 아주 가까운 해를 출력한다는 사실을 확인했다.

Energy-Flow network problem is the problem that minimizes total energy cost with flow-balance, energy balance and upper and lower bound of energy and flow constraints. In this paper, we de칗e the E-F network problem which includes various problems in 칎ld such as water distribution problem and gas pipeline problem. The problem is NP-hard. We present the Critical Path algorithm which is faster than the most common algorithm and print out the feasible solution and lowerbound of objective. The results show that the proposed method achieves lowerbound-close solution.