IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v128y2019icp23-49.html
   My bibliography  Save this article

Fleet sizing for one-way electric carsharing services considering dynamic vehicle relocation and nonlinear charging profile

Author

Listed:
  • Xu, Min
  • Meng, Qiang

Abstract

This study aims to determine the electric vehicle fleet size for one-way carsharing services by maximizing the profit of carsharing operators while taking into account the vehicle relocation operations and nonlinear electric vehicle charging profile. We formulate a set partitioning model for the considered problem. A tailored branch-and-price (B&P) approach is proposed to find the exact optimal solution of the model. In particular, an effective multi-label correcting method is developed to solve the pricing problem (i.e., generate columns) within the B&P approach. A novel non-dominated charging strategy is put up to avoid the exponential growth of labels caused by the allowance of partial charging with a nonlinear charging profile. In addition to the B&P approach, two heuristic methods are put forward for solving the large-scale problems or reinforcing the B&P approach. Numerical experiments with randomly generated instances and a case study based on a one-way carsharing operator in Singapore are conducted to further assess the efficiency and applicability of the proposed solution methods. The effects of several key parameters, i.e., the fixed cost of EV, relocation cost, electricity cost, service charge, EV driving range, the charging efficiency, and the number of rentals on the performance of a one-way electric carsharing system are also examined.

Suggested Citation

  • Xu, Min & Meng, Qiang, 2019. "Fleet sizing for one-way electric carsharing services considering dynamic vehicle relocation and nonlinear charging profile," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 23-49.
    • Handle: RePEc:eee:transb:v:128:y:2019:i:c:p:23-49
    DOI: 10.1016/j.trb.2019.07.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261518309822
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2019.07.016?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wang, Hua & Zhao, De & Meng, Qiang & Ong, Ghim Ping & Lee, Der-Horng, 2019. "A four-step method for electric-vehicle charging facility deployment in a dense city: An empirical study in Singapore," Transportation Research Part A: Policy and Practice, Elsevier, vol. 119(C), pages 224-237.
    2. Nourinejad, Mehdi & Zhu, Sirui & Bahrami, Sina & Roorda, Matthew J., 2015. "Vehicle relocation and staff rebalancing in one-way carsharing systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 81(C), pages 98-113.
    3. Li, Xiaopeng & Ma, Jiaqi & Cui, Jianxun & Ghiasi, Amir & Zhou, Fang, 2016. "Design framework of large-scale one-way electric vehicle sharing systems: A continuum approximation model," Transportation Research Part B: Methodological, Elsevier, vol. 88(C), pages 21-45.
    4. 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.
    5. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    6. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    7. Xu, Min & Meng, Qiang & Liu, Zhiyuan, 2018. "Electric vehicle fleet size and trip pricing for one-way carsharing services considering vehicle relocation and personnel assignment," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 60-82.
    8. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    9. Juho Andelmin & Enrico Bartolini, 2017. "An Exact Algorithm for the Green Vehicle Routing Problem," Transportation Science, INFORMS, vol. 51(4), pages 1288-1303, November.
    10. Boysen, Nils & Briskorn, Dirk & Emde, Simon, 2018. "Scheduling electric vehicles and locating charging stations on a path," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 109725, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    11. Timothy M. Sweda & Irina S. Dolinskaya & Diego Klabjan, 2017. "Adaptive Routing and Recharging Policies for Electric Vehicles," Transportation Science, INFORMS, vol. 51(4), pages 1326-1348, November.
    12. Hatem Ben Amor & Jacques Desrosiers & José Manuel Valério de Carvalho, 2006. "Dual-Optimal Inequalities for Stabilized Column Generation," Operations Research, INFORMS, vol. 54(3), pages 454-463, June.
    13. Georg Brandstätter & Claudio Gambella & Markus Leitner & Enrico Malaguti & Filippo Masini & Jakob Puchinger & Mario Ruthmair & Daniele Vigo, 2016. "Overview of Optimization Problems in Electric Car-Sharing System Design and Management," Dynamic Modeling and Econometrics in Economics and Finance, in: Herbert Dawid & Karl F. Doerner & Gustav Feichtinger & Peter M. Kort & Andrea Seidl (ed.), Dynamic Perspectives on Managerial Decision Making, pages 441-471, Springer.
    14. Martin Desrochers & François Soumis, 1989. "A Column Generation Approach to the Urban Transit Crew Scheduling Problem," Transportation Science, INFORMS, vol. 23(1), pages 1-13, February.
    15. 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.
    16. Xu, Min & Meng, Qiang & Liu, Kai, 2017. "Network user equilibrium problems for the mixed battery electric vehicles and gasoline vehicles subject to battery swapping stations and road grade constraints," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 138-166.
    17. 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).
    18. Brandstätter, Georg & Kahr, Michael & Leitner, Markus, 2017. "Determining optimal locations for charging stations of electric car-sharing systems under stochastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 17-35.
    19. Zhao, Meng & Li, Xiaopeng & Yin, Jiateng & Cui, Jianxun & Yang, Lixing & An, Shi, 2018. "An integrated framework for electric vehicle rebalancing and staff relocation in one-way carsharing systems: Model formulation and Lagrangian relaxation-based solution approach," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 542-572.
    20. Jorge, Diana & Molnar, Goran & de Almeida Correia, Gonçalo Homem, 2015. "Trip pricing of one-way station-based carsharing networks with zone and time of day price variations," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 461-482.
    21. Long He & Ho-Yin Mak & Ying Rong & Zuo-Jun Max Shen, 2017. "Service Region Design for Urban Electric Vehicle Sharing Systems," Manufacturing & Service Operations Management, INFORMS, vol. 19(2), pages 309-327, May.
    22. Boyacı, Burak & Zografos, Konstantinos G. & Geroliminis, Nikolas, 2017. "An integrated optimization-simulation framework for vehicle and personnel relocations of electric carsharing systems with reservations," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 214-237.
    23. Nils Boysen & Dirk Briskorn & Simon Emde, 2018. "Scheduling electric vehicles and locating charging stations on a path," Journal of Scheduling, Springer, vol. 21(1), pages 111-126, February.
    24. Nourinejad, Mehdi & Roorda, Matthew J., 2014. "A dynamic carsharing decision support system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 66(C), pages 36-50.
    25. Boyacı, Burak & Zografos, Konstantinos G. & Geroliminis, Nikolas, 2015. "An optimization framework for the development of efficient one-way car-sharing systems," European Journal of Operational Research, Elsevier, vol. 240(3), pages 718-733.
    26. Samuel Pelletier & Ola Jabali & Gilbert Laporte, 2016. "50th Anniversary Invited Article—Goods Distribution with Electric Vehicles: Review and Research Perspectives," Transportation Science, INFORMS, vol. 50(1), pages 3-22, February.
    27. Xu, Min & Meng, Qiang & Liu, Kai & Yamamoto, Toshiyuki, 2017. "Joint charging mode and location choice model for battery electric vehicle users," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 68-86.
    28. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    29. Zhang, Dong & Liu, Yang & He, Shuangchi, 2019. "Vehicle assignment and relays for one-way electric car-sharing systems," Transportation Research Part B: Methodological, Elsevier, vol. 120(C), pages 125-146.
    30. Pelletier, Samuel & Jabali, Ola & Laporte, Gilbert & Veneroni, Marco, 2017. "Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 158-187.
    31. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    32. Montoya, Alejandro & Guéret, Christelle & Mendoza, Jorge E. & Villegas, Juan G., 2017. "The electric vehicle routing problem with nonlinear charging function," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 87-110.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wang, Dong & Liao, Feixiong, 2021. "Analysis of first-come-first-served mechanisms in one-way car-sharing services," Transportation Research Part B: Methodological, Elsevier, vol. 147(C), pages 22-41.
    2. Chang, Ximing & Wu, Jianjun & Correia, Gonçalo Homem de Almeida & Sun, Huijun & Feng, Ziyan, 2022. "A cooperative strategy for optimizing vehicle relocations and staff movements in cities where several carsharing companies operate simultaneously," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 161(C).
    3. Cai, Yutong & Ong, Ghim Ping & Meng, Qiang, 2022. "Dynamic bicycle relocation problem with broken bicycles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    4. Qingyu Luo & Zhihao Ye & Hongfei Jia, 2023. "A Charging Planning Method for Shared Electric Vehicles with the Collaboration of Mobile and Fixed Facilities," Sustainability, MDPI, vol. 15(22), pages 1-16, November.
    5. Wang, Dong & Liao, Feixiong & Gao, Ziyou & Tian, Qiong, 2022. "Analysis of activity duration-related charging behavioral responses of electric vehicle travelers to charging services," Transport Policy, Elsevier, vol. 123(C), pages 73-81.
    6. Golalikhani, Masoud & Oliveira, Beatriz Brito & Carravilla, Maria Antónia & Oliveira, José Fernando & Antunes, António Pais, 2021. "Carsharing: A review of academic literature and business practices toward an integrated decision-support framework," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    7. Li, Lu & Lo, Hong K. & Huang, Wei & Xiao, Feng, 2021. "Mixed bus fleet location-routing-scheduling under range uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 155-179.
    8. Zipeng Zhang & Ning Zhang, 2021. "Re-Recognition of Ride-Sourcing Service: From the Perspective of Operational Efficiency and Social Welfare," Sustainability, MDPI, vol. 13(15), pages 1-14, July.
    9. Yixi Xue & Yi Zhang & Yi Chen, 2019. "An Evaluation Framework for the Planning of Electric Car-Sharing Systems: A Combination Model of AHP-CBA-VD," Sustainability, MDPI, vol. 11(20), pages 1-22, October.
    10. Zhang, Si & Sun, Huijun & Wang, Xu & Lv, Ying & Wu, Jianjun, 2022. "Optimization of personalized price discounting scheme for one-way station-based carsharing systems," European Journal of Operational Research, Elsevier, vol. 303(1), pages 220-238.
    11. Ma, Jie & Xu, Min & Meng, Qiang & Cheng, Lin, 2020. "Ridesharing user equilibrium problem under OD-based surge pricing strategy," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 1-24.
    12. Li, Qing & Liao, Feixiong, 2020. "Incorporating vehicle self-relocations and traveler activity chains in a bi-level model of optimal deployment of shared autonomous vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 151-175.
    13. Zheng, Hankun & Sun, Huijun & Kang, Liujiang & Dai, Peiling & Wu, Jianjun, 2023. "Multi-route coordination for bus systems in response to road disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 179(C).
    14. Qin, Hu & Su, E. & Wang, Yilun & Li, Jiliu, 2022. "Branch-and-price-and-cut for the electric vehicle relocation problem in one-way carsharing systems," Omega, Elsevier, vol. 109(C).
    15. Zhang, Le & Wang, Shuaian & Qu, Xiaobo, 2021. "Optimal electric bus fleet scheduling considering battery degradation and non-linear charging profile," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    16. Feifeng Zheng & Zhaojie Wang & Ming Liu, 2022. "Overnight charging scheduling of battery electric buses with uncertain charging time," Operational Research, Springer, vol. 22(5), pages 4865-4903, November.
    17. Xu, Min & Meng, Qiang, 2020. "Optimal deployment of charging stations considering path deviation and nonlinear elastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 135(C), pages 120-142.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Shen, Zuo-Jun Max & Feng, Bo & Mao, Chao & Ran, Lun, 2019. "Optimization models for electric vehicle service operations: A literature review," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 462-477.
    2. Çalık, Hatice & Fortz, Bernard, 2019. "A Benders decomposition method for locating stations in a one-way electric car sharing system under demand uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 125(C), pages 121-150.
    3. Huang, Kai & An, Kun & Rich, Jeppe & Ma, Wanjing, 2020. "Vehicle relocation in one-way station-based electric carsharing systems: A comparative study of operator-based and user-based methods," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    4. Liu, Yang & Xie, Jiaohong & Chen, Nan, 2022. "Stochastic one-way carsharing systems with dynamic relocation incentives through preference learning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    5. Masmoudi, Mohamed Amine & Hosny, Manar & Demir, Emrah & Genikomsakis, Konstantinos N. & Cheikhrouhou, Naoufel, 2018. "The dial-a-ride problem with electric vehicles and battery swapping stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 392-420.
    6. Qin, Hu & Su, E. & Wang, Yilun & Li, Jiliu, 2022. "Branch-and-price-and-cut for the electric vehicle relocation problem in one-way carsharing systems," Omega, Elsevier, vol. 109(C).
    7. Bektaş, Tolga & Ehmke, Jan Fabian & Psaraftis, Harilaos N. & Puchinger, Jakob, 2019. "The role of operational research in green freight transportation," European Journal of Operational Research, Elsevier, vol. 274(3), pages 807-823.
    8. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem, 2021. "Green vehicle routing problem: A state-of-the-art review," Post-Print hal-03182944, HAL.
    9. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2021. "Green vehicle routing problem: A state-of-the-art review," International Journal of Production Economics, Elsevier, vol. 231(C).
    10. Erfan Ghorbani & Mahdi Alinaghian & Gevork. B. Gharehpetian & Sajad Mohammadi & Guido Perboli, 2020. "A Survey on Environmentally Friendly Vehicle Routing Problem and a Proposal of Its Classification," Sustainability, MDPI, vol. 12(21), pages 1-71, October.
    11. Zhao, Meng & Li, Xiaopeng & Yin, Jiateng & Cui, Jianxun & Yang, Lixing & An, Shi, 2018. "An integrated framework for electric vehicle rebalancing and staff relocation in one-way carsharing systems: Model formulation and Lagrangian relaxation-based solution approach," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 542-572.
    12. Xu, Min & Meng, Qiang & Liu, Zhiyuan, 2018. "Electric vehicle fleet size and trip pricing for one-way carsharing services considering vehicle relocation and personnel assignment," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 60-82.
    13. Raeesi, Ramin & Zografos, Konstantinos G., 2022. "Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping," European Journal of Operational Research, Elsevier, vol. 301(1), pages 82-109.
    14. Cui, Shaohua & Ma, Xiaolei & Zhang, Mingheng & Yu, Bin & Yao, Baozhen, 2022. "The parallel mobile charging service for free-floating shared electric vehicle clusters," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 160(C).
    15. Alexandre M. Florio & Nabil Absi & Dominique Feillet, 2021. "Routing Electric Vehicles on Congested Street Networks," Transportation Science, INFORMS, vol. 55(1), pages 238-256, 1-2.
    16. Alvo, Matías & Angulo, Gustavo & Klapp, Mathias A., 2021. "An exact solution approach for an electric bus dispatch problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    17. Schiffer, Maximilian & Walther, Grit, 2018. "Strategic planning of electric logistics fleet networks: A robust location-routing approach," Omega, Elsevier, vol. 80(C), pages 31-42.
    18. Goeke, Dominik, 2019. "Granular tabu search for the pickup and delivery problem with time windows and electric vehicles," European Journal of Operational Research, Elsevier, vol. 278(3), pages 821-836.
    19. Li, Lu & Lo, Hong K. & Huang, Wei & Xiao, Feng, 2021. "Mixed bus fleet location-routing-scheduling under range uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 155-179.
    20. Schiffer, Maximilian & Schneider, Michael & Laporte, Gilbert, 2018. "Designing sustainable mid-haul logistics networks with intra-route multi-resource facilities," European Journal of Operational Research, Elsevier, vol. 265(2), pages 517-532.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:128:y:2019:i:c:p:23-49. See general information about how to correct material in RePEc.

    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 CitEc recognized a bibliographic reference but did not link an item in RePEc 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.