The electric vehicle touring problem

Chung-Shou Liao, Shang-Hung Lu and Zuo-Jun Max Shen

Transportation Research Part B: Methodological, 2016, vol. 86, issue C, 163-180

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.

Keywords: Approximation algorithm; Battery swap; Electric vehicle; Shortest path; Traveling salesman problem; Vehicle routing (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261516000278
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:86:y:2016:i:c:p:163-180

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2016.02.002

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().