The electric vehicle routing problem with shared charging stations

Çağrı Koç; Ola Jabali; Jorge E. Mendoza; Gilbert Laporte

doi:10.1111/itor.12620

The electric vehicle routing problem with shared charging stations

Çağrı Koç, Ola Jabali, Jorge E. Mendoza, Gilbert Laporte

Research output: Contribution to journal › Article › peer-review

90 Citations (SciVal)

Abstract

We introduce the electric vehicle routing problem with shared charging stations (E-VRP-SCS). The E-VRP-SCS extends the electric vehicle routing problem with nonlinear charging function (E-VRP-NL) by considering several companies that jointly invest in charging stations (CSs). The objective is to minimize the sum of the fixed opening cost of CSs and the drivers cost. The problem consists of deciding the location and technology of the CSs and building the routes for each company. It is solved by means of a multistart heuristic that performs an adaptive large neighborhood search coupled with the solution of mixed integer linear programs. It also contains a number of advanced efficient procedures tailored to handle specific components of the E-VRP-SCS. We perform extensive computational experiments on benchmark instances. We assess the competitiveness of the heuristic on the E-VRP-NL and derive 38 new best known solutions. New benchmark results on the E-VRP-SCS are presented, solved, and analyzed.

Original language	English
Pages (from-to)	1211-1243
Number of pages	33
Journal	International Transactions in Operational Research
Volume	26
Issue number	4
DOIs	https://doi.org/10.1111/itor.12620
Publication status	Published - Jul 2019

Funding

The authors thank the three anonymous referees for their insightful comments and suggestions that helped improve the content and the presentation of the paper. They also gratefully acknowledge the funding provided by the Canadian Natural Sciences and Engineering Research Council under grants 2015-06189 and 436014-2013, and by the French National Research Agency (Agence Nationale de la Recherce) through project e-VRO under grant ANR-15-CE22-0005-01. The authors are indebted to Aur?lien Froger for his technical support.

Keywords

ALNS
ehicle routing
electric vehicles
multidepot
nonlinear charging function

ASJC Scopus subject areas

Business and International Management
Computer Science Applications
Strategy and Management
Management Science and Operations Research
Management of Technology and Innovation

Access to Document

10.1111/itor.12620

Cite this

@article{e8ad8a67b4994da49fdf3b27b2959e9c,

title = "The electric vehicle routing problem with shared charging stations",

abstract = "We introduce the electric vehicle routing problem with shared charging stations (E-VRP-SCS). The E-VRP-SCS extends the electric vehicle routing problem with nonlinear charging function (E-VRP-NL) by considering several companies that jointly invest in charging stations (CSs). The objective is to minimize the sum of the fixed opening cost of CSs and the drivers cost. The problem consists of deciding the location and technology of the CSs and building the routes for each company. It is solved by means of a multistart heuristic that performs an adaptive large neighborhood search coupled with the solution of mixed integer linear programs. It also contains a number of advanced efficient procedures tailored to handle specific components of the E-VRP-SCS. We perform extensive computational experiments on benchmark instances. We assess the competitiveness of the heuristic on the E-VRP-NL and derive 38 new best known solutions. New benchmark results on the E-VRP-SCS are presented, solved, and analyzed.",

keywords = "ALNS, ehicle routing, electric vehicles, multidepot, nonlinear charging function",

author = "{\c C}ağrı Ko{\c c} and Ola Jabali and Mendoza, {Jorge E.} and Gilbert Laporte",

year = "2019",

month = jul,

doi = "10.1111/itor.12620",

language = "English",

volume = "26",

pages = "1211--1243",

journal = "International Transactions in Operational Research",

issn = "0969-6016",

publisher = "John Wiley and Sons Inc",

number = "4",

}

TY - JOUR

T1 - The electric vehicle routing problem with shared charging stations

AU - Koç, Çağrı

AU - Jabali, Ola

AU - Mendoza, Jorge E.

AU - Laporte, Gilbert

PY - 2019/7

Y1 - 2019/7

N2 - We introduce the electric vehicle routing problem with shared charging stations (E-VRP-SCS). The E-VRP-SCS extends the electric vehicle routing problem with nonlinear charging function (E-VRP-NL) by considering several companies that jointly invest in charging stations (CSs). The objective is to minimize the sum of the fixed opening cost of CSs and the drivers cost. The problem consists of deciding the location and technology of the CSs and building the routes for each company. It is solved by means of a multistart heuristic that performs an adaptive large neighborhood search coupled with the solution of mixed integer linear programs. It also contains a number of advanced efficient procedures tailored to handle specific components of the E-VRP-SCS. We perform extensive computational experiments on benchmark instances. We assess the competitiveness of the heuristic on the E-VRP-NL and derive 38 new best known solutions. New benchmark results on the E-VRP-SCS are presented, solved, and analyzed.

AB - We introduce the electric vehicle routing problem with shared charging stations (E-VRP-SCS). The E-VRP-SCS extends the electric vehicle routing problem with nonlinear charging function (E-VRP-NL) by considering several companies that jointly invest in charging stations (CSs). The objective is to minimize the sum of the fixed opening cost of CSs and the drivers cost. The problem consists of deciding the location and technology of the CSs and building the routes for each company. It is solved by means of a multistart heuristic that performs an adaptive large neighborhood search coupled with the solution of mixed integer linear programs. It also contains a number of advanced efficient procedures tailored to handle specific components of the E-VRP-SCS. We perform extensive computational experiments on benchmark instances. We assess the competitiveness of the heuristic on the E-VRP-NL and derive 38 new best known solutions. New benchmark results on the E-VRP-SCS are presented, solved, and analyzed.

KW - ALNS

KW - ehicle routing

KW - electric vehicles

KW - multidepot

KW - nonlinear charging function

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

U2 - 10.1111/itor.12620

DO - 10.1111/itor.12620

M3 - Article

AN - SCOPUS:85058145289

SN - 0969-6016

VL - 26

SP - 1211

EP - 1243

JO - International Transactions in Operational Research

JF - International Transactions in Operational Research

IS - 4

ER -

The electric vehicle routing problem with shared charging stations

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this