### ※ 기업체와의 비밀유지동의서에 의한 비밀유지 의무로 인하여 개략적인 내용만 서술하였습니다. **1. 기업소개**  * 1985년 설립된 이후 대전광역시 전역과 계룡시에 도시가스를 공급하고 있는 종합 에너지서비스 주식회사 * 자본금 475억원, 연매출 4805억원 규모의 중견기업 ※ 2017년 10월, ㈜충남도시가스에서 ㈜CNCITY에너지로 상호를 변경함 **2. 문제배경 및 소개** * 도시가스의 안전한 관리를 위해 각 구역별 담당자가 매일 가스배관 매설지역을 순회점검 하고, 이벤트(굴착공사 확인, 민원신고 처리 등)를 해결하는 업무를 실시함. 이벤트의 발생지역과 시간이 매번 다르기 때문에, 이벤트 처리 후 점검해야 할 잔여배관들의 위치가 항상 달라지고, 현재는 잔여배관의 점검 순서를 담당자의 경험에만 의존해 결정 * 그래프 이론 등의 수학적인 원리를 이용해 잔여배관 순회점검의 최적경로를 구하는 알고리즘을 개발하여, 현재의 방법이 최선인지 확인하고, 더 효율적인 순회점검 방법을 찾고자 함 **3. 해결 과정** (2016년 4월 ~ 11월, 8개월) * 현재 위치와 잔여배관들을 입력하면, 이곳을 돌아 본사까지 돌아오는 최단경로를 출력하는 알고리즘을 개발함 * 그래프 이론에서의 Chinese Postman Problem, Minimal perfect matching 등의 원리를 활용하여 최단경로를 찾고, 이것을 지도상에 보여줌 **4. 성과 및 향후계획** * 개발된 알고리즘을 활용한 최적의 순회점검 경로 설정 가능성 확인