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

The electric vehicle touring problem

Author

Listed:
  • Liao, Chung-Shou
  • Lu, Shang-Hung
  • Shen, Zuo-Jun Max

Abstract

The increasing concern over global warming has led to the rapid development of the electric vehicle industry. Electric vehicles (EVs) have the potential to reduce the greenhouse effect and facilitate more efficient use of energy resources. In this paper, we study several EV route planning problems that take into consideration possible battery charging or swapping operations. Given a road network, the objective is to determine the shortest (travel time) route that a vehicle with a given battery capacity can take to travel between a pair of vertices or to visit a set of vertices with several stops, if necessary, at battery switch stations. We present polynomial time algorithms for the EV shortest travel time path problem and the fixed tour EV touring problem, where the fixed tour problem requires visiting a set of vertices in a given order. Based on the result, we also propose constant factor approximation algorithms for the EV touring problem, which is a generalization of the traveling salesman problem.

Suggested Citation

  • Liao, Chung-Shou & Lu, Shang-Hung & Shen, Zuo-Jun Max, 2016. "The electric vehicle touring problem," Transportation Research Part B: Methodological, Elsevier, vol. 86(C), pages 163-180.
  • Handle: RePEc:eee:transb:v:86:y:2016:i:c:p:163-180
    DOI: 10.1016/j.trb.2016.02.002
    as

    Download full text from publisher

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

    File URL: https://libkey.io/10.1016/j.trb.2016.02.002?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.

    Citations

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


    Cited by:

    1. Li, Jiapei & Xie, Chi, 2024. "Identifying and minimizing critical driving range thresholds for electric vehicles in intercity networks," Socio-Economic Planning Sciences, Elsevier, vol. 93(C).
    2. Leandro do C. Martins & Rafael D. Tordecilla & Juliana Castaneda & Angel A. Juan & Javier Faulin, 2021. "Electric Vehicle Routing, Arc Routing, and Team Orienteering Problems in Sustainable Transportation," Energies, MDPI, vol. 14(16), pages 1-30, August.
    3. Jie, Wanchen & Yang, Jun & Zhang, Min & Huang, Yongxi, 2019. "The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology," European Journal of Operational Research, Elsevier, vol. 272(3), pages 879-904.
    4. Strehler, Martin & Merting, Sören & Schwan, Christian, 2017. "Energy-efficient shortest routes for electric and hybrid vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 111-135.
    5. Hof, Julian & Schneider, Michael & Goeke, Dominik, 2017. "Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 102-112.
    6. 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.
    7. Zhang, Anpeng & Kang, Jee Eun & Kwon, Changhyun, 2017. "Incorporating demand dynamics in multi-period capacitated fast-charging location planning for electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 5-29.
    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. Luo, Yugong & Feng, Guixuan & Wan, Shuang & Zhang, Shuwei & Li, Victor & Kong, Weiwei, 2020. "Charging scheduling strategy for different electric vehicles with optimization for convenience of drivers, performance of transport system and distribution network," Energy, Elsevier, vol. 194(C).
    10. Dimitrios Rizopoulos & Domokos Esztergár-Kiss, 2020. "A Method for the Optimization of Daily Activity Chains Including Electric Vehicles," Energies, MDPI, vol. 13(4), pages 1-21, February.
    11. 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).
    12. Cen, Xuekai & Lo, Hong K. & Li, Lu & Lee, Enoch, 2018. "Modeling electric vehicles adoption for urban commute trips," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 431-454.
    13. 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.
    14. Sina Rastani & Bülent Çatay, 2023. "A large neighborhood search-based matheuristic for the load-dependent electric vehicle routing problem with time windows," Annals of Operations Research, Springer, vol. 324(1), pages 761-793, May.
    15. Moritz Baum & Julian Dibbelt & Andreas Gemsa & Dorothea Wagner & Tobias Zündorf, 2019. "Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles," Transportation Science, INFORMS, vol. 53(6), pages 1627-1655, November.
    16. 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.
    17. Amin Aghalari & Darweesh Ehssan Salamah & Carlos Marino & Mohammad Marufuzzaman, 2023. "Electric vehicles fast charger location-routing problem under ambient temperature," Annals of Operations Research, Springer, vol. 324(1), pages 721-759, May.
    18. 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.
    19. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    20. 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.

    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:86:y:2016:i:c:p:163-180. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.