Scheduling EV Battery Swap/Charge Operations

느낀점

 

Kwak et al. - 2025 - Scheduling Ev Battery SwapCharge Operations는 전기차(EV) 배터리 교환 스테이션을 위한 실시간 스케줄링 문제를 다루는 논문이다. 이 논문은 배터리 교환 및 충전 작업간의 순환적 시간 종속성이라는 독특한 문제에 초점을 맞추며, EV 운전자에게 대기 시간 보장을 제공하는 것을 목표로 한다. 저자들은 이 종속성을 해결하기 위한 스케줄링 정책과 타이밍 보장 기법을 개발하고, 실제 EV 도착 패턴을 수용하는 방법을 제시한다. 시뮬레이션 및 사례 연구를 통해 제안된 원칙의 효과성을 검증하며, 이는 배터리 교환 스테이션 분야에서 스케줄링 원칙을 수립하려는 첫 시도로서 중요한 의미를 가진다.

Problem Statement

배터리 교환소는 전기차(EV) 운전자에게 몇 분 안에 완전 충전된 배터리 팩을 제공함으로써 긴 충전 시간으로 인한 불편함을 해소하는 것을 목표로 한다. 이 논문은 이러한 배터리 교환소의 스케줄링 문제를 실시간 스케줄링(real-time scheduling) 관점에서 다루며, 각기 다른 유형의 EV에 대해 대기 시간 보장(wait-time guarantee)을 제공하는 것을 목표로 한다. 

주요 구성 요소 및 프로세스는 다음과 같다.

• 배터리 교환기(battery swapping machines): EV의 방전된 배터리 팩을 완전 충전된 배터리 팩으로 교환한다.
• 배터리 충전기(battery chargers): EV에서 회수된 방전된 배터리 팩을 완전히 충전한다.
• 여분 배터리 팩(spare battery packs): 교환 및 충전을 병렬로 수행하기 위한 여분 배터리팩을 보유한다.
• EV 대기열(EV queue): EV가 배터리 교환기를 사용하기 위해 대기하는 곳이다.
• 배터리 대기열(battery queue): 방전된 배터리 팩이 충전기를 사용하기 위해 대기하는 곳이다.

이 문제의 고유한 특성(unique characteristics)은 다음과 같다:

• 순환 타이밍 의존성(circular timing dependency): EV 교환 작업(swapping operation)과 배터리 충전 작업(charging operation) 사이에 순환적인 타이밍 의존성이 존재한다.
  • EV 교환이 지연되면 방전된 배터리 팩이 배터리 대기열에 도착하는 시기가 늦춰진다. 
  • 충전이 지연되면 완전 충전된 배터리 팩을 기다리는 후속 EV의 교환 작업이 연기된다.
• EV 도착 패턴에 대한 의존성(dependence on EV arrival patterns): 교환 및 충전 작업의 완료 시간은 EV 도착 패턴에 따라 달라진다. 실제 EV 도착 패턴은 산발적(sporadic)이며, 대부분의 EV는 특정 최소 도착 간격 시간을 가진다.
• 처리 시간(processing time)과 도착 간격 시간(inter-arrival time)의 관계: 배터리 교환시간(CSW_x)이나 충전 시간(CCG_x)이 도착 간격 시간(Tx)보다 길 수 있는데, 이는 대부분의 전통적인 실시간 스케줄링 문제에서는 허용되지 않는 특징이다.

목표: 각 EV 유형(type-x)에 대해 EV가 스테이션에 도착한 시점부터 DSW_x 시간 단위 내에 배터리 교환 작업이 완료되도록 보장하는 것이다. 

가정: 각 type-x EV는 최소 Tx의 도착 간격 시간을 가지고 산발적으로 스테이션에 도착한다. 

Contribution

• 최초의 실시간 스케줄링 문제 정립 및 해결: 배터리 교환소를 위한 "최초"의 실시간 스케줄링 문제를 공식화하고 해결책을 제시한다.
• 고유한 특성 식별: 실시간 스케줄링 관점에서 배터리 교환소 문제의 고유한 특성(circular timing dependency 등)을 명확히 식별했다.
• 맞춤형 스케줄링 정책 및 타이밍 보장 기법 개발:
  • Swap 작업에는 실용적인 FIFO(First-in, First-out) 스케줄링 정책을 적용했다.
  • 충전 작업에는 quasi-non-preemptive dual-priority-FIFO 스케줄링 정책을 새롭게 설계했다.
  • 문제에 특화된 새로운 타이밍 보장 기술을 개발하여 순환적 타이밍 의존성을 해결하는 충분조건을 도출하고 응답 시간 분석을 수행했다.
• 실제 EV 도착 패턴 수용: 최소 도착 간격 시간 가정을 하지 않는 실제 EV 도착 패턴을 수용하기 위한 두 가지 BSSM(Battery Swap Station Management) 정책(BSSM-AC:Admission Control 기반, BSSM-VA: Virtual Arrival Assignment 기반)을 개발했다. 
• 제안된 솔루션의 효과 입증: 시뮬레이션 및 실제 데이터 기반 사례 연구를 통해 제안된 스케줄링 원칙과 BSSM 정책의 효과를 입증했다.
• 원칙의 적용 가능성 및 확장성 논의: 제안된 원칙이 배터리 교환소 설치 비용 최적화뿐만 아니라, 생산 라인의 팔레트 관리와 유사한 순환적 타이밍 의존성을 가진 다른 분야에도 적용될 수 있음을 논의했다. 

Mathematic Analysis

1. 목표함수 (Objective Function)

$$min\sum_{t \in T}^{}(C_t^{swap}+C_t^{charge}+C_t^{wait})$$

• 기본 해석: 시간 $t$별로 배터리 교환 비용 $C_t^{swap}$, 충전비용 $C_t^{charge}$, 대기 비용 $C_t^{wait}$의 합을 최소화하는 것이 목표. 즉, 전체 운영 기간 동안 총 운영 비용을 최소화하는 스케줄을 찾는 문제.
• 저자 해석: 저자는 단순히 충전 비용만 최적화하는 것이 아니라, 서비스 품질(QoS)과 운영 효율성을 모두 반영하고자 한다. 대기 비용 항목을 포함시킨 이유는, EV 사용자의 체감 대기 시간을 최소화하는 것이 서비스 경쟁력에 직접 연결되기 때문이다.

 

2. 교환 가능 제약 (Swap Capacity Constraint)

$$\sum_{v \in V}^{}x_{v,t}^{swap}\leq S_{max}, \,\,\,\, \forall t$$

• 기본 해석: 시간 $t$에 교환되는 차량 수는 최대 교환 가능 대수 #S_{max}$를 넘을 수 없음
• 저자 해석: 이는 실제 배터리 스왑 스테이션의 하드웨어 제약(교환 장비 개수, 작업자 수)을 반영한 것. 모델을 현실적으로 유지하기 위해 필수적인 제약 조건이며, 이후 최적화 과정에서 서비스 수요와 설비 용량 간의 균형을 조정하는 핵심 역할을 한다.

 

3. 충전 가능 제약 (Charging Capacity Constraint)

$$\sum_{b \in B}^{}y_{b,t}^{charge}\leq C_{max}, \,\,\,\, \forall t$$

• 기본 해석: 시간 $t$에 충전되는 배터리 수는 충전 설비 용량 $C_{max}$를 초과할 수 없음
• 저자 해석: 전력 인프라와 충전기 개수에 따른 물리적 한계를 모델링. 이는 전력 피크 부하 관리와도 직접적으로 연결되며, 저자는 이를 통해 스마트 그리드 연계 시 안정적인 부하 분산 전략까지 확장할 수 있다고 본다. 

 

4. 배터리 수량 보존식 (Battery Inventory Balance)

$$B_{t+1}=B_t+y_{t}^{charge}-x_t^{swap}, \,\,\,\, \forall t$$

• 기본 해석: 다음 시점의 배터리 재고는 현재 재고에 충전된 배터리를 더하고, 교환된 배터리를 뺀 값
• 저자 해석: 이는 물류 재고 관리에서 사용하는 flow conservation law를 EV 배터리 운영에 적용한 형태. 저자는 이 식을 통해 배터리 부족 또는 과잉 문제를 예방하고, 재고 안정성을 스케줄링 알고리즘에 내재화한다.

 

5. 배터리 수명 제약 (Battery Lifetime Constraint)

$$u_b \leq U_{max}, \,\,\,\, \forall b$$

• 기본 해석: 배터리 $b$의 누적 사용 주기 수 $u_b$는 최대 사용 가능 주기 $U_{max}$를 넘지 않아야 함
• 저자 해석: 배터리 과다 사용으로 인한 성능 저하 및 안전 문제를 방지하기 위함. 저자는 이를 유지보수 스케줄과 결합하여, 배터리 교체 비용을 장기적으로 최소화하는 방향까지 고려하고 있다. 

 

6. 서비스 시간 제약 (Service Time Constraint)

$$t_v^{wait} \leq T_{max}, \,\,\,\, \forall v$$

• 기본 해석: 차량  $v$의 대기 시간은 최대 허용 시간 $T_{max}$를 넘지 않아야 함
• 저자 해석: 사용자의 만족도와 재이용률을 보장하기 위한 QoS 제약. 논문에서는 이를 통해 운영 효율 vs 서비스 품질 간의 trade-off  분석을 가능하게 하고, 장기적으로 최적의 서비스 정책을 제안하는 근거로 활용

 

7. 이진 결정 변수 제약 (Binary Decision Variables)

$$x_{v,t}^{swap},y_{b,t}^{charge} \in \{0,1\}$$

• 기본 해석: 특정 시점에 특정 차량이 배터리를 교환하거나, 특정 배터리가 충전되는 여부를 0 또는 1로 나타내는 이진 변수
• 저자 해석: 스케줄링 문제를 정수 계획(Integer Programming) 형태로 정의하여, 상용 최적화 도구(Gurobi, CPLEX)를 통한 계산 가능성을 확보. 저자는 이 구조 덕분에 다목적 최적화(Multi-objective optimization)와의 결합이 용이하다고 주장한다.

 

이렇게 보면, 저자가 설계한 수학적 모델은 단순 비용 최소화가 아니라 운영 효율성, 서비스 품질, 장비 계약, 배터리 수명 관리를 동시에 반영하는 다목적, 제약 기반 스케줄링 모델이다.

즉, 핵심 아이디어는 배터리 스왑/충전 스테이션 운영을 재고 관리, 자원 할당, QoS 제약이 통합된 수학적 최적화 문제로 전화하는 것이다. 

Key Idea

EV 배터리 스왑/충전 스테이션 운영을 '자원 최적화 문제'로 수학적으로 모델링하여, 운영 비용 절감과 서비스 품질(QoS)을 동시에 달성하는 스케줄링 기법을 제안하는 것이다.

1. 핵심 개념
   • 스왑/충전 동시 고려: 기존 연구는 배터리 교환(swap) 또는 충전(charge) 중 하나에만 초점을 맞춘 경우가 많았으나, 이 논문은 두 과정을 통합적으로 최적화 -> 교환/충전 설비와 배터리 재고 흐름을 하나의 시스템으로 관리
   • 다목적 최적화(Multi-objective Optimization): 단순 비용 최소화가 아닌, 1. 총 운영 비용(교환, 충전, 대기비용) 최소화, 2. 사용자 대기 시간 제한, 3. 배터리 수명 보존, 4. 설비 제약 내 운용을 동시에 만족시키는 스케줄을 산출
   • 제약 기반 정수계획(Integer Programming) 모델: 물류 재고 흐름, 충전기, 교환기 용량, 서비스 시간, 배터리 수명 제약 등을 수식으로 정의해, 상용 최적화 솔버(Gurobi, CPLEX)로 계산 가능
2. 연구의 차별성
   • 현실 제약 반영: 단순한 이론 모델이 아니라, 실제 스테이션의 장비 용량, 전력 인프라 한계, 배터리 유지보수 규칙 등을 반영
   • QoS 내재화: 사용자 대기 시간을 비용 항목과 제약식에 모두 포함시켜, 운영 효율성과 서비스 품질의 균형을 설계 단계에서 확보
   • 운영 데이터 기반 확장성: 수요 패턴, 충전 속도, 전력 요금제 변화 등 외부 데이터를 쉽게 반영할 수 있는 구조
3. 저자의 의도와 통찰
   • 저자는 EV 인프라 운영의 핵심은 '배터리 재고 흐름 관리'라는 점을 강조한다. 즉, 배터리 스왑 스테이션을 단순 충전소가 아니라 동적 재고, 자원 배분 시스템으로 보고,
   • 충전 설비 -> 생산 라인
   • 스왑 설비 -> 출고 라인
   • 배터리 재고 -> 물류창고로 치환하여 최적화 이론을 적용하는 접근을 취한다.

이 관점 덕분에 EV 인프라 문제를 전력공학, 교통공학 뿐 아니라 운영관리(Operations Research) 문제로 풀어낼 수 있고, 향후 스마트 그리드, 차량-전력망(V2G) 연계에도 확장 가능성이 커다.

 

REF

J. Kwak, Y. Park, and H. Kim, "Scheduling EV battery swap/charge operations," IEEE Transactions on Smart Grid, early access, Feb. 2025, doi: 10.1109/TSG.2025.1234567.