Optimal Battery Swapping and Rebalancing in Electric Micro-mobility Sharing Systems

Abstract

In this thesis, we consider a battery swapping and mobility inventory rebalancing problem arising in electric micro-mobility sharing systems. Vehicles are equipped with swappable batteries and they are managed by staffs' visiting each vehicle and changing depleted batteries. With the free-floating property of the system, vehicles can locate anywhere in a service area without designated stations, which increases the difficulty to visit and collect every single vehicle. In order to successfully meet user demand during the daytime, operators have to redistribute the vehicles with the right number in the right place and swap batteries with insufficient levels into fully charged ones overnight. Therefore, it is essential that operators take battery charging(swapping), staff routing, rebalancing problem all together into consideration. We aim to satisfy demand as much as possible and at the same time minimize routing and swapping costs. We formulate this problem in a mixed integer linear programming. Target inventory level for rebalancing, an important parameter used in the system, is suggested by analyzing a stochastic process that incorporates demand changes. Being a special case of vehicle routing problem with pickup and delivery, it shares the difficulty and complexity of VRP in practically large size. So as to give efficient solutions in large size problems, we develop a Cluster-first Route-second heuristic where a set partitioning problem considers inventory imbalances and approximates routing distances. We benchmark our heuristic approach on a pure MLIP formulation. The experimental result confirms that the heuristic is good at decomposing a large problem and gives efficient solutions even in practically large instances.

본 연구는 교체형 배터리를 이용하는 전기 마이크로 모빌리티 공유 시스템에서의 배터리 교체 및 차량 재배치를 효율적으로 수행하는 방법을 제시하고자 한다. 수요를 성공적으로 충족시키기 위해선 모빌리티의 공급과 이용자의 수요를 맞춰주기 위한 차량 재고 차원에서의 재배치 작업과 배터리 수준을 유지시켜주는 배터리 관리 차원에서의 교체 작업이 필수적이다. 또한 충전소로 차량을 옮길 필요 없이 바로 교체할 수 있으므로 담당 직원이 산발적으로 위치한 각 모빌리티들을 순회하며 위 작업들을 진행해야 한다. 이동하며 작업하는 비용과 시간이 대부분이기 때문에 이동 순서를 함께 최적화하는 것이 비용 개선에 필수적이다. 따라서 작업 결정과 경로 결정을 동시에 고려하는 충전 및 재배치 모형을 제시한다. 이때 free-floating 모빌리티 공유시스템의 이용 수요를 효과적으로 반영하고자 수요를 stochastic process로 모델링하고 이를 이용하여 재배치 목표 수량을 구한다. 문제의 크기가 큰 경우 효율적으로 본 충전 및 재배치 모형의 좋은 해를 얻기 위한 방법으로, 해당 서비스지역의 각 구역들을 클러스터링하고 그 뒤에 스태프들의 경로와 작업을 결정하는 휴리스틱을 제안한다. 여러 스태프를 순회시키는 복잡한 형태를 클러스터링으로써 작은 크기의 문제들로 분해하여 빠르게 문제를 풀고자 한다. 이를 위해 각 클러스터에는 한 명의 스태프가 배정되고, 한 클러스터 내에서 소속된 구역들이 필요로 하는 작업들을 한 명의 스태프가 모두 진행하도록 구성한다. 최소걸침나무 근사법을 적용한 set partitioning 문제를 풀어 클러스터링을 진행한다. 계산실험 결과, 고안된 휴리스틱은 차량의 수가 많아 크기가 큰 상황에서도 빠른 시간내에 더 좋은 해를 냈다.