Electric Vehicle Routing Problem with States of Charging Stations

Abstract

This paper proposes an electric vehicle routing problem, considers the states of charging stations and suggests solution strategies. The charging of electric vehicles is a main issue in the field of electric vehicle routing. There are many studies that find the locations of charging stations, recharging functions for the batteries of vehicles, and so on. However, the state of charging stations significantly affects the routes of electric vehicles, which is not much explored. The states may include open or closed charging stations, occupied or empty charging slots, and so on. This paper investigates how the states of charging stations are estimated and how routing strategies are determined. We formulate a mixed integer programming model and suggest how to solve the problem with an exact method. Numerical examples provide the optimal routing strategies of electric vehicles for the changing environments regarding the states of charging stations.

1. Introduction

The fast growth of air pollution and global climate change has driven the consideration of sustainability in various sectors including energy, manufacturing, logistics, and so on. Countries are forced to reduce the use of fossil fuel as it is the main cause of global warming. Transportation has accounted for more than 23% of greenhouse gas emissions causing air pollution (Xiao et al., 2021 [1]). Accordingly, transportation has been changed to encourage the use of electric vehicles rather than internal combustion vehicles. The study of the vehicle routing problem has been extended to the study of the electric vehicle routing problem. The electric vehicle routing problem has become an important issue in the field of sustainability.

Many studies have been conducted for the electric vehicle routing problem. Compared to the conventional vehicle routing problem, the electric vehicle routing problem has additional issues, while both problems aim to find the optimal route from the alternatives. The issues of the electric vehicle routing problem include finding the optimal location of charging stations, estimating the recharging functions of the battery and energy consumption, and so on. Most studies are related to charging the battery of electric vehicles. Without the charging issue, the problem is the same as the conventional vehicle routing problem. The issue with location is to find the optimal locations of charging stations, minimizing the total travel costs. With vehicle routing, this problem becomes the location routing problem. For the charging function, the problem is to find the change or pattern of charging level by time. The function is assumed as a linear or nonlinear function. Since the charging time is long, there are some studies on partial charging instead of full charging. Research questions include where the charging stations are in place and how to charge the battery.

On the other hand, there is a lack of studies into the states of charging stations. When an electric vehicle arrives at a charging station and all charging slots are occupied, the electric vehicle may have to wait for a long time. If the charging station is closed, the electric vehicle should go to another charging station. The state of the charging station can be defined by its availability. If the charging station is not available when the vehicle arrives, this situation significantly affects its route. Thus, this paper considers the states of charging stations for the electric vehicle routing problem. Each charging station has its own state. The states for charging stations may have distributions or patterns. Once the patterns of the states are found, one can find the optimal location routes of electric vehicles.

One of the concerns for the electric vehicle routing problem is that the charging time is too long, rather than the issue of using fossil fuels. Due to their long charging time, vehicles occupy the charging slots for an extended period, so there may be lack of available slots. If the stations are crowded, the availability does matter. For example, assuming a vehicle arrives at a charging station and all charging slots are occupied, if the earliest available slot is in thirty minutes, the vehicle has to wait at least thirty minutes. The states of the charging station are not deterministic, but random or stochastic. Each station has a different uncertainty such as open/closed, occupied/empty, normal/out of order, and so on. These uncertainties present the availability of the charging station. Assuming there are multiple deliveries, each vehicle travels twice in a day, and needs to recharge one time either in the first time period or the second time period. If a vehicle’s battery is recharged in the first time period, the vehicle can travel without recharge in the second time period. On the other hand, if the vehicle wants to recharge in the second time period, the vehicle can travel without recharging in the first time period. In this case, the vehicle has to decide the time period to recharge to minimize the total travel costs in a day. Depending on the states of charging stations, we can decide when to recharge the battery for each vehicle. Thus, the patterns for the states of charging stations can be used as input parameters in the electric vehicle routing problem.

The contributions of this paper are as follows: This paper suggests an electric vehicle routing problem with states of charging stations and an optimization model. Depending on the states of charging stations, the optimal routes may be different. We also propose the strategy to achieve the optimal routing plans for vehicles. Vehicles must decide when and where to go at the next time period to minimize the total travel costs. Lastly, this paper provides some numerical experiments to show the viability of the proposed solution approach.

This paper presents the literature about this issue in Section 2. Section 3 describes the problem and a mathematical model for the electric vehicle routing problem. Section 4 proposes solution methods for the electric vehicle routing problem with the states of charging stations. Numerical examples and results are presented in Section 5. Finally, this paper summarizes the paper and discusses future work.

2. Literature Review

The electric vehicle routing problem has become an interesting issue in a variety of different fields such as transportation, energy, sustainability, and so on. Researchers have focused on charging-related issues or solution approaches. This section presents the related works for the electric vehicle routing problem rather than the conventional vehicle routing problem.

Various problems for the electric vehicle routing problem have been considered. Chakraborty et al. (2021, [2]) have dealt with the electric vehicle routing problem to find optimal charging schedules and routes. Schneider et al. (2015, [3]) have introduced time window constraints in the electric vehicle routing problem. Keskin et al. (2019, [4]) have considered the electric vehicle routing problem with time windows and explored the queues at charging stations. Hiermann et al. (2016, [5]) have also explored the electric vehicle routing problem with different vehicle sizes. Charging the vehicle has also been explored. Montoya et al. (2017, [6]) assumed a nonlinear function for the charging rate and suggested proper charging behavior. Froger et al. (2019, [7]) used a nonlinear function and proposed arc-based and path-based tracking of the time approach rather than a node-based model to avoid replicating the charging station nodes. If vehicles are fully charged during the travel, the total traveling time will be significantly increased. Instead of full charging, partial charging has been proposed in many studies. Bac and Erdem (2021, [8]) proposed the electric vehicle routing problem with multiple depots and heterogeneous fleets. Basso et al. (2021, [9]) also considered partial charging. In their research, the problem has included uncertainties such as road condition or energy consumption. Hybrid electric vehicles have been considered. In their research, Kasani et al. (2021, [10]) investigated electric vehicles and hybrid electric vehicle routing and scheduling problems in the private and public sectors. Ma et al. (2021, [11]) suggested the shared autonomous electric vehicle routing problem with battery swapping and proposed a speed optimization model on the travel arc. Pelletier et al. (2019, [12]) explored the uncertainty of energy consumption during a delivery tour. Al-dal’ain and Celebi (2021, [13]) investigated the problem of the vehicle compositions of electric and conventional vehicles to minimize total operational costs in urban areas. Brady and O’Mahony (2016, [14]) tried to find the patterns of travel of the vehicle and charging behavior. They used a dataset of vehicles traveling to resolve uncertainty.

For the modeling of the electric vehicle routing problem, studies have adopted optimization models. Mixed integer programming has been mostly used to formulate the problems, as many studies have adopted the mixed integer programming model for the vehicle routing problem. The objective function is similar to that of the conventional vehicle routing problem. Schneider et al. (2014, [15]) formulated their model to minimize the total travel distance. Hiermann et al. (2016, [5]) tried to minimize the total distance and vehicle costs. Ma et al. (2021, [11]) formulated the objective function to minimize the total travel distance, travel time, and energy consumption. Froger et al. (2019, [7]) and Montoya et al. (2017, [6]) constructed their objective function to minimize total driving and charging times. Bac and Erdem (2021, [8]) tried to minimize the total travel time, time window deviations, unscheduled jobs, and overtime. Al-dal’ain and Celebi (2021, [13]) constructed the objective function to minimize the total costs of vehicles: purchasing and salvage value, operational cost, maintenance cost, CO₂ emission cost, and fuel cost. Variants of the mixed integer programming have been used for the model. Pelletier et al. (2019, [12]) formulated a robust mixed integer programming model. Chakraborty et al. (2021, [2]) proposed a multi-objective mixed integer programming model for minimizing energy consumption and travel time. Nolz et al. (2022, [16]) developed their model with a mixed integer quadratic programming model as a nonlinear programming model. A data analytical model has also been used for the problem. Basso et al. (2021, [9]) used Bayesian regression for the estimation of energy consumption. Brady and O’Mahony (2016, [14]) suggested a model with the Monte Carlo simulation and copula function. Alizadeh et al. (2014, [17]) used a network model with a single-shortest-path problem on an extended transportation graph with virtual nodes. Lu and Wang (2019, [18]) developed a dynamic programming model for the capacitated electric vehicle routing problem. Gan et al. (2013, [19]) adopted an optimal control problem to find the optimal schedule of electric vehicles.

For the solution method, a variety of different approaches have been used to find the optimal solutions. Like the conventional vehicle routing problem, various heuristic methods have been used. Schneider et al. (2014, [15]) adopted a variable neighborhood search with the tabu search method. In their approach, a tabu search was plugged in the variable neighborhood search algorithm. Bac and Erdem (2021, [8]) used the variable neighborhood search algorithm and variable neighborhood descent algorithm. The variable neighborhood search was used to handle the dynamic problem and the variable neighborhood descent algorithm was used to cover the deterministic problem. An adaptive large neighborhood search algorithm has also been used to solve the problem. Nolz et al. (2022, [16]) proposed a template-based adaptive large neighborhood search algorithm with a two-phase solution scheme. Ma et al. (2021, [11]) used an adaptive large neighborhood search method with a speed optimization algorithm as a subroutine. Hiermann et al. (2016, [5]) solved the problem using branch and price combined with the adaptive large neighborhood search algorithm. Kessler and Bogenberger (2019, [20]) estimated the energy consumption model for electric vehicles with statistical analysis. Montoya et al. (2017, [6]) adopted a hybrid meta-heuristic combining an iterated local search and heuristic concentration. Basso et al. (2021, [9]) suggested a two-stage approach: the first stage is to find the paths between all the nodes to be visited; the second is to select the best order of the tour to minimize energy consumption. An exact algorithm has also been used. Pelletier et al. (2019, [12]) used an exact method with reformulation and a two-phase heuristic based on a large neighborhood search for large instances. Keskin et al. (2019, [4]) solved the problem using the exact algorithm for small instances and the adaptive large neighborhood search for large instances. Al-dal’ain and Celebi (2021, [13]) also used the exact algorithm with the software GAMS. Chakraborty et al. (2021, [2]) proposed a multi-objective heuristic algorithm, which is a graph-based centralized scheduling strategy.

Luo et al. (2023, [21]) proposed a co-operative planning method of considering fixed charging stations and mobile charging stations. In their study, the vehicles can charge in both a fixed charging station and a mobile charging station. Wang et al. (2022, [22]) suggested an electric vehicle charging station and location routing problem with resource sharing. They considered the location routing problem with multiple depots and multiple periods. Jeong et al. (2024, [23]) proposed a two-stage adaptive robust optimization approach for the electric vehicle routing problem with energy consumption uncertainty.

The related works listed above show that the electric vehicle problem has been explored in a variety of ways. Finding the optimal locations of charging stations has been studied for the vehicle routing problem. The issues of charging have also been suggested. They are charging functions, charging behaviors, partial charging, and so on. Most studies have formulated the problem with mixed integer programming. Various methods have been proposed to solve the electric vehicle problem. However, although there have been many studies for the electric vehicle routing problem, there is a lack of research for the state of charging stations, while their states can affect optimal routes. Thus, this paper can be a trigger to tackle this issue.

3. Electric Vehicle Routing Problem

3.1. Problem Statement

The vehicle routing problem is finding the optimal routes for vehicles that have to travel to customer sites which are geographically dispersed. The vehicle routing problem is comprised of two problems: the traveling salesman problem and the bin packing problem. The traveling salesman problem is known as the NP-hard problem. Accordingly, the vehicle routing problem is also the NP-hard problem. The electric vehicle routing problem has additional issues of charging the battery.

Figure 1 presents the electric vehicle routing problem. We assume that the change in weather conditions do not affect the optimal route, which is considered in the dynamic vehicle routing problem. There are charging stations that vehicles can visit during their delivery tours. The problem must consider charging the battery for the electric vehicle while the conventional vehicle routing problem does not need to consider this. As the number of electric vehicles increases, the number of charging stations has been increased in city areas. So, we assume that there are multiple charging stations so that the vehicle can choose one of them. Selected charging stations can affect the optimal routes for vehicles and total travel costs or distances. Thus, the vehicle must choose the charging station to minimize the total travel costs. We assume that some factors affecting routing solutions such as terrain and weather conditions or the degree of vehicle loading are not taken into account at this moment.

Assuming there are many customer sites to deliver, each vehicle has to do the delivery tour twice in a day because of the capacity of vehicle. We also assume that each vehicle should charge in either the first route or the second one. Thus, each vehicle has to decide when it charges.

Figure 2 denotes the vehicles servicing twice in a day. The information related to the status of the charging stations is updated daily. The states of charging stations are revealed every day before the start of routing. At the beginning, the customer sites are determined for delivery in the day and they are divided into two groups: the first time period group to visit and the second one. If a vehicle decides to charge in the first time period, the vehicle needs no charging in the second time period. On the other hand, if a vehicle does not charge in the first time period, the vehicle has to charge in the second time period. We assume the vehicle has no time to charge the battery in between period one and two since the vehicle has to load the products for the deliveries in period two during the time in between. The problem is to find the optimal routes for two time periods, as well as when the vehicles charge to minimize the total travel cost for a whole day.

3.2. Mathematical Model

We consider an electric vehicle routing problem with time windows. There is one depot, multiple vehicles, and multiple customer sites. The model for the problem is as follows.

Sets

$V=\left\{0,1,2,\dots ,n,n+1,\dots ,n+p\right\}$: (0: depot node, 1 ~ $n+p$: nodes)

$F=\left\{n+1, \dots , n+p\right\}$: Charging stations

$F^{\prime }$: Dummy charging stations

$N=V\backslash \left\{\left\{0\right\}\cup F\right\}$: Customer sites

$A=\left\{\left(i,j\right)|i,j\in V,i\ne j\right\}$: Arcs

$M=\left\{1,\dots ,m\right\}$: Vehicles

$V^{+}\left(i\right)=\left\{j\in V\left|\right(i,j)\in A\right\}$: Successor nodes of node $i$

$V^{-}\left(i\right)=\left\{j\in V\left|\right(j,i)\in A\right\}$: Predecessor nodes of node $i$

Parameters

$\left[a_i,b_i\right]$: Time window for node $i$

$s_i$: Service time for node $i$

$q_i$: Demand for node $i$

$w_i$: Difficulty of using the charging station $i$

$d_{i,j}$: Travel time from node $i$ to node $j$

$\tau$: Charging time per unit energy

$\delta$: Energy consumption per unit distance

$\mathrm{K}$: Capacity of a vehicle

$\mathrm{Q}$: Capacity of energy (electricity) for a vehicle

$L$: Large constant number

Variables

$x_{i,j}^m$: Binary variable, 1 if arc $\left(i,j\right)\in A$ belongs to the optimal routes by vehicle $m$, 0 otherwise

$t_i^m$: Arrival time of vehicle $m$ at node $i$ (beginning of service)

$y_i^m$: Energy level of vehicle $m$ at node $i$

$z_i$: Binary variable, 1 if charging station $i$ is used, 0 otherwise

$$\left(\mathrm{EVRP}\right) Min{\sum }_{m\in M}{\sum }_{(i,j)\in A}{d}_{i,j}{x}_{i,j}^m+{\sum }_{i\in F^{\prime }}{w}_i{z}_i$$

(1)

$$s.t.{\sum }_{m\in M}{\sum }_{j\in V}{x}_{i,j}^m=1, \forall i\in N,$$

(2)

$${\sum }_{m\in M}{\sum }_{j\in V}{x}_{i,j}^m\le 1, \forall i\in F^{\prime },$$

(3)

$${\sum }_{j\in V^{+}\left(0\right)}{x}_{0,j}^m=1, \forall m\in M,$$

(4)

$${\sum }_{i\in V^{-}\left(h\right)}{x}_{j,i}^m-{\sum }_{i\in {V }^{+}\left(h\right)}{x}_{i,j}^m=0, \forall j\in N,m\in M,$$

(5)

$${\sum }_{i\in {V }^{-}\left(0\right)}{x}_{i,0}^m=1, \forall m\in M,$$

(6)

$${\sum }_{i\in N}{q}_i{\sum }_{j\in V}{x}_{i,j}^m\le K, \forall m\in M,$$

(7)

$$t_i^m+\left(s_i+d_{i,j}\right)x_{i,j}^m-t_j^m\le \left(1-x_{i,j}^m\right)L, \forall (i,j)\in A, i,j\in N,m\in M,$$

(8)

$$t_i^m+d_{i,j}{x}_{i,j}^m+\tau \left(Q-y_i^m\right)-t_j^m\le \left(L+\tau Q\right)\left(1-x_{i,j}^m\right),\forall i\in F^{\prime },j\in N,m\in M,$$

(9)

$$\left(\delta d_{i,j}\right)x_{i,j}^m-Q\left(1-x_{i,j}^m\right)\le y_i^m-y_j^m,\forall i,j\in N, m\in M,$$

(10)

$$y_i^m-y_j^m\le \left(\delta d_{i,j}\right)x_{i,j}^m+Q\left(1-x_{i,j}^m\right),\forall i,j\in N, m\in M,$$

(11)

$${\sum }_{i\in N,j\in F^{\prime }}{x}_{i,j}^m=1, \forall m\in M,$$

(12)

$$x_{i,j}^m\le z_i, \forall i\in F^{\prime },j\in N,m\in M,$$

(13)

$$x_{i,j}^m\le z_j, \forall i\in N,j\in F^{\prime },m\in M,$$

(14)

$$a_i\le t_i^m\le b_i, \forall i\in N,m\in M,$$

(15)

$$x_{i,j}^m,y_i^m,z_i\in \left\{0,1\right\}, \forall i,j\in V,m\in M$$

(16)

The objective function (1) aims to minimize total travel distances and the difficulty of visiting charging stations. The second term plays a role as the availability. If a charging station is easy to access, the value of $w_i$ will have a small value. That is the state of each charging station. Constraint (2) ensures that each customer site is served once by one vehicle. Constraint (3) presents that each charging station can be used once at most. Constraints (4) and (6) enforce that each vehicle has to leave and return to the depot. Constraint (5) presents that once a vehicle enters a node, the vehicle has to leave the node except the depot. The capacity of each vehicle is in constraint (7). Constraints (8) and (15) are time window constraints for customer nodes. Constraint (9) denotes the constraint for the time of charging. Constraints (10) and (11) present energy consumption through the arc. Constraint (12) forces each vehicle to visit a charging station once. Constraints (13) and (14) ensure a charging station is open only if a vehicle travels to the charging station. Constraint (16) is for binary variables.

If $w_i$ has a large value, the charging station $i$ will have a low possibility to be chosen by a vehicle. Thus, depending on the value, we can control the availability of the charging station. The model assumes that the capacity of the battery is limited, so each vehicle has to visit a charging station during a delivery tour. In the problem of two time periods, we solve the problem of electric vehicle routing with the above EVRP model. Depending on the locations of customer sites and available charging stations, decisions will be made if the vehicles visit the charging stations in the first time period or not with the solutions from the model. The solution of the model provides the optimal strategy for the electric vehicle routing problem.

4. Solution Method

This section presents how to solve the electric vehicle routing problem with the states of charging stations. For a conventional vehicle routing problem, we have to determine the optimal routes for vehicles. When it comes to an electric vehicle routing problem, the locations of charging stations are additionally determined. Considering the states of charging stations, the states will affect the optimal solution. In this paper, we consider a two-time-period problem. The vehicles have to determine how to travel for the time periods. This seems to have two electric vehicle routing problems. The optimal route for each time period may include a visit to the charging stations or may not. These decisions are to be made for the problem in this paper.

In Figure 3, the problem is solved with two phases. At first, the patterns of states for the charging stations are estimated to present the availability of charging stations. Each charging station has its own pattern for the state of occupation. Upon collecting the data from the charging stations, the patterns are determined by analyzing the data. Once the pattern is found, it can be seen as the availability of the charging station. In the second phase, we solve the electric vehicle routing problem of the model proposed in the previous section. The patterns become the parameters in this routing problem. The solution presents the total travel costs with the states of the charging stations. The solutions for time periods can be used to find the optimal strategy.

The algorithm has been designated to find optimal routing schemes for vehicles. For the problem described in this paper, three algorithms have been adopted to find the solutions of the vehicle routings. The Algorithm 1 randomly chooses the charging time. At the beginning of the day, a random number is generated for each vehicle. If the number is less than 0.5, the vehicle will charge the battery at time period two. Otherwise, the vehicle can charge the battery at time period one.

Algorithm 1: random solution strategy

Initialize:  $\mathrm{T}=\left\{\mathrm{1,2},\dots ,n\right\}$: time horizon for all days  $r_{i,j}$: route in period $i$ with $j$ action where $j=\left\{\mathrm{0,1}\right\}$;  where 1 (visit charging station), 0 (no visit charging station)  $D_{i,j}$: demand for period $j$ in day $i$ Repeat: until $k=n$   $k\to 1$  For day $k$   $\mathrm{R}\mathrm{n}\mathrm{d}$ = random(): generate random number [0,1]  If$\mathrm{R}\mathrm{n}\mathrm{d}\ge 0.5$$, {\pi }^{\ast }\left(k\right)=\left\{r_{\mathrm{1,1}}, r_{\mathrm{2,0}}\right\}$  If$\mathrm{R}\mathrm{n}\mathrm{d}<0.5$, ${\pi }^{\ast }\left(k\right)=\left\{r_{\mathrm{1,0}}, r_{\mathrm{2,1}}\right\}$  $k\to k+1$  End

For the Algorithm 2, total travel distances are considered to make the decisions of charging. Solutions for the vehicle routing problems for period one and two present the total distances of travel for each vehicle. Each vehicle will charge the battery at period one if the total distance of period one is less than the period two.

Algorithm 2: minimal distance solution strategy

Initialize:  $\mathrm{T}=\left\{\mathrm{1,2},\dots ,n\right\}$: time horizon for all days  $r_{i,j}$: route in period $i$ with $j$ action where $j=\left\{\mathrm{0,1}\right\}$;   where 1 (visit charging station), 0 (no visit charging station)   $D_{i,j}$: demand for period $j$ in day $i$ Repeat: until $k=n$  $k\to 1$  For day $k$    Solve (EVRP) with $D_{k,1}$: ${Td}_{k1}$ (total distances)    Solve (EVRP) with $D_{k,2}$: ${Td}_{k2}$ (total distances)   If ${Td}_{k1}<{Td}_{k2}$, ${\pi }^{\ast }\left(k\right)=\left\{r_{\mathrm{1,1}}, r_{\mathrm{2,0}}\right\}$   If ${Td}_{k1}\ge {Td}_{k2}$, ${\pi }^{\ast }\left(k\right)=\left\{r_{\mathrm{1,0}}, r_{\mathrm{2,1}}\right\}$   k→k + 1 End

The Algorithm 3 considers the states of charging stations in order to find the optimal solution for vehicle routings. In addition to the solutions for vehicle routings for period one and two, the solutions considering the states of the charging stations are also considered to make decisions for the optimal routing strategy.

Algorithm 3: charging stations solution strategy

Initialize:   Find states $\mathsf{\Omega }(\mathrm{s},\mathrm{t})$ of charging stations   $\mathrm{T}=\left\{\mathrm{1,2},\dots ,n\right\}$: time horizon for all days   $r_{i,j}$: route in period $i$ with $j$ action where $j=\left\{\mathrm{0,1}\right\}$;   where 1 (visit charging station), 0 (no visit charging station)   $D_{i,j}$: demand for period $j$ in day $i$ Repeat: until $k=n$   $k\to 1$   For day $k$    Solve (EVRP) with $D_{k,1}$: $z_{k1}$ (objective value)    Solve (EVRP) with $D_{k,2}$: $z_{k2}$ (objective value)    Solve (EVRP) with $D_{k,1}$ and $\mathsf{\Omega }(\mathrm{s},\mathrm{t})$: $z_{k3}$ (objective value)    Solve (EVRP) with $D_{k,2}$ and $\mathsf{\Omega }(\mathrm{s},\mathrm{t})$: $z_{k4}$ (objective value)   If $z_{k1}+z_{k4}>z_{k2}+z_{k3}$, ${\pi }^{\ast }\left(k\right)=\left\{r_{\mathrm{1,1}}, r_{\mathrm{2,0}}\right\}$   If $z_{k1}+z_{k4}<z_{k2}+z_{k3}$, ${\pi }^{\ast }\left(k\right)=\left\{r_{\mathrm{1,0}}, r_{\mathrm{2,1}}\right\}$   $k\to k+1$ End

The above algorithms can help vehicles to decide when they should charge. We have compared the results of three algorithms with an example to see their performance.

Table 1. Total costs for three algorithms.

Days	Algorithm 1	Algorithm 2	Algorithm 3
1	922.3	922.3	874.0
2	943.7	963.9	943.7
3	788.4	840.2	788.4
4	862.3	862.3	860.5
5	746.3	825.0	742.5
Sum	4263.0	4413.7	4209.1

shows the experimental results for the three algorithms with examples which will be shown in Section 5. From the results, the CS algorithm has obtained better solutions than the other algorithms. Each vehicle can visit the charging station only once, minimizing the total travel costs.

For the estimation of the patterns for the states of charging stations, we can derive the probability distribution of the states from the data. The state of a charging station is defined as the time a vehicle must wait when it arrives at the charging station. The data from a charging station may not be the waiting time, so we can derive the waiting time from the dataset. Common data at a station are the number of vehicles that arrive at a certain time. With these data, we can derive the distributions of waiting times at charging stations.

Arrivals to a system are usually assumed as following a Poisson distribution in a queueing system. Let $\mathsf{\lambda }$ be the parameter of the Poisson distribution and denote the number of events in a given interval. The probability density function is defined as follows.

$$P\left(X=x\right)=\frac{{\lambda }^x{e}^{-\lambda }}{x!}, x=\mathrm{0,1},2, \dots$$

(17)

Function (17) presents the probability that the number of events is $x$ in a unit time interval. From the probability distribution of arrivals, we can derive the distribution of the time intervals between arrivals. The probability distribution of the time interval can be defined as an exponential distribution as follows.

$$f\left(x\right)=\lambda e^{-\lambda x}, x\ge 0$$

(18)

Function (18) denotes the probability that the interarrival time between events is $x$. These two probability distributions are used to estimate the states of charging stations. The waiting time of a vehicle is calculated by summing the charging time with the interarrival time. For instance, we assume a simple example for estimating the states from the data.

Table 2. Arrival of vehicles in time intervals.

Time Interval	Arrivals of Vehicles	Time Interval	Arrivals of Vehicles
11:00–11:10	1	12:20–12:30	1
11:10–11:20	0	12:30–12:40	2
11:20–11:30	0	12:40–12:50	1
11:30–11:40	0	12:50–13:00	0
11:40–11:50	1	13:00–13:10	4
11:50–12:00	2	13:10–13:20	0
12:00–12:10	3	13:20–13:30	2
12:10–12:20	4

shows the number of vehicles arriving in time intervals. The data can be counted in each charging station. With the data, we can derive the probability distribution of arrivals, which is assumed to follow a Poisson distribution.

Table 3. Count of arrivals.

Number of Arrivals (A)	Observed Counts (B)	A × B
0	5	0
1	4	4
2	3	6
3	1	3
4	2	8
Sum	14	21

presents the counts of the arrivals from Table 2. For example, there were zero arrivals five times in Table 1 and two vehicle arrivals occurred three times. The third column is the value of the product of two numbers. With the two sums, we can calculate the $\mathsf{\lambda }$ of the distribution as follows.

$$\mathsf{\lambda }=\frac{A\times B}{\mathrm{S}\mathrm{u}\mathrm{m} \mathrm{o}\mathrm{f} \mathrm{o}\mathrm{b}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{v}\mathrm{e}\mathrm{d} \mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}\mathrm{s}}=\frac{21}{14}=1.5$$

(19)

Function (19) presents the calculation of $\mathsf{\lambda }$ of the distribution of arrivals of vehicles at the charging station. The value of $\mathsf{\lambda }$ denotes that the average number of vehicles in a unit time period is 1.5. With this $\mathsf{\lambda }$, we can derive the interarrival time distribution with the exponential distribution. Thus, the average time of interarrival is calculated as $\frac{1}{\mathsf{\lambda }}=0.67$. Adding the charging time from the interarrival can estimate the waiting time of the vehicle.

These estimated waiting times are the parameters for the electric vehicle routing problem as the EVRP model. The routing problem can be solved with the exact algorithm. We show some numerical examples for the routing problem in the next section.

5. Experimental Results

This section presents simple numerical examples for the electric vehicle routing problem. This paper considers an instance modified from a Solomon benchmark problem. The dataset, so-called Solomon benchmark instance, generated by M.M. Solomon (1987, [24]) has been used in many studies into vehicle routing problems; for example, instances.

Figure 4 shows an instance for an electric vehicle routing problem. The instance is randomly modified from a Solomon benchmark problem. We have plotted the layout of the instance with the co-ordinates of x and y in the dataset as shown in Figure 4. In the layout, we have not taken into account the route topography since the dataset is generated from the benchmark problem. There is one depot, multiple customer sites, and multiple charging stations. In the figure, the square denotes the depot, circles represent charging stations, and stars represent customer sites. All customer sites have to be visited, but some of the charging stations are selected to visit. A vehicle has to visit a charging station once during the delivery tour.

Solving a mixed integer programming problem with an exact algorithm is a time-consuming task. Thus, we have sampled five small instances from the problem of Figure 4, reducing the size to 15 customer sites. Figure 5 shows the sample example one from the instance in Figure 4, so the instance has one depot, 21 potential charging stations, and 15 customer sites for each time period. Vehicles have to service all customer sites for two time periods and charge either in period one or period two. Potential charging stations are selected to minimize the total travel costs.

In this paper, we have implemented the EVRP model with C# with the concert technology of the CPLEX 12.6.1 software. Solving the instance in Figure 5 for period one and period two, we have the following results.

Figure 6 and Figure 7 show the solution of example one. The numbers in each row denote the nodes of the depot (0), charging stations, and customer sites. The order of the node numbers in a row presents the sequence of the optimal route. The sequence of nodes in a row is for the route of each vehicle. The vehicle starts from depot node 0 and returns to the depot. The objective value is the total cost of each route. The total cost is calculated with the sum of the total distances of the routes and costs of reaching the charging stations. Three vehicles are used to service the customer sites. In Figure 6, vehicles travel without visiting charging stations. On the other hand, vehicles are visiting charging stations once in Figure 7 and the number with an asterisk presents the charging station the vehicle visits. From the results, it can be seen that the optimal routes are changed when the vehicles visit the charging stations. The objective values as total travel costs are also changed. For the optimal strategy, we can calculate $z_{11}+z_{14}$ and $z_{12}+z_{13}$ and compare them.

$$z_{11}+z_{14}=385+489=874<z_{12}+z_{13}=485.9+436.4=922.3$$

(20)

From comparison (20), $z_{11}+z_{14}$ is less than $z_{12}+z_{13}$. Accordingly, vehicles are recommended to visit charging stations in period two rather than period one.

The results of Figure 6 without visiting charging stations can be seen as the routing from fossil-fueled vehicles. The results of Figure 7 from electric vehicles have 6% more total distances than the results of Figure 6. However, for the emission of CO₂, the results of traditional routing solutions are much larger than the results of the optimal routings from Figure 7.

Figure 8, Figure 9, Figure 10 and Figure 11 show the experimental results of examples 2~5. The examples are generated by randomly sampling 15 customer sites from the instance in Figure 4. Optimal routes are determined by solving the EVRP model with the exact method. For the strategy for a day, we calculate $z_{k1}+z_{k4}$ and $z_{k2}+z_{k3}$ for each example.

$$z_{21}+z_{24}=448.6+525.1=973.7<z_{22}+z_{23}=516.2+468.8=985$$

(21)

$$z_{31}+z_{34}=352.9+435.5=788.4<z_{32}+z_{33}=392.3+404.7=797$$

(22)

$$z_{41}+z_{44}=393+467.5=860.5<z_{42}+z_{43}=442.3+420=862.3$$

(23)

$$z_{51}+z_{54}=309.6+436.7=746.3>z_{52}+z_{53}=354.2+388.3=742.5$$

(24)

Equations (21)–(24) present the comparisons of total travel costs for the days. In examples two, three, and four, the total travel costs of $z_{k1}+z_{k4}$ are smaller than $z_{k2}+z_{k3}$. Thus, in case of examples two, three, and four, visiting the charging stations in period two is better than the other way. On the other hand, for example five, it is better for vehicles to visit the charging stations in period one. In this way, we can make decisions how and when the vehicles take charging during the delivery tours.

Figure 12 presents the solutions as the difficulties of charging at the stations change. The difficulty of charging is the weight in the objective function of the EVRP model. As the difficulty changes, the optimal route changes. If the change is small, the optimal solution does not change. However, if the change is big enough, the optimal route will be different. The model can find the threshold of the difficulty to change the optimal routes. Thus, with the values, we can control the routing strategy for vehicles.

Depending on the battery state or charger’s power output or other factors, the charging times vary in some charging stations. The variability of the charging times may affect the routing solutions. We have conducted the sensitivity analysis to show how the changes in the charging times affect the routing solutions.

Table 4. Sensitivity analysis: charging times affect the routing solutions.

Charging Stations	1~7	8~14	15~21	Charging Stations Used in the Optimal Routes for Three Vehicles
Charging times	5	5	5	4, 8, 17
	10	5	5	4, 8, 17
	…	5	5	4, 8, 17
	35	5	5	4, 8, 17
	40	5	5	8, 14, 21
	45	5	5	8, 14, 21
	5	5	5	4, 8, 17
	5	10	5	4, 6, 17
	5	15	5	4, 6, 17
	5	5	5	4, 8, 17
	5	5	10	4, 8, 17
	5	5	15	4, 8, 14
	5	5	20	4, 8, 14

shows the sensitivity analysis of charging times and routing solutions. In total, 21 potential charging stations are divided into three groups: 1~7, 8~14, and 15~21. We have assigned the charging times differently to those three groups to see the changes to the routing solutions. As the charging times in only a certain group increase, the charging stations in that group have not been used in the optimal routes.

6. Conclusions

This paper suggests the electric vehicle routing problem by considering the states of charging stations. The issue of charging is important for the electric vehicle routing problem. Charging functions, energy consumption, and the location of charging stations have been explored in many studies. However, the state of a charging station is also important to find the optimal route in the electric vehicle routing problem. The state of a charging station can be seen as the availability of the charging station. If charging is not available when a vehicle arrives, the travel costs will significantly increase. In this paper, we consider the states of charging stations, formulate the model, and suggest the solution approach.

The first step of the solution approach is to collect the data from all charging stations. The arrivals of vehicles to the station are collected as raw data. The data has been analyzed to find the patterns of states of the charging stations. Estimating the probability distribution of arrivals and interarrival times can be used to find the pattern of waiting times when a vehicle arrives at the charging station. Once the patterns of the states of charging stations are determined, the values are used as input parameters for the model of the electric vehicle routing problem. With the solutions, we can find the optimal routing strategy for the two-time-period problem.

Experimental results provide how to find the optimal strategy for the electric vehicle routing problem with the states of charging stations. In the two-time-period problem, we are able to determine in which time period the vehicles visit the charging stations. The difficulty of charging can be used to find the threshold where the optimal routes change. Thus, we can control the electric vehicle routing by considering the availability of the charging stations.

The nonstationary distributions for the states of charging stations should be explored in future work. Investigating the uncertainty of charging durations for vehicles is also a challenging issue. Obtaining real-world scenarios for the states of charging stations and investigating the charging behaviors of vehicles are the future works of our study. In addition, the change in atmospheric conditions, especially temperature, change of topography (driving uphill or downhill), or carried weight have a significant impact on the operation of batteries and thus the range of electric vehicles. Taking into account these parameters is also future work.