Location; Urban mobility; Electric car sharing; Benders decomposition; Mixed integer stochastic programming; Stochastic demand
Abstract :
[en] We focus on a problem of locating recharging stations in one-way station based electric car sharing systems which operate under demand uncertainty. We model this problem as a mixed integer stochastic program and develop a Benders decomposition algorithm based on this formulation. We integrate a stabilization procedure to our algorithm and conduct a large-scale experimental study on our methods. To conduct the computational experiments, we develop a demand forecasting method allowing to generate many demand scenarios. The method is applied to real data from Manhattan taxi trips. We are able to solve problems with 100–500 scenarios, each scenario including 1000–5000 individual customer requests, under high and low cost values and 5–15 min of accessibility restrictions, which is measured as the maximum walking time to the operating stations.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Çalık, H.
Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt
Language :
English
Title :
A Benders decomposition method for locating stations in a one-way electric car sharing system under demand uncertainty
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Arslan, O., Karaşan, O.E., A Benders decomposition approach for the charging station location problem with plug-in hybrid electric vehicles. Transp. Res. Part B 93 (2016), 670–695.
Asamer, J., Reinthaler, M., Ruthmair, M., Straub, M., Puchinger, J., Optimizing charging station locations for urban taxi providers. Transp. Res. Part A 85 (2016), 233–246.
Fouad Baouche, Romain Billot, Rochdi Trigui, and Nour-Eddin El Faouzi. Efficient allocation of electric vehicles charging stations: Optimization model and application to a dense urban network. IEEE Intelligent Transportation Systems Magazine, 6 (3): 33–43, 2014. ISSN 1939-1390. doi: 10.1109/mits.2014.2324023.
Matthew Barth, Michael Todd, and Lei Xue. User-based vehicle relocation techniques for multiple-station shared-use vehicle systems. In Transportation Research Board, 80th Annual Meeting, 2004. URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.360.8614.
Ben-Ameur, W., Neto, J., Acceleration of cutting-plane and column generation algorithms: applications to network design. Networks 49:1 (2007), 3–17.
Biesinger, B., Hu, B., Stubenschrott, M., Ritzinger, U., Prandtstetter, M., Optimizing charging station locations for electric car-sharing systems. Evol. Comput. Comb. Optim., 2017, 157–172.
Botton, Q., Fortz, B., Gouveia, L., Poss, M., Benders decomposition for the hop-constrained survivable network design problem. INFORMS J. Comput. 25:1 (2013), 13–26.
Burak Boyacı, Konstantinos G. Zografos, and Nikolas Geroliminis. An optimization framework for the development of efficient one-way car-sharing systems. European Journal of Operational Research, 240 (3): 718–733, February 2015. ISSN 0377-2217. doi: 10.1016/j.ejor.2014.07.020.
Boyacı, B., Zografos, K.G., Geroliminis, N., An integrated optimization-simulation framework for vehicle and personnel relocations of electric carsharing systems with reservations. Transp. Res. Part B 95 (2017), 214–237.
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. Dynamic Perspectives on Managerial Decision Making, 2016, Springer, 441–471.
Brandstätter, G., Kahr, M., Leitner, M., Determining optimal locations for charging stations of electric car-sharing systems under stochastic demand. Transp. Res. Part B 104 (2017), 17–35.
Brandstätter, G., Leitner, M., Ljubić, I., Location of Charging Stations in Electric Car Sharing Systems. Technical Report. 2016, Department of Statistics and Operations Research, University of Vienna, Vienna, Austria.
Maurizio Bruglieri, Alberto Colorni, and Alessandro Luè. The vehicle relocation problem for the one-way electric vehicle sharing: An application to the milan case. Procedia - Social and Behavioral Sciences, 111: 18–27, February 2014. ISSN 1877-0428. doi: 10.1016/j.sbspro.2014.01.034.
Calik, H., Leitner, M., Luipersbeck, M., A Benders decomposition based framework for solving cable trench problems. Comput. Oper. Res. 81 (2017), 128–140.
Carlier, A., Munier-Kordon, A., Klaudel, W., Mathematical model for the study of relocation strategies in one-way carsharing systems. Transp. Res. Procedia 10 (2015), 374–383.
Joana Cavadas, Gonçalo H.A. Correia, and Joao Gouveia. A MIP model for locating slow-charging stations for electric vehicles in urban areas accounting for driver tours. Transportation Research Part E: Logistics and Transportation Review, 75: 188–201, March 2015. ISSN 1366-5545. doi: 10.1016/j.tre.2014.11.005.
Hatice Çalık and Bernard Fortz. Demand forecasting models for one-way car sharing systems. Technical Report: Université Libre de Bruxelles, Brussels, Belgium, 2017. https://dipot.ulb.ac.be/dspace/bitstream/2013/277634/3/Demand_Forecasting.pdf
Çalık, H., Fortz, B., Location of stations in a one-way electric car sharing system. Computers and Communications (ISCC), 2017 IEEE Symposium on, pages 134–139, 2017, IEEE.
Hatice Çalık and Bernard Fortz. A Benders decomposition method for locating stations in a one-way electric car sharing system under demand uncertainty. Technical Report: Université Libre de Bruxelles, Brussels, Belgium, 2018. https://dipot.ulb.ac.be/dspace/bitstream/2013/277804/3/6486.pdf
T Donna Chen, Kara M Kockelman, Moby Khan, et al. The electric vehicle charging station location problem: a parking-based assignment method for seattle. In 92nd Annual Meeting of the Transportation Research Board. Washington DC, USA, 2013. URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.300.2883.
Clemente, M., Fanti, M.P., Mangini, A.M., Ukovich, W., The vehicle relocation problem in car sharing systems: modeling and simulation in a petri net framework. Lect. Notes Comput. Sci. 7927 (2013), 250–269.
Codato, G., Fischetti, M., Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54:4 (2006), 756–766.
Gonçalo H.A. Correia and António Pais Antunes. Optimization approach to depot location and trip selection in one-way carsharing systems. Transportation Research Part E: Logistics and Transportation Review, 48 (1): 233–247, January 2012. ISSN 1366-5545. doi: 10.1016/j.tre.2011.06.003.
Gonçalo H.A. Correia, Diana Ramos Jorge, and David Marques Antunes. The added value of accounting for users’ flexibility and information on the potential of a station-based one-way car-sharing system: An application in Lisbon, Portugal. Journal of Intelligent Transportation Systems, 18 (3): 299–308, June 2014. ISSN 1547-2442. doi: 10.1080/15472450.2013.836928.
Sevgi Erdoǧan and Elise Miller-Hooks. A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 48 (1): 100–114, January 2012. ISSN 1366-5545. doi: 10.1016/j.tre.2011.08.001.
Ahmed El Fassi, Anjali Awasthi, and Marco Viviani. Evaluation of carsharing network's growth strategies through discrete event simulation. Expert Systems with Applications, 39 (8): 6692–6705, June 2012. ISSN 0957-4174. doi: 10.1016/j.eswa.2011.11.071.
Ángel Felipe, M. Teresa Ortuño, Giovanni Righini, and Gregorio Tirado. A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transportation Research Part E: Logistics and Transportation Review, 71 (0): 111–128, 2014. ISSN 1366-5545. doi: 10.1016/j.tre.2014.09.003.
Fischetti, M., Ljubić, I., Sinnl, M., Redesigning Benders decomposition for large-scale facility location. Manage. Sci., 2016.
Fortz, B., Poss, M., An improved Benders decomposition applied to a multi-layer network design problem. Oper. Res. Lett. 37:5 (2009), 359–364.
Inês Frade, Anabela Ribeiro, Gonçalo Gonçalves, and António Pais Antunes. Optimal location of charging stations for electric vehicles in a neighborhood in lisbon, Portugal. Transportation Research Record: Journal of the Transportation Research Board, 2252: 91–98, December 2011. ISSN 0361-1981. doi: 10.3141/2252-12.
Gambella, C., Malaguti, E., Masini, F., Vigo, D., Optimizing relocation operations in electric car-sharing. Omega 81 (2018), 234–245.
Shaoyun Ge, Liang Feng, and Hong Liu. The planning of electric vehicle charging station based on grid partition method. In 2011 International Conference on Electrical and Control Engineering (ICECE). IEEE, September 2011. ISBN http://id.crossref.org/isbn/978-1-4244-8162-0. doi: 10.1109/iceceng.2011.6057636.
He, J., Yang, H., Tang, T.-Q., Huang, H.-J., An optimal charging station location model with the consideration of electric vehicle's driving range. Transp. Res. Part C 86 (2018), 641–654.
Herrmann, S., Schulte, F., Voß, S., Increasing Acceptance of Free-floating Car Sharing Systems Using Smart Relocation Strategies: A Survey Based Study of Car2Go Hamburg. Computational Logistics, 2014, Springer, 151–162.
Andrea Hess, Francesco Malandrino, Moritz Bastian Reinhardt, Claudio Casetti, Karin Anna Hummel, and Jose M. Barceló-Ordinas. Optimal deployment of charging stations for electric vehicular networks. In Proceedings of the First Workshop on Urban Networking, UrbaNe ’12, pages 1–6, New York, NY, USA, 2012. ACM. ISBN 978-1-4503-1781-8. doi: 10.1145/2413236.2413238.
Hooker, J.N., Ottosson, G., Logic-based Benders decomposition. Math Program 96:1 (2003), 33–60.
Diana Jorge, Goncalo H.A. Correia, and Cynthia Barnhart. Comparing optimal relocation operations with simulated relocation policies in one-way carsharing systems. IEEE Transactions on Intelligent Transportation Systems, 15 (4): 1667–1675, August 2014. ISSN 1558-0016. doi: 10.1109/tits.2014.2304358.
Kaspi, M., Raviv, T., Tzu, M., Parking reservation policies in one-way vehicle sharing systems. Transp. Res. Part B 62 (2014), 35–50.
Alvina G.H. Kek, Ruey Long Cheu, Qiang Meng, and Chau Ha Fung. A decision support system for vehicle relocation operations in carsharing systems. Transportation Research Part E: Logistics and Transportation Review, 45 (1): 149–158, January 2009. ISSN 1366-5545. doi: 10.1016/j.tre.2008.02.008.
Li, X., Ma, J., Cui, J., Ghiasi, A., Zhou, F., Design framework of large-scale one-way electric vehicle sharing systems: a continuum approximation model. Transp. Res. Part B 88 (2016), 21–45.
Magnanti, T.L., Wong, R.T., 1981. Accelerating benders decomposition: algorithmic enhancement and model selection criteria. Oper. Res. 29:3 (1981), 464–484.
Miranda, E.A., Ljubić, I., Luipersbeck, M., Sinnl, M., Solving minimum-cost shared arborescence problems. Eur. J. Oper. Res. 258:3 (2017), 887–901.
Pelletier, S., Jabali, O., Laporte, G., 50th anniversary invited article—goods distribution with electric vehicles: review and research perspectives. Transp. Sci. 50:1 (2016), 3–22, 10.1287/trsc.2015.0646.
Ruthmair, M., Stubenschrott, M., Input Data Processing. Technical Report, 2015, AIT Austrian Institute of Technology, Vienna, Austria.
Michael Schneider, Andreas Stenger, and Dominik Goeke. The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48 (4): 500–520, November 2014. ISSN 1526-5447. doi: 10.1287/trsc.2013.0490.
Schulte, F., Voß, S., Decision support for environmental-friendly vehicle relocations in free-floating car sharing systems: The case of car2go. Procedia CIRP 30 (2015), 275–280.
Hengsong Wang, Qi Huang, Changhua Zhang, and Aihua Xia. A novel approach for the layout of electric vehicle charging station. In The 2010 International Conference on Apperceiving Computing and Intelligence Analysis Proceeding. IEEE, December 2010. ISBN http://id.crossref.org/isbn/978-1-4244-8025-8. doi: 10.1109/icacia.2010.5709852.
Ying-Wei Wang and Chuah-Chih Lin. Locating multiple types of recharging stations for battery-powered electric vehicle transport. Transportation Research Part E: Logistics and Transportation Review, 58: 76–87, November 2013. ISSN 1366-5545. doi: 10.1016/j.tre.2013.07.003.
Xu, M., Meng, Q., Liu, Z., Electric vehicle fleet size and trip pricing for one-way carsharing services considering vehicle relocation and personnel assignment. Transp. Res. Part B 111 (2018), 60–82.
Zhang, D., Liu, Y., He, S., Vehicle assignment and relays for one-way electric car-sharing systems. Transp. Res. Part B 120 (2018), 125–146.
Zhao, M., Li, X., Yin, J., Cui, J., Yang, L., An, S., An integrated framework for electric vehicle rebalancing and staff relocation in one-way carsharing systems: model formulation and lagrangian relaxation-based solution approach. Transp. Res. Part B 117 (2018), 542–572.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
