Rights statement: This is the author’s version of a work that was accepted for publication in Transportation Research Part B: Methodological. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Transportation Research Part B: Methodological, 140, 2020 DOI: 10.1016/j.trb.2020.06.012
Accepted author manuscript, 895 KB, PDF document
Available under license: CC BY-NC-ND
Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - The Electric Vehicle Routing Problem with Time Windows and Synchronised Mobile Battery Swapping
AU - Raeesi, Ramin
AU - Zografos, Konstantinos. G.
N1 - This is the author’s version of a work that was accepted for publication in Transportation Research Part B: Methodological. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Transportation Research Part B: Methodological, 140, 2020 DOI: 10.1016/j.trb.2020.06.012
PY - 2020/10/1
Y1 - 2020/10/1
N2 - 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.
AB - 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.
U2 - 10.1016/j.trb.2020.06.012
DO - 10.1016/j.trb.2020.06.012
M3 - Journal article
VL - 140
SP - 101
EP - 129
JO - Transportation Research Part B: Methodological
JF - Transportation Research Part B: Methodological
SN - 0191-2615
ER -