A Benders decomposition method for locating stations in a one-way electric car sharing system under demand uncertainty

Çalık, H.; Fortz, Bernard

doi:10.1016/j.trb.2019.05.004

Download

Article (Scientific journals)

A Benders decomposition method for locating stations in a one-way electric car sharing system under demand uncertainty

Çalık, H.; Fortz, Bernard

2019 • In Transportation Research. Part B, Methodological, 125, p. 121-150

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/318167

DOI
10.1016/j.trb.2019.05.004

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

CalikFortz2018R2.pdf

Author postprint (1.06 MB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

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

Publication date :

2019

Journal title :

Transportation Research. Part B, Methodological

ISSN :

0191-2615

eISSN :

1879-2367

Publisher :

Elsevier, United Kingdom

Volume :

125

Pages :

121-150

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85065464512&doi=10.1016%2fj.trb.2019.05.004&partnerID=40&md5=00dd857cb78d3cb5b1b501ee648b06b0

Available on ORBi :

since 15 May 2024

Statistics

Number of views

8 (2 by ULiège)

Number of downloads

4 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

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.
Benders, J.F., Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4:1 (1962), 238–252.
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.
Birge, J.R., Louveaux, F., Two-stage recourse problems. Introduction to Stochastic Programming, 2011, Springer, 181–263.
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.
Whong, C., 2018. NYC taxi trip data. https://chriswhong.com/.
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.