Home > Research > Publications & Outputs > The Electric Vehicle Routing Problem with Time ...

Associated organisational unit

Electronic data

  • EVRPTW-SMBS-RR-KGZ

    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

    Embargo ends: 14/08/21

    Available under license: CC BY-NC-ND

Links

Text available via DOI:

View graph of relations

The Electric Vehicle Routing Problem with Time Windows and Synchronised Mobile Battery Swapping  

Research output: Contribution to journalJournal article

Published

Standard

The Electric Vehicle Routing Problem with Time Windows and Synchronised Mobile Battery Swapping  . / Raeesi, Ramin; Zografos, Konstantinos. G.

In: Transportation Research Part B: Methodological, Vol. 140, 01.10.2020, p. 101-129.

Research output: Contribution to journalJournal article

Harvard

APA

Vancouver

Author

Bibtex

@article{5b46d236e11d438184f0d97ad176a469,
title = "The Electric Vehicle Routing Problem with Time Windows and Synchronised Mobile Battery Swapping  ",
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{\textquoteright} 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.",
author = "Ramin Raeesi and Zografos, {Konstantinos. G.}",
note = "This is the author{\textquoteright}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",
year = "2020",
month = oct,
day = "1",
doi = "10.1016/j.trb.2020.06.012",
language = "English",
volume = "140",
pages = "101--129",
journal = "Transportation Research Part B: Methodological",
issn = "0191-2615",
publisher = "PERGAMON-ELSEVIER SCIENCE LTD",

}

RIS

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 -