A multi-stage stochastic integer programming approach for locating electric vehicle charging stations. (English) Zbl 1458.90405
Summary: Electric vehicles (EVs) represent one of the promising solutions to face environmental and energy concerns in transportation. Due to the limited range of EVs, deploying a charging infrastructure enabling EV drivers to carry out long distance trips is a key step to foster the widespread adoption of EVs. In this paper, we study the problem of locating EV fast charging stations so as to satisfy as much recharging demand as possible within the available investment budget. We focus on incorporating two important features into the optimization problem modeling: a multi-period decision making horizon and uncertainties on the recharging demand in terms of both the number of EVs to recharge and the set of long-distance trips to cover. Our objective is to determine the charging stations to be opened at each time period so as to maximize the expected value of the satisfied recharging demand over the entire planning horizon. To model the problem, we propose a multi-stage stochastic integer programming approach based on the use of a scenario tree to represent the uncertainties on the recharging demand. To solve the resulting large-size integer linear program, we develop two solution algorithms: an exact solution method based on a Benders decomposition and a heuristic approach based on a genetic algorithm. Our numerical results show that both methods perform well as compared to a stand-alone mathematical programming solver. Moreover, we provide the results of additional simulation experiments showing the practical benefit of the proposed multi-stage stochastic programming model as compared to a simpler multi-period deterministic model.
MSC:
| 90B80 | Discrete location and assignment |
| 90C15 | Stochastic programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
electric vehicles; facility location problem; multi-stage stochastic optimization; scenario tree; Benders decomposition; genetic algorithmReferences:
| [1] | Ahmed, S.; King, A. J.; Parija, G., A multi-stage stochastic integer programming approach for capacity expansion under uncertainty, J. Glob. Optim., 26, 3-24 (2003) · Zbl 1116.90382 |
| [2] | AIE, Transport Energy and CO_2 : Moving towards Sustainability (2009), Éditions OCDE: Éditions OCDE Paris |
| [3] | AIE, Global EV Outlook 2016 : Beyond one million electric cars (2016), Éditions OCDE: Éditions OCDE Paris/AIE, Paris |
| [4] | Arslan, O.; Karasan, O. O., A benders decomposition approach for the charging station location problem with plug-in hybrid electric vehicles, Transp. Res. Part B, 93, 670-695 (2016) |
| [5] | Capar, I.; Kuby, M.; Leon, V. V., An arc cover-path-cover formulation and strategic analysis of alternative-fuel station locations, Eur. J. Oper. Res., 227, 1, 142-151 (2013) |
| [6] | Caroe, C. C.; Schultz, R., Dual decomposition in stochastic integer programming, Oper. Res. Lett., 24, 37-45 (1999) · Zbl 1063.90037 |
| [7] | Carpentier, P.; Cohen, G.; Culioli, J. C., Stochastic optimal control and decomposition-coordination methods part i: theory, (Durier, R.; Michelot, C., Recent Developments in Optimization. Lecture Notes in Economics and Mathematical Systems, Vol. 429 (1995), Springer: Springer Berlin, Heidelberg) · Zbl 0851.93075 |
| [8] | Chan, M.; Wong, C.; Luo, W.; Cheung, B., Investment stock portfolio with multi-stage genetic algorithm optimization, (Abraham, A.; Dote, Y.; Furuhashi, T.; Köppen, M.; Ohuchi, A.; Ohsawa, Y., Soft Computing as Transdisciplinary Science and Technology. Advances in Soft Computing, Vol. 29 (2005), Springer: Springer Berlin, Heidelberg) |
| [9] | Chung, S. S.; Kwon, C., Multi-period planning for electric car charging station locations: a case of korean expressways, Eur. J. Oper. Res., 242, 2, 677-687 (2015) |
| [10] | De Vries, H.; Duijzer, E., Incorporating driving range variability in network design for refueling facilities, Omega, 69, 102-114 (2017) |
| [11] | Dupacová, J.; Gröwe-Kuska, N.; Römisch, W., Scenario reduction in stochastic programming, Math. Program., 95, 3, 493-511 (2003) · Zbl 1023.90043 |
| [12] | Egbue, O.; Long, S., Barriers to widespread adoption of electric vehicles: an analysis of consumer attitudes and perceptions, Energy Policy, 48, 717-729 (2012) |
| [13] | Escudero, L. L.; Garin, A.; Unzeuta, A., Cluster lagrangean decomposition in multistage stochastic optimization, Comput. Oper, Res., 67, 48-62 (2016) · Zbl 1349.90656 |
| [14] | Fattahi, M.; Govindan, K.; Keyvanshokooh, E., A multi-stage stochastic program for supply chain network redesign problem with price-dependent uncertain demands, Comput. Oper, Res., 100, 314-332 (2018) · Zbl 1458.90086 |
| [15] | Fotheringham, A. A.; O’Kelly, M. E., Spatial Interaction Models: Formulations and Applications (1989), Kluwer Academic Publishers |
| [16] | Gade, D.; Hackebeil, G.; Ryan, S. M.; Watson, J. P.; Wets, R. J.B.; Woodruff, D. L., Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs, Math. Program. Ser. B, 157, 47-67 (2016) · Zbl 1338.90282 |
| [17] | Ghamami, M.; Zockaie, A.; Nie, Y. M., A general corridor model for designing plug-in electric vehicle charging infrastructure to support intercity travel, Transp. Res. Part C, 68, 389-402 (2016) |
| [18] | Guan, Y.; Ahmed, S.; Nemhauser, G. L., Cutting planes for multistage stochastic integer programs, Oper. Res., 57, 2, 287-298 (2009) · Zbl 1181.90199 |
| [19] | Heitsch, H.; Römisch, W., Scenario tree modeling for multistage stochastic programs, Math. Program., 118, 371-406 (2009) · Zbl 1173.90007 |
| [20] | Hodgson, M. M., A flow capturing location allocation model, Geogr. Anal., 22, 3, 270-279 (1990) |
| [21] | Hosseini, M.; MirHassani, S., Refueling-station location problem under uncertainty, Transp. Res. Part E, 84, 101-116 (2015) |
| [22] | Hosseini, M.; MirHassani, S. S., A heuristic algorithm for optimal location of flow-efueling capacitated stations, Int. Trans. Oper. Res., 24, 1377-1403 (2017) · Zbl 1386.90086 |
| [23] | Hoyland, K.; Wallace, S. W., Generating scenario trees for multistage decision problems, Manag. Sci., 47, 2, 295-307 (2001) · Zbl 1232.91132 |
| [24] | Hu, S.; Han, C.; Dong, Z. Z.; Meng, L., A multi-stage stochastic programming model for relief distribution considering the state of road network, Transp. Res. Part B, 123, 64-87 (2019) |
| [25] | Kim, J. J.; Kuby, M., The deviation-flow refueling location model for optimizing a network of refueling stations, Int. J. Hydrogen Energy, 37, 6, 5406-5420 (2012) |
| [26] | Kim, J. J.; Kuby, M., A network transformation heuristic approach for the deviation flow refueling location model, Comput. Oper, Res., 40, 4, 1122-1131 (2013) |
| [27] | Kuby, M.; Lim, S., The flow-refueling location problem for alternative-fuel vehicles, Socio-Econ. Plan. Sci., 39, 2, 125-145 (2005) |
| [28] | Lee, C.; Han, J., Benders-and-price approach for electric vehicle charging station location problem under probabilistic travel range, Transp. Res. Part B, 106, 130-152 (2017) |
| [29] | Li, S.; Huang, Y.; Mason, S. S., A multi-period optimization model for the deployment of public electric vehicle charging stations on network, Transp. Res. Part C, 65, 128-143 (2016) |
| [30] | Lim, S.; Kuby, M., Heuristic algorithms for siting alternative-fuel stations using the flow-refueling location model, Eur. J. Oper. Res., 204, 1, 51-61 (2010) · Zbl 1178.90291 |
| [31] | 1996 · Zbl 0869.90056 |
| [32] | Magnanti, T. T.; Wong, R. R., Acceleration benders decomposition: algorithmic enhancement and model selection criteria, Oper. Res., 29, 3, 464-484 (1981) · Zbl 0455.90064 |
| [33] | Miralinaghi, M.; Lou, Y.; Keskin, B. B.; Zarrinmehr, A.; Shabanpour, R., Refueling station location problem with traffic deviation considering route choice and demand uncertainty, Int. J. Hydrogen Energy, 42, 5, 3335-3351 (2017) |
| [34] | MirHassani, S. S.; Ebrazi, R. R., Flexible reformulation of the refueling station location problem, Transp. Sci., 47, 4, 617-628 (2012) |
| [35] | Nickel, S.; Saldanha-da Gama, F.; Ziegler, H., A multi-stage stochastic supply network design problem with financial decisions and risk management, Omega, 40, 5, 511-524 (2012) |
| [36] | Nowak, M. M.; Römisch, W., Stochastic lagrangian relaxation applied to power scheduling in a hydro-thermal system under uncertainty, Ann. Oper. Res., 100, 1-4, 251-272 (2000) · Zbl 1017.90072 |
| [37] | Owen, S. S.; Daskin, M. M., Strategic facility location: A review, Eur. J. Oper. Res., 111, 3, 423-447 (1998) · Zbl 0938.90048 |
| [38] | Pflug, G., Scenario tree generation for multiperiod financial optimization by optimal discretization, Math. Program., Ser. B, 89, 251-271 (2001) · Zbl 0987.91034 |
| [39] | Pimentel, B. B.; Mateus, G. R.; Almeida, F. F., Stochastic capacity planning and dynamic network design, Int. J. Prod. Econ., 145, 139-149 (2013) |
| [40] | Smith, M., Castellano, J., 2015. Costs associated with non-residential electric vehicle supply equipment. Retrieved from the U.S. Department of Energy website: https://www.afdc.energy.gov/uploads/publication/evse_cost_report_2015.pdf. |
| [41] | http://www.ieee-holm.org/h2017/Morton |
| [42] | Taghavi, M.; Huang, K., A multi-stage stochastic programming approach for network capacity expansion with multiple sources of capacity, Nav. Res. Logist., 63, 8, 600-614 (2016) · Zbl 1411.90242 |
| [43] | https://www.greentechmedia.com/articles/read/fast-charging-key-to-electric-vehicle-adoption-study-finds. 2013. (accessed 17 November 2013). |
| [44] | Upchurch, C.; Kuby, M., A model for location of capacitated alternative-fuel stations, Geogr. Anal., 41, 1, 85-106 (2009) |
| [45] | Wang, Y. Y.; Lin, C. C., Locating multiple types of recharging stations for battery-powered electric vehicle transport, Transp. Res. Part E, 58, 76-87 (2013) |
| [46] | Wu, F.; Sioshansi, R., A stochastic flow-capturing model to optimize the location of fast-charging stations with uncertain electric vehicle flows, Transp. Res. Part D, 53, 354-376 (2017) |
| [47] | Xie, F.; Huang, Y., A multistage stochastic programming model for a multi-period strategic expansion of biofuel supply chain under evolving uncertainties, Transp. Res. Part E, 111, 130-148 (2018) |
| [48] | Yahyatabar, A.; Najafi, A. A., Condition based maintenance policy for series-parallel systems through proportional hazards model: a multi-stage stochastic programming approach, Comput. Ind. Eng., 126, 30-46 (2018) |
| [49] | Yang, X., Improving portfolio efficiency: a genetic algorithm approach, Computational Economics, 28, 1-14 (2006) · Zbl 1184.91196 |
| [50] | Yildiz, B.; Arslan, B.; Karaan, O. O., A branch and price approach for routing and refueling station location model, Eur. J. Oper. Res., 248, 3, 815-826 (2016) · Zbl 1346.90525 |
| [51] | Zeballos, L. J.; Mendez, C. A.; Barbosa-Povoa, A. P.; Novais, A. Q., Multi-period design and planning of closed-loop supply chains with uncertain supply and demand, Comput. Chem. Eng., 66, 151-164 (2014) |
| [52] | Zhang, A.; Kang, J.; Kwon, C., Incorporating demand dynamics in multi-period capacitated fast-charging location planning for electric vehicles, Transp. Res. Part B, 103, 5-29 (2017) |
| [53] | Zhang, H.; Ha, M.; Zhao, H.; Song, J., Inexact multistage stochastic chance constrained programming model for water resources management under uncertainties, Sci. Program., 2017 (2017) |
| [54] | Zhang, K. K.; Zhang, X. X., Using a genetic algorithm to solve a new multi-period stochastic optimization model, J. Comput. Appl. Math., 231, 114-123 (2009) · Zbl 1167.65378 |
| [55] | Zou, J.; Ahmed, S.; Sun, X. X., Stochastic dual dynamic integer programming, Math. Program., 175, 461-502 (2019) · Zbl 1412.90101 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
