Electric vehicles are a prime candidate for use within an urban car sharing system, both from an economic and environmental perspective. However, their relatively short range necessitates frequent and rather time-consuming recharging throughout the day. Thus, charging stations must be built throughout the system’s operational area where cars can be charged between uses. In this work, we introduce and study an optimization problem that models the task of finding optimal locations and sizes for charging stations, using the number of expected trips that can be accepted (or their resulting profit) as a gauge of quality. Integer linear programming formulations and construction heuristics are introduced and the resulting algorithms are tested on grid-graph-based instances, as well as on real-world instances from Vienna. The results of our computational study show that the best-performing exact algorithm solves most of the benchmark instances to proven optimality and usually provides small optimality gaps for the remaining instances. Results also reveal that our heuristics can provide high quality solutions very quickly.
Citation
Technical Report, Department of Statistics and Operations Research, University of Vienna, 10/2018