(n+1)TSP 모델링에 기반한 전기자동차 투어-충전 스케줄러

Abstract

전기자동차는 배터리에 저장된 전기에 의해 구동되므로 운송 시스템마저도 전력 네트 워크의 한 부분으로 만들어 에너지 사용의 효율을 향상시킬 수 있을 뿐 아니라 공해물 질 배출을 감소시킬 수 있다. 반면 주행거리가 짧고 충전시간이 길다는 단점이 있는데 급속 충전으로도 수십분이 소요된다. 이를 극복하기 위해 지능적인 컴퓨터 알고리즘을 바탕으로 에너지 효율적인 주행계획을 수립하여야 한다. 본 논문에서는 다중목적지를 방문하는 렌터카를 위한 방문-충전 스케줄러를 설계하고 그 성능을 평가한다. 현재 급 속 충전기의 확산과 일일 관광 거리를 고려한다면 하루 1회의 급속충전이면 관광에 지 장이 없다. 결국, 해결하고자 하는 문제는 n 개의 관광지가 주어졌을 때, m 개의 충전 기중 하나를 추가적으로 포함하는 (n+1) 목적지에 대한 방문순서를 결정하는 것이다. 모든 m 개의 충전기에 대해 (n+1)!의 방문순서에 따르는 비용을 계산하면 최적의 답을 구할 수는 있으나 계산시간이 폭증한다. 따라서, m 대신 오직 m' (m' << m)개만의 충전기를 사전에 지능적으로 필터링하여 서치 스페이스를 줄임으로써 납득할 만한 수 준의 답을 빠른 시간 내에 구할 수 있다. 이를 위하여 모든 m 에 대해 관광지 집합까 지의 최소거리를 구하고 가장 근접한 m' 개의 후보를 선택한다면 전체 투어 길이의 증 가를 최소화할 수 있으며 배터리 소모도 줄일 수 있어서 추가적인 충전도 피할 수 있 다. 각 (n+1) 목적지의 방문순서에 있어서 운행에 따르는 배터리 잔량을 추적하여 배터 리 고갈이 일어난다면 그 솔루션은 제외한다. 프로토타입 구현에 의해 실제 제주도 도 로 네트워크를 대상으로 수행된 성능 평가는 주어진 인자 집합에 대해 최적의 스케줄 과 비교시 투어 길이의 차이는 단지 1% 에 불과하고 0.7의 확률로 최적의 스케줄을 발 견한 반면, 5/29의 속도향상을 불러왔다. 순수 관광거리에 따르는 실험 결과, 최적의 스 케줄과 비교하여 주행거리는 최대 7% 정도밖에 증가하지 않았다.

Electric vehicles, or EVs in short, are powered by battery-stored electricity, making even the transport system a part of the power network. They cannot only enhance the energy efficiency but also reduce air pollution, however, their driving range is quite short and it takes tens of minutes do charge an EV even with a fast charger. Intelligent computer algorithms can overcome this problem by finding an energy-efficient route. Targeting at EV rent-a-cars willing to visit multiple destinations, this thesis designs a tour-and-charging scheduler and evaluates its performance. Considering the ongoing penetration of fast chargers and the common daily tour length, a single fast charging is enough for an average trip schedule. In addition to the given n destinations, our scheme selects 1 out of m charging stations, simultaneously making a tour plan for (n+1) spots. For m chargers, the cost estimation of all (n+1)! feasible sequences can obtain the best solution, but inevitably brings computation time explosion. Our approach cuts down the search space not taking m but m' (m >> m') stations intelligently filtered by the distance criteria. It finds an acceptable quality schedule within a sufficiently fast response time. Here, for all m station, the minimum distance to any of n destinations is calculated and the smallest m' stations are selected. The heuristic can suppress the increase in the tour length, reduce battery consumption, and avoid additional charging. The performance measurement result, obtained by a prototype implementation on real-life tour spot distribution in Jeju, Republic of Korea, shows that our scheme increases the tour length just by 1 %, compared with the optimal scheme, achieving the speedup of 5/29 for the given parameter set having 7 destinations. The increase in the pure tour distance can lead to 7 % overhead in the final tour length.