최적화 해법을 통한 네트워크 관경 결정문제 해법 개발

Abstract

상수도 관망 설계에 대한 연구는 주로 관망 레이아웃 설계와 관망 관경 결정문제에 집중되어 있다. 본 논문은 관망 네트워크의 레이아웃이 주어졌을 때 각 관의 관경을 결정하는 문제를 다룬다. 관, 펌프, 탱크, 밸브 등 관망의 구성요소들을 설치 할 때 관이 전체 비용 중 차지하는 비중이 큰 만큼 최적 관경에 의한 비용 감소 효과를 기대할 수 있기 때문이다. 네트워크 관경 결정문제는 관의 용량을 결정하는 문제이기 때문에 상수도 관망에만 국한되지 않고 가스, 오일, 통신까지 적용될 수 있다. 이때 보다 현실적인 관 설치 비용을 산출하여 효과적으로 관 설치 비용을 감소시킨다. 설치 가능한 관들의 관경은 이산적으로 주어지고 비선형성을 갖는 에너지 보존 제약식에 의해 네트워크 관경 결정문제는 비선형 이산 최적화 문제에 속한다. 관망 토플로지는 나무 구조라고 가정하고 미래의 발생 가능한 수요를 만족하는 관경을 결정한다. 이때 관망의 공급지는 유일하다는 가정 하에 네트워크 관경 결정문제는 다수의 배낭 제약식과 할당 제약식을 갖는 선형 정수 최적화 문제가 된다. 본 논문에서는 분지한계법과 분지절단법을 사용하여 최적 관경을 구하고 선형 완화 기법, 휴리스틱 기법, 그리고 라그랑지안 기반 휴리스틱 기법을 사용하여 최적해에 가까운 관경을 탐색한다. 제시한 방법론들을 실제 존재하는 관망에 적용하여 해법의 타당성을 비교해본다.