The necessity of charger installation studies stems from the accelerated pace of battery based electric vehicles sales. While cost reduction in battery technology and favorable green vehicle policies have placed electric vehicles more competitive against internal combustion en-gines, the lack of charging infrastructures remains as a huge barrier to the expansion of electric vehicles. Unless charging infrastructures can provide drivers with the same levels of easy ac-cessibility and quick availability that gasoline stations do, battery based vehicles will still lag behind internal combustion engines. To address this barrier, Korea’s municipal authorities have devised plans to increase the charging network across the country. Considering that charger installations are limited by the number of chargers and the locations that they can be installed, it is imperative to develop methodologies that effectively distribute chargers with the purpose of increasing their accessibility and availability.
Concerning this issue, this paper examines two sequential problems related to electric vehicle charger installation. The first problem concerns the optimal distribution of electric ve-hicle chargers to candidate locations in consideration of traffic patterns and available charger installation locations. The optimization model assumes that drivers choose the closest charger point. The problem is approached through evaluating an integer programming (IP) method and a constraint satisfaction problem (CSP) method.
The second problem builds on the first problem by examining two scenarios: greedy al-location and smart allocation. Unlike the first problem, drivers are able to choose multiple charger points, in case the closest charger is occupied. In the greedy allocation scenario, driv-ers are the sole decision makers and can choose the charger point they wish to charge at; in the smart allocation scenario, a smart system allocates chargers to electric vehicles with the pur-pose of minimizing the total distance traveled by all vehicles in the domain. In both scenarios, the Monte Carlo simulation approach is used to generate random traffic patterns following Poisson distributions.
Simulation results show advantages of IP and CSP methods in different scenarios to address to issue of charger accessibility and availability. IP method performs better under the scenario where a smart allocation system is present, whereas the CSP method performs better in a scenario absent of such a system. Considering municipal plans to install chargers, the IP and CSP methods discussed in this paper will provide the required tools and methodologies for charger installations.
본 논문은 정부가 발표한 전기 자동차 충전 인프라 확충 계획에서 대두되고 있는 두 가지 문제를 살펴본다. 첫번째 문제는 충전기 배치(distribution) 문제이다. 밀집된 도심의 경우 충전기 설치를 위한 공간이 절대적으로 부족한데, 이 문제를 정수 계획법(integer programming, IP)과 제약 만족 문제 방식 (constraint satisfaction problem, CSP)을 통해 접근한다. 몬테카를로 (Monte Carlo) 방식을 적용하여 도로 별 전기자동차 충전 수요를 가정하고, 운전자가 도로에서 가장 가까운 충전기를 선택한다고 했을 때, 일정 대 수의 충전기를 설치 가능 후보지(candidate location)에 효율적으로 배치해 동시간에 충전 가능한 전기차 대수를 최대화 하는 모형을 제시한다.
두번째 문제는 충전기 배분(allocation) 문제이다. 여기서는 앞서 살펴본 배치 문제에서 운전자가 다수의 충전기를 선택할 수 있다는 가정을 더한다. 그 가정 하 충전기의 최적 분배(allocate)를 통하여 전체 자동차의 총 운행거리(total distance)를 최소화하는 모형을 제시한다. 또한 본 논문은 이 문제를 스마트(smart) 시나리오와 탐욕 선택(greedy allocation) 시나리오로 나누어 접근하였으며, 각 시나리오는 충전기 선택 (charger selection, CS) 알고리즘과 자동차 선택 (vehicle selection, VS) 알고리즘을 통해 전개된다. CS알고리즘은 두 시나리오 동일하게 적용되었다. 운전자는 현재 위치에서 가장 가까운 곳의 충전기를 선택하고, 해당 충전기 사용이 불가 할 경우 그 다음으로 가까운 충전기인 대안(alternate) 충전기를 선택하는 것으로 한다. 스마트 시나리오에서 VS알고리즘은 각 충전소에 들어오는 차량 중 자동차와 대안 충전기의 거리가 가장 먼 차량부터 우선적으로 충전하는 것으로 한다. 탐욕 시나리오에서 VS 알고리즘은 자동차와 충전기 사이의 이동거리가 가장 가까운 차량을 우선적으로 충전하는 것으로 하였다. 이 두 개 시나리오에 몬테카를로 시뮬레이션을 적용하여, IP와 CSP중 어느 접근법이 더 효과적인지 살펴본다.
