The electric vehicle routing problem with time windows and synchronised mobile battery swapping

Ramin Raeesi and Konstantinos G. Zografos

Transportation Research Part B: Methodological, 2020, vol. 140, issue C, 101-129

Abstract: This paper introduces an alternative to intra-route recharging of Electric Commercial Vehicles (ECVs) used for freight distribution by exploiting new pertinent technological developments that make mobile battery swapping possible. The Electric Vehicle Routing Problem with Time Windows and Synchronised Mobile Battery Swapping (EVRPTW-SMBS) is introduced in which route planning is carried out in two interdependent levels: (i) for the ECVs to deliver customers’ demands, and (ii) for the Battery Swapping Vans (BSVs) to swap the depleted battery on an ECV with a fully charged one at a designated time and space. Each BSV route can provide the battery swapping service to multiple ECVs, and each ECV can extend its autonomy by requesting the battery swapping service for as many times as required with no need to divert from its original delivery route. The EVRPTW-SMBS opens up multiple opportunities to facilitate eco-friendly goods distribution using ECVs and brings in extra flexibility and cost savings. At the same time, it is a challenging problem to tackle mainly due to the interdependence problem that stems from the spatio-temporal synchronisation requirement between the vehicles in the two levels (i.e. ECVs and BSVs). To tackle these complications, the paper proposes a methodology for exact evaluation of an EVRPTW-SMBS solution based on a two-stage hybridisation of a dynamic programming and an integer programming algorithm, and places the resulting procedure at the heart of an intensified large neighbourhood search algorithm to solve instances of the EVRPTW-SMBS efficiently. A library of EVRPTW-SMBS test instances is developed and used to demonstrate the added value of the proposed problem variant and the efficiency of the proposed algorithms. Our results demonstrate the benefits of using BSVs in the design of the delivery routes for ECVs, and indicate that a particular variant of the proposed algorithms which is based on a specific lexicographical decomposition routine can efficiently approximate the optimal solution to the EVRPTW-SMBS.

Keywords: Electric vehicle; Routing and scheduling; Recharging; Battery swapping; Spatio-temporal synchronisation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261520303593
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:140:y:2020:i:c:p:101-129

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.2020.06.012

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 ().