Skip to main content
Kent Academic Repository

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

Raeesi, Ramin, Zorafos, Konstantinos G. (2020) The electric vehicle routing problem with time windows and synchronised mobile battery swapping. Transportation Research Part B: Methodological, 140 . pp. 101-129. ISSN 0191-2615. (doi:10.1016/j.trb.2020.06.012) (KAR id:82536)

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.

Item Type: Article
DOI/Identification number: 10.1016/j.trb.2020.06.012
Uncontrolled keywords: Electric vehicle; Routing and scheduling; Recharging; Battery swapping; Spatio-temporal synchronisation;
Divisions: Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Depositing User: Ramin Raeesi
Date Deposited: 21 Aug 2020 07:12 UTC
Last Modified: 04 Oct 2023 16:28 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/82536 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.