Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.45 No.4 pp.217-224
DOI : https://doi.org/10.11627/jksie.2022.45.4.217

Solving the Location Problem of Charging Station with Electric Vehicle Routing Problem

Gitae Kim†

Department of Industrial Management Engineering, Hanbat National University

^†Corresponding Author : gitaekim@hanbat.ac.kr

Received 29/11/2022 Finally Revised 16/12/2022 Accepted 19/12/2022

Abstract

Due to the issue of the sustainability in transportation area, the number of electric vehicles has significantly increased. Most automakers have decided or planned to manufacture the electric vehicles rather than carbon fueled vehicles. However, there are still some problems to figure out for the electric vehicles such as long charging time, driving ranges, supply of charging stations. Since the speed of growing the number of electric vehicles is faster than that of the number of charging stations, there are lack of supplies of charging stations for electric vehicles and imbalances of the location of the charging stations. Thus, the location problem of charging stations is one of important issues for the electric vehicles. Studies have conducted to find the optimal locations for the charging stations. Most studies have formulated the problem with deterministic or hierarchical models. In this paper, we have investigated the fluctuations of locations and the capacity of charging stations. We proposed a mathematical model for the location problem of charging stations with the vehicle routing problem. Numerical examples provide the strategy for the location routing problems of the electric vehicles.

Key Words : Electric Vehicle Routing Problem , Location Routing Problem , Charging Stations , Transportation , Optimization

전기차량경로문제의 충전소 위치선정문제의 해법

김 기태†

한밭대학교 산업경영공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

물류에서 재고문제와 함께 중요한 문제 중에 하나는 차 량을 어떻게 배송할 것인지와 어떤 경로를 이용할 것인지 를 결정하는 문제이다. 복수의 차량으로 지역적으로 흩어 져 있는 수요지에 물건을 배송하거나 서비스를 하도록 차 량을 배송할 때, 차량의 수송비용이 최소가 되도록 하는 차량들의 경로를 찾는 문제를 차량경로문제라고 한다.

차량경로문제는 경영과학에서 오래 동안 연구되어져 왔던 분야이기도 하다. 최근 들어, 차량이 전기차량으로 바뀌어 가면서 전기차량과 관련된 연구도 활발히 진행되 어지고 있다. 전기차량에서 중요한 문제들 중에 하나는 차 량을 충전하는 것이다. 충전할 때의 문제는, 충전하는 시 간이 많이 걸리는 것과 충전소가 많이 없다는 문제가 있 다. 충전소에 대한 수요가 많아 충전소 공급이 부족한데 원인이 있다. 따라서, 부족한 충전소를 적절한 위치에 설 치하는 것은 충전에 대한 수요를 충족하는데 필수적이라 고 볼 수 있다.

차량의 이동이 많지 않은 곳에 충전소가 있으면 충전소 의 활용이 낮아지고, 차량의 밀도가 높은 지역에 충전소가 많지 않으면, 충전소에서 기다리는 차량이 많아져 효율적 으로 운영되지 못하게 된다. 이러한 문제는 시설의 위치를 찾는 시설위치선정문제(facility location problem)와 유사 하고 동일한 방법으로 모형화 되어 문제를 해결할 수 있 다. 하지만, 시설에 대한 위치선정은 시설이 고정되고 차 량들이 시설을 기준으로 운송을 하게 되며, 비교적 고정되 어 있는 운송지에 배송이 이루어지기 때문에 시설에 대한 위치선정문제는 간단하게 모형화 할 수 있다. 반면에, 전 기차량에 대한 충전소의 위치선정은 복잡성이 추가될 수 있다. 전기차량은 차량들이 이동을 하면서 충전을 하고, 이동에 대한 경로가 고정되어 있지 않기 때문에 차량들의 경로들이 가장 많은 곳을 찾기는 쉽지 않다. 이러한 불확 실성은 수요의 변동과 차량과 수요지의 변동 등이 원인이 라고 할 수 있다.

충전소의 최적위치를 찾는 연구는 주로 설비위치선정 문제와 차량경로문제를 두 단계로 나누어 해를 구하는 방 법을 많이 사용하였다. 먼저, 충전소는 수요지의 위치들을 고려하여 충전소가 담당할 수요지들이 적절하게 배분될 수 있는 위치가 선정이 되도록 한다. 충전소의 위치가 결 정이 되면 차량들을 이용한 차량경로문제에 대한 최적경 로를 찾게 되는데, 충전소의 위치를 거쳐 가도록 경로를 만들어 주어야 한다. 하지만, 모형이 다소 복잡하지만 충 전소의 위치와 차량의 경로를 함께 고려해서 최적해를 찾 는 것도 생각해 볼 수 있다. 또한 충전소의 용량도 고려하 여 차량의 경로를 설정하는 것이 필요하다.

본 연구는 전기차량의 차량경로문제와 충전소의 위치 선정문제를 함께 고려한 모형을 제시하고, 충전소의 용량 과 위치들에 따라 차량경로가 어떻게 변화되는지를 분석 해본다.

2. 선행연구

전기차량을 위한 충전소 위치를 찾는 문제는 많이 연구가 되어지고 있다. 문제의 모형에 있어서 다양한 모형이 제시 되고 있고, 문제의 형태에서 고려하는 부분과 제약을 두는 부분 등을 중심으로 최근에 연구가 활발히 진행중이다.

시뮬레이션을 이용하여 모형화 하거나 구현을 하는 연 구들이 진행되었는데, Huang and Kockelman[4]은 이득을 최대화 하는 충전소의 최적위치를 찾는 문제를 연구하였 다. 이 연구에서의 모형은 설치, 운영, 유지보수와 부지매 입을 포함한 관련 비용들을 고려하였다. 이 모형은 탄력적 인 수요와 차량들의 충전소 선택에 대해 교통체증과 정체 가 되고 있는 충전소를 고려하였다. 모형은 시뮬레이션을 기반으로 한 모형을 제안했고, 유전자 알고리즘으로 문제 를 해결하였다. Gong et al.[3]는 공공 전기 차량을 위한 충전소의 위치에 대한 연구를 진행하였다. 이들의 모형은 마일리지, 차량의 분포, 승객의 분포를 고려하였다. 에이 전트 기반의 시뮬레이션 모형을 이용하여 문제를 구현하 고 해를 찾았다. 이 연구의 내용은 우선순위, 마일리지, 차 량과 승객의 분포가 충전소 위치에 영향을 준다는 것을 보여주었고, 해당 모형은 인구가 밀집한 대도시에 적합하 다고 주장하였다. Li et al.[8]은 전기자동차 충전소 위치문 제를 풍력이나 광전지와 같은 재생에너지와 결합하여 문 제를 모형화하고 해결하려고 했다. 이들은 수요의 변화와 불확실성을 표현하기 위해 강건최적화 모형을 제안했고, 충전소의 저장용량에 대한 부분도 고려하였다. 이 모형은 시뮬레이션을 이용해서 구현이 되었으며 가능한 해 중에 서 최적의 조건을 찾는 과정을 수행하였다.

확정적 모형을 이용한 위치선정문제가 많이 연구되고 있고, 불확실한 상황을 반영한 확률적 모형을 이용한 연구 도 진행되고 있다. Lee and Han[7]은 충전소의 최적위치를 결정하기 위해 흐름충전위치모형(Flow refueling location model, FRLM)을 이용하였다. 이 모형은 출발지에서 도착 지까지 이송할 수 있는 흐름을 최대화 할 수 있는 문제를 다루었는데, 여러 가지 요인들로 인해 수송 영역이 확률적 으로 변하는 네트워크를 고려하였다. 이들 연구에서는 비 선형 혼합정수계획법을 사용하였는데, 해법으로는 Benders and price 방법을 사용하였다.

도로 상태, 교통혼잡도, 차량의 상태 등의 변화나 불확 실성을 반영하는 연구가 주로 많이 진행되어지고 있지만, 사람에 대해 초점을 두고 연구를 진행하기도 하였다. Lam et al.[6]은 전기자동차의 충전소 문제를 두 단계의 문제로 접근하였다. 첫 번째 단계는 충전소의 위치에 대해 부지사 용 형태, 환경영향, 안전 등의 요소를 고려하였고, 두 번째 단계의 문제는 운전자의 관점에서 인간과 관련된 요소를 이용하였다. 이 연구에서의 모형은 비선형혼합정수계획법 으로 해를 찾기 어려운 문제이기 때문에, 해법은 선형혼합 정수계획법을 여러 번 풀어서 해결하는 방법이나 탐색 방 법 등을 이용한 발견적 해법들을 이용하여 최적해를 구하 였다. Ahmad et al.[1]은 전기자동차에 관한 연구들에 대해 정리를 하였는데, 배송네트워크 운영자 관점, 충전소 주인 의 관점, 전기자동차의 주인의 관점에서 문제를 모형화 하 는 내용을 다루었다. 또한 해법으로 사용되는 알고리즘에 대한 내용과 최적해가 단일 최적인지, 다목적 최적인지에 대한 부분을 나누어 정리를 했다. 이러한 문제들과 함께, 전기자동차의 적재와 관련된 문제도 다루었다.

차량을 운송하는 물류업체를 기준으로 최적해를 찾는 연구가 많이 진행되고 있지만, 정부나 거주자를 위한 최적 방안을 찾는 연구도 수행되고 있으며, 사회적인 비용을 고 려한 연구들이 있었다. Luo and Qiu[9]는 도심에서의 전기 차량 충전소 위치문제를 다루었고, 예약서비스, 비혼잡 시 간대의 유휴, 혼잡시간대의 대기시간 등을 고려한 모형을 제안했다. 또한 모형에서는 정부의 입장에서 사회적 비용 을 고려하였고, 대기시간을 줄이고 시스템의 효율과 고객 의 만족도를 높이기 위해 예약서비스를 도입하였다. 문제 의 해는 유전자 알고리즘을 이용하여 예약시스템의 사용 과 관련 비용에 대한 민감도분석을 수행하였다. Zhou et al.[11]은 충전소에 대해 총 사회비용을 분석했는데, 시설 설치비용과 운영비용을 포함한 경제적 비용과 환경적 비 용으로 구분해서 비용을 추정하였다. 또한 충전소 위치선 정을 위해 문제를 모형화 하여 유전자 알고리즘으로 해를 구하였다. 또한 변전소의 위치선정과 관련된 문제들에 대 해서도 다루었다. 아일랜드의 실제 사례를 통해 충전소의 설치현황과 전기자동차의 보급대수를 비교하고 향후 대책 을 수립하기 위해 최적위치선정의 정보를 제공하였다.

전기차량경로문제와 위치선정문제는 차량경로문제에 복잡성이 추가된 형태로 모형화가 되기 때문에 해법은 주로 발견적 해법이 많이 이용되고 있다. Kizhakkan et al.[5]은 충전소 위치선정을 위한 연구들에 대해 정리를 하였는데, 주로 알고리즘과 모형이 어떤 것들이 사용 되었는지에 관 한 내용이다. 모형은 주로 혼합정수계획법이 많이 사용되 었으며, 알고리즘은 유전자 알고리즘과 같은 발견적해법이 주로 사용되었다고 정리를 했다. Meng and Kai[10]는 충전 소 위치선정문제를 위해 게임이론을 이용하였다. 비협조 완전정보 게임을 이용하여 위치선정문제를 모형화 하고, 내시균형 기반의 해를 찾아 최적의 전략으로 사용하였다. Chakraborty et al.[2]은 충전소 위치문제를 다목적계획법으 로 모형화 하였는데, 에너지 소비를 최소화 하는 것과 차량 이동시간을 최소로 하는 목적함수를 만들었다. 이들 모형은 그래프 기반으로 네트워크형태의 모형을 제안했으며, 다목 적계획법의 최적해를 찾기 위한 발견적해법 알고리즘을 제 안하였다.

3. 전기차량의 충전소위치경로문제

차량경로문제는 복수의 차량으로 수요지에 물품이나 서 비스를 보내주는 최적의 경로를 찾는 문제이다. 최적의 경 로는 주로 차량의 총이동거리나 총 수송비용을 최소로 하는 경로를 말한다. 차량경로문제는 외판원문제(TSP)와 통채우 기문제(Bin packing problem)를 결합한 문제이며 외판원문 제가 NP-hard 문제이기 때문에 차량경로문제도 해를 구하 기 어려운 문제라고 할 수 있다. 전기차량문제는 차량경로 문제에 충전소를 방문하여 충전하는 제약이 추가된 문제이 므로 더욱 복잡하면서 해를 찾기 어려운 문제이다.

전기차량경로문제는 수요지와 충전소를 방문하고 돌아 오는 문제인데, 본 연구에서는 이 문제에 충전소의 위치선 정문제를 결합한 문제를 다룬다. 충전소의 위치가 바뀌면 차량의 경로가 함께 바뀌게 되고, 충전소의 용량 또한 영 향을 준다.

전기차량에 대한 충전소과 관련된 문제들은 다양하다. 어느 충전소를 방문해야 되는지를 결정하는 충전소 방문 문제가 있고, 차량이 충전소에 도착하여 충전이 진행되는 데, 충전을 완전충전이 될 때까지 할지 또는 부분충전을 할지에 대해 결정하는 문제도 있다. 부분충전을 하는 경우 에는 충전시간을 얼마나 오래 지속해야 되는지에 대해 충 전함수를 추정하고 이를 이용해서 충전시간을 최적화 하 는 문제도 있다. 전기와 에너지의 사용율을 최적화 시키는 문제도 생각할 수 있다. 또한 단순히 차량경로문제의 확장 형 문제라고 볼 수도 있다. 이러한 모형화 측면 뿐만 아니 라 모형에 대해 어떻게 문제의 최적해를 찾을지에 대한 해법도 다양하게 연구되고 있다.

전기차량에 대한 충전소 위치선정과 경로문제는 아래 와 같다.

<Figure 1>은 전기차량의 충전소위치선정 차량경로문 제를 보여주고 있다. 복수의 차량이 수요지와 함께 수요지 와 다른 위치에 있는 충전소를 거쳐서 돌아오는 문제이다.

충전소 위치를 선정하는 문제는 실제로 충전소를 모든 위치에 설치를 할 수가 없다. 예를 들어, 도로 위나 물이 있는 지역은 충전소가 세워질 수 없는 지역들이다. 따라 서, 수요지를 고려하여 최적의 위치를 찾아도 그 위치에 설치하지 못할 수 있기 때문에, 일반적으로 충전소의 위치 를 찾기 위해서는 가능한 위치들을 찾아 놓고 이들 중에서 최적의 위치를 찾는 방법을 이용한다. 충전소의 위치가 차 량의 이동경로와 가까운 위치에 있어야 차량의 수송비용 도 줄어들고 효율을 높일 수가 있다. 복수차량의 이동경로 와 겹치거나 차량들의 이동경로들과 멀리 있는 경우에는 추가적인 시간소요와 수송비용의 증가를 초래한다. 따라 서 본 논문에서는 충전소로 이용이 가능한 위치들 중에서 어느 위치에 설치 또는 운영을 할지를 결정하는 위치선정 문제를 고려한다.

차량의 경로문제는 단기간의 최적 경로를 찾는 문제이 고, 충전소의 위치는 설치 후에 계속해서 사용할 수 있는 중장기적인 의사결정이라고 볼 수 있다. 하지만, 화물을 운송하는 한 업체를 위한 임시 충전소나 충전소에서 해당 업체를 위해 자리를 확보해 두는 비용을 고려하면 차량경 로와 함께 위치를 결정하는 문제로도 생각해 볼 수 있다.

이 논문에서는 차량경로문제에 대한 모형에서 출발하 여 충전소를 방문하고 돌아오는 제약이 추가된 전기차량 경로문제에 대한 모형을 제시하고, 이 모형에 충전소의 최 적위치를 찾는 부분이 고려된 충전소 위치선정과 전기차 량의 최적경로를 결합한 모형을 제시한다. 또한 충전소를 개설하는 비용이 위치에 따라 다를 때 차량의 최적해가 어떻게 변화하는지에 대해서도 살펴본다.

4. 충전소 위치선정을 고려한 모형

차량경로문제의 기본 모형은 시간제약(time window)을 갖는 차량경로문제를 사용한다. 복수차량으로 복수의 수 요지를 방문해야 하고 수요지는 원하는 배송시간이 존재 한다. 시간제약 차량경로문제를 시작으로 전기차량경로문 제와 충전소 위치선정을 위한 차량경로문제에 대한 모형 을 제시한다. 문제의 모형은 아래와 같다.

<집합>

0: (0: 차량의 출발위치 또는 도착위치),
V = {0, …, n} : 모든 노드집합
N = V∖0, n: 최종수요지
F : 충전소집합, F ′: 더미 충전소집합,
$A = {(i, j) | i, j \in V, i \neq j}$ : 아크집합,
M = {1, …, m } : 차량집합
$V^{+} (i) = {j \in V | (i, j) \in A}$ : 노든 i에서 나가는 아크들의 집합
$V^{-} (i) = {j \in V | (j, i) \in A}$ : 노드 i로 들어오는 아크들의 집합

<파라미터>

[a_i, b_i ]: 노드 i에 대한 시간제약(Time window)
s_i : 노드 i에 대한 서비스 시간
d_i,j: 노드 i에서 노드 j까지의 이동시간
q_i : 노드 i의 수요량
g : 단위에너지당 충전시간
h: 단위거리당 에너지소모량
Q : 차량의 최대에너지용량
w_i : 충전소 i가 개설되는 비용
L : 큰 수

<변수>

$x_{i, j}^{m}$ : 이진변수, 아크(i,j)∈A 가 차량 m에 의한 최적경 로에 포함되면 1, 아니면 0
$t_{i}^{m}$ : 차량 m이 노드 i에 도착하는 시간 (서비스의 시작 시간)
$y_{i}^{m}$ : 노드 i에서 차량 m의 에너지 수준
z_i : 이진변수, 충전소 i가 개설되면 1, 아니면 0

시간제약(time window)이 있는 차량경로문제는 아래와 같이 모형화 된다.

(VRP-TW)

M i n \sum_{m \in M} \sum_{(i, j) \in A} d_{i, j} x_{i, j}^{m}

(1)

s . t . \sum_{m \in M} \sum_{j \in V} x_{i, j}^{m} = 1, \forall i \in N,

(2)

\sum_{j \in V^{+} (0)} x_{0, j}^{m} = 1, \forall m \in M,

(3)

\begin{array}{l} \sum_{i \in V^{-} (h)} x_{i, h}^{m} - \sum_{j \in V^{+} (h)} x_{h, j}^{m} = 0 \\ \forall h \in N, \forall m \in M \end{array}

(4)

\sum_{i \in V^{-} (0)} x_{i, 0}^{m} = 1 \forall m \in M,

(5)

\sum_{i \in N} q_{i} \sum_{j \in V} x_{i, j}^{m} \leq K \forall m \in M,

(6)

\begin{array}{l} t_{i}^{m} + (s_{i} + d_{i, j}) x_{i, j}^{m} - t_{j}^{m} \leq (1 - x_{i, j}^{m}) L \\ \forall (i, j) \in A, m \in M \end{array}

(7)

a_{i} \leq t_{i}^{m} \leq b_{i}, \forall i \in N, m \in M

(8)

x_{i, j}^{m} \in 0, 1, \forall i, j \in V, m \in M

(9)

목적함수 (1)은 차량들의 총수송비용을 최소화 하는 것 을 나타낸다. 제약식 (2)는 최종수요지는 한 차량에 의해 서 한번만 방문된다는 것을 나타낸다. 제약식 (3)은 모든 차량들은 차량출발지에서 출발해야 되는 제약이다. 제약 식 (4)는 네트워크 흐름의 균형 제약식으로 한 노드로 들 어간 차량은 다시 그 노드를 나가야 되는 것을 의미하고, 한 노드는 하나의 차량만 거쳐가는 것도 나타낸다. 제약식 (5)는 모든 차량은 경로를 통과하고 다시 하나의 도착지로 돌아와야 된다는 제약이다. 제약식 (6)은 차량의 용량제약 으로 각 최종수요지의 수요를 충족시키면서 용량제약을 갖고 운행해야 되는 제약이다. 제약식 (7)은 시간제약(time window)으로 도착한 시간 이후에 서비스시간 동안에 그 노드에 머물고 서비스가 끝나면 다른 노드로 이동을 하는 것을 나타낸다. 제약식 (8)은 각 최종수요지마다 원하는 시간을 나타내는 시간제약(time window)을 나타낸다. (9) 는 이진변수의 정의를 나타낸다.

시간제약 차량경로문제에 전기차량에 대한 문제로 확 장하면, 전기차량이 충전소를 거쳐서 돌아오는 제약식들 이 추가된다. 충전소는 모든 충전소를 다 방문하지 않아도 되고, 일부분만 방문하도록 하면 되는 제약식이 추가된다. 이 모형은 아래와 같다.

(EVRP-TW)

M i n \sum_{m \in M} \sum_{(i, j) \in A} d_{i, j} x_{i, j}^{m}

(10)

s . t . \sum_{m \in M} \sum_{j \in V} x_{i, j}^{m} = 1, \forall i \in N

(11)

\sum_{m \in M} \sum_{j \in V} x_{i, j}^{m} \leq 1, \forall i \in F^{'}

(12)

\sum_{j \in V^{+} (0)} x_{0, j}^{m} = 1, \forall m \in M

(13)

\begin{array}{l} \sum_{i \in V^{-} (h)} x_{i, h}^{m} - \sum_{j \in V^{+} (h)} x_{h, j}^{m} = 0 \\ \forall h \in N, m \in M \end{array}

(14)

\sum_{i \in V^{-} (0)} x_{i, 0}^{m} = 1, \forall m \in M

(15)

\sum_{i \in N} q_{i} \sum_{j \in V} x_{i, j}^{m} \leq K, \forall m \in M

(16)

\begin{array}{l} t_{i}^{m} + (s_{i} + d_{i, j}) x_{i, j}^{m} - t_{j}^{m} \leq (1 - x_{i, j}^{m}) L \\ \forall (i, j) \in A, m \in M \end{array}

(17)

\begin{array}{l} t_{i}^{m} + d_{i, j} x_{i, j}^{m} + g (Q + y_{i}^{m}) \\ - t_{j}^{m} \leq (L - + g Q) (1 - x_{i, j}^{m}) \\ \forall i \in F^{'}, j \in N, m \in M \end{array}

(18)

\begin{array}{l} 0 \leq y_{j}^{m} \leq y_{i}^{m} - (h d_{i, j}) x_{i, j}^{m} + Q (1 - x_{i, j}) \\ \forall i, j \in N, m \in M \end{array}

(19)

\begin{array}{l} 0 \leq y_{j}^{m} \leq Q - (h d_{i, j}) x_{i, j}^{m} \\ \forall i, j \in N, m \in M \end{array}

(20)

a_{i} \leq t_{i}^{m} \leq b_{i}, \forall i \in N, m \in M

(21)

x_{i, j}^{m} \in {0, 1}, \forall i, j \in V, m \in M

(22)

t_{i}^{m} \geq 0, y_{i}^{m} \geq 0, \forall i \in V, m \in M

(23)

전기차량경로문제는 차량이 충전소를 방문하고 충전을 하면서 배송을 해야 하는 제약이 추가되는 모형이다. 먼저 목적함수 (10)는 총수송비용을 최소로 하는 경로를 찾는 것은 같다고 볼 수 있다. 전기를 이용하는 차량은 내연기 관 차량보다 주행할 수 있는 거리가 제한적이며 충전하는 시간도 많이 소요되는 특징이 있다. 충전소를 모두 방문하 지 않고 최적이 되는 일부분만 방문하도록 한다.

제약식 (12)는 모든 충전소가 사용되지 않아도 된다는 제약식이다. 제약식 (13)~(17)은 시간제약 차량경로문제와 같다. 제약식 (18)은 제약식 (17)이 서비스 시간에 대한 제 약인 것처럼 노드에서 충전시간에 대한 제약식을 나타낸 다. 제약식 (19)와 (20)은 각 노드에서의 에너지 소모에 따 른 제약식을 나타낸다. 제약식 (21)은 노드별 시간제약에 대한 제약식이고 제약식 (22)와 (23)은 변수 제약이다.

다음으로, 충전소 위치문제에 대해서, 본 논문에서는 전 기차량의 충전소에 대한 위치문제를 차량경로문제와 결합 하면서 문제를 단순화 하고자 한다. 차량은 한 경로를 전 부 운행할 용량이 충분하지 않다고 가정하고 경로 중에 한번은 충전소를 들렸다고 와야 된다고 가정한다. 이렇게 되면, 전기차량의 에너지 소모량과 충전량을 위한 제약식 은 필요없게 된다. 따라서 전기차량에 대한 차량경로문제 에 충전소의 위치선정을 위한 문제가 추가된 모형은 아래 와 같다.

(EVRP-TW-CL)

\begin{array}{l} M i n \sum_{m \in M} \sum_{(i, j) \in A} d_{i, j} x_{i, j}^{m} \\ + \sum_{i \in F^{'}} w_{i} z_{i}, \end{array}

(24)

s . t . \sum_{m \in M} \sum_{j \in V} x_{i, j}^{m} = 1, \forall i \in N

(25)

\sum_{m \in M} \sum_{j \in V} x_{i, j}^{m} \leq 1, \forall i \in F^{'}

(26)

\sum_{j \in V}^{+} (0) x_{0, j}^{m} = 1, \forall m \in M

(27)

\begin{array}{l} \sum_{i \in V^{-} (h)} x_{i, h}^{m} - \sum_{j \in V^{+} (h)} x_{h, j}^{m} = 0 \\ \forall h \in N, m \in M \end{array}

(28)

\sum_{i \in V^{-} (0)} x_{i, 0}^{m} = 1, \forall m \in M

(29)

\sum_{i \in N} q_{i} \sum_{j \in V} x_{i, j}^{m} \leq K, \forall m \in M

(30)

\begin{array}{l} t_{i}^{m} + (s_{i + d_{i, j}}) x_{i, j}^{m} - t_{j}^{m} \leq (1 - x_{i, j}^{m}) L \\ \forall (i, j) \in A, m \in M \end{array}

(31)

\sum_{i \in N, j \in F^{'}} x_{i, j}^{m} = 1, \forall m \in M

(32)

x_{i, j}^{m} \leq z_{i}, \forall i \in F^{'}, j \in N, m \in M

(33)

x_{i, j}^{m \leq z_{j}}, \forall i \in N, j \in F^{'}, m \in M

(34)

a_{i} \leq t_{i}^{m} \leq b_{i}, \forall i \in N, m \in M

(35)

x_{i, j}^{m}, z_{i} \in {0, 1}, \forall i, j \in V, m \in M

(36)

t_{i}^{m} \geq 0, \forall i \in V, m \in M

(37)

목적함수 (24)는 차량의 총 이동거리와 충전소를 개설 하는 총비용을 최소로 하는 것을 목표로 한다. 이것은 충 전소별 개설비용이 다른 경우에 이동거리와 충전소 개설 비용을 고려하여 최적의 개설 위치를 찾도록 해준다. 제약 식 (25)~(31)은 전기차량경로문제와 같다. 제약식 (32)는 차량이 충전소를 한번은 방문해야 하는 제약식이다. 제약 식 (33)과 (34)는 충전소가 개설되는 노드로 차량이 이동 한다는 제약식이고, 제약식 (35)는 시간제약이며, 제약식 (36)과 (37)은 변수제약이다.

제안된 모형은 복수의 전기차량이 충전소를 거치면서 수요지를 한 번씩 방문하며 돌아오는 최적경로를 찾는 문제 로 충전소의 위치가 가능한 수요지를 방문하는 경로와 멀지 않게 하면서 총수송비용이 최소가 되도록 하는 경로를 찾고 최적의 위치를 갖는 충전소의 위치도 찾는 모형이다.

5. 실험결과

차량경로문제에 전기 충전소의 위치선정을 고려한 문 제에 대해 간단한 예제를 통해 결과를 살펴본다. 문제의 모형 EVRP-TW-CL에 대해 공개된 차량경로 데이터인 Solomon benchmark 문제 중에 하나를 충전소들의 가능한 위치들을 추가한 데이터를 이용하여 실험을 진행한다.

<Figure 2>는 실험에 사용된 예제 데이터를 보여주는데, 출발점(Depot)이 있고 수요지들이 지리적으로 흩어져 있 으며, 복수의 차량을 이용하여 화물을 배송하는 문제이다. 이 예제에서 수요지는 100개, 차량은 10대이고 그림에서 진한 점으로 표현된 가능한 충전소는 21개이다.

모형은 C#으로 구현되었고, C#에서 concert technology 를 이용해서, 해는 CPLEX 12.6.1 를 이용하여 구하였다. 차량의 대수는 10대로 고정되어 있다고 가정하였고, 충전 소의 운영비용(개설비용)이 동일한 경우와 위치별로 다른 경우에 대해 최적경로가 변화되는지를 살펴보았다. 실험 결과는 최적해에서 차량들이 어떤 충전소를 선택하였는지 를 나타낸다.

<Figure 3>은 목적함수에서 충전소의 개설 또는 운영 비용을 고려하는 항을 제외하고 문제를 풀었을 때의 해를 보여준다. 21개의 가능한 충전소 위치에서 차량들이 각각 하나의 충전소를 이용한 것을 보여준다.

목적함수에서 충전소의 개설비용을 고려한 경우에 대 한 실험결과는 다음과 같다.

<Figure 4>는 목적함수에 충전소 개설비용 항목을 고려 하는 경우의 해를 보여준다. 이 경우에 모든 위치의 개설 비용을 동일하게 4.0으로 주었을 때, 고려하지 않았을 때 의 <Figure 3>의 해와 차량들이 충전소를 이용하는 것이 동일하다는 것을 알 수 있다.

<Figure 5>는 가능한 충전소 위치들 중에서 1~10번 노 드들은 개설비용을 4.0으로 하고 나머지 노드들의 개설비 용은 9.0으로 했을 경우의 해이다. 충전소 개설비용을 고 려하지 않은 <Figure 4>의 결과와 비교하면, 충전소를 이 용하는 차량들이 바뀐 것을 볼 수 있다. 하지만, 사용된 충전소는 case 1 에서 보여준 충전소들과 같고 이용한 차 량만 다른 것을 볼 수 있다.

<Figure 6>은 <Figure 5>와 대비하여 1~10 노드의 충전 소 개발비용을 9.0, 11~20 노드의 비용을 4.0으로 바꾸었 을 때의 해를 보여준다. 이 결과에서는 case 2의 결과와 비교하면, 충전소 중에서 2번이 사용되지 않았고 16번이 사용된 것을 볼 수 있다. 충전소와의 거리가 가까워도 충 전소의 개설비용이 높으면 다른 충전소를 이용하는 것을 알 수 있다.

<Figure 7>은 충전소 개설비용을 1.0과 4.0 사이의 임의 의 수를 넣어서 문제의 해를 구한 결과를 보여준다. 이 결 과는 차량들이 이용하는 충전소의 순서가 다르지만, case 1과 case 2와 같이 사용된 충전소들의 노드들은 같은 것을 볼 수 있다.

차량이 충전소까지의 거리가 가까워도 충전소의 개설 비용이 크면, 거리가 먼 충전소를 이용할 수 있고, 충전소 의 개설비용이 상대적으로 크지 않으면, 충전소 개설비용 이 위치별로 같이 않더라도 거리를 기준으로 결정된 경로 를 선택하는 것을 볼 수 있다.

<Figure 8>은 <Figure 7>의 case 4 처럼 충전소 개설비 용에 임의의 수를 할당하였는데 비용을 1.0에서 9.0으로 좀 더 큰 값으로 설정한 경우의 결과이다. 이 경우에는 충 전소 중에서 17이 사용되지 않았고 15가 사용된 것을 볼 수 있다. 개설비용이 큰 경우에는 거리에 의존하지 않고 개설비용에 의존해서 경로를 결정하는 것을 볼 수 있다.

<Figure 9>는 충전소 개설비용에 좀 더 편차를 크게하 여 변화를 주었을 때의 해를 보여준다. case 5와 비교하면, 충전소 2와 15가 사용되지 않고 충전소 11과 16이 새롭게 사용된 것을 볼 수 있다.

전기차량의 경우에 차량의 배송 경로 중간에 충전이 필 요한 경우에 배송업체를 위해 임시로 충전소를 개설하거 나 기존의 충전소에서 해당 업체의 차량을 위해 자리를 확보하는 등의 비용이 발생할 경우에 차량이 어느 충전소 를 선택해야 최적인지를 찾는 예제를 살펴보았다. 충전소 의 개설비용이 작은 경우에는 충전소까지의 거리를 기반 으로 충전소를 선택하게 되고, 충전소의 개설비용이 크면 거리가 멀지만 비용이 적게 드는 충전소를 선택하는 것을 알 수 있다.

6. 결 론

내연기관을 이용한 차량으로 인한 배기가스가 공기오 염의 원인 중에 하나로 알려지면서, 환경에 대한 문제의식 을 갖고 최근의 자동차 산업에서는 전기차의 생산이 늘리 고 있다. 이러한 상황은 전기차에 대한 개발과 연구를 활 발하게 만드는 원동력이 되고 있다. 차량경로문제에 대한 연구도 전기차량에 대한 경로문제로 확장되어 연구가 진 행되고 있다. 하지만, 전기자동차는 여전히 충전에 관한 문제가 해결되어야 할 부분으로 남아있다. 충전에 걸리는 시간도 문제이고 충전소의 위치도 중요한 문제가 되고 있 다. 따라서, 충전소의 위치선정은 전기차량경로문제에서 중요한 부분을 차지한다.

본 연구에서는 전기차량경로문제를 다루는데, 충전소 의 위치선정에 대한 문제도 함께 고려했다. 시간제약이 있 는 차량경로문제의 모형에서 출발하여, 전기차량경로문제 에 대한 수리모형을 제시하였고, 배송업체를 위한 임시충 전소나 충전소에서의 자리확보 등을 고려하여 어떤 충전 소를 선택하는 것이 최적인지를 찾는 모형을 제안했다. 또 한 간단한 예제를 통해 충전소 개설비용이 위치별로 같은 경우와 다른 경우에 차량들이 충전소를 선택하는 결정에 변화가 있는지를 살펴보았다.

실험결과를 통해, 충전소의 개설비용이 위치별로 다른 경우에 차량들의 충전소 선택에 대한 결정이 달라지는 것 을 확인하였다. 개설비용이 작은 경우는 차량들이 최적경 로로 이동하면서 경로와 가장 가까운 충전소를 이용하여 이동거리에 의존한 의사결정을 하게 되고, 개설비용이 큰 경우에는 충전소까지의 위치가 가깝더라도 비용을 줄이기 위해 멀리 있는 충전소를 이용하는 것을 알 수 있다. 이 결과를 이용하면, 충전소의 개설비용에 따라 차량이 충전 소를 선택할지를 결정할 수 있는 하한값을 제공해 줄 수 있고, 충전을 위한 준비를 해야 되는지도 결정하는데 도움 을 줄 수 있을 것으로 보인다.

Acknowledgement

This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government( MSIT) (No. 2021R1A2C10141801231482092260102).

Figure

<Figure 1>.

Charging Station Location Electric Vehicle Routing Problem

<Figure 2>.

Distribution Network with Charging Stations

<Figure 3>.

Result without Considering Charging Station Cost

<Figure 4>.

Result of Case 1 (All Charging Station Costs are 4.0)

<Figure 5>.

Result of Case 2 (Charging Station Costs of 1~10: 4.0, those of 11~21: 9.0)

<Figure 6>.

Result of Case 3 (Charging Station Costs of 1~10: 9.0, those of 11~21: 4.0)

<Figure 7>.

Result of Case 4 (Charging Station Costs are Random Numbers between 1 and 4)

<Figure 8>.

Result of Case 5 (Charging Station Costs are Random Numbers between 1 and 9)

<Figure 9>.

Result of Case 6 (Charging Station Costs of 1~10: Random in (10, 20), those of 11~21: Random in (1,5))

Table

Reference

Ahmad, F. and Iqbal, A., Ashraf, I., Marzband, M., Khan, I., Optimal location of electric vehicle charging station and its impact on distribution network: A review, Energy Reports, 2022, Vol. 8, pp. 2314-2333.
Chakraborty, N., Mondal, A., and Mondal, S., Intelligent charge scheduling and eco-routing mechanism for electric vehicles: A multi-objective heuristic approach, Sustainable Cities and Society, 2021, Vol. 69, p. 102820.
Gong, D., Tang, M., Buchmeister, B., and Zhang, H., Solving Location Problem for Electric Vehicle Charging Stations— A Sharing Charging Model, IEEE Access, 2019, Vol. 7, pp. 138391-138402.
Huang, Y. and Kockelman, K.M., Electric vehicle charging station locations: Elastic demand, station congestion, and network equilibrium, Transportation Research Part D: Transport and Environment, 2020, Vol. 78, p. 102179.
Kizhakkan, A.R., Rathore, A.K., and Awasthi, A., Review of Electric Vehicle Charging Station Location Planning, IEEE Transportation Electrification Conference (ITEC-India), 2019, pp. 1-5.
Lam, A.Y.S., Leung, Y.W., and Chu, X., Electric Vehicle Charging Station Placement: Formulation, Complexity, and Solutions, IEEE Transactions on Smart Grid, 2014, Vol. 5, No. 6, pp. 2846-2856.
Lee, C., and Han, J., Benders-and-Price approach for electric vehicle charging station location problem under probabilistic travel range, Transportation Research Part B: Methodological, 2017, Vol. 106, pp. 130-152.
Li, C., Zhang, L., Ou, Z., Wang, Q., Zhou, D., and Ma, J., Robust model of electric vehicle charging station location considering renewable energy and storage equipment, Energy, 2022, Vol. 238, Part A, p. 121713.
Luo, X. and Qiu, R., Electric Vehicle Charging Station Location towards Sustainable Cities, International Journal of Environmental Research and Public Health, 2020, Vol. 17, No. 8, 2785.
Meng, W. and Kai, L., Optimization of electric vehicle charging station location based on game theory, Proceedings 2011 International Conference on Transportation, Mechanical, and Electrical Engineering (TMEE), 2011, pp. 809-812.
Zhou, G., Zhu, Z., and Luo, S., Location optimization of electric vehicle charging stations: Based on cost model and genetic algorithm, Energy, 2022, Vol. 247, p. 123437.