A Multilevel Optimization Approach for Large Scale Battery Exchange Station Location Planning

Abstract

We propose a multilevel optimization algorithm (MLO) for solving large scale instances of the Multi-Period Battery Swapping Station Location Problem (MBSSLP), i.e., a problem for deciding the placement of battery swapping stations in an urban area. MLO generates a solution to an MBSSLP instance in three steps. First the problem size is iteratively reduced by coarsening. Then, a solution to the coarsest problem instance is determined, and finally the obtained solution is projected to more fine grained problem instances in reverse order until a solution to the original problem instance is obtained. We test our approach on benchmark instances with up to 10000 areas for placing stations and 100000 user trips. We compare MLO to solving a mixed integer linear program (MILP) in a direct way as well as solving the instances with a construction heuristic (CH). Results show that MLO scales substantially better for such large instances than the MILP or the CH.