Keywords

1 Introduction

With rising pollution levels globally, cities are adopting means and technologies that are social and environmental friendly for various activities. The movement of vehicles on the roads is one of the major contributors of the overall rise in the air pollution over the globe. Recent advancements in the electric vehicle technology with high power and compact batteries have opened up new modalities to shape the transportation for people and goods. The prominent advantage of using electric vehicles is that they do not emit the green house gases that act as the major contributor to the global pollution. For large scale logistics operations such Electric Vehicles (EVs) now provide more viable green technology to serve customers (mostly referred as green logistics). However, EVs have their own share of drawbacks which limits their usage. At the very basic, it is the limited driving range with one complete charge that EVs can scale up to. The maximum driving range of the EVs is around 100–150 miles which gets further reduced by the operating and environmental conditions such as low temperatures, battery age, weight of the vehicle with payload, etc. Further EVs can take more than half-an-hour to completely charge their batteries which is also dependent on the type of batteries and the capacity of charging outlets.

To make way for the EVs to join the mainstream commercial logistics services, one needs to consider all such constraints for route planning and scheduling of these vehicles. Although researchers have considered the limited battery capacity of the EVs in planning the routes, the limited capacity of charging stations have scarcely been addressed in the literature. The scarcity of charging station resources is particularly pertinent in cities where EVs are still in the infant stage of adoption. The station locations, number of charging outlets and charge delivery capacities put limitations to the number of EVs that can be charged simultaneously at a charging station. In addition, due to the long charging time of EVs with limited charging infrastructure, one needs to consider the significant queuing time at the charging stations while planning routes for logistics fleet operations.

In this paper, our focus is to plan the routes for a fleet of EVs for logistics operations by allowing the EVs to queue and wait at the fixed capacity charging stations. We present an exact mathematical formulation of the classical VRP problem with the considerations of limited battery charge, cargo capacity constraints and waiting times at the charging stations. One major difficulty in modeling this problem is to handle the queuing sequence at each charging station, which we overcome by using a subtour elimination technique commonly used for solving the Traveling Salesman Problem (TSP). Such considerations can make the route planning of EVs more viable for real world operations. Further, the last mile delivery operations can further be streamlined with such EVs taking the central stage with carefully planned routes and visits to the charging stations. Hence, our work extends the current literature by addressing the challenging aspect of route planning for a logistics fleet with an explicit modeling of waiting times at the charging stations. Further in our proposed solution, we handle the constraints (such as charging sequence of EVs) by integrating a Constraint Programming (CP) model in our heuristic approach.

The rest of the paper is organized as follows. In the next section, we discuss the related literature for solving EV routing. The succeeding sections present the problem formulation as an MIP considering the limited battery capacities of EVs and waiting times at the charging stations. Next, we present a GA method to solve large problem instances and the results gathered from the numerical experiments. The last sections concludes the paper with avenues of future research.

2 Related Literature

The Electric Vehicle Routing Problem (EVRP) is a special case of the traditional Vehicle Routing Problem with the additional set constraints due to the electric engine technology. Schneider et al. [1] describe the EVRP with Time Windows (EVRPTW) as an MIP formulation and propose a heuristic combining variable neighborhood search and tabu search. In their problem formulation, the authors considered charging stations having no capacity constraint on number of chargers. In addition, they have not considered any waiting times at the charging stations. Goeke and Schneider [2] extended the EVRPTW model for a mixed fleet of conventional and electric vehicles with time windows and capacity constraint. The authors emphasize on the energy consumption models for the conventional and electric vehicles which is non-linear by nature. Sassi and Oulamara [3] considered an electric vehicle scheduling and optimal charging problem in order to assign vehicles to tours and minimize the charging cost. In their model, they considered constraints related to chargers, electricity grid, and EVs driving range.

In [4], the authors discuss the formulation of a mixed fleet with a case study at the city of Amsterdam. In their objective, the authors factors in the fixed cost of vehicles and the variable cost which depends on the en-route time and distance. Although the authors consider the battery capacity constraints of the electric vehicles, there is no consideration given to the amount of time a vehicle may need to spend at a charging station. The authors in [5] considers partial charging of electric vehicles with non-linear charging functions. The non-linearity of the battery charging function is handled using a piece-wise linear approximation. The authors model the problem to minimize the total time which includes the travel time and time spent at the charging stations.

Qin and Zhang [6] discuss the scheduling of charging activities with minimal waiting time of EVs in a network of EVs and charging stations. The authors consider EVs in general not involving a logistic fleet operation. Although, the authors address the problem of waiting time at the charging stations which translates to the availability of the charging outlets, the routing problem of the vehicle is not considered. Additionally, Froger et al. [7] address the problem of limited capacity charging stations for vehicle routing and provide matheuristic based approach to solve the problem. EVRP can be considered a specialized problem of the larger set of the Green Vehicle Routing Problem (G-VRP) that focuses on the use of alternative fuel sources for the vehicles. Hence, G-VRP also focuses on similar issues such as the limits to driving range and limited refueling stations. In [8] for example, the authors discuss the G-VRP and provide an MIP formulation for this problem.

Table 1. Variables and parameters of our proposed EVRP model
Full size table

As can be noted from the discussions above, the literature on EVs is segregated in two broad groups - those who consider it as a routing problem for fleet of EVs and those who consider the problem of scheduling and congestion at the charging stations. There is also a third variant which is related to the placement of charging stations infrastructure such as the one discussed in [9]. However, the problem of restricted number of charging outlets at the charging stations for the EV fleet operations does not seem to be addressed in the literature. The waiting times due to unavailability of charging outlets or scheduling the vehicle at the charging stations while planning their routes in a traditional VRP setting warrants further considerations to come up with real-world solutions.

3 Mathematical Model

The primary objective of our work is to address the limited capacities of the charging stations which may result in the formation of queues in order to service a logistics fleet of EVs. A charging station consists of a set of charging outlets wherein a vehicle is plugged in to recharge its battery. Such charging outlets could be limited in number at the charging stations depending upon the electric grid capacity and charging stations’ space constraints. In this section, we provide the exact mathematical model for our EVRP considering waiting times of the vehicles at the charging stations.

Let V be the set of customer nodes and R be the set of charging stations. Let the start and end depot node instances be denoted by 0 and \(N+1\). We will use 0 and \(N+1\) in the subscript to denote the set of nodes with start or end depot instance or both as in [1]. Table 1 lists the variables and parameters used in our model. To allow multiple visits to the charging station outlets, we create dummy nodes for every charging stations outlet in R. We further consider a linear discharge of the vehicle batteries and the distance among the nodes is Euclidean. We assume that the vehicles leave the depot with full charge and will not visit charging station outlet before completing their first delivery. Moreover, each visit to the charging station outlet results in full battery charge of the vehicles.

The objective function in our mixed integer program is to minimize the sum of route durations, which includes the travel time, the service time at the customer nodes, the charging and waiting times at the charging station outlets.

$$\begin{aligned} \min \sum _{\hbar \in \varOmega } \tau _{N+1}^{\hbar } \end{aligned}$$
(1)

Subject to:

$$\begin{aligned} \sum _{j \in V_{N+1}^{'}} x_{ij}= & {} 1, \forall i \in V \end{aligned}$$
(2)
$$\begin{aligned} \sum _{j \in V_{N+1}^{'}} x_{ij}\le & {} 1, \forall i \in R \end{aligned}$$
(3)
$$\begin{aligned} \sum _{i \in V_{N+1}^{'}} x_{ji} - \sum _{i \in V_{0}^{'}} x_{ij}= & {} 0, \forall j \in V' \end{aligned}$$
(4)
$$\begin{aligned} \tau _i + (t_{ij} + s_i)x_{ij} - T(1-x_{ij})\le & {} \tau _j , \forall i \in V_0, \forall j \in V^{'} \end{aligned}$$
(5)
$$\begin{aligned} w_i + \beta (B-y_i)+ t_{ij}x_{ij} - (T+\beta B)(1-x_{ij})\le & {} \tau _j, \forall i \in V_0, \forall j \in V_{N+1}^{'} \end{aligned}$$
(6)
$$\begin{aligned} \tau _i + (t_{i,N+1} + s_i)x_{i,N+1} - T(1-x_{i,N+1})\le & {} \tau _{N+1}^\hbar , \forall i \in V, \hbar \in \varOmega \end{aligned}$$
(7)
$$\begin{aligned} w_i + \beta (B-y_i) + t_{i,N+1}x_{i,N+1} - (T+\beta B)(1-x_{i,N+1})\le & {} \tau _{N+1}^\hbar ,\forall i \in \bigcup _{k \in R} R^k, {\hbar } \in \varOmega \end{aligned}$$
(8)
$$\begin{aligned} \tau _i\le & {} w_i, \forall i \in R^k \end{aligned}$$
(9)
$$\begin{aligned} u_i - D_ix_{ij} + C(1-x_{ij}) \ge f_j\ge & {} 0, \forall i \in V_{0}^{'}, \forall j \in V_{N+1}^{'} \end{aligned}$$
(10)
$$\begin{aligned} C \ge f_0\ge & {} 0 \end{aligned}$$
(11)
$$\begin{aligned} y_i - \delta d_{ij}x_{ij} +B(1-x_{ij}) \ge y_j\ge & {} 0, \forall j \in V_{N+1}^{'}, \forall i \in V \end{aligned}$$
(12)
$$\begin{aligned} B - \delta d_{ij} x_{ij} \ge y_j\ge & {} 0, \forall j \in V_{N+1}^{'}, \forall i \in R^k, k\in R \end{aligned}$$
(13)
$$\begin{aligned} \sum _{u \in R^k} b^k_{uv}\le & {} 1, \forall v \in \varOmega , \forall k \in R \end{aligned}$$
(14)
$$\begin{aligned} \sum _{v \in V} b^k_{uv} - \sum _{v \in V}x_{uv}= & {} 0, \forall u \in R^k, \forall k \in R \end{aligned}$$
(15)
$$\begin{aligned} \sum _{v \in V} vb^k_{uv}= & {} z^k_{u}, \forall u \in R^k, \forall k \in R \end{aligned}$$
(16)
$$\begin{aligned} z_v^k-z_u^k-(m-1) -Ma_{m,u,v}^1\le & {} 0, \forall m\in \varOmega \backslash N,u,v\in R^k \end{aligned}$$
(17)
$$\begin{aligned} (m+1) - (z_v^k-z_u^k) -Ma_{m,u,v}^2\le & {} 0 , \forall m\in \varOmega \backslash N,u,v\in R^k \end{aligned}$$
(18)
$$\begin{aligned} a_{m,u,v}^1+a_{m,u,v}^2-a_{m,u,v}\le & {} 1, \forall m\in \varOmega \backslash N,u,v\in R^k \end{aligned}$$
(19)
$$\begin{aligned} \sum _{m \in \varOmega \backslash N} a_{m,u,v}= & {} a_{uv},\forall u,v\in R^k \end{aligned}$$
(20)
$$\begin{aligned} (a_{uv}-1)M\le & {} \tau _v-\tau _{u}, ~\forall u,v\in R^k \end{aligned}$$
(21)
$$\begin{aligned} w_v -w_{u}+ (1-a_{uv})M\ge & {} (B-y_u)\beta , \forall u,v \in R^k \end{aligned}$$
(22)
$$\begin{aligned} x_{ij} \in \{0,1\}, \forall i \in V_0^{'}, j \in V_{N+1}^{'}&\,\,&b^k_{uv} \in \{0,1\}, \forall u \in R^k, v \in \varOmega , k\in R \end{aligned}$$
(23)

Equation (1) minimizes the sum of route duration of each individual route. Constraint (2) specifies that all the customer nodes must be visited. Constraint (3) defines the visit to the charging station outlets. The constraint in (4) ensures flow conservation, which basically means all the outflows from a node and inflows to a node must be equal i.e. all the vehicles that leave a node must be equal to the number of vehicles that arrived at that node. Constraints (5) and (6) provide the arrival time at a node from a customer node and charging station outlet respectively. Constraints (7) and (8) provide the arrival time at the depot from a customer node and charging station outlet. Constraint (9) forces that the start of charging at the charging station outlet must be after the arrival and possible waiting. Constraints (10) and (11) is for the fulfillment of customer demand while constraints (12) and (13) are to ensure that the vehicles batteries always have positive charge.

Constraints (14)–(22) are meant to derive the waiting times of the vehicles that queue at a charging station outlet. The basic idea here is to sequence the vehicle based on their arrivals at the charging station outlet and use this sequence to calculate the start of charging of the vehicles at the charging station outlet. Constraint (14) forces that whenever a vehicle visits the charging station outlet, it gets assigned a sequence index. Constraint (15) ensures that all the vehicles that has arrived, also leave the charging station outlet, while (16) assigns the sequence index to the vehicles that arrive at the charging station outlet after serving a given customer node. Constraints (17)–(20) ensure the vehicle sequence of charging at the charging station outlet. Finally, constraints (21)–(22) calculate the time to start the charging based on the sequence index of the vehicles.

The binary variables \(a^1_{m,u,v}\), \(a^2_{m,u,v}\) and \(a_{m,u,v}\) are introduced to get the visiting order of the EVs at a charging station outlet based on m. The associated constraints (17)–(20) ensures that, if \(a^1_{m,u,v}\) equals to 1, \(Z_v^k - Z_u^k > m-1\), similarly, if \(a^2_{m,u,v}\) equals to 1, it means \(Z_v^k - Z_u^k < m+1\), and if \(a_{m,u,v}\) equals to 1, it means \(Z_v^k - Z_u^k = m+1\). Constraint (17–20) is to define the sequence of vehicles visit at charge station and deduct the waiting time. Note that m belongs to the set of {1,..., \(\textit{N}\)-1}, hence, the big \(\textit{M}\) in (17) and (18) can be defined as \(\textit{N}\).

4 Genetic Algorithm (GA)

In this Section, we present our Genetic Algorithm (GA) approach to solve our EVRP problem defined above. The initial population size is set to \(\Lambda \). We use a greedy algorithm to generate the initial population of solutions, which vary the order of selection of customer nodes to generate different individuals of the population. The fitness function used to evaluate an individual solution is the total route duration of all the routes to serve all the customers in the problem instance. The children solutions are improved by applying a local search heuristics and battery charge station visiting algorithm.

To generate an initial solution, we first assign an empty route that start and end at depot to each vehicle. We then randomly insert a customer node at the best position of the route for the vehicle with the smallest additional cost. If the battery charge of the vehicle cannot support visiting to the next customer, we add a charging station outlet visit. Once the route has been updated, we block the corresponding charging station outlet time interval occupied by this vehicle. When no more customer nodes could be added to the first vehicle, we proceed to the second vehicle, and so on. We repeat this process until all customers are fully served.

We represent each individual solution (chromosome) as a sequence of node labels. Hence, each chromosome starts with a depot label and ends with a depot label. All the customers and stations labels are inserted in between based on the routes taken. The end/start of each route is marked by the depot label. Hence, a single chromosome can be divided into a set of segments with starting and ending depot labels. Each such segment represents a vehicle route. Figure 1 depicts the representation of a chromosome with three routes, two charging station outlets and eight customer nodes wherein D denotes depot, C denotes customer nodes, and S denotes the charging station outlets. Hence, when we evaluate the fitness function, we will translate the chromosome to multi-routes, which is split by D, then, we calculate the sum of route durations.

Fig. 1.
figure 1

An individual solution representation in the GA

Full size image

4.1 Constraint Programming (CP) for Fitness Evaluation

We vary the order of selection of customer nodes to generate different individuals of the population. The fitness function used to evaluate an individual solution is the total route duration to serve all the customers in the problem instance.

Table 2. Variables and parameters of the CP model
Full size table

Let c(s) be the routing cost (that is, sum of the travel time and service time) of route s. The fitness function f is defined to be the sum of routing costs and waiting times of all routes, each route has a fitness value \(f(s)=c(s)+w(s)\), where w(s) is the total waiting time incurred for route s. Interestingly, for a route s, c(s) is easy to calculate, but the calculation of waiting time is complicated, as vehicles can visit charging station outlet many times, and wait either at charging station or customer locations. This makes the calculation of the consequent waiting times (if any) non-trivial. For this purpose, we apply a Constraint Programming (CP) model for calculating the optimal fitness value.

For the CP model, we first find that the solution satisfies the capacity and battery charge constraints for the vehicle. If the constraints are satisfied, then, we apply the CP model to calculate the fitness value of the total route duration.

$$\begin{aligned} \min \sum \limits _{k\in \varOmega }serv_{e_k}-arr_{s_k} \end{aligned}$$
(24)

Subject to:

$$\begin{aligned} arr_i\le serv_i,\forall ~i\in V \end{aligned}$$
(25)
$$\begin{aligned} serv_i+\lambda _i+t_{i,succ_i}=arr_{succ_i},\forall ~i\in V\backslash E \end{aligned}$$
(26)
$$\begin{aligned} CUMULATIVE(\{serv_i, \lambda _i:i\in R^o\},1,C^o),\forall ~R^o\in R \end{aligned}$$
(27)

The variables and parameters used in the CP model are listed in Table 2. The objective function (24) minimizes the total route duration. Constraints (25)–(26) define the earliest arrival time, and start time of charging at node i. The charging resource constraint (27) is modeled using the global constraint, where \(serv_i\), \(\lambda _i\), 1 and \(C^o\) represent the start time of charging, duration, resource requirement, and the capacity of the resource respectively. The cumulative constraint (27) specifies the requirements on tasks which need to be scheduled on a number of resources. It expresses the fact that at any time instant the total use of these resources for the tasks does not exceed a given limit. For our problem, we have a list of charging tasks, each task requires only one resource, and the upper limit of the amount of charging resources limit equals to \(C^o\).

figure a

The average running time for our CP model is around 2 seconds for 100-nodes problem instances. Hence, we provide the following model simplification procedure before running the CP model: (1) If a vehicle never visits any charging station outlet, we can remove the whole path of vehicle k from the model; (2) If there are fewer than \(C^o\) visits for \(o^{th}\) charging station, it is unnecessary to check the cumulative constraint (27) as the constraint is automatically satisfied; (3) Suppose a charging station has only been visited by the same vehicle k, then we can also remove the whole path of vehicle k since there is no dependency on other vehicles.

Unfortunately, it is still quite time-consuming to apply CP to compute the exact waiting time in every iteration, hence, we only trigger CP under two cases: (1) when we manage to find a solution that satisfies vehicle capacity and time window constraints; and (2) after every p (a parameter that we set default value to 20) iterations. In other cases, we apply a heuristic to estimate the waiting times. The basic idea of this heuristic is to simulate a virtual booking system that will compute an approximated waiting time and station capacity violation whenever a vehicle visits a charging station as follows.

Heuristic for Charging Station Waiting Time Calculation. Let us define a charging station visit as a special task. Since waiting time is a global variable that depends on the arrival times at all charging station visited by all vehicles, we are not able to compute the exact waiting time by simply considering each trip independently. Therefore, for a given charging task i in the solution, we apply Algorithm 1 to estimate the waiting time. Let \(\tau _i\) be the earliest service start time for charging task i, and \(\lambda _i\) be the charge time at charge station m.

  • Case 1: charging station m has an available (i.e. unoccupied) time interval at \([\tau _i,\tau _i+\lambda _i]\).

    This is very straightforward - we assign \([\tau _i, \tau _i+\lambda _i]\) to charging task i (shown in lines 1–5 in Algorithm 1).

  • Case 2: charging station m has an available time interval with length at least \(\lambda _i\) but later than \(\tau _i\). Let \(\varvec{\varTheta }\) be the set of booked charging outlets intersect with time \(\tau _i\), and \(\tau _i'\) denote the earliest completion time of charging tasks in \(\varvec{\varTheta }\). We assign \([\tau _i', \tau _i'+\lambda _i]\) to charging task i (shown in lines 6–8).

  • Case 3: there is no available time interval that can fit charging task i. We assign task i after time \(\tau _i\) (line 11). Note that by doing so, the booked charging outlets time interval will be overlapping (i.e. the solution is infeasible). Therefore, penalties need to be imposed (line 12).

Overall, the total waiting time w(s) is evaluated by sum of all tasks \(\varpi _{i}\) and \(\overline{v_i}\).

4.2 Selection and Crossover

The top K elite individuals are kept for the next generation based on their fitness. All the individuals will participate to produce new individuals generated by applying the crossover operator. Noted that the crossover rate is 100%, as we will apply our local search operator in Sect. 4.4, which is more powerful than general mutation operator in the GA. The pair of parents for crossover are chosen using tournament selection method. This means, we randomly sample two individuals from the individuals. The partially matched crossover operator is used to create two new individuals to replace the parents. For given parents \(P_1\) and \(P_2\), two cutting points are chosen. With the middle sub-path kept intact, we swap the arc and nodes between two parents. Figure 2 shows an example. The top two rows represent parents individuals, and bottom two rows stand for the children individuals. The crossover operation results in the creation of new children. All the customers must be served in our problem instance, hence if left arcs or nodes cannot be inserted to the child because of vehicle load or vehicle available time infeasibility, we add empty vehicles and insert the leftover arcs/nodes to the empty vehicles. The two new individuals along with the current population form the new population for the next generation of GA. We terminate GA when there is no improvement in the best solution for a fixed number of generations or the number of iterations reaches the upper limit.

Fig. 2.
figure 2

Crossover operator

Full size image

4.3 Columns Based Chromosome Generation

In every 1000 iterations of GA generations, we generate new chromosomes by recording the last 1000 iterations of feasible vehicle paths in the population as columns. We find the best combination of those columns, generate new chromosomes and add them to the population. Let R be the set of all columns, V be the set of customers included in the columns, and P stands for presetting price of a customer. Parameters include \(c_r\) and \(a_{r}^{i}\), where \(c_r\) equals to the travel time of column and r, \(a_{r}^{i}\) is a parameter that equals 0 or 1, where 1 indicates node i is served by column r. Binary decision variables include \(y_i\) and \(z_r\), \(y_i\) which equals to 1 if customer i is selected. Similarly, \(z_r\) equals to 1 if column (trip) r is selected. We aim to generate better solutions from a population of historical solutions, with the Set Covering formulation shown as follows:

$$\begin{aligned} \max \sum \limits _{i\in V}P y_i-\sum \limits _{r\in R}c_r z_r \end{aligned}$$
(28)

Subject to:

$$\begin{aligned} \sum _{r\in R}a_{r}^{i}z_r= & {} y_i,~~\forall ~i\in V \end{aligned}$$
(29)

We assume serving a customer leads to revenue P, hence the objective function (28) maximize the revenue minus the total travel time. We use \(y_i\) to check customer i be served or not in Constraints (29). If not all the customers can be served, we will insert the leftover customers to the solution one by one to the position with the smallest insertion cost added.

4.4 Local Search on Solutions

Once a new chromosome been generated, we improve the solution by local search. Customer nodes are selected and added to a perturbation set. To select the customer nodes, we use an objective value based operator. By checking the vehicle routes, we calculate the objective value after removing one customer node, then, descending sort the values, we choose the top 10% customer nodes and added to the perturbation set.

After the customer nodes selection, three perturbation operators (I1-I3) are used. The probability of using first operator is set to 0.5 while the probability of using second and third operators is set to 0.25. We accept the new solution if the fitness value is better after applying local search.

  • 1-by-1 (I1): The selected customer nodes are sequentially removed one by one and reinserted into the best position (the highest improvement for the current objective value).

  • 1-by-1 different vehicle (I2): Suppose, customer node i is removed from some route k, this operator tries to insert the customer node i into different route (which is not k) in a better position.

  • 1-by-1 same vehicle (I3): Suppose, customer node i is removed from some route k, this operator tries to insert the node i into the same route k again but in a better position.

4.5 Management of Charging Station Visits

If no feasible solution can be obtained because of the violation of battery limit constraint, we add charging station outlet visits (described in Algorithm 2) to fix the infeasibility. Basically, we include charging station visits if only the vehicles cannot reach to the customer nodes \(\rho _i\) with the available charge in their batteries. The position to insert the charging station visit can be any location before \(\rho _i\), hence, we find the best position to insert the closest charging station (line 4–9 of Algorithm 2). In case, a charging station cannot be inserted (due to long distance) then we split the visits to customers to two or more vehicles.

During the GA iterations, once a charging station has been removed, we reinsert it only if the same would lead to a better fitness value. Besides that, every 20 iterations, we double check the current iteration solution, and remove useless charging stations and insert new charging station. Once a new best solution or new best feasible solution has been found, the charging station visit gets updated as well.

figure b

5 Numerical Experiments

To evaluate our approach, we performed numerical experiments using two sets of problem instances on an Intel Xeon E5-2667v4 8C/16T (3.2 GHz) 16 core CPU 32 GB RAM machine. We used a batch file to utilize all the 16 cores while running the numerical experiments wherein each instance used one single core. The first set is the self-generated small instances (having 5 and 10 number of customers), aimed to compare the solutions between the heuristic approach and math model (using CPLEX solver version 12.8.0) along with the verification of the solution details such as travel time, waiting time and charging time. The second set is based on instances provided by Schneider et al. [1] that are adapted from Solomon [10] instances to include charging stations. These instances are provided in three different categories with 100 customer nodes. With our specific problem setup that focuses on limited charging capacity at the charging stations, we realized that generating instances suitable this problem is in itself a complex problem. As the literature do not provide Solomon instances with more than 100 customer nodes, we only focus on the variety of 100 nodes instances for our experimentation. According to our problem definition, we ignore the customer time windows available in the Solomon instances. All test instances can be found at https://unicen.smu.edu.sg/research/urban-logistics/electric-vehicles-routing-problem-waiting-times-charging-stations.

Fig. 3.
figure 3

GA converge curve

Full size image
Table 3. Cplex and GA heuristic based solution on 5 and 10 nodes instances
Full size table

For the first set of instances, the battery capacity was fixed at 30, charging station outlet capacity equals to 1, and the vehicle capacity was set to 100. The service time at all the customer nodes was set to 10 time units. The second set of instances used the parameters as defined in the type “C”, “R” and “RC” of Solomon instances. The vehicle battery capacity was set to 62.14 or 79.69, number of charging station locations was set to a random number between 5–18, charging station outlet capacity equals to 1, the location is randomly chosen within the spatial distribution, and charging rate was set to full charge battery divided by average customer service time. For GA, we use the following parameter values: initial population size \(\Lambda = 100\), number of top elite individual \(K =20\), number of iterations was set to 5000, penalty parameter equals to 20 for waiting time approximation, and customer price in column based operator was set to twice of average travel time between nodes. All the experiments were performed for 10 times and the best result from the multiple runs are reported. Before discussing the results, we depict the evolution of GA in Fig. 3 for one typical instance. As can be seen, the fitness value decreases in the number of generations, and improves from 5979 to 2218 in about 3000 generations and stop improving afterwards.

Table 4. Results of GA based heuristics solution on the 100-node Solomon instances.
Full size table

5.1 Results

Table 3 compares the results from the exact math model solved using Cplex and the GA based heuristics for the first set of small instances. The table shows the fitness value which is the sum of route durations, travel time (TT), service time (ST), the combined waiting and charging time (WCT), and the running time in seconds for all different instances. As can be observed the gap between the travel time for Cplex and GA is quite comparable for the instances with 5 customer nodes. A similar trend can be noted for the waiting and charging time. However, for instances with 10 customer nodes, GA based solutions seems to spend less time in travel as well as waiting and charging. The results shows that considering waiting time at the charging stations while planning the routes for EV based fleet is crucial as the amount of time spend in waiting and charging is almost equal to the travel time.

One can see, for the 5 customer node instances, Cplex can solve it quickly, while for the instances with 10 customer nodes, we have to stop Cplex after 3 hrs (10800 secs) and get the best solution discovered so far. In comparison to the best solution found by Cplex, the GA heuristics fairs well with very less execution time. For problem instances with 5 customer nodes, there are very low gap between the solutions while in case of instances with 10 customer nodes, GA always finds a better quality solution in very less time as compared to the Cplex.

Table 4 lists the best and average results for the set of Solomon instances using the GA based heuristics approach. The best objective value (from 10 runs) is the sum of the route durations of all the vehicles after they return to the depot. On average, the CPU time equals to 10 min overall instances. Since our objective value involve charging and waiting times at the charging stations, the same is not directly comparable with the literature [10]. We observed that the “R" group Solomon instances have longest travel time, while “C" and “RC" group instances have similar travel times. This happens as the distribution of “R" group Solomon instances are more disperse than other two groups. Further, the waiting times of “C" group instances are much longer than other two groups, mainly because of the difference in the rate of charging.

6 Conclusions

The advancement of electric vehicles technology has paved the way forward for EV based logistic fleets for customer delivery. However, the route planning with EVs brings forward new challenges to the already complex problem of vehicle routing. In this paper, we consider the problem of formation of vehicle queues at the charging stations en-route to customers. We consider the extra waiting time due to the queue at the charging stations to formulate an exact mathematical model for route planning of EV based logistics fleet. The evaluations are performed on a set of problem instances catering to specific requirement of our problem setup. Although it is difficult to get a solution from the exact mathematical model beyond 10 customer nodes, the GA heuristic based solution has shown comparable performance and can be quickly executed for large size instances. In the future, we plan to extend our work by adding more practical constraints in our model such as customer time-windows, partial charging of vehicle at the charging stations, etc. Further, using the current results as benchmark, more comparative evaluations with variety of instances can be carried out in order to validate the scalability and efficiency of our GA based heuristics approach.