전기 자동차 네트워크를 위한 충전 스케줄링 문제

전기 자동차(EV)는 낮은 탄소 배출과 높은 에너지 효율성 등 많은 이점을 가진 유망한 교통수단입니다. 그러나 빈번하고 긴 충전이 필요합니다. 공공 충전소에서는 특히 피크 시간대에 EV들이 긴 대기 시간을 겪습니다. 따라서 EV의 총 충전 시간을 줄이기 위한 효율적인 방법이 필요합니다. 본 논문에서는 전기 자동차 충전 스케줄링(EVCS) 문제를 연구합니다. 먼저 EVCS가 NP-완전임을 증명하며, 이는 하나의 병렬 기계 스케줄링(PMS) 문제로부터 축소될 수 있습니다. 그 후, 두 가지 휴리스틱 알고리즘을 제안합니다: 가장 이른 시작 시간(EST) 알고리즘과 가장 이른 종료 시간(EFT) 알고리즘입니다. EST는 고객을 가능한 빨리 서비스하기 위해 충전 시작 시간을 앞당기려고 하고, EFT는 가능한 충전 종료 시간을 기반으로 고객이 가능한 빨리 서비스받도록 합니다. 마지막으로 시뮬레이션 결과, 제안된 알고리즘이 고전적인 탐욕스러운 가장 가까운 스케줄링 알고리즘보다 우수함을 보여줍니다: 각 EV를 가장 가까운 충전소에 배정한 후, 대기 중인 EV가 가장 적은 출구를 선택합니다. 일반적으로, 우리의 시뮬레이션 설정 하에서 평균 종료 시간과 최대 종료 시간은 각각 약 한 시간과 여섯 시간이 줄어들 수 있습니다.