A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function

Xiaorong Zuo, Yiyong Xiao, Meng You, Ikou Kaku, Yuchun Xu

Research output: Contribution to journalArticle

Abstract

The electric vehicle routing problem with time window (EVRPTW) is an extension of the traditional vehicle routing problem with time window (VRPTW), where new features of electric vehicles are considered, such as limited battery capacities, lack of infrastructures, and long charging time. In this study, new technical formulations were presented for vehicle route selection and charging station visit, which reduces the formulation complexity without using duplicated dummy nodes or arcs. Besides, a new linearization method was developed that employs a set of secant lines to surrogate the concave nonlinear charging function with linear constraints. This method defines the charging time as a continuous variable and uses fewer variables than existing formulation in literature. A mixed-integer linear programming (MILP) model was developed for the EVRPTW and computational experiments on Solomon's VRPTW instances were conducted to verify the proposed model. The experimental results were compared with those obtained by traditional routing models, which showed that the proposed model can result in better EVs logistics schedules with higher charging time utilizations.
Original languageEnglish
Article number117687
JournalJournal of Cleaner Production
Volume236
Early online date17 Jul 2019
DOIs
Publication statusPublished - 1 Nov 2019

Fingerprint

electric vehicle
Vehicle routing
Electric vehicles
routing
Linearization
Linear programming
Logistics
linear programing
Time windows
Vehicle routing problem
Electric vehicle
logistics
infrastructure
Experiments

Bibliographical note

© 2019, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/

Keywords

  • Continuous optimization
  • Electric vehicle routing problem
  • Mixed-integer linear programming
  • Nonlinear charging function

Cite this

@article{8728c0f40c9244e687677b0a0e2806d8,
title = "A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function",
abstract = "The electric vehicle routing problem with time window (EVRPTW) is an extension of the traditional vehicle routing problem with time window (VRPTW), where new features of electric vehicles are considered, such as limited battery capacities, lack of infrastructures, and long charging time. In this study, new technical formulations were presented for vehicle route selection and charging station visit, which reduces the formulation complexity without using duplicated dummy nodes or arcs. Besides, a new linearization method was developed that employs a set of secant lines to surrogate the concave nonlinear charging function with linear constraints. This method defines the charging time as a continuous variable and uses fewer variables than existing formulation in literature. A mixed-integer linear programming (MILP) model was developed for the EVRPTW and computational experiments on Solomon's VRPTW instances were conducted to verify the proposed model. The experimental results were compared with those obtained by traditional routing models, which showed that the proposed model can result in better EVs logistics schedules with higher charging time utilizations.",
keywords = "Continuous optimization, Electric vehicle routing problem, Mixed-integer linear programming, Nonlinear charging function",
author = "Xiaorong Zuo and Yiyong Xiao and Meng You and Ikou Kaku and Yuchun Xu",
note = "{\circledC} 2019, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/",
year = "2019",
month = "11",
day = "1",
doi = "10.1016/j.jclepro.2019.117687",
language = "English",
volume = "236",
journal = "Journal of Cleaner Production",
issn = "0959-6526",
publisher = "Elsevier",

}

A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function. / Zuo, Xiaorong; Xiao, Yiyong; You, Meng; Kaku, Ikou; Xu, Yuchun.

In: Journal of Cleaner Production, Vol. 236, 117687, 01.11.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function

AU - Zuo, Xiaorong

AU - Xiao, Yiyong

AU - You, Meng

AU - Kaku, Ikou

AU - Xu, Yuchun

N1 - © 2019, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/

PY - 2019/11/1

Y1 - 2019/11/1

N2 - The electric vehicle routing problem with time window (EVRPTW) is an extension of the traditional vehicle routing problem with time window (VRPTW), where new features of electric vehicles are considered, such as limited battery capacities, lack of infrastructures, and long charging time. In this study, new technical formulations were presented for vehicle route selection and charging station visit, which reduces the formulation complexity without using duplicated dummy nodes or arcs. Besides, a new linearization method was developed that employs a set of secant lines to surrogate the concave nonlinear charging function with linear constraints. This method defines the charging time as a continuous variable and uses fewer variables than existing formulation in literature. A mixed-integer linear programming (MILP) model was developed for the EVRPTW and computational experiments on Solomon's VRPTW instances were conducted to verify the proposed model. The experimental results were compared with those obtained by traditional routing models, which showed that the proposed model can result in better EVs logistics schedules with higher charging time utilizations.

AB - The electric vehicle routing problem with time window (EVRPTW) is an extension of the traditional vehicle routing problem with time window (VRPTW), where new features of electric vehicles are considered, such as limited battery capacities, lack of infrastructures, and long charging time. In this study, new technical formulations were presented for vehicle route selection and charging station visit, which reduces the formulation complexity without using duplicated dummy nodes or arcs. Besides, a new linearization method was developed that employs a set of secant lines to surrogate the concave nonlinear charging function with linear constraints. This method defines the charging time as a continuous variable and uses fewer variables than existing formulation in literature. A mixed-integer linear programming (MILP) model was developed for the EVRPTW and computational experiments on Solomon's VRPTW instances were conducted to verify the proposed model. The experimental results were compared with those obtained by traditional routing models, which showed that the proposed model can result in better EVs logistics schedules with higher charging time utilizations.

KW - Continuous optimization

KW - Electric vehicle routing problem

KW - Mixed-integer linear programming

KW - Nonlinear charging function

UR - https://linkinghub.elsevier.com/retrieve/pii/S0959652619325375

UR - http://www.scopus.com/inward/record.url?scp=85069555788&partnerID=8YFLogxK

U2 - 10.1016/j.jclepro.2019.117687

DO - 10.1016/j.jclepro.2019.117687

M3 - Article

VL - 236

JO - Journal of Cleaner Production

JF - Journal of Cleaner Production

SN - 0959-6526

M1 - 117687

ER -