The Shortest Path Problems in Battery-Electric Vehicle Dispatching with Battery Renewal

Minfang Huang and Jing-Quan Li
Additional contact information
Minfang Huang: School of Economics and Management, North China Electric Power University, Beijing 102206, China
Jing-Quan Li: California PATH, University of California, Berkeley, Richmond, CA 94804, USA

Sustainability, 2016, vol. 8, issue 7, 1-17

Abstract: Electric vehicles play a key role for developing an eco-sustainable transport system. One critical component of an electric vehicle is its battery, which can be quickly charged or exchanged before it runs out. The problem of electric vehicle dispatching falls into the category of the shortest path problem with resource renewal. In this paper, we study the shortest path problems in (1) electric transit bus scheduling and (2) electric truck routing with time windows. In these applications, a fully-charged battery allows running a limited operational distance, and the battery before depletion needs to be quickly charged or exchanged with a fully-charged one at a battery management facility. The limited distance and battery renewal result in a shortest path problem with resource renewal. We develop a label-correcting algorithm with state space relaxation to find optimal solutions. In the computational experiments, real-world road geometry data are used to generate realistic travel distances, and other types of data are obtained from the real world or randomly generated. The computational results show that the label-correcting algorithm performs very well.

Keywords: electric vehicles; battery swapping or charging; resource-constrained shortest path; label-correcting algorithm (search for similar items in EconPapers)
JEL-codes: O13 Q Q0 Q2 Q3 Q5 Q56 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://www.mdpi.com/2071-1050/8/7/607/pdf (application/pdf)
https://www.mdpi.com/2071-1050/8/7/607/ (text/html)

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:gam:jsusta:v:8:y:2016:i:7:p:607-:d:72912

Access Statistics for this article

Sustainability is currently edited by Ms. Alexandra Wu

More articles in Sustainability from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().