Charging station optimization for balanced electric car sharing

This work focuses on finding optimal locations for charging stations for one-way electric car sharing programs. The relocation of vehicles by a service staff is generally required in vehicle sharing programs in order to correct imbalances in the network. We seek to limit the need for vehicle relocation by strategically locating charging stations given estimates of traffic flow. A mixed-integer linear programming formulation is presented with a large number of potential charging station locations. A column generation approach is used which finds an optimal set of locations for the continuous relaxation of our problem. Results of a numerical experiment using real traffic and geographic information system location data show that our formulation significantly increases the balanced flow across the network, while our column generation technique was found to produce a superior solution in much shorter computation time compared to solving the original formulation with all possible station locations.