제주대학교 Repository

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

Metadata Downloads
Alternative Title
A tour and Charging scheduler for electric vehicles based an (n+1)Traveling Salesman Problem Modeling.
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.
Author(s)
오호건
Issued Date
2014
Awarded Date
2015. 2
Type
Dissertation
URI
http://dcoll.jejunu.ac.kr/jsp/common/DcLoOrgPer.jsp?sItemId=000000007057
Alternative Author(s)
Ho-Gun Oh
Department
대학원 전산통계학과
Table Of Contents
I. 서 론 1
II. 배경과 관련 연구 4
1. 전기자동차 동향 4
2. 관광-충전 스케줄 6
III. 제안 기법 12
1. 기본 가정 12
2. ODBC릍 통한 리눅스와의 연결 13
3. 제안 기법 20
IV. 성능평가 23
V. 결 론 28
Ⅵ. 참고문헌 30
Degree
Master
Publisher
제주대학교 대학원
Citation
오호건. (2014). (n+1)TSP 모델링에 기반한 전기자동차 투어-충전 스케줄러
Appears in Collections:
General Graduate School > Computer Science and Statistics
Authorize & License
  • AuthorizeOpen
Files in This Item:

Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.