1. 서 론

1.1 연구배경 및 목적

전 세계적으로 자원고갈과 대기환경 보존을 위한 요구 로 친환경차 중 하나인 전기차에 대한 관심이 급증하고 있으며 유럽과 미국을 중심으로 시장 확대가 이루어지고 있다. 특히 글로벌 에너지소비의 1/5를 차지하는 수송부 문은 전기차 보급으로 온실가스 배출 감축, 대기오염 개 선, 에너지안보향상에 상당한 기여를 할 수 있다[9]. 2000 년대에 들어서 전 세계적인 환경규제의 강화와 고유가에 현실적으로 대응하고 지역별로 차별화되는 소비자들의 요구를 충족시키기 위하여 자동차 업계의 전기차 개발과 다양한 모델이 출시되면서 본격적인 대량 생산이 이루어 지고 있다. 이에 따라 2015년 기준 신차 시장에서 전기차 판매비중은 0.62%(56만대)로 연 74% 성장함으로써 초기 시장이 형성되었다고 볼 수 있으며, 누적판매대수는 약 131만 대를 기록했다.

국내의 경우 정부의 전기차산업 육성과 대중화 지원 의 일환으로 다양한 세제지원을 마련하고 있다. 2016년 까지 누적보급대수가 11,767대로 급격하게 증가하고 있는 추세이며 2017년에는 30,000대, 2020년까지 누적 200,000 대를 목표로 보급할 예정이다. <Table 1>은 환경부의 전 기차 충전기 보급 실적으로 2016년 기준 491기의 급속충 전기가 설치되어 있다. 나아가 2017년 말까지 710기의 급속충전기를 추가 보급하고 2020년까지 서울과 제주에 2km당 1기의 공공 급속충전기를 설치함으로써 전기차 상용화를 위한 충전인프라 환경수준을 끌어올릴 계획이 다. 전기차 충전소는 도로 운행 중 긴급 충전에 대비한 비상용 목적으로 설치한다는 점에서 공공재적 성격이 강 하다. 공공재는 공급수준에 따라 지역사회 후생의 하락 으로 이어질 수 있기 때문에 자원배분의 효율성과 지역 균형개발을 강조한다. 이러한 관점에서 전기차의 본격적 인 민간보급에 맞추어 전국 단위의 공공 충전소에 대한 중장기적인 구축 방안이 요구되고 있다. 이를 위해 전기 차 충전소의 입지선정은 운전자의 운행패턴에 따른 충전 소 수요변화, 전기차의 주행가능거리, 일평균 주행거리, 서비스의 편의성이 고려되어야 뿐만 아니라 편익의 형평 성을 제고할 필요가 있다.

이에 따라 본 논문에서는 부하 평준화 기법(load balancing method)을 활용한 최적 입지선정 모형을 제시하였 으며 해당 모형은 전체 수요를 충족시킬 수 있는 최적의 전기차 충전소 위치를 결정함과 동시에 충전소에 걸리는 최대 부하의 최소화를 목적으로 한다. 특히 운전자가 충 전소의 부하상태에 따라 최단거리에 있는 충전소만이 아 닌 더 멀리 있는 충전소를 이용할 수 있다는 행태를 고 려했다는 점에 초점을 맞추었다. 전기차 충전소 입지선 정에 관한 연구는 다수 진행되었지만 이러한 사례를 모 두 고려하여 실증적으로 다룬 문헌은 아직까지 없는 것 으로 판단된다. 본 연구는 국내 1세대 전기차 선도 도시 인 제주도 지역의 실제 데이터를 사용하고 다양한 시나 리오를 기반으로 실증분석을 수행하여 현실성 있는 결과 를 도출하고자 하였다. 이렇게 도출된 연구 결과를 바탕 으로 공급 불균형을 해결하고 불필요한 사회적 비용을 절감할 수 있는 충전소 구축 전략을 제안하였다.

본 연구는 다음과 같이 구성된다. 제 1.2절에서는 전기 차 충전소 입지선정에 대한 기존 연구들을 분류하고 그 특징을 분석하겠다. 제 2장에서는 충전소 입지선정 문제 에 대하여 설명하고 혼합정수계획모형을 제안한다. 제 3 장에서는 입지선정 문제를 해결하기 위하여 지역 탐색 기반의 휴리스틱을 제안한다. 제 4장에서는 실제 데이터 를 이용하여 다양한 시나리오를 구성하고 실험결과를 바 탕으로 휴리스틱 알고리즘의 성능을 평가한다. 제 5장에 서는 본 연구의 결론에 따른 시사점과 한계점을 제시하 고 연구결과를 요약한다.

1.2 선행연구 고찰

주유 및 대체연료 시설물 입지선정 모형 연구는 수요 를 어떤 형태로 표현하는지에 따라 크게 점 기반 수요 (Point-based demand)와 흐름 기반 수요(Flow-based demand) 의 최적화 모형으로 구분할 수 있다. 점 기반 수요를 이 용하는 대표적인 최적화 모형인 p-median 접근법은 입지 선정 분석에서 널리 사용된 모형으로 p개의 시설물에 대 하여 시설물을 이용하려는 모든 수요지점과 시설물간 거 리의 총합이 최소가 되도록 최적의 입지를 찾고 수요지점 마다 시설물을 할당해주는 입지-배분 모델이다. Goodchild and Noronha[7]을 시작으로 Melendez and Milbrandt[18] 가 대체연료 충전 시설물 입지선정에 적용하여 공간적 효율성을 강조하였으나 p-median 접근법에는 시장 자기 잠식효과가 내포되어 있다는 중요한 문제가 있다. p-median 접근법은 주로 인구 중심점 또는 네트워크 링크의 교통 량을 수요로 가정하는데 입지 결과 인구가 많고 시설물 과 접근성이 좋은 지역이거나 교통량이 많은 링크와 가 까운 지역이 선정된다. 하지만 이렇게 선정된 지점들은 기종점 경로 위에 중복적으로 입지가 되고 한 지점의 시 장을 다른 지점이 상당 부분 잠식하게 되는 비최적 결과 가 발생할 수 있다. P-median 접근법 이외에도 점 기반 수요를 사용한 전기차 충전소 입지선정에 대한 연구는 Frade et al.[5]에서 찾아볼 수 있으며 제한된 충전소 건 설 개수에 따라 포괄할 수 있는 수요를 최대화하고자 하 였다. 반면 Chen et al.[3]과 Ghamami et al.[6]은 수요 지 점과 충전소까지의 거리를 비용으로 환산한 후 충전소를 건설할 때 발생할 수 있는 비용의 총합을 최소화하고자 하였다.

반면, 수요는 점이 아닌, 기종점 경로상의 흐름에서 나 온다고 가정하는 흐름 기반 수요에 대한 연구들에서는, 이러한 점 기반 수요의 단점들에서 자유롭다. Hodgson [8]은 제한된 수의 시설을 이용하여 흐름 기반 수요를 최 대로 수용하기 위한 FCLM(Flow-capturing location model) 을 제안했으며, Berman et al.[2]는 같은 문제를 독립적으 로 제안하여 이를 FILM(Flow-intercepting location model) 이라고 명명하였다. 이 문제를 우리는 편의상 FILM이라 지칭할 것이다. FILM는 전기차 충전 시설 위치선정을 위 해서 크게 두 가지 방향으로 확장되어왔다. 첫째, FILM 에서는 모든 요소가 확정적으로 모델링되었지만, 충전 수요와 충전 시간에 대한 확률적인 속성을 반영한 화장 연구가 수행되었다. Yang[22]은 이들을 확률적으로 모델 링해서 급속 충전소에서 발생하는 혼잡을 관리할 수 있 는 모델을 제시하였다. 둘째, FILM는 세워진 시설물들을 지나는 흐름 기반 수요는 모두 충족된다고 가정했으나, 전기차의 장거리 운행 수요는 최대 주행 거리를 감안해 서 다중 충전이 가능해야 충족될 수 있다는 사실을 반영 한 확장된 연구들도 수행되었다. Kuby and Lim[14]는 처 음으로 이를 반영한 혼합정수계획법인 FRLM(Flow-refueling location model)을 제안하였다. Kuby et al.[15, 16]는 대규모의 현실세계 문제에 FRLM을 적용하였으며 더 나 아가 Lim and Kuby[17]는 효율적으로 해를 구하기 위하 여 탐욕 알고리즘과 유전 알고리즘을 활용하였다. 또한, FRLM을 확장한 연구들도 수행되었다. Upchurch et al. [21]는 충전 시설물의 서비스 한계용량을 고려한 CFRLM (Capacitated FRLM)을 제안했으며, Kim and Kuby[13]는 운전자가 충전 시설물을 방문하기 위하여 최단거리의 경 로가 아닌 우회경로를 이용하는 행태를 반영한 DFRLM (Deviation-FRLM)을 개발하였다.

시설물들의 작업부하 평준화는 시설물 입지선정 문제 의 주요한 목적중 하나이다. 따라서 이를 고려한 연구는 다양한 분야의 시설에 대한 위치 선정을 위해서 수행되 어왔다. Baron et al.[1]과 Kim and Kim[12]은 의료시설 입지선정을 위해 시설물에 할당되는 수요의 최대치 최소 화를 목적함수로 고려한 문제들에 대한 분지한계 알고리 즘을 제안하였다. Jeon and Lee[10]는 대규모 생산시설내 에서 창고의 위치를 결정하기 위해서 각 작업자들의 최 대 이동거리 최소화를 목적함수로 사용한 문제를 다루었 다. Kang and Park[11]은 생산문제에서 라인설비의 작업 량 밸런싱을 문제에 대하여 각 생산라인의 작업배분 분 포를 평가하여 각 휴리스틱의 성능을 조명하였다. 입지 결정 문제와 관련된 국내연구를 조사한 바, Oh[19]는 클 러스터링 알고리즘인 DBSCAN를 기반으로 수정된 알고 리즘을 제안한 후, 본 알고리즘을 활용한 결과에 대한 적 용결과를 이론과 실례를 가정하여 연구하였다. Song[20] 은 사회연결망분석(Social network analysis)을 이용하여 농수산물 도매시장의 적정입지를 결정하는 방법론을 제 안하였다. 앞선 선행연구 결과들을 바탕으로, 우리는 모 든 흐름 기반 수요를 만족시키면서, 충전소의 부하 평준 화를 위한 충전소 입지 선정 문제를 다루고자 한다.

2. 문제정의 및 수리모형

2.1 문제설명 및 정의

본 절에서는 전기차 충전소 입지선정 문제에 대하여 상 세히 설명하고자 한다. 전기차의 가장 큰 특징은 1회 충전 시 최대 주행가능거리이며 운전자가 목적지까지 가는 도 중 충전소를 방문하게 될 때 현재 위치에서 제일 가까운 충전소를 이용하는 것이 이상적인 행태라고 할 수 있다.

<Figure 1>은 전기차 운전자들이 충전소를 방문할 때의 경로를 묘사하고 있다. 기점 O1, O2, O3, O4에서 종점 D 까지 가는 도중 임의의 충전소를 방문할 때 기점-충전소- 종점 거리의 합이 최소가 되도록 하는 충전소는 각각 a, b, b, b이며 최단거리의 경로는 실선으로 표시되어 있다. 각 기종점 간의 수요가 동일하다고 보았을 때 충전소 b는 a에 비하여 상대적으로 수요가 집중되고 있으며 충전소의 서비스 한계용량에 따라서는 포화상태에 이를 수 있다. 이 렇게 수요가 특정 충전소에 집중되는 경우 기존 사용자의 충전서비스가 완료될 때까지 기다려야 하는 대기시간이 발생하고 이는 곧 비효율적인 서비스 운영으로 이어진다.

따라서 본 연구에서는 다음의 사항을 고려한다. 상황 에 따라 최단거리의 경로에서 우회경로를 선택하는 운전 자의 합리적 행태를 고려한다. <Figure 1>을 보면 기존의 O4-b-D를 잇는 최단경로 외에 O4-c-D의 우회경로가 있 다. 기존 최단경로인 O4-b-D의 단위거리가 7인데 비하여 O4-c-D 우회경로의 단위거리는 9이기 때문에 운전자는 종점 D까지 가기 위해 단위거리 2만큼 더 가야 하지만 수용능력에 여유가 있는 충전소 c를 사용할 수 있다는 장점이 있다. 그리고 서비스 공급업자의 측면에서도 서 비스를 고르게 분배할 수 있어 충전소의 적절한 부하 조 절이 가능해진다.

본 논문에서 다루는 전기차 충전소 입지선정 문제는 부하 평준화 기법을 기반으로 혼합정수계획모형을 정의 하였으며 사용된 가정 사항은 다음과 같다. 첫째, 모든 전기차는 기종점 사이를 동일한 속도로 왕복운행하며 후 보지 노드를 포함한 모든 노드 사이의 운행은 최단경로 를 이용하여 운행한다. 둘째, 전기차 충전소는 후보지 노 드에만 건설된다. 셋째, 운전자는 최대 한계 우회거리의 범위 내에서 갈 수 있는 충전소들 중 한 곳을 방문한다. 넷째, 충전소의 서비스 한계용량은 모두 동일하다. 다섯 째, 전기차는 동일차종으로 1회 충전 시 최대 주행가능 거리는 같다.

다음은 부하 평준화 기법 기반의 전기차 충전소 입지 선정 문제에 대한 혼합정수계획모형에 사용되는 기호 및 정의들이다.

집합(Sets)

상수(Parameters)

결정변수(Decision variables)

2.2 혼합정수계획모형

subject to

본 연구에서 제시한 모형의 목적함수(1)는 충전소의 한계용량 대비 할당되는 수요의 최대비율을 최소화하는 것이다. 제약조건 (2)은 기종점 노드 간에 운행하는 전기 차 운전자는 반드시 한 곳의 충전소로부터 서비스를 받 는다. 즉, 중복서비스나 서비스 부재지역은 존재하지 않 는다. 제약조건 (3)은 기종점 노드 간 운행하는 운전자가 후보지 노드 k에 위치한 충전소에서 서비스를 받기 위해 서는 노드 k에 충전소가 존재해야 한다는 것을 의미한 다. 제약조건 (4)은 각 충전소에 할당되는 수요의 총합을 한계용량으로 나누어 부하율을 구하는 식이자, 부하율은 선정된 충전소들의 부하율 중 최대값인 L_max보다 작거 나 같다는 것을 의미한다. 이 때 부하율이 1보다 크면 피 크시간대의 수요가 충전소의 수용능력을 초과하는 상태 를 말하며 1보다 작다면 그 반대의 상황을 나타낸다. 제 약조건 (5)은 후보지 노드 k에 충전소를 건설하는 비용 의 총 합은 주어진 예산 내에서 수행한다는 것을 의미한다. 마지막으로, 제약조건 (6)과 (7)은 결정변수의 이진변수제 약이다.

3. 지역탐색 기반 휴리스틱

3.1 휴리스틱 개발 필요성

제 2절에서 다룬 부하 평준화 모델은 n개의 충전소 후 보지들로 구성된 네트워크에서 모든 경로의 수요를 포괄 할 수 있는 k개의 충전소 후보지를 선정하고 각 경로에 최적의 충전소를 할당하여 전체 전기차 충전소의 부하 평 준화를 꾀하는 조합최적화 문제라 할 수 있다. 일반적으로 이러한 문제는 현실세계의 복잡한 데이터와 네트워크를 반영한 NP-hard 문제로 알려져 있으며 문제의 크기가 작 은 경우 주로 상업용 최적화 소프트웨어 패키지인 ILOG CPLEX나 LINGO를 사용하여 문제를 해결한다. 그러나 본 연구에서는 광범위한 교통 네트워크와 입지선정에 관련된 예산 제약이 존재하며 각 경로마다 방문할 수 있는 충전소의 범위가 모두 다르기 때문에 문제가 더욱 복잡하다. 문제의 크기는 충전소를 방문하기 위한 최대 한계 우회거리와 충전소를 건설하는데 주어진 총 예산 에 의존적이다. 예를 들어, 최대 한계 우회거리를 2km 로 설정하게 되면 결정변수 Y k i j 는 21,324개 이지만 최대 한계 우회거리가 3km로 증가하게 되면 26,856개로 증가 한다. 이는 운전자가 더 먼 범위에 있는 충전소를 방문 할 수 있기 때문이다. 또한 충전소 건설에 필요한 예산 의 액수에 따라 n개의 충전소 후보지들 중 건설할 수 있 는 k개의 조합(_nC_k)의 수가 달라진다. 이러한 이유로 상 업용 최적화 소프트웨어 패키지를 이용하면 완전 최적해 (Optimal solution)를 구하는 데 시간이 오래 걸리게 된다. 따라서 이 절에서는 빠른 시간 내에 최근사해(Nearest optimal solution)를 도출하기 위한 휴리스틱을 제안하고자 한다.

3.2 전체 휴리스틱 절차

부하 평준화 모델을 해결하기 위해 제안한 휴리스틱 의 전체 순서도는 <Figure 2>와 같다. 이 휴리스틱은 초 기해 S 를 산출함으로써 시작한다. 휴리스틱은 초기해 S 에 저장된 경로별 할당 충전소 정보를 사용하여 지역탐 색을 수행하며 개선된 이웃해(Neighborhood)를 생성한다. 생성된 이웃해가 더 이상 개선이 되지 않는다면 현재 충 전소 중 한 곳을 선택하여 해당 충전소에 할당되어 있는 모든 경로들의 수요를 선택된 충전소를 제외한 다른 충 전소로 변경해준다. 이는 선택되는 충전소의 조합을 재 구성함으로써 해를 다양하게 만들기 위한 방법이며 이렇 게 재구성된 충전소 조합에서 다시 지역탐색을 수행해 새로운 개선된 해를 탐색한다. 이러한 해의 개선 단계와 다양화 단계는 주어진 횟수만큼 반복하게 되고 최종적으 로 최근사해로 산출하게 된다.

본 연구에서 다루는 전기차 충전소 입지선정 문제는 충전소를 건설할 후보지 위치를 결정하고, 선택된 충전 소에 걸리는 최대부하를 최소화하기 위하여 각 충전소에 서 서비스를 받게 되는 경로별 수요를 할당한다. 문제의 해는 3차원 배열구조로 배열의 첫 인덱스는 전기차 운행 의 기점, 두 번째 인덱스는 종점, 세 번째 인덱스는 기점- 종점으로 향하는 전기차가 운행 중간에 방문할 충전소를 의미하며 각 배열의 값은 정수와 문자로 표현하였다.

초기해의 생성은 탐욕 알고리즘(Greedy algorithm)을 기반으로 이루어진다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것 을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 그러나 순간마다 행하는 선택들은 그 순간에 대하여 지역적으로는 최적이지만, 그 선택들을 계속 수 집하여 최종적인 해답을 만들었을 때 그것이 최적이라는 보장은 할 수 없다.

제안한 휴리스틱을 사용해 초기해와 이웃해를 생성하 는 과정을 설명하기 위한 데이터 예제는 <Table 2>와 같 다. 이 표는 동일한 기점(i)과 종점(j)을 지나는 경로를 제외한 총 12개의 경로와 각 경로의 수요 및 최대 한계 우회거리 범위 내에서 방문 가능한 충전소 집합(K^ij)에 포함된 원소들을 나타내고 있다. 먼저 경로 1부터 12까 지 차례대로 방문할 충전소를 선택한다. 이때, 현재 경로 에서 방문 가능한 충전소 집합(K^ij)에 포함된 충전소만 선택할 수 있다. 또한 선택할 수 있는 충전소들의 현재상 태의 누적수요를 모두 비교하여 누적수요가 가장 작은 곳에 해당 경로의 수요를 할당하며 주어진 충전소 건설 예산의 범위 내에서 최대로 선택할 수 있다.

한편, 전체 경로 중에서 방문 가능한 충전소의 수가 한 개 밖에 없는 경로는 우선적으로 할당을 해준다. 이는 반 드시 건설되어야 하는 충전소를 미리 선택해줌으로써 예 산 제약조건에 따라 충전소를 최대로 건설할 수 있는 수 를 초과하지 않기 위함이다. 예를 들어, 주어진 예산의 범 위 내에서 최대로 건설할 수 있는 충전소의 수가 5개라고 가정하고 경로 1~경로 12를 차례대로 초기해 생성 규칙 에 따라 수행했을 때 선택된 충전소에 할당된 수요(경로) 를 나타낸 누적수요 그래프는 <Figure 3>과 같다. 즉, 총 6개의 충전소에 할당되면서 최대로 건설할 수 있는 충전 소의 수인 5개를 초과한다. 그러나 방문 가능한 충전소 가 한 곳 뿐인 경로 9와 12를 우선적으로 충전소 E에 할 당한 후 나머지 경로들에 대해 충전소 할당을 수행하면 <Figure 4>와 같이 총 5개의 충전소가 선택되며 예산 제 약조건을 만족한다.

앞에서 설명한 과정에 따라 전체 경로의 충전소 할당 이 완료되면 초기해인 S가 구성된다. 이번 절에서 설명 할 단계는 초기해(이전해) S를 통해 계산된 목적함수값 과 동일하거나 더 좋게 만드는 이웃해를 얻는 과정이다. 이 과정은 지역 탐색을 수행하여 해를 개선시키는 단계 와 전역 최적해에 보다 근사하게 수렴할 수 있도록 기존 에 선택된 충전소의 조합과 다른 충전소의 조합을 만들 어주는 단계로 구성되어 있다.

3.2.1 지역 탐색 단계

먼저, 최대 수요 충전소 탐색 함수에 의해 투입된 해 S 에서 누적수요가 가장 큰 충전소 Max와 해당 충전소에 할당되어 있는 모든 경로들을 찾는다. 그리고 하나의 특 정 경로를 선택하여 다른 충전소로 재할당을 하는데 이때 경로 수요의 크기에 따라 내림차순 또는 오름차순 정렬 후, 정렬된 순서대로 재할당 가능 여부를 확인하는 두 가 지 방법이 있다. 데이터 예제를 이용한 이웃해 생성과정 은 오름차순 정렬 방법으로 소개하며 본 연구의 실험은 두 가지 방법을 각각 적용하여 결과를 비교해 보고자 한다.

정렬된 순서에 따라 경로의 재할당 가능 여부를 판단 하기 위해서 방문 가능한 다른 충전소들의 현재 누적수요 와 재할당 하고자 하는 경로의 수요를 합산하여 최소값을 보여주는 충전소를 찾는다. 이 최소값이 충전소 Max의 누적수요값보다 작은 경우에만 다른 충전소로의 재할당 이 가능하며 그렇지 않은 경우에는 차순의 경로에 대해 재할당 가능 여부를 확인한다. 이렇게 하나의 경로를 방 문 가능한 다른 충전소들 중 한 곳으로 재할당 해줌으로 써 충전소 Max의 누적수요를 감소시키는 과정을 반복한 다. 만약 충전소 Max를 사용하는 모든 경로에 대해 확인 절차를 거쳤음에도 재할당 조건을 충족하지 못하는 경우 지역 탐색 휴리스틱은 종료한다.

<Table 3>은 제 3.3절에서 데이터 예제를 사용하여 얻 어진 초기해 S 에서 Max값인 충전소 C를 사용하는 경로 들 중 수요가 작은 경로부터 순차적으로 나열한 경로 리 스트를 나타낸다. 또한 <Figure 5>는 초기해 S 에 대하여 앞서 설명한 이웃해 생성 과정을 반복 수행한 결과로 목 적함수의 값이 110, 100, 90으로 감소하였다. 마지막 결 과에서 충전소 A를 이용하는 경로 1, 4, 7은 다른 충전소 로 재할당을 할 수 없기 때문에 지역 탐색을 통한 해의 개선 단계는 종료되며 이때의 최종 솔루션을 저장한다.

3.2.2 충전소 조합 재구성 단계

지역 탐색으로 더 이상 해의 개선이 이루어지지 않으 면 수행하는 단계이다. 지역 최적해의 충전소 조합에서 누적수요가 가장 낮은 충전소를 선택한 후 할당되어 있 는 모든 수요들을 나머지 충전소들로 재할당하여 선택된 충전소의 누적수요를 0으로 만들어준다. 단, 누적수요가 가장 작은 충전소를 이용하는 경로들 중에서 현재 충전 소 외에 방문 가능한 충전소가 없는 경로가 존재한다면 누적수요가 다음으로 작은 충전소를 선택하도록 한다. 이러한 과정은 주어진 예산 내에서 최대로 선택된 충전 소의 개수를 한 단위 줄여줌으로써 지역 최적해의 충전 소 조합에 존재하지 않았던 새로운 충전소를 선택할 수 있는 기회를 제공한다.

<Figure 6>은 <Figure 5>의 지역 최적해 상태에서 수 행하는 충전소 조합 재구성 단계를 보여주고 있다. 누적 수요가 가장 작은 충전소는 E이지만 E를 이용하는 경로 9와 12는 E외에 다른 충전소를 이용할 수 없다. 따라서 누적수요가 다음으로 작은 B에 해당하는 수요 70을 충 전소 A에 재할당 해주게 된다. 그 결과 선택된 충전소 조합은 {E, A, B, C, D}에서 {E, A, C, D}로 바뀌었으며 선택된 충전소의 개수가 4개로 줄어 1개의 충전소를 추 가로 선택할 수 있는 여유가 생긴다.

충전소 B가 없어진 자리에는 충전소 A를 이용하는 경 로 1, 2, 4, 7에서 방문 가능한 충전소 중 기존에 존재하지 않았던 새로운 충전소가 자리하게 된다. 현재 데이터 예제 의 경우 경로 7은 충전소 F를 방문할 수 있기 때문에 {E, A, C, D, F}의 조합으로 재구성한 후 해당 단계는 종료된 다. 충전소 조합 재구성 단계가 종료되면 다시 지역 탐색 을 통한 해의 개선 단계가 반복 수행되며 지역 최적해와 현재 상태에서의 최적해를 비교하여 더 좋은 해를 저장한다.

4. 실험데이터 및 결과분석

4.1 실험데이터

본 연구에서 제안한 혼합 정수계획모형과 휴리스틱을 이용한 실증 분석을 수행하기 위하여 대한민국 제주특별 자치도 지역의 데이터를 활용하였다. 현재 사례 지역인 제주도의 행정조직은 <Table 4>와 같이 제주시와 서귀포 시, 2개 행정시로 나뉘어져 있으며 7개 읍, 5개 면, 31개 행정동, 총 43개의 행정구역으로 구성되어 있다. 추자면 과 우도면은 제주도 본토와의 충전소 네트워크 연결이 어려운 도서지역이라는 점을 감안해 추자면과 우도면을 제외한 41개 행정구역을 기종점 노드로 고려하였다. 또 한 제주도에서 관리하는 공영주차장 중 노외주차장이면 서 주차면수가 20대 이상인 82곳을 전기차 충전소 후보 지로 고려하였다. <Figure 7>은 각 행정구역에 속한 읍/ 면/동 사무소와 공영주차장의 주소지를 지오코딩한 후 그 위치를 도로 네트워크와 함께 국가공간정보포털에서 제공하는 지도상에 포인트로 표시한 것이다. 이때의 위· 경도는 WGS84 좌표계를 따른다. 설정된 기종점 노드 간 의 거리(d^ji = d^ij ) 및 기종점 노드와 충전소 후보지 노드 의 거리(d_ik)는 최단 거리의 값을 기반으로 한다.

기종점 간 전기차 교통량의 경우 다양한 경로와 시간 에 따른 변수들이 존재하기 때문에 정확하게 측정하기에 는 어려운 점이 있다. 또한 전기차 사용자들은 일반적으 로 퇴근 이후 저녁시간을 이용하여 배터리 충전을 하는 특징이 있다. 따라서 본 연구에서는 식 (8)을 이용하여 행 정구역 간 출퇴근을 목적으로 운행하는 전기차의 교통량 (e_ji)을 산출하였다. 이렇게 얻어진 전기차 교통량에 피크 타임 내 충전소를 방문할 확률과 급속충전소에서의 평균 충전시간을 곱한 값은 충전소에서의 전기차 평균 충전시 간(s_ij), 즉 충전소의 수요로 설정하였고 식 (9)과 같다.

전기차는 일반 내연기관 차량과는 다르게 계절에 따 른 기온변화, 공조기 가동여부, 각종 전자장비 가동여부 등에 따라 실 주행가능거리의 변화폭이 심하다. 무엇보 다 전기차 충전소는 기존 주유소와 같이 생활공간 내에 충분히 보급되어 있지 않아 사용자의 심리적 불안감이 존재하고 이에 따라 일반 내연기관 차량에 비하여 상대 적으로 충전빈도가 높은 경향이 있다. 이에 본 연구에서 는 잔여 주행가능거리에 따라 충전소를 방문할 확률을 고려하기 위하여 1일 평균 주행거리에서 1회 충전 시 최 대 주행가능거리로 나눈 값을 하루에 충전소를 방문할 확률로 보았으며, 확률의 크기는 1일 평균 주행거리에 비례한다. 여기서 1일 평균 주행거리는 출퇴근 왕복거리 와 일상생활 속에서 운행하는 기타거리를 포함한다. 그 리고 본 연구에서는 충전소 이용이 가장 잦은 시간대에 서의 충전소 간 부하를 낮추기 위한 수요분배를 고려하 기 때문에 전기차 사용자가 하루 중 피크타임에 충전소 를 방문할 확률(α)을 적용할 필요가 있다.

이처럼 실험 데이터는 현실 상황의 분석과 실제 데이 터를 기반으로 생성하였다. 행정구역별 전기차 등록대수 는 제주도 지자체에서 제공하는 2016년 12월 기준 자료 를 사용하였으며 한국스마트그리드사업단에서 발간한 전기차 구축방안 최종보고서에 따라 급속충전소 한 곳을 건설하는데 필요한 단위 비용을 4,000만 원으로 설정하 였다. 또한 1회 충전 시 최대 주행가능거리는 180km, 급 속충전소에서의 평균 충전시간은 30분, 충전소의 피크시 간대는 5시간(오후 6시~오후 11시), 그리고 이 피크시간 대에 충전소를 방문할 확률은 60%로 설정하였다.

<Table 5>는 실험에 사용된 18개의 데이터를 보여준다. 데이터는 이웃해 생성방법, 운전자의 최대 한계 우회거리 범위, 충전소 건설에 주어진 예산을 나타낸다. 이웃해 생 성방법의 A는 누적수요가 가장 큰 충전소에서 하나의 경 로에 대한 수요를 다른 충전소로 재할당 해주는 과정에서 수요가 큰 경로부터 재할당 가능여부를 확인하는 방법(내 림차순)이며 이웃해 생성방법의 B는 그 반대인 방법(오름 차순)이다. 예산은 각각 16.4억, 24.8억, 32.8억 원으로 전 체 82곳의 후보지 중 41곳, 62곳, 82곳에 충전소를 건설할 수 있는 액수이다.

4.2 실험결과 및 분석

실험에 사용된 컴퓨터는 Intel i7-5500U CPU@ 2.40GHz, Microsoft Windows 10 64비트 운영체제를 사용하였다. 그 리고 본 연구에서 제안한 휴리스틱은 Microsoft Visual Studio 2015를 사용하여 C언어로 구현하였다. 제 2장에서 제시한 혼합정수계획모형을 이용하여 상업용 최적화 소 프트웨어 패키지인 ILOG CPLEX 12.6.3이 제한시간 동안 찾은 해의 목적함수 값과 비교하여 휴리스틱 알고리즘이 찾은 해의 품질을 평가한다. CPLEX의 최대 수행시간은 7200초, 2시간으로 설정하였다.

<Table 6>은 <Table 5>의 실험 데이터와 제안한 휴리 스틱을 사용해 도출한 목적함수의 결과값을 나타낸다. 이 웃해 생성방법 A를 적용한 데이터 1~데이터 9의 모든 목 적함수값이 이웃해 생성방법 B를 적용한 데이터 1~데이 터 9의 목적함수값보다 작은 결과를 주었다. 이 결과로 부터, 이웃해 생성방법 A가 B보다 우수함을 알 수 있다. 따라서, 이후 실험에서는 이웃해 생성방법 A를 적용한 휴 리스틱을 이용하여 진행하였다.

<Table 7>은 이웃해 생성방법 A를 적용한 휴리스틱과 CPLEX로 도출한 목적함수값 및 계산 시간을 보여준다. 실험결과를 비교했을 때 CPLEX는 데이터 1~9의 모든 경우 에 대해서 7,200초 동안 계산을 수행하여도 최적해를 얻을 수 없었다. 특히 데이터 1~데이터 3에서 얻은 목적함수값은 제한 시간으로 계산이 중단된 시점의 Best bound와 차이가 크기 때문에 휴리스틱과의 비교가 어려워 데이터 4~데이터 9의 실험결과를 비교한 결과, CPLEX보다 휴리스틱의 목적함 수값이 좋지 않은 경우가 존재하는 것을 확인할 수 있었다. 그러나 계산 시간의 측면에서 CPLEX는 7,200초의 제한 시간에서 도출된 결과인 반면 휴리스틱은 CPLEX보다 매우 짧은 시간에 결과를 도출한 것을 확인할 수 있다. 따라서 휴리스틱의 목적함수값이 CPLEX보다 좋지 않아도 그 차이 가 미미하기 때문에 본 연구의 문제에 대한 최근사해를 빠른 시간 내에 구하는데 있어 효과적이라고 볼 수 있다.

<Figure 8>은 데이터 2와 데이터 5의 실험결과를 지도 상에 나타낸 것이다. 두 데이터는 예산을 제외한 나머지 조건이 동일하며 선정된 충전소 후보지의 수가 각각 41 곳, 62곳이다. 데이터 5에서는 데이터 2에서 선정된 41곳 의 충전소 후보지(●) 외에 새로운 21곳의 충전소 후보지 (⊕)가 추가로 선정되었다. 또한 41개 행정구역(D1~D41) 들을 잇는 1,640개의 경로 중 전기차의 교통량이 상위 5% 에 해당하는 경로들을 주요 도로 구간으로 표현하였다.

한편, 데이터 2에서 선정된 충전소 후보지들을 살펴보 면 기종점 노드들로부터 인접한 지역과 비교적 멀리 떨 어져 있는 지역에 산발적으로 분포해있다. 그리고 이 후 보지들은 데이터 5에서도 선정되는 후보지들인 만큼 상 대적으로 우선순위에 있는 입지라는 것을 확인할 수 있 다. 데이터 5에서 추가로 선정된 후보지들은 데이터 2에 서 선정되지 않았던 기종점 노드의 지역(D4, D25, D38, D40)과 데이터 2에서 선정된 후보지의 주변으로 확산되어 나가는 모습을 보였다. 특히 데이터 2를 포함하여 데이 터 5에서 선정된 충전소 후보지들은 전반적으로 주요 도 로 구간과 매우 인접한 곳에 위치한 경우가 많았다.

최대 한계 우회거리의 증가는 운전자가 더 멀리 떨어 진 충전소까지 방문할 수 있다는 의미이며 충전소의 입 지 분포도 달라질 수 있다. 따라서 주어진 예산 제약조건 은 동일한 대신 최대 한계 우회거리가 서로 다른 데이터 1, 데이터 2, 데이터 3을 사용하여 선정되는 충전소 후 보지를 확인하였다. 그리고 충전소 후보지의 중요도를 평가하였다. 세 개의 데이터에서 모두 선정되는 충전소 후보지를 수준 3, 세 개의 데이터 중 두 개의 데이터에 서 선정되는 충전소 후보지를 수준 2, 그리고 한 개의 데이터에서만 선정되는 충전소 후보지를 수준 1로 구분 하였다.

<Figure 9>에 따르면 수준 3의 충전소 후보지는 28곳, 수준 2의 충전소 후보지는 15곳, 수준 1의 충전소 후보 지는 6 곳이다. 즉, 운전자의 행태 중 하나인 최대 한계 우회거리에 상관없이 항상 선정되는 수준 3의 충전소 후 보지들은 수요를 충족시키기 위해 반드시 충전소가 건설 되어야 하는 입지이다. 그러므로 데이터 1, 데이터 2, 데 이터 3에서 각각 선정된 총 41곳의 후보지 중에서도 우 선순위를 두고 입지 선정할 필요가 있다는 것을 뜻한다.

<Figure 10>는 제주도 행정구역별 사업체 종사자수를 맵핑한 결과이다. 내추럴브레이크를 사용해 4개 등급으 로 구분하였으며 지도에서 짙은 색으로 칠해진 지역일수 록 종사자수가 많은 지역에 해당한다. 이러한 관점에서 보면 종사자수가 많은 제주시 및 서귀포시의 도심지역에 집중적으로 위치하는 것을 확인할 수 있었다. 즉, 종사자 수가 많은 지역은 출퇴근 시에 전기차의 유출입 교통량 이 높을 것이며 충전수요가 높은 지역이라고 해석할 수 있다.

또한 부하 평준화 기법을 적용한 결과 <Figure 11>과 같이 충전소들의 부하율이 대체적으로 일정한 것을 확인 할 수 있다. 이는 특정 충전소에 수요가 몰리지 않고 거 의 균등하게 분배된 것을 의미한다. 데이터 2와 데이터 5 에서 최대 부하율 상태인 충전소는 각각 10개소, 17개소 였다. 데이터 5가 데이터 2보다 부하율이 낮은 이유는 <Figure 8>과 <Figure 10>에서 확인하였듯이 수요가 집 중되는 충전소로부터 최대한 가까운 위치에 추가로 건설 되면서 충전수요를 분담하는 역할을 수행하기 때문이다.

5. 결론 및 향후 연구방향

본 논문에서는 전기차 충전소가 공공재라는 성격을 고려하여 특정 충전소의 수요 집중으로 발생하는 불균형 을 완화하고 공공 서비스의 형평성과 효율성을 반영하기 위하여 부하 평준화 기법을 접목시킨 충전소 입지선정 모형을 제시하였다. 그리고 제주도 지역을 대상으로 공 영주차장에 공공 급속충전소를 설치할 때의 최적 입지를 찾은 후 충전소의 부하상태를 고려한 각 경로별 최적 충 전소를 결정하였다.

본 연구 결과를 통하여 얻은 결론은 다음과 같다.첫째, 현재 전기차 충전소의 구축은 막대한 사회적 비용이 수반 되며 특히 공공부문에서 서비스가 주로 제공되고 있기 때 문에 그 수익성도 현 시점에서는 가늠하기 어려운 상황이 다. 이러한 점에서 충전소 부하의 평준화는 충전소의 공 급에 있어 한정된 자원의 효율적 배분을 가져다 줄 수 있 으며 전기차 운전자에게도 보다 원활한 서비스를 제공할 수 있도록 기여하는데 의의가 있다. 부하 평준화 모델을 사용한 시나리오 분석 결과 충전소의 최대부하율은 운전 자의 최대 한계 우회거리 변화에 영향을 거의 받지 않는 반면, 예산에 따라 건설할 수 있는 충전소의 개수에는 큰 영향을 받는다. 이러한 영향요인들은 향후 국가 재원이 투입되는 전기차 충전소 입지선정의 의사결정이나 계획 에 참고자료로 활용될 수 있을 것으로 예상된다.

둘째, 주거지(근무지)가 밀집되어 있는 생활권역을 중 심으로 구축한 후 수요가 편중되는 충전소의 인근 지역 에 추가적으로 확대해 나갈 필요가 있다. 이는 충전소 클 러스터를 조성하여 인근 충전소의 수요를 분담해줌으로 써 충전소의 효율적인 운영이 이루어질 수 있기 때문이 다. 또한 기종점을 잇는 경로들 중 주요 간선도로 주변 지역을 우선적으로 고려할 필요가 있다. 지선도로에 비 하여 상대적으로 교통량이 많은 간선도로의 주변에 입지 하는 것이 다수의 기종점 경로에 대한 수요를 수용할 수 있을 것이다.

셋째, 개발된 휴리스틱은 입지 문제를 빠른 시간 내에 효율적으로 해결하였고 더욱 복잡한 네트워크에서 큰 효 과를 낼 것으로 기대된다.

마지막으로, 정부가 추진하는 충전인프라 보급의 정책 방향과 같다는 점에서 의의가 있다. 현재 정부는 공영주 차장을 활용한 전기차 충전소 구축사업을 추진 중에 있 다. 이러한 관점에서 본 연구는 환경부의 ‘전기자동차 충 전인프라 설치운영 지침’에 부합하는 공영주차장을 선별 하여 충전소 입지 후보지로 고려하였으며 지역별 전기차 보급대수 및 운전자 운행패턴을 반영함으로써 사전 시뮬 레이션의 사례가 될 수 있다.