[KISE 2018] A Problem of Locating Electric Vehicle Charging Stations for Load Balancing

논문 정보

로드밸런싱을 위한 전기차 충전소 입지선정 문제

---

1. Introduction

본 논문은 부하 평준화 기법(load balancing method)을 활용한 최적 입지선정 모델을 제시하였다.해당 모형은 전체 수요를 충족시킬 수 있는 최적의 전기차 충전소 위치를 결정함과 동시에 충전소에 걸리는 최대 부하의 최소화를 목적으로 한다.추가로, 운전자가 충전소의 부하상태에 따라 최단거리에 있는 충전소가 아닌 더 멀리 있는 충전소를 이용할 수 있다는 행태를 고려하였다.

 

본 연구는 제주도 지역의 전기차 이용 데이터를 사용하여 다양한 시나리오를 기반으로 실증분석을 진행하였다.

 

시설물 입지 선정 모형은 수요를 표현하는 형태에 따라 점 기반 수요와 흐름 기반 수요로 구분할 수 있다.

 

점 기반 수요를 이용한 대표적인 모형에는 p-median 접근법(p개의 시설물에 대해 시설물을 이용하려는 모든 수요지점과 시설물간 거리의 총합이 최소가 되도록 최적의 입지를 찾고 수요지점마다 시설물을 할당하는 입지 배분 모델)이 있다.

 

흐름 기반 수요에 대한 연구에는 제한된 수의 시설을 이용하여 흐름 기반 수요를 최대로 수용하기 위한 FCLM(Flow-capturing location model)가 있으며, 전기차의 장거리 운행 수요는 최대 주행 거리를 감안해서 다중 충전이 가능해야 충족될 수 있다는 사실을 반영한 FRLM(Flow-refueling location model)이 있다. 더 나아가, 충전 시설물의 서비스 한계용량을 고려한 CFRLM(Capacitated FRLM), 운전자가 최단거리 경로가 아닌 우회경로를 이용하는 행태를 반영한 DFRLM(Deviation FRLM)으로 확장되었다.

 

시설물들의 작업부하 평준화 관련 연구로는 Baron et al.[1] 과 Kim and Kim[12]은 의료시설 입지선정에서 시설물에 할당되는 수요의 최대치를 최소화하는 문제에 대한 분지한계 알고리즘을 제안하였고, Jeon and Lee[10]는 대규모 생산시설 내에서 작업자들의 이동거리 최소화하는 창고의 위치를 결정하는 문제를 다루었다. Kang and Park[11]는 생산문제에서 라인설비의 작업량 밸런싱을 휴리스틱을 활용하여 접근하였으며, Oh[19]는 DBSCAN을 기반으로 접근하였다. 

 

2. 문제정의 및 수리모형

전기차 충전소 입지선정 문제에서 전기차는 1회 충전시 최대 주행가능거리이며 운전자가 목적지까지 가는 도중에 충전소를 방문하게 되면 현재 위치에서 가장 가까운 충전소를 이용하는 것이 이상적이다.

 

수요가 특정 충전소에 집중되는 경우 기존 사용자의 충전서비스가 완료될 때까지 기다리게 되는데 이는 비효율적인 서비스 운영으로 이어진다.

따라서, 상황에 따라 최단거리 경로에서 우회경로를 선택하는 운전자의 합리적 행태를 고려한다.(Fig 1 참고)

 

Fig 1. An Example Depicting Origin-Destination EV Trips Each of Which Visits a Charging Station in the Middle

 

본 연구에서는 전기차 충전소 입지선정 문제를 부하 평준화 기법을 기반으로 혼합정수계획모형을 정의하였으며, 가정 사항은 다음과 같다.

1. 모든 전기차는 기종점 사이를 동일한 속도로 왕복운행하며 후보지 노드를 포함한 모든 노드 사이의 운행은 최단경로를 이용한다.

2. 전기차 충전소는 후보지 노드에만 건설된다.

3. 운전자는 최대 한계 우회거리의 범위 내에서 갈 수 있는 충전소들 중 한 곳을 방문한다.

4. 충전소의 서비스 한계용량은 모두 동일하다.

5. 전기차는 동일차종으로 1회 충전 시 최대 주행가능거리가 같다.

 

혼합정수계획모형에 사용되는 기호 및 정의

혼합정수계획모형

 

목적함수(1) : 한 충전소에 걸리는 최대 부하율을 최소화한다. 부하율은 충전소의 용량 대비 할당된 수요로, 특정 충전소가 수용할 수 있는 최대 수요를 최소화하는 방향으로 최적화를 진행한다.

제약조건(2) : 모든 전기차에 대해 출발지에서 목적지로 가는 경로 중에 최소 한 번 충전소를 방문해야 한다. (충전소의 부재, 중복 서비스를 방지)

제약조건(3) : 운전자가 특정 경로에서 충전소를 방문하기 위해서는 해당 위치에 충전소가 설치되어 있어야 한다. (충전소가 설치되지 않은 후보지는 충전소 이용이 불가능함)

제약조건(4) : 각 충전소에 할당되는 수요의 총합은 충전소의 한계 용량을 초과하지 않아야 하는 수요 제약조건이다.

제약조건(5) : 충전소의 수에 대한 제약조건으로, 주어진 예산 값을 이용한다.

제약조건(6)(7) : 결정변수의 이진변수제약이다.

 

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

다루는 문제의 크기는 충전소를 방문하기 위한 최대 한계 우회거리와 충전소를 건설하는데 주어진 총 예산(충전소의 갯수)에 의존적이다.

따라서 상업용 최적화 소프트웨어 패키지를 이용하면 완전 최적해를 구하는데 시간이 오래 걸리게 되어 휴리스틱을 활용하고자 한다.

Fig 2. Flowchart for the Proposed Heuristic

 

휴리스틱은 초기해 S에 저장된 경로별 할당 충전소 정보를 사용하여 지역탐색을 수행하며 개선된 이웃해를 생성한다.

이웃해가 개선되지 않는다면 현재 충전소 중 한 곳을 선택하여 해당 충전소에 할당되어 있는 경로들의 수요를 다른 충전소로 변경한다.

이 과정을 통해 충전소의 조합을 재구성하여 다양한 해를 만들 수 있으며, 재구성된 충전소 조합에서 다시 지역탐색을 수행하여 새로운 해를 탐색한다.해의 개선 단계와 다양화 단계를 반복하여 최종적인 최근사해를 도출한다.

 

지역 탐색 단계

Fig 5. Progress Process for the Local Search Step

 

현재 해에서 부하가 가장 큰 충전소를 찾고, 해당 충전소에 할당된 경로 중 하나를 선택하여 다른 충전소로 재할당한다. (부하가 가장 큰 충전소에서 상대적으로 여유 있는 충전소로 옮긴다.) 경로를 재할당할 때, 여러 순서로 재할당 순서를 정한다. 충전소에 할당된 모든 경로에 대해 재할당할 수 없는 경우 탐색을 종료하고, 해를 저장한다.

 

충전소 조합 재구성 단계

Fig 6. Progress Process for the Charging Station Reconfiguration Step

 

기존 충전소 조합에서 누적 수요가 가장 낮은 충전소를 선택한다. 해당 충전소에 할당된 경로를 다른 충전소로 재할당하고, 충전소를 제거한다. 충전소 조합을 줄이면서 새로운 충전소를 선택할 수 있어 지역 탐색 단계를 통해 새로운 해를 개선한다.

 

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

제주특별자치도 지역의 데이터를 활용하여 후보지는 제주도에서 관리하는 공영주차장 중 82곳을 선정하였다.

기종점 간 전기차 교통량은 다음과 같이 설정하였으며,

 

전기차 평균 충전시간, 즉 충전소의 수요는 다음과 같이 설정하였다.

 

잔여 주행가능거리에 따라 충전소 방문 확률을 고려하기 위해 1일 평균 주행거리 / 최대 주행 가능 거리를 하루에 충전소를 방문할 확률로 보았으며,

충전소 이용이 가장 잦은 시간대에 충전소 간 부하를 낮추기 위한 수요분배를 고려하기 위해 하루 중 피크타임에 충전소를 방문할 확률을 적용하였다.

 

해당 데이터는 제주도 지자체에서 제공하는 자료, 한국스마트그리드사업단에서 발간한 전기차 구축방안 최종보고서를 활용하여충전소 건설 비용을 4,000만원, 최대 주행가능거리 180km, 평균 충전시간 30분, 피크시간대는 5시간(오후 6시~오후 11시), 피크시간 방문 확률은 60%로 설정하였다.

 

실험 데이터셋은 이웃해 생성 방법, 예산, 최대 한계 우회거리에 따라 Table 5와 같이 데이터셋을 구축하였다.

Table 5. Experimental Data

 

이웃해 생성방법은 두 가지 방법을 사용하였으며, 누적수요가 가장 큰 충전소에서 하나의 경로에 대한 수요를 다른 충전소로 재할당 해주는 과정에서 수요가 큰 경로부터 재할당 가능여부를 확인하는 방법(방법 A)과 작은 경로부터 재할당 가능여부를 확인하는 방법(방법 B)을 사용하였다.

Table 6. Performance of the Heuristic for the Neighbor Solution Generating Methods

 

최대 한계 우회거리가 다른 데이터 1,2,3을 사용하여 선정되는 충전소 후보지를 확인하고, 충전소 후보지의 중요도를 평가하였다. 각 데이터에서 선정되는 횟수에 따라 수준 1,2,3으로 구분하여 최종적으로 수준 3의 충전소 후보지는 28곳, 수준 2의 충전소 후보지는 15곳, 수준 1의 충전소 후보지는 6곳을 선정하였다.

Fig 9. Distribution of the Resulting Charging Stations on Different Settings of the Maximum Allowed Detour Distance

 

부하 평준화 기법을 적용한 결과 Fig 11에서 확인할 수 있듯이 충전소들의 부하율이 대체적으로 일정한 것을 확인하였다.

Fig 11. Load Ratios of the Resulting Charging Stations for Different Budgets

5. Conclusion

연구 결과를 통해 4가지 결론을 얻을 수 있었다.

첫째, 충전소 부하의 평준화는 충전소의 공급에 있어 한정된 자원의 효율적 배분을 가져다 주어 전기차 운전자에게 원활한 서비스를 제공하는데 기여한다.

시나리오 분석 결과 충전소의 최대부하율은 운전자의 최대 한계 우회거리 변화에 영향을 거의 받지 않고, 건설할 수 있는 충전소 개수에 큰 영향을 받는다.

둘째, 주거지가 밀집되어 있는 생활권역을 중심으로 구축하여 수요가 편중되는 인근 지역에 확대하는 방향을 가져야 한다.

기종점을 잇는 경로들 중 주요 간선도로 주변 지역을 우선적으로 고려해야 한다.

셋째, 휴리스틱 모델은 입지 문제를 빠른 시간 내에 효율적으로 해결하였으며 복잡한 네트워크에서 큰 효과를 낼 것이다.

넷째, 정부가 추진하는 충전인프라 보급의 정책 방향과 같다는 점에서 사전 시뮬레이션의 사례가 될 수 있다.