IDEAS home Printed from https://ideas.repec.org/
MyIDEAS: Log in (now much improved!) to save this article

A Benders decomposition approach for the charging station location problem with plug-in hybrid electric vehicles

Listed author(s):
  • Arslan, Okan
  • Karaşan, Oya Ekin
Registered author(s):

    The flow refueling location problem (FRLP) locates p stations in order to maximize the flow volume that can be accommodated in a road network respecting the range limitations of the vehicles. This paper introduces the charging station location problem with plug-in hybrid electric vehicles (CSLP-PHEV) as a generalization of the FRLP. We consider not only the electric vehicles but also the plug-in hybrid electric vehicles when locating the stations. Furthermore, we accommodate multiple types of these vehicles with different ranges. Our objective is to maximize the vehicle-miles-traveled using electricity and thereby minimize the total cost of transportation under the existing cost structure between electricity and gasoline. This is also indirectly equivalent to maximizing the environmental benefits. We present an arc-cover formulation and a Benders decomposition algorithm as exact solution methodologies to solve the CSLP-PHEV. The decomposition algorithm is accelerated using Pareto-optimal cut generation schemes. The structure of the formulation allows us to construct the subproblem solutions, dual solutions and nondominated Pareto-optimal cuts as closed form expressions without having to solve any linear programs. This increases the efficiency of the decomposition algorithm by orders of magnitude and the results of the computational studies show that the proposed algorithm both accelerates the solution process and effectively handles instances of realistic size for both CSLP-PHEV and FRLP.

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261516300170
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.

    Article provided by Elsevier in its journal Transportation Research Part B: Methodological.

    Volume (Year): 93 (2016)
    Issue (Month): PA ()
    Pages: 670-695

    as
    in new window

    Handle: RePEc:eee:transb:v:93:y:2016:i:pa:p:670-695
    DOI: 10.1016/j.trb.2016.09.001
    Contact details of provider: Web page: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description

    Order Information: Postal: http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
    Web: https://shop.elsevier.com/order?id=548&ref=548_01_ooc_1&version=01

    References listed on IDEAS
    Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:

    as
    in new window


    1. Lei, Chao & Lin, Wei-Hua & Miao, Lixin, 2014. "A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 699-710.
    2. Wheatley, David & Gzara, Fatma & Jewkes, Elizabeth, 2015. "Logic-based Benders decomposition for an inventory-location problem with service constraints," Omega, Elsevier, vol. 55(C), pages 10-23.
    3. Capar, Ismail & Kuby, Michael & Leon, V. Jorge & Tsai, Yu-Jiun, 2013. "An arc cover–path-cover formulation and strategic analysis of alternative-fuel station locations," European Journal of Operational Research, Elsevier, vol. 227(1), pages 142-151.
    4. Melaina, Marc & Bremson, Joel, 2008. "Refueling availability for alternative fuel vehicle markets: Sufficient urban station coverage," Energy Policy, Elsevier, vol. 36(8), pages 3223-3231, August.
    5. Arslan, Okan & Yıldız, Barış & Karaşan, Oya Ekin, 2015. "Minimum cost path problem for Plug-in Hybrid Electric Vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 80(C), pages 123-141.
    6. Lim, Seow & Kuby, Michael, 2010. "Heuristic algorithms for siting alternative-fuel stations using the Flow-Refueling Location Model," European Journal of Operational Research, Elsevier, vol. 204(1), pages 51-61, July.
    7. Jean-François Cordeau & Goran Stojković & François Soumis & Jacques Desrosiers, 2001. "Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling," Transportation Science, INFORMS, vol. 35(4), pages 375-388, November.
    8. Trukhanov, Svyatoslav & Ntaimo, Lewis & Schaefer, Andrew, 2010. "Adaptive multicut aggregation for two-stage stochastic linear programs with recourse," European Journal of Operational Research, Elsevier, vol. 206(2), pages 395-406, October.
    9. He, Fang & Wu, Di & Yin, Yafeng & Guan, Yongpei, 2013. "Optimal deployment of public charging stations for plug-in hybrid electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 47(C), pages 87-101.
    10. Wang, Ying-Wei & Wang, Chuan-Ren, 2010. "Locating passenger vehicle refueling stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(5), pages 791-801, September.
    11. S. A. MirHassani & R. Ebrazi, 2013. "A Flexible Reformulation of the Refueling Station Location Problem," Transportation Science, INFORMS, vol. 47(4), pages 617-628, November.
    12. Fengqi You & Ignacio Grossmann, 2013. "Multicut Benders decomposition algorithm for process supply chain planning under uncertainty," Annals of Operations Research, Springer, vol. 210(1), pages 191-211, November.
    13. Hosseini, Meysam & MirHassani, S.A., 2015. "Refueling-station location problem under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 84(C), pages 101-116.
    14. Chung, Sung Hoon & Kwon, Changhyun, 2015. "Multi-period planning for electric car charging station locations: A case of Korean Expressways," European Journal of Operational Research, Elsevier, vol. 242(2), pages 677-687.
    15. Wang, Ying-Wei & Lin, Chuah-Chih, 2009. "Locating road-vehicle refueling stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(5), pages 821-829, September.
    16. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    17. Nie, Yu (Marco) & Ghamami, Mehrnaz, 2013. "A corridor-centric approach to planning electric vehicle charging infrastructure," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 172-190.
    18. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    19. Jean-François Cordeau & François Soumis & Jacques Desrosiers, 2000. "A Benders Decomposition Approach for the Locomotive and Car Assignment Problem," Transportation Science, INFORMS, vol. 34(2), pages 133-149, May.
    20. Axsen, Jonn & Kurani, Kenneth S, 2008. "The Early U.S. Market for PHEVs: Anticipating Consumer Awareness, Recharge Potential, Design Priorities and Energy Impacts," Institute of Transportation Studies, Working Paper Series qt4491w7kf, Institute of Transportation Studies, UC Davis.
    21. Yıldız, Barış & Arslan, Okan & Karaşan, Oya Ekin, 2016. "A branch and price approach for routing and refueling station location model," European Journal of Operational Research, Elsevier, vol. 248(3), pages 815-826.
    22. Romm, Joseph, 2006. "The car and fuel of the future," Energy Policy, Elsevier, vol. 34(17), pages 2609-2614, November.
    23. Fontaine, Pirmin & Minner, Stefan, 2014. "Benders Decomposition for Discrete–Continuous Linear Bilevel Problems with application to traffic network design," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 163-172.
    24. Erdoğan, Sevgi & Miller-Hooks, Elise, 2012. "A Green Vehicle Routing Problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 100-114.
    25. Wang, Ying-Wei & Lin, Chuah-Chih, 2013. "Locating multiple types of recharging stations for battery-powered electric vehicle transport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 76-87.
    26. Arslan, Okan & Yıldız, Barış & Ekin Karaşan, Oya, 2014. "Impacts of battery characteristics, driver preferences and road network features on travel costs of a plug-in hybrid electric vehicle (PHEV) for long-distance trips," Energy Policy, Elsevier, vol. 74(C), pages 168-178.
    27. Halit Üster & Panitan Kewcharoenwong, 2011. "Strategic Design and Analysis of a Relay Network in Truckload Transportation," Transportation Science, INFORMS, vol. 45(4), pages 505-523, November.
    28. Peiling Wu & Joseph C. Hartman & George R. Wilson, 2005. "An Integrated Model and Solution Approach for Fleet Sizing with Heterogeneous Assets," Transportation Science, INFORMS, vol. 39(1), pages 87-103, February.
    29. Melaina, Marc W & Bremson, Joel, 2008. "Refueling Availability for Alternative Fuel Vehicle Markets: Sufficient Urban Station Coverage," Institute of Transportation Studies, Working Paper Series qt8ng1g4rf, Institute of Transportation Studies, UC Davis.
    30. Kuby, Michael & Lim, Seow, 2005. "The flow-refueling location problem for alternative-fuel vehicles," Socio-Economic Planning Sciences, Elsevier, vol. 39(2), pages 125-145, June.
    31. Bapna, Ravi & Thakur, Lakshman S. & Nair, Suresh K., 2002. "Infrastructure development for conversion to environmentally friendly fuel," European Journal of Operational Research, Elsevier, vol. 142(3), pages 480-496, November.
    32. de Sá, Elisangela Martins & de Camargo, Ricardo Saraiva & de Miranda, Gilberto, 2013. "An improved Benders decomposition algorithm for the tree of hubs location problem," European Journal of Operational Research, Elsevier, vol. 226(2), pages 185-202.
    33. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    34. Khatami, Maryam & Mahootchi, Masoud & Farahani, Reza Zanjirani, 2015. "Benders’ decomposition for concurrent redesign of forward and closed-loop supply chain network with demand and return uncertainties," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 79(C), pages 1-21.
    35. Birge, John R. & Louveaux, Francois V., 1988. "A multicut algorithm for two-stage stochastic linear programs," European Journal of Operational Research, Elsevier, vol. 34(3), pages 384-392, March.
    36. Li, Shengyin & Huang, Yongxi, 2014. "Heuristic approaches for the flow-based set covering problem with deviation paths," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 144-158.
    37. Ricardo Saraiva de Camargo & Gilberto de Miranda & Henrique Pacca L. Luna, 2009. "Benders Decomposition for Hub Location Problems with Economies of Scale," Transportation Science, INFORMS, vol. 43(1), pages 86-97, February.
    38. Michael Kuby & Seow Lim, 2007. "Location of Alternative-Fuel Stations Using the Flow-Refueling Location Model and Dispersion of Candidate Sites on Arcs," Networks and Spatial Economics, Springer, vol. 7(2), pages 129-152, June.
    Full references (including those not matched with items on IDEAS)

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:93:y:2016:i:pa:p:670-695. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu)

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.