Ⅰ. 서 론
1. 연구의 배경 및 목적
전 세계적으로 지구온난화로 인한 환경문제가 심각한 위기로 인식되어지면서 리우 UN회의(1992 년) 이후 교토의정서(1997년) 및 발리로드맵(2007 년) 등 국제적인 논의가 활발히 진행되어왔다. 교토 의정서에는 세계 각국의 탄소배출량에 대한 규제를 담고 있고, 그 결과 현재 유럽탄소배출권거래소 (ECX: European Climate Exchange)에서 탄소배출권 에 대한 거래가 이루어지고 있다.
이와 같이 지구온난화로 인해 세계 각국에서는 전 산업분야에 걸쳐 이산화탄소 배출을 줄이고자 노력하고 있으며 2009년 11월 우리나라 정부도 2020년 국내 온실가스 배출량을 배출전망치(BAU) 대비 30% 감축하기로 결정하였다. 이에 따라 각 부 문별로 세부목표를 정하고 관리하는 ‘온실가스 및 에너지 목표관리제’를 도입하여 건물과 교통 등 비 산업 분야 위주로 온실가스 배출량 감축을 진행할 계획에 있다.
국내 에너지 부문 CO2 배출량의 약 20%를 차지 하는 수송분야의 ‘저탄소 녹색성장’ 실현을 위해서 는 전기자동차 보급 확산이 필수적이므로 정부는 저탄소 녹색성장 기본법(2010.04.14. 시행)의 제정 추진과 지속가능 교통물류 발전법(2009.12.10. 시행) 을 통해 친환경·비동력·무탄소 교통수단의 활성화 를 도모하고 있다.
2012년부터는 EU 지역 내 차량탄소배출량의 상 한치를 2012년에는 평균 130g/km, 2020년에는 95g/km의 탄소배출량 목표를 설정하고 있으나 국산 차의 대부분은 탄소배출량 수준이 130g/km를 초과 하여 국제적 기준에 부합하지 못하고 있어 전기자 동차에 대한 관심이 높아지고 있다. 이에 따라 2009년 10월 정부에서 “전기자동차 산업 활성화 방안” 마 련하고 2011년 말에 전기자동차 양산을 결정하는 등 전기자동차 보급 활성화를 위한 노력을 기울이 고 있다. 그러나 긴 충전시간과 배터리의 가격에 의 한 비싼 차량가격 (승용차의 경우 약 55%) 짧고 불 규칙한 운행거리와 부족한 충전인프라 등으로 인하 여 향후 전기자동차의 보급 확대는 매우 불투명한 상태이다. 이러한 단점을 해결하고 효과적으로 전 기자동차를 보급할 수 있는 방법 중 하나가 바로 BSS(Battery Swapping Stations)이다[5].
BSS는 배터리 교환 방식을 통해 전기자동차가 긴 충전시간을 소모할 필요 없이 짧은 시간 내에 배터리를 충전하고 이동할 수 있도록 하는 시스템 이다. 이러한 시스템을 대중교통, 특히 공공버스에 적용함으로써 보다 빠른 시간 안에 전기자동차를 보급, 확산시키는 것이 가능할 것으로 기대된다. 또 한 BSS에 설치되는 배터리 자동 교환-충전시설인 QCM(Quick Changing Machine)의 경우 정류소지점 에 지지구조물을 토대로 대부분의 기자재가 실제 정류소 이용객 사용공간과 분리된 정류소 상단부분 에 설치되어 시설 설치 및 운용에 무리가 없으며 전력을 사용하는 시설물의 특성 상 시설구조물에 VMS 등의 전력사용 교통시설과 운용을 병행할 수 있는 장점이 있다.
일반버스를 전기버스로 전환하여 버스 노선을 운영할 경우 전기버스가 중간에 멈추지 않도록 적 절한 위치에 충전시설을 구축할 필요가 있다. 전기 버스에 대한 충전시설은 버스 노선의 기·종점 및 기존 버스정류장에 추가로 설치하여 버스가 승객의 승·하차를 위해 정차할 때 신속하게 배터리를 교환 할 수 있게 구축해야 한다.
본 연구에서는 전기버스를 위한 배터리 자동교 환충전시설(BSS)의 위치선정 문제를 Set Covering Problem에 적용하여 해결하였다. 배터리 충전 시 최대 주행거리를 영향권으로 설정하였으며 메타 휴리스틱 기법인 그리디 알고리즘을 활용하여 전 기버스를 위한 배터리 자동교환충전시설 위치선정 알고리즘을 개발하였고 현재 운영 중인 서울시의 버스노선을 대상으로 실제 충전시설의 위치를 선 정하였다.
2. 연구의 내용 및 방법
전기버스를 위한 배터리 자동교환충전시설 위치 선정 문제의 경우 기존 정류장에 충전시설을 설치 한다는 점, 모든 충전시설 간 간격이 배터리 충전 시 최대 주행거리 내에 위치해야한다는 점 등을 고 려하여 가장 적합한 방법론은 Set Covering Problem 이라고 판단하였다.
Set Covering Problem의 경우 NP-Complete의 특성 을 가지고 있으며, 정수계획법(Integer Programming) 에 의한 접근법을 사용한다. 정수계획법에 의한 접 근은 최적해를 구할 수 있지만 노드의 수가 증가하 면 문제를 푸는 시간이 지수적으로 증가하므로 메 타휴리스틱 기법을 적용하여 전기버스를 위한 배터 리 자동교환충전시설의 설치 위치를 도출하였으며, 그리디 알고리즘과 시뮬레이티드 어닐링을 적용하 여 알고리즘을 개발하였다.
또한 실제 충전시설을 설치할 경우에는 충전시 설의 설치 위치뿐만 아니라 충전시설의 규모와 용 량을 고려해야 실제 설치 가능한 위치를 선정할 수 있다. 그러므로 기존 알고리즘의 개선을 통해 전기 버스를 위한 배터리 자동교환충전시설의 규모와 용 량을 고려하여 최적의 위치를 선정할 수 있는 새로 운 알고리즘을 개발하였다.
본 연구에서는 전기버스를 위한 배터리 자동교 환충전시설 위치선정 문제의 특성을 정리하고 이 문제를 해결할 수 있는 Set Covering Problem에 대 한 문헌 고찰을 통하여 유사 문제에 적용 가능한 방법론을 조사하였다. 또한 문제의 특성을 고려한 메타휴리스틱 알고리즘을 제시하였고, 실제 서울시 버스노선에 적용하여 실제 위치를 선정하였다.
Ⅱ. 문헌고찰
1. Set covering problem의 분석
기업은 경제활동을 위해 많은 지역에 지점을 개 설하여 많은 사람들에게 서비스를 제공하고 이윤을 극대화 하는 것이 목적이지만 동시에 불필요한 곳 에서의 지점 개설로 비용을 낭비하는 경우를 최소 화하여야 한다. 이러한 문제들을 일반적으로 위치설 정 모델링(location modeling) 문제라 하며 기업이 지 점을 개설하는 문제, 통신망에서의 기지국 설정 문 제뿐만 아니라, 특정 지역에서의 소방서나 응급센터 의 위치 설정 등이 대표적인 위치설정 문제들이다.
본 논문에서 다루는 Set covering problem은 위치 설정 문제의 가장 기본적인 형태이다. Set covering problem은 네트워크 전체 노드를 포함하는 최소 비 용의 시설 위치를 결정하는 문제이다.
Set covering problem의 경우 NP-Complete 문제로 서 일반적으로 정수계획법(Integer programming)을 통 하여 정확한 해를 구할 수 있다. 하지만 문제의 크기 가 커질수록 해를 구하는 시간이 지수적으로 증가한 다는 단점을 가지고 있다. 본 연구의 배경인 서울시 의 경우 분석대상인 정류장의 개수가 7146개이고 노 선별로 구분한 정류장의 수는 23458개이므로 이를 정수계획법을 통해 해결할 경우 해결 시간은 기하급 수적으로 증가하게 된다. 그러므로 본 연구에서는 휴 리스틱 방법론을 이용하여 최적해에 가까운 해를 찾 아가는 방법을 개발하였다. 또한 연구대상이 되는 배 터리 자동교체형 전기버스의 배터리 용량을 고려하 여 해당 배터리의 약 80%수준에서 충전 시 주행가능 거리인 16km를 영향권으로 설정한다.
2. Set covering problem과 관련된 문헌조사
기존 연구에서는 Set covering problem의 해결을 위해 다양한 휴리스틱 알고리즘이 제안되어 왔다.
대표적인 그리디 알고리즘(Greedy Algorithm)은 현재 상태에서 최선의 위치를 선택한 후 다음 상태 로 이동하는 과정을 반복함으로써 최적해에 근사한 값을 구하는 방법이다. 여기에서 최선의 선택이란 영향권 내에 포함되지 않은 모든 열들 중에서 가장 많은 행을 포함하는 열을 우선적으로 선택하는 것 을 말한다. 결국, 모든 행이 영향권 내에 포함되는 순간까지 이 과정을 반복함으로써 해를 얻는 것이 다. 그러나 특정 상황에서 가장 많은 행을 포함하는 열을 선택하는 것은 해당 상황에서는 최선의 선택 이지만 전체적으로 보면 최선이 아닌 결과를 가져 올 수 있다. 이런 문제 때문에 그리디 알고리즘의 경우 빠른 시간 안에 해를 얻을 수 있지만 지역 최 적해에 빠지기 쉬운 단점이 있다[11].
Michael J. Brusco 외 2명은 이러한 문제를 해결 하기 위해 시뮬레이티드 어닐링 알고리즘(Simulated Anealing Algorithm)을 기반으로 한 휴리스틱 방법 을 제안하였다[8]. 시뮬레이티드 어닐링 알고리즘 (Simulated Annealing Algorithm, SA)은 1983년 Scott Kirkpatrick, Gelatt and Vecchi 등에 의해 처음으로 소개된 방법론으로 금속공학의 담금질에서 착안점 을 얻어 고안된 메타 휴리스틱 기법이다. 시뮬레이 티드 어닐링 알고리즘은 연속적으로 해들을 생성하 고 한정된 수의 계산과정을 통해 최적의 해를 찾는 방법이다. 해공간에서 현재해 X 를 선택하고 X 의 이웃해 X ′을 얻어 이웃해로 이동하는 과정을 반복 함으로써 전체해공간을 탐색하여 이 탐색결과 근사 최적해를 얻는 것이다.
이현남 외 1명은 시뮬레이티드 어닐링 알고리즘 의 단점을 보완하고 보다 좋은 해를 얻기 위하여 개선된 시뮬레이티드 어닐링 알고리즘을 제안하였 다[3]. 위 연구에서는 시뮬레이티드 어닐링 알고리 즘의 탐색시간이 오래 걸린다는 단점을 보완하기 위해 유전자 알고리즘의 교차연산을 결합하고, 또 한 더욱 전역 최적해에 근접수렴하기 위하여 지역 탐색방법을 결합하였다.
또한 J.E. Beasley외 1명은 유전자 알고리즘 (Genetic Algorithm)을 적용하여 Set covering problem 을 해결하였다[9].
유전자 알고리즘(Genetic algorithm, GA)은 19세기 영국의 생물학자인 찰스 다윈이 주장한 생물진화론 에 영향을 받은 방법론이다. 이런 생물학적 진화과 정의 아이디어를 최적화 문제에 적용하여 개발한 것이 유전자 알고리즘이다. 다음 <그림 2>은 일반 적인 유전자 알고리즘의 흐름도이다.
자연계에 있는 생물의 진화 과정에서, 한 세대를 형성하는 개체들의 집합인 개체군(Population)을 중 에서 유전 형질이 우수한 개체들이 환경에 대한 적 합도가 높아 살아남을 확률이 높으며, 이렇게 살아 남은 개체들끼리 교배(교차) 및 돌연변이의 과정을 거쳐 다음 세대를 생성하면서 우수한 유전 형질을 유전하게 된다. 이러한 진화의 과정을 Set covering problem에 적용하면 하나의 생물 개체가 하나의 실 현가능해가 되고, 개체군은 실현가능해들의 군을 의미한다. 이러한 유전자 알고리즘은 지역해에 빠 질 가능성은 적지만, 유전자 표류현상(Genetic drift) 과 해의 조기수렴현상(Premature convergence)을 해 결하지 않으면 최적해로의 접근을 보장할 수 없다. 특히 문제의 크기가 크고 최적 위치의 수가 적을수 록 조기수렴현상이 두드러지게 나타난다.
강병천 외 1명은 유전자 표류현상과 조기수렴현 상을 해결하기 위한 방법으로 선형함수를 이용한 보정기법과 비선형함수를 이용한 보정기법을 적용 하였으며 비선형함수를 이용한 보정기법이 우수함 을 증명하였다[4].
Ⅲ. 전기버스를 위한 배터리 자동교환충전시설 위치 선정
1. 변수 정의 및 분석 대상 설정
Set covering problem을 전기버스 충전스테이션 위치선정 문제에 적용할 경우 변수는 다음 <표 1> 과 같다.
Xj의 경우 j번 정류소에 충전시설의 설치 여부 를 나타내며 충전시설을 설치할 경우 1, 설치하지 않을 경우 0으로 표현한다.
aij는 i번 정류소가 j번 정류소에 설치된 시설에 의해서 영향권 범위 내에 포함이 되는 경우 1, 포함 되지 않는 경우 0으로 표현함으로써 i번 정류소의 영향권 범위 내 포함 여부를 나타낸다.
fj의 경우 j번째 정류소에 시설이 설치되었을 경 우 드는 비용을 의미하며 현 문제에서는 시설의 설 치비용을 고려하지 않기 때문에 모든 f값을 1로 가 정한다.
r은 전기버스를 위한 배터리 자동교환충전시설 의 영향권 범위로 완충된 전기버스 배터리가 최대 로 이동할 수 있는 거리를 의미한다. 본 연구에서는 16km 이하 노선길이의 노선에 적용 운행하는 type 1 전기버스(배터리 1개 장착, 차고지 출발 후 최대 16km 이동 가능)와 16km 이상 노선길이의 노선에 적용 운행하는 type 2 전기버스(배터리 2개 장착, 차 고지 출발 후 최대 32km 이동 가능), 2가지 종류의 전기버스를 서울시 대상으로 운행하는 경우를 가정 하였으며, 버스의 종류에 관계없이 일반 정류장의 배터리 교환시설에서는 배터리 1회 교체 시 16km 의 최대 이동가능거리, 즉 영향권을 가진다. 영향권 에 대한 정의는 다음 <그림 3>과 같다.
본 연구에서는 전기버스를 위한 배터리 자동교 환충전시설의 위치선정을 수행하기 위한 분석 대상 으로 서울시를 통과하는 모든 노선을 선정하였다. 서울시를 통과하는 노선 중 광역버스를 제외한 버 스노선은 총 385개, 총 정류소 수는 8320개소로 각 버스노선의 차고지에는 충전시설이 설치가 되어있 다고 가정함으로써 전체 노선의 길이가 16km 이하 인 노선(즉 type1 버스종류 운행대상 노선)은 분석 대상에서 제외하였다. 그 결과 분석 대상이 되는 총 노선은 298개 노선이 선정되었으며 총 정류장 수는 7403개소이다.
2. 일반적인 Set covering model 적용
일반적인 Set covering model 적용 시 그리디 알 고리즘(Greedy Algorithm)은 전기버스를 위한 배터 리 자동교환충전시설의 위치 선정 문제를 가장 간 단하게 해결할 수 있는 방법으로 분석 절차는 다음 <그림 4>와 같다.
1) 영향권 범위 선정 및 정류소간 거리 측정
영향권 범위(r)는 완충된 전기버스 배터리가 최 대로 이동할 수 있는 거리로 본 연구에서는 16km를 영향권 범위로 설정하였다. 각 노선의 정류소가 충 전시설의 영향권 범위 내에 포함되는지 여부를 판 단하기 위해서는 분석 대상이 되는 각 정류소간 거 리를 도출하여 L matrix를 만든다. L matrix는 다음 <표 2>와 같다.
L matrix의 열 번호는 각 정류소를 나타내는 번 호이고 행 번호는 노선별 정류소를 나타내는 번호 이다. 즉 L11은 1번 정류소에서 A 노선의 1번 정류 소까지의 거리를 의미한다. 이런 방식으로 각 정류 소 간 거리를 나타내는 것이 L matrix이다.
2) 영향권 범위와 각 정류소간 거리 비교
도출된 L matrix를 영향권 범위와 비교하여 a matrix를 구축한다. 즉, j정류소에 설치된 충전시설 의 영향권 내에 i정류소가 포함될 경우 (r ≥ Lij) a 값은 1이 되고 포함되지 않을 경우 (r<Lij) a값이 0 이 된다. 이러한 방법으로 구축된 a matrix는 다음 <표 3>과 같다.
다음 <표 4>는 영향권 범위를 10으로 가정하였 을 때 정류소간 거리 비교를 한 예시이다.
3) 가장 많은 정류소를 포함하는 위치에 충전시설 설치
그리디 알고리즘은 가장 많은 정류소를 포함하 는 위치에 우선적으로 충전시설을 설치하는 방법이 므로 가장 많은 정류소를 포함하는 위치를 찾는 것 이 중요하다. 앞서 도출된 a matrix의 각 열의 합은 각 정류소가 포함하는 노선상의 정류소 개수를 나 타내므로 열의 합 중 가장 큰 값을 가지는 열의 정 류소를 충전시설 설치 위치로 선정한다. 다음 <표 5> 는 충전시설의 위치를 선정하는 방법을 나타내는 표이다.
<표 5>에서 Tj값은 a matrix 각 열의 합을 나타 내며 이 Tj값이 최대인 지점에 충전시설을 설치하게 된다.
4) 영향권 범위 내 포함된 정류소를 포함여부 고려 대상에서 제거
Tj값이 최대인 지점에 충전시설을 구축하게 되면 이미 설치된 충전시설로 인해 포함되는 노선상의 정류소들은 더 이상 포함 여부를 고려할 필요가 없 다. 그러므로 다음 충전시설의 위치를 선정할 때 이 정류소들을 제거하고 판단해야 한다. 다음 <표 6> 은 영향권 범위 내 포함된 정류소를 포함 여부 고 려 대상에서 제거하는 과정이다.
<표 6>에서 3번 정류소의 Tj값이 4로 가장 크기 때문에 3번 정류소에 충전시설을 설치하게 되면 A-3, B-1, B-2, C-1 정류소는 이미 3번 정류소에 의 해서 포함되기 때문에 <표 6>과 같이 A-3, B-1, B-2, C-1 정류소 각 행의 모든 a값을 0으로 전환한다. a matrix를 변환한 후 다시 Tj값이 최대인 정류소를 찾을 경우 1번 정류소가 선택된다. 이러한 과정을 반복하여 모든 a matrix의 값이 0이 될 때 노선 상 모든 정류소가 충전시설의 영향권 범위 내에 포함 이 되며 이 때 위치선정이 종료된다.
5) 알고리즘의 올바른 수행 여부 검사
그리디 알고리즘을 통해 선정된 충전시설이 노선 상 모든 정류소를 포함하는지 여부를 확인해야한 다. 이를 확인하는 방법은 a matrix를 이용하는 방법 과 해당 정류소에 충전시설을 설치하고 각 충전시 설 간 거리를 측정하는 방법이 있다. a matrix를 이 용하는 방법은 다음 <표 7>과 같다.
우선 충전시설이 설치된 정류소만으로 구성된 a matrix를 만들고 도출된 a matrix에서 행의 합이 0인 행이 존재하면 모든 노선 상 정류소를 포함하지 못 하므로 잘못된 해라고 판단한다. 즉, 모든 행의 합 이 0보다 크면 도출된 해는 노선 상 모든 정류소를 포함하므로 유효한 해라고 볼 수 있다.
또한 설치 위치로 선정된 정류소에 충전시설을 배치한 후 각 충전시설 간 거리가 16km보다 작으면 전기버스가 모든 노선을 멈추지 않고 운행할 수 있 다는 의미이므로 이 때 설치 위치를 유효한 해라고 판단한다.
6) 그리디 알고리즘(Greedy Algorithm)을 이용한 위치 선정 결과
서울시 통과 노선을 대상으로 하여 그리디 알고 리즘을 통해 선정된 충전시설 설치 정류소는 총 87 개소로 각 정류소는 다음 <표 8>과 같다.
이 때 분석 대상이 되는 서울시의 총 정류소 수 는 7403개소이며 그리디 알고리즘 수행 시 분석 결 과가 도출되는 시간66.67초(1분 7초)가 소요되었다. 그리디 알고리즘의 분석 결과를 각 노선마다 필요 한 충전시설을 16km 간격으로 설치했을 경우와 비 교한 결과는 다음 <표 9>와 같다.
전기버스를 위한 배터리 자동교환충전시설 설치 시 QCM 한 대당 처리할 수 있는 버스 교통량과 한 정류소에 설치 가능한 QCM 대수가 제한되어있기 때문에 한 정류소에서 배터리를 교환 가능한 횟수 에 한계가 있다. 위 표는 QCM 한 대당 처리할 수 있는 버스 교통량이 최대 15대라고 가정한 후 구한 QCM 설치 대수이다. 그리디 알고리즘 적용 시 각 노선별 16km 간격으로 설치할 경우보다 충전시설 을 설치하는 정류소의 수는 152개소가 적지만 실제 QCM 시설을 설치해야하는 수는 23대가 적어 비용 은 적게 들지만 감소비율은 그다지 높지 않다. 또한 그리디 알고리즘 적용 시 한 정류소에 최대 10대의 QCM을 설치해야 하는데 이는 현실적으로 시설을 구축하는데 무리가 있다. 그러므로 전기버스를 위 한 배터리 자동교환충전시설의 위치를 선정함에 있 어서 충전시설의 용량과 규모를 고려해야 한다. 본 연구에서는 일반적인 그리디 알고리즘을 개선하여 충전시설의 용량과 규모를 고려한 새로운 설치 위 치를 선정하였다.
3. 시설의 용량과 규모를 고려한 Set covering model 적용
일반적인 Set covering model을 통해 나타난 문제 점을 해결하기 위해서 시설의 용량과 규모를 고려한 새로운 모델을 개발하였다. 본 방법은 Set covering model의 일부 과정을 개선한 모델로 그리디 알고리 즘을 이용한 위치 선정 절차는 다음 <그림 5>과 같다.
개선된 Set covering model에서 정류소간 거리를 측정하는 부분과 영향권 범위와 각 정류소간 거리 비교를 통해서 L matrix와 a matrix를 도출하는 과정 은 일반 Set covering model과 동일하다.
1) 충전시설 설치 시 영향권 범위에 포함되는 노선 상 정류소 수 파악
기본적으로 그리디 알고리즘은 가장 많은 수의 노선 상 정류소를 포함하는 위치에 충전시설의 설 치해야 효과적이라는 가정에서 시설의 위치를 선정 한다.
본 연구에서는 충전시설 설치 시 영향권 범위에 포함되는 노선 상 정류소 수를 파악하기에 앞서 다 음 두 가지 가정을 설정하였다.
위 두 가지 가정을 바탕으로 각 정류소별 충전시 설 설치 시 포함 가능한 노선 상 정류소 수를 파악 할 경우 QCM 설치 대수에 따라 배터리 공급이 가 능한 전기버스의 수가 달라지기 때문에 포함 가능 한 노선 상 정류소 수가 다르게 나타난다. 일반적으 로 QCM의 설치 대수가 많을수록 더 많은 정류소를 포함 가능하게 되는데 이 때 주의해야할 점은 무작 정 많은 정류소를 포함한다고 최적의 위치가 아니 라는 것이다.
예를 들어 한 정류소에 QCM 3대를 설치할 경우 90개의 정류소를 포함하는 경우와 QCM 1대를 설 치할 경우 50개의 정류소를 포함하는 경우를 비교 하면 총 포함하는 정류소 수는 QCM 3대를 설치하 는 경우가 더 많지만 이 경우 QCM 1대당 30개의 정류소를 포함하기 때문에 QCM 1대를 설치하는 경우보다 더 비효율적이다.
이러한 이유 때문에 충전시설 설치 시 영향권 범 위에 포함되는 정류소 수를 파악하기 위해서는 각 정류소별 충전시설 설치 시 포함되는 총 정류소 수 가 아닌 각 정류소별 QCM 1대당 포함 가능한 정류소 수를 파악해야 하며 이러한 과정은 다음 <표 10>과 같다.
2) 충전시설 설치 위치 선정
충전시설의 설치 위치를 설정할 경우 QCM 1대 당 가장 많은 노선 상 정류소를 포함하는 위치가 가장 효과적인 위치이므로 이러한 지점을 찾아서 충전시설을 설치한다. 다음 <표 11>는 충전시설의 설치 위치를 선정하는 방법을 보여준다.
위 표를 보면 3번 정류소에 QCM 1대를 설치하 는 경우 가장 많은 15개의 정류장을 포함하기 때문 에 가장 효율적인 위치라고 할 수 있다. 그러므로 3 번 정류소에 QCM 1대를 설치하게 된다.
3) 영향권 범위 내 포함된 정류소를 포함여부 고려 대상에서 제거
충전시설의 위치와 QCM의 설치 대수를 결정하 면 영향권 범위 내 포함된 정류소를 포함 여부 고려 대상에서 제거해야한다. 기존의 그리디 알고리즘에 서는 충전시설 설치 지점의 영향권 범위에 포함되 는 모든 노선 상 정류소를 고려 대상에서 제거하였 지만 시설의 용량과 규모를 고려할 경우 영향권 범 위에 포함되는 노선만 선택적으로 제거해야한다. 영 향권 범위 내 포함된 정류소를 포함 여부 고려 대상 에서 제거하는 방법은 다음 <표 12>와 같다.
<표 12>와 같이 3번 정류소에 충전시설을 설치 할 경우 QCM의 용량 제한으로 인해 A 노선만 포 함이 가능하다. 그러므로 A 노선을 통과하는 정류 소는 더 이상 포함 여부를 고려할 필요가 없으므로 a matrix의 값을 0으로 변환한다.
4) 시설의 규모와 용량을 고려한 그리디 알고리즘 (Greedy Algorithm)의 위치 선정 결과
전기버스를 위한 배터리 자동교환충전시설의 규 모와 용량을 고려한 그리디 알고리즘을 수행한 결 과 총 173개소에 198대의 QCM이 설치되었다. 다음 <표 13>은 각 위치선정 방법 간 결과를 비교 분석 한 내용이다.
전기버스를 위한 배터리 자동교환충전시설의 규 모와 용량을 고려하여 그리디 알고리즘을 수행한 결과 각 노선마다 충전시설을 따로 설치할 경우보 다 총 QCM 설치 대수를 157대 감소시킬 수 있었다. 또한 1개 정류소에 최대로 설치할 수 있는 QCM 수 는 3대로 현실적으로 설치 가능한 수가 도출되었다.
4. 교통거점과 시설의 용량 및 규모를 고려한 Set covering model 적용
물리적․공간적 제약에 따라 배터리 교환 충전 시설 용량의 제약이 있는 일반 정류소 지점보다 공 간적 제약이 덜하고 위치적으로 주요 교통의 거점 의 되는 환승센터 지점 및 건립계획 지점을 교통거 점으로 선정한다. 선정된 교통거점은 설치가능한 충전시설의 규모제약이 없는 것으로 가정한다.
이는 중요 교통거점의 위치적 이점을 고려하고 정류장 배터리 교환충전시설의 설치지점과 설치 QCM 대수를 줄이는 것을 목적으로 개발하였다.
개선된 Set covering model에서 정류소간 거리를 측정하는 부분과 영향권 범위와 각 정류소간 거리 비교를 통해서 L matrix와 a matrix를 도출하는 과정 은 일반 Set covering model과 동일하다.
1) 교통거점 위치 설정
서울시 버스노선 대상 9개 교통환승센터 내 30개 버스정류장의 버스노선을 교통거점지점 대상으로 선정한다.
2) 용량제약 없는 거점지점 정류소 설정
9개 거점 30개 정류장을 대상으로 용량 제약이 없는 일반적인 Set covering model에 적용한 greedy Algorithm 기법을 이용하여 위치별 설치 규모를 산 정한다.
여기서 설치 규모라 함은 개별 교통거점별로 교 황형 충전시설의 보유 배터리규모를 나타낸다.
3) 거점지점에 의해 커버되는 네트워크를 제외한 버스 노선네트워크를 대상으로 정류소 배터리 교환형 충전시설 위치선정
거점지점에 의해 커버되는 노선 상 정류소를 제 외한 노선네트워크를 대상으로 시설의 용량 및 규 모를 고려한 Set covering model의 개선된 Greedy Algorithm 기법을 적용하여 충전시설의 위치를 선 정한다.
교통거점과 시설 용량 및 규모를 고려한 Set covering model의 경우, 정류소 충전시설의 설치 정 류소 수는 42지점 감소, 필요 정류소 QCM의 수는 52대 감소하였으나 전체적인 QCM 규모로는 2대분 량이 증가하였다. 결과 도출 시간 또한 16.6초의 감 소 개선이 나타냈다.
Ⅳ. 결론 및 향후 연구과제
1. 결론
본 연구에서는 전기버스를 위한 배터리 자동교 환충전시설의 적절하고 효과적인 위치를 선정하기 위한 알고리즘을 개발하였다. 현재 운영 중인 일반 버스를 전기버스로 전환하여 운영하기 위해서는 전 기버스가 운행 중간에 멈추는 것을 방지할 수 있도 록 적절한 위치에 충전시설을 구축하는 것이 필수 적이다. 전기버스를 위한 배터리 자동교환충전시설 의 위치선정 문제에 대한 특성을 분석한 결과 Set covering model을 적용하는 것이 효과적이라고 판단 하였다. Set covering problem은 적절한 장소에 시설 을 설치함으로써 최대한의 서비스를 제공하면서도 설치비용을 최소화하는 문제이다. 이러한 Set covering problem은 NP-Complete 문제로서 이 문제 의 해를 효율적으로 구하기 위해서 메타 휴리스틱 방법을 이용하였으며 알고리즘은 그리디 알고리즘 을 적용하였다.
또한 일반적인 Set covering model 적용 시 현실 성 없는 위치와 설치 규모가 도출되었기 때문에 전 기버스를 위한 배터리 자동교환충전시설의 규모와 용량을 고려한 개선된 Set covering model을 적용하 여 시설의 규모에 대한 문제를 해결하였으며, 추가 적으로 설치 지점의 공간적 제약이 상대적으로 적 고 교통의 요지가 되는 환승센터 9개 지점 30개 대 상 정류소를 교통거점으로 선정하여 그리디 알고리 즘의 단계적인 적용을 통해 결과를 도출하였다.
알고리즘 적용 결과 시설 용량 및 규모를 고려하 여 그리디 알고리즘 적용한 경우 충전시설을 각 노 선별 16km 간격으로 설치할 경우보다 157대의 QCM 설치 대수를 감소시킬 수 있었다. 추가적으로 교통거점을 고려하여 현실제약에 따른 추가적 모델 링을 수행한 결과, 시설 용량 및 규모를 고려하여 그리디 알고리즘 적용의 결과와 비교해서 QCM 설 치 규모 대수는 유사했지만 설치 지점 수는 42지점 의 감소가 있었다.
실제 각 지자체에 전기버스 충전 인프라를 구축 할 경우 단순히 노선별로 설치할 경우보다는 본 알 고리즘을 이용하여 효과적인 위치를 선정한다면 많 은 인프라 구축비용을 절감시킬 수 있을 것이다.
2. 향후 연구과제
본 연구는 교통거점을 제외한 설치 대상이 되는 모든 정류소가 동일한 환경을 가진다는 가정으로 연구를 진행하였다. 그러나 버스 정류소가 중앙차 선에 설치된 경우와 노변에 설치된 경우 설치 가능 한 QCM의 대수가 다르기 때문에 다양한 충전시설 설치 환경을 반영해야 한다. 이러한 분석이 가능하 기 위해서는 모든 정류소에 대한 설치 환경 조사가 이루어져야하며 이를 바탕으로 정류소마다 QCM 설치 가능 대수를 다르게 적용할 수 있는 알고리즘 의 개발이 필요할 것이다.
또한 본 연구에서는 전기버스 배터리 충전을 통 한 최대 이동 가능 거리를 16km로 설정하였으나 각 노선별 지형 특성에 따라 이동 가능 거리가 달라질 것이므로 각 노선별로 영향권 범위를 다르게 지정 할 수 있는 알고리즘을 개발할 필요성이 있다.
마지막으로 유전자 알고리즘과 같은 다양한 메 타 휴리스틱 방법론을 적용하여 충전시설의 설치 규모를 보다 최소화할 수 있는 방안을 찾는 연구가 요구된다. 특히 유전자 알고리즘의 경우 해의 조기 수렴 문제를 해결한다면 보다 효과적인 위치선정 알고리즘이 도출될 것으로 기대된다.
