Abstract
This paper is about strategic decisions required for running an urban station-based electric car-sharing system. In such a system, users can rent and return publicly available electric cars from charging stations. We approach the problem of deciding on the location and size of these stations and on the total number of cars in such a system using a bi-level model. The first level of the model identifies the number of rental stations, the number of slots at each station, and the total number of cars to be acquired. Then, such a generated solution is evaluated by computing which trips can be accepted by the system using a path-based heuristic on a time-expanded location network. This path-based heuristic iteratively finds paths for the cars through this network. We compare three different pathfinder methods, which are all based on the concept of tree search using a greedy criterion. The algorithm is evaluated on a set of benchmark instances which are based on real-world data from Vienna, Austria using a demand model derived from taxi data of about 3500 taxis operating in Vienna. Computational tests show that for smaller instances the algorithm is able to find near optimal solutions and that it scales well for larger instances.
This work has been partially funded by the Austrian Federal Ministry for Transport, Innovation and Technology (bmvit) in the JPI Urban Europe programme under grant number 847350 (e4share).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
References
Asamer, J., Reinthaler, M., Ruthmair, M., Straub, M., Puchinger, J.: Optimizing charging station locations for urban taxi providers. Transp. Res. Part A: Policy Pract. 85, 233–246 (2016)
Boyacı, B., Zografos, K.G., Geroliminis, N.: An optimization framework for the development of efficient one-way car-sharing systems. Eur. J. Oper. Res. 240(3), 718–733 (2015)
Brandstätter, G., Gambella, C., Leitner, M., Malaguti, E., Masini, F., Puchinger, J., Ruthmair, M., Vigo, D.: Overview of optimization problems in electric car-sharing system design and management. In: Dawid, H., Doerner, K.F., Feichtinger, G., Kort, P.M., Seidl, A. (eds.) Dynamic Perspectives on Managerial Decision Making. DMEEF, vol. 22, pp. 441–471. Springer, Heidelberg (2016). doi:10.1007/978-3-319-39120-5_24
Brandstätter, G., Kahr, M., Leitner, M.: Determining optimal locations for charging stations of electric car-sharing under stochastic demand (2016, submitted)
Brandstätter, G., Leitner, M., Ljubić, I.: Location of charging stations in electric car sharing systems (2016, submitted)
Cavadas, J., de Almeida Correia, G.H., Gouveia, J.: A MIP model for locating slowcharging stations for electric vehicles in urban areas accounting for driver tours. Transp. Res. Part E: Logist. Transp. Rev. 75, 188–201 (2015)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Duin, C., Voß, S., et al.: The pilot method: a strategy for heuristic repetition with application to the steiner problem in graphs. Networks 34(3), 181–191 (1999)
Frade, I., Ribeiro, A., Gonçalves, G., Antunes, A.: Optimal location of charging stations for electric vehicles in a neighborhood in Lisbon, Portugal. Transp. Res. Rec.: J. Transp. Res. Board 2252, 91–98 (2011)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Ge, S., Feng, L., Liu, H.: The planning of electric vehicle charging station based on grid partition method. In: 2011 International Conference on Electrical and Control Engineering (ICECE), pp. 2726–2730. IEEE (2011)
Hess, A., Malandrino, F., Reinhardt, M.B., Casetti, C., Hummel, K.A., Barceló-Ordinas, J.M.: Optimal deployment of charging stations for electric vehicular networks. In: Proceedings of the First Workshop on Urban Networking, pp. 1–6. ACM (2012)
Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)
Ow, P.S., Morton, T.E.: Filtered beam search in scheduling. Int. J. Prod. Res. 26(1), 35–62 (1988)
Prandtstetter, M., Straub, M., Puchinger, J.: On the way to a multi-modal energy-efficient route. In: IECON 2013–39th Annual Conference of the IEEE Industrial Electronics Society, pp. 4779–4784. IEEE (2013)
Weikl, S., Bogenberger, K.: Relocation strategies and algorithms for free-floating car sharing systems. IEEE Intell. Transp. Syst. Mag. 5(4), 100–111 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Biesinger, B., Hu, B., Stubenschrott, M., Ritzinger, U., Prandtstetter, M. (2017). Optimizing Charging Station Locations for Electric Car-Sharing Systems. In: Hu, B., López-Ibáñez, M. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017. Lecture Notes in Computer Science(), vol 10197. Springer, Cham. https://doi.org/10.1007/978-3-319-55453-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-55453-2_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55452-5
Online ISBN: 978-3-319-55453-2
eBook Packages: Computer ScienceComputer Science (R0)