Thomas Jatschka, Tobias Rodemann, Guenther Raidl, "A Multilevel Optimization Approach for Large Scale Battery Exchange Station Location Planning", EvoCOP 2023, 2023.

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 in a coarsening phase. Afterwards, a solution to the coarsest problem is obtained and the obtained solution is projected to coarsened problems in reverse order until a solution to the original problem is obtained. We test our approach on benchmark instances with up to roughly 10000 areas for placing stations and approximately 100000 user trips. We compare our approach to a solving a mixed integer linear program (MILP) as well as solving the instances with a construction heuristic (CH). The results show that MLO scales substantially better for such large instances than the MILP or the CH.