The electric vehicle routing problem with shared charging stations

• DOI: http://doi.org/10.1111/itor.12620
• Published date: 01 July 2019
• Author: Jorge E. Mendoza,Gilbert Laporte,Ola Jabali,Çağrı Koç
• Date: 01 July 2019

Intl. Trans. in Op. Res. 26 (2019) 1211–1243

DOI: 10.1111/itor.12620

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

The electric vehicle routing problem with shared

charging stations

C¸a˘

grı Koc¸a, Ola Jabalib, Jorge E. Mendozacand Gilbert Laported

aDepartment of Business Administration, Social Sciences University of Ankara,

H¨

uk¨

umet Meydanı, 06050 Ulus, Ankara, Turkey

bDipartimento di Elettronica, Informazione e Bioingegneria Politecnico di Milano,

Piazza Leonardo da Vinci, 32, 20133 Milano, Italy

cHEC Montr´

eal, 3000 chemin de la Cˆ

ote-Sainte-Catherine, Montr´

eal H3T 2A7, Canada

dCIRRELT, Canada Research Chair in Distribution Management and HEC Montr´

eal, 3000 chemin de la

Cˆ

ote-Sainte-Catherine, Montr´

eal H3T 2A7, Canada

E-mail: cagri.koc@asbu.edu.tr [Koc¸]; ola.jabali@polimi.it [Jabali]; jorge.mendoza@hec.ca [Mendoza];

gilbert.laporte@cirrelt.ca [Laporte]

Received 7 August2017; received in revised form 13 November 2018; accepted 15 November 2018

Abstract

We introduce the electric vehicle routing problem with shared charging stations (E-VRP-SCS). The E-VRP-

SCS extends the electric vehicle routingproblem 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 problemconsists of deciding the location and technology of

the CSs and building the routes foreach company. It is solved by means of a multistartheuristic that performs

an adaptive large neighborhood search coupled with the solution of mixed integer linear programs. It also

contains a number of advancedefficient 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:ehicle routing; electric vehicles; multidepot; ALNS; nonlinear charging function

1. Introduction

In recent years, we have witnessed a growing interest in the integration of environmental aspects

within the vehicle routing problem (VRP) and its variants (Demir et al., 2014; Eglese and Bektas¸,

2014; Lin et al., 2014). The electric VRP (E-VRP), introduced as a consequence of this research

effort, considers the technical limitations of electric vehicles (EVs), such as their limited payload

and driving range. In particular, E-VRP solutions frequentlyinclude routes with planned detours to

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1212 C¸.Koc¸ et al. / Intl. Trans. in Op.Res. 26 (2019) 1211–1243

out-of-the-depot charging stations (CSs). This is especially true in mid-haul applications arising in

rural and semiurban areas because in these cases the distance covered by the routes on a single day

is often higher than the driving range. While en route recharge is performed mainly for feasibility

reasons, it also offers economical benefits. For instance, in a recent study carried for the French

electricity giant ENEDIS, Villegas et al. (2018) showedthat by allowing en route charging, in certain

settings, the company could save up to 14% on operational routing costs.

En route charging can be performed in public or private CSs. The latter are usually located in

facilities owned by the company operating the routes (e.g., administrative buildings and secondary

depots). With a few exceptions such as Sweda et al. (2017) and Kullman et al. (2017), most papers

in the E-VRP literature assume private CSs (Montoya et al., 2017). In practice, installing en route

charging infrastructure requires significant investments. For example,according to the U.S. Depart-

ment of Energy, the cost of acquiring a fast charger in the United States may vary between USD

14K and USD 91K depending on the charger model (Smith and Castellano, 2015). For companies

operating small EV fleets, the economical benefits of en route charging may be quickly offset by the

long payback times of these large investments. In these cases, one possible strategy to leverage the

investment is to explore mutualization opportunities. In this paper, we model the situation where

the investment in out-of-depot charging infrastructure is jointly made by a number of companies,

which ultimately share it on a daily basis.

Our aim is to develop a heuristic to efficiently solve the electric vehicle routing problem with

shared CSs (E-VRP-SCS), which combines location and routingdecisions. The location component

includes decisions on where to open CS and which type of technology to install in them, while the

routing component builds the routes for each company using the CSs established by the first

component.

1.1. A brief literature review

Erdo˘

gan and Miller-Hooks (2012) introduced the green VRP (GVRP) in which alternative fuel

vehicles are considered. The problem aims to minimize the total traveled distance where fuel is

consumed at a given rate per traveled distance and the tank of the vehicle can be refueled at

alternative fuel stations. The authors proposed two construction heuristics whose performance was

tested on instances with up to 500 customers. Koc¸ and Karaoglan (2016) developed a branch-and-

cut algorithm for the GVRP, which combines several valid inequalities and includes a simulated

annealing based heuristic algorithm. The method can optimally solve instances with up to 20

customers. Montoya et al. (2016) developed a multispace sampling two-phase heuristic for the

GVRP. The first phase applies randomized route-first cluster-second heuristics, and the second

phase is based on the solution of a set partitioning formulation (SPF). Bartolini and Andelmin

(2017) modeled the GVRP as a set partitioning problem and developed an exact algorithm for

it. The authors strengthened their formulation by adding a number of valid inequalities. They

optimally solved instances with up to 110 customers. Andelmin and Bartolini (2016) developed a

multistart local search heuristic for the GVRP and solved instances with up to 470 customers.

Felipe et al. (2014) extended the GVRP to EVs by allowing partial recharges using multiple

technologies. In their problem, EVs have capacity and route duration limits. The authors developed

construction and local search algorithms, as well as a simulated annealing metaheuristic. Schneider

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

C¸.Koc¸ et al. / Intl. Trans. in Op.Res. 26 (2019) 1211–1243 1213

et al. (2014) introduced the E-VRP with time windows (E-VRPTW) and recharging stations and

proposed a hybrid metaheuristic that integrates variable neighborhood search and tabu search.

The performance of the method was tested on the GVRP instances of Erdo˘

gan and Miller-Hooks

(2012), on the multidepot VRP with interdepot routes instances of Crevier et al. (2007) and of

Tarantilis et al. (2008), and on newly generated instances for the E-VRPTW. Goeke and Schneider

(2015) solved heterogeneousfleet VRP in the context of the E-VRPTW, whereboth EVs and internal

combustion engine vehicles are considered. The objective was to minimize the energy consumption

that depends on speed, gradient, and cargo load distribution. The authors applied an adaptive

large neighborhood search (ALNS) algorithm for this problem. Desaulniers et al. (2016) developed

branch-price-and-cut algorithms for the E-VRPTW and also extended the problem by considering

four rechargingstrategies: a single recharge per route when the batteries are fullyrecharged, multiple

recharges per route and full recharges, at most a single recharge per route and partial recharges

per route, and multiple and partial recharges. Hiermann et al. (2016) introduced the fleet size and

mix VRP with time windows where EVs are considered. The authors developed a branch-and-

price algorithm and a hybrid metaheuristic that combines ALNS and labeling procedures. Keskin

and C¸ atay (2016) studied the E-VRPTW with partial recharge strategies and developed an ALNS

algorithm with several new mechanisms adapted to the problem. Same authors later developed a

matheuristic algorithm to solve the E-VRPTW with fast chargers (Keskin and C¸ atay, 2018).

Depot location and vehicle routingare two interdependent decisions. Their joint studyhas evolved

into what is now commonly known as the location-routing problem (LRP) (for recent reviews, see

Prodhon and Prins, 2014; Albareda-Sambola, 2015; Drexl and Schneider, 2015). Yang and Sun

(2015) studied the EV battery swap stations (BSSs) LRP which aims to determine the locations

of BSSs, as well as a routing plan. The authors proposed a hybrid algorithm including a modified

sweep heuristic, iterated greedy search, tabu search, and several improvement procedures. Hof et al.

(2017) later studied the same problem and developed an adaptive variable neighborhood search

algorithm which obtained several new best known solutions (BKSs). More recently, Schiffer and

Walther (2017a) studied the electric LRP with time windows and partial recharging. The problem

considers one type of technology at the CS,and vehicles can charge at any of the nodes.The problem

considers three separate objectives: minimizationof distance, number of vehicles, or number of CSs.

The authors proposed a mathematical formulation for the problem and presented exact results on

small-sized instances with up to 15 customers. In the context of city logistics, Schiffer and Walther

(2017b) introduced the LRP with intraroute facilities wherethe location of the depots is known and

the location of facilities for intermediate stops has to be determined. These facilities are not depots

and do not necessarily coincide with customer locations. They can be visited on a route and enable

the vehicle to stay operational by replenishing, loading, or unloading certain resources like energy,

fuel, freight, or waste. The authors proposed an ALNS heuristic including dynamic programming

components. They first solved the problem of Schiffer and Walther (2017a), and then applied their

method to real-world instances obtained from a German retail company. Schiffer et al. (2018a)

studied the LRP with intraroute facilities with combined facilities offering different replenishment

services. The authors developed an ALNS that uses a lower bounding procedure. Schiffer and

Walther (2018) introduced a robust LRP for strategic network design of electric logistics fleets. It

considers simultaneous decisions on locating CSs and vehicle routes, and the uncertain customer

patterns with respect to the spatial customer distribution, demand, and service time windows. CS

prices heavily influence the viability of electric commercial vehicles in mid-haul logistics (Schiffer

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies