Exact approaches for routing capacitated electric vehicles

Hesamoddin Tahami, Ghaith Rabadi and Mohamed Haouari

Transportation Research Part E: Logistics and Transportation Review, 2020, vol. 144, issue C

Abstract: We investigate a variant of the standard Capacitated Vehicle Routing Problem (CVRP), where each vehicle is powered exclusively by electricity stored in its rechargeable battery. Consequently, each vehicle should visit not only customer nodes but also (possibly) some charging stations before the battery got depleted. The importance of this problem stems from the fact that logistics companies are increasingly relying on electric vehicles in urban distribution. We propose three exact approaches. The first one requires solving a compact polynomial-sized formulation. The second approach is a branch-and-cut algorithm. An original feature of this algorithm is that it embeds the first exact separation of the well-known rounded capacity constraints. Finally, the third approach is a hybrid algorithm that requires solving an augmented variant of the compact formulation. We report the results of a computational study that was carried out on a set of 125 instances, providing evidence that the polynomial-sized formulation can consistently solve instances having up to 30 customer nodes and 21 charging stations, and that the hybrid algorithm solves some instances having up to 100 customer nodes and 21 charging stations while requiring moderate CPU times. Furthermore, the proposed approach was shown to exhibit limitations in solving some large-scale tightly-constrained instances.

Keywords: Electric vehicle routing; Compact formulation; Branch-and-cut; Rounded capacity constraints; Separation procedure (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554520307742
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:transe:v:144:y:2020:i:c:s1366554520307742

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2020.102126

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().