Introduction

Global warming has become a serious threat to the humans and nature. After adopting the so-called Paris Accordance by the United Nations Framework Convention on Climate Change in 2015, global efforts toward rapid reduction of CO2 emissions have been accelerated. Fossil energy is the largest source of CO2 emission in the world. Introduction of green transportation (e.g., hybrid and electric vehicles or EVs) represents an excellent example of the efforts toward using non-fossil fuels. Nevertheless, green transportation suffers from difficulties in scheduling and routing for complicated product distribution systems. Product distribution scheme has long been a challenging issue. In the past, shipping (consider a letter, for example) was aimed at nothing but to deliver an envelope/parcel from the sender to the receiver at the destination — a presumption that ruled out the necessity of accurate scheduling. Today, however, product delivery has become crucially important because of various factors including air pollution, urban traffic, and possible savings in terms of time and money. Meanwhile, the demand time is almost known for particular products such as diaries for which customers demand on a relatively regular basis. Accordingly, shipping to this group of customers must be scheduled in such a way that shipping method is well determined for different periods. Considering such situations in the field of operational research following the general view to the product distribution, they usually represent periodic vehicle routing problems (PVRP). This means that the customers are not visited on a daily basis but rather on a periodic basis to satisfy their demand timely. Periodic decision-making imposes a substantial impact on the decisions adopted in various days. The fact that not every customer needs a delivery (product shipping) makes this problem a bit more complicated than the conventional vehicle routing problem. The reason of this increased complexity is that a conventional vehicle routing problem tries to address the routing for a particular day, while a periodic routing problem begins with assigning different customers to the corresponding visit days and then T vehicle routing problem is developed that must be solved. Therefore, green vehicle routing and scheduling are complex tasks in product distribution systems (Revesz et al. 2014).

With the development of new technologies, various energies have been invented to power vehicles. Critical decrease in the availability of fossil fuel supplies, high cost of such fuels, and significance of environmental issues and air pollution have led to extensive development and rapid growth of electrical vehicles (EVs). A routing problem in which environmental concerns are further taken into consideration is referred to as a green vehicle routing problem. In this respect, the present research can be categorized in the field of green routing as it focuses on the EVs to lower environmental pollution.

Numerous research works have been reported on periodic routing for vehicles, but only a few of them have specifically focused on EVs. The fact that we further consider the delivery due date can add to the novelty and attractiveness of the present research to practitioners. Considering various factors related to EVs in the modeling for periodic vehicle routing, the present work represents an attempt to not only fill in the research gap but also get the problem closer to reality to improve its practical applicability. Dominik and Schneider (2015) presented an EV routing problem considering delivery time windows and a mixed transportation fleet including commercial EVs and conventional vehicles. In this model, the researchers assumed that the fuel consumption is a linear function of traveled distance, with equations of fuel consumption, velocity, slope, and parcel weight applied as constraints. They employed neighborhood search (NS) algorithm to solve the developed problem. In another piece of research, Keskin and Catay (2016) relaxed the full charging constraint to let the EV to be partially recharged — a relaxation that pushed the problem closer to reality while reducing the recharging time. They then presented an integer programming model and utilized adaptive neighborhood search (ANS) to have it solved. Their modeling outcomes indicated that partial recharging can improve the routing decisions and that the proposed methodology could outperform similar methods in converging to high-quality solutions. Raeesi and Zografos (2020) presented a capacity-constrained EV routing problem where the EVs could be recharged by mobile charger vehicles. They used a large neighborhood search (LNS) algorithm for solving the problem. Based on the results, they further investigated differences between the proposed model and one where recharging was done at charge stations.

In a PVRP, the aim is to design routes for a vehicle for some particular period. The PVRP was first introduced by Beltrami and Bodin (1974) for addressing the assignment of municipal waste compactor trucks in New York. Francis and Smilowitz (2006) considered a PVRP into which service selection was further taken into account. The objective was to find a tour for each vehicle along the time horizon, where traveled distance minus service profit was taken as the objective function, and vehicle capacity and minimum visiting frequency were seen as constraints. In this problem, a required visiting frequency was defined for each customer and a constraint was declared by which the visiting frequency to each customer was surely higher than that minimum required visiting frequency. Finally, they used an exact method based on the lower bound and Lagrangian method for solving small- and medium-scale problems and presented a heuristic method for addressing large-scale problems. Baldacci et al. (2011) formulated an exact method for solving PVRP. In this respect, they presented an integer programming model and then solved it using the exact solution method presented by Baldacci and Boschetti (2007) to come up with the lower bound to the problem. This methodology includes the calculation of a near-optimal dual solution that is obtained by relaxing inequality constraints. They then utilized the dual solution to generate a reduced integer problem including the exact solutions. Finally, the reduced problem was solved using an integer programming solver.

Optimization models can represent a physically existing phenomenon and, with the help of rational mathematical relationships, produce the best possible mix of multiple variables for the sake of a particular objective, such as minimization of routing costs for EVs during a particular period of time. Nevertheless, unique features of optimization models have made them widely popular for routing problems. Noteworthily, an optimization model may not necessarily lead to actual optimality due to the special assumptions made to the problem complexity and/or assumptions made to build/run the model. Should the problem at hand is so large, evolutionary algorithms can be devised to avoid local optima and rather converge to universal optimum point. The evolutionary algorithms can identify the universal optimum point and have demonstrated promising potentials for solving real-world problems (Heidari et al. 2019). So far, various researchers have proposed numerous algorithms for solving optimization problems in the field of conjunctive utilization, of which one may refer to simulated annealing (SA) as an example. High efficiency of this algorithm for solving a wide spectrum of different optimization problems has convinced researchers toward using it for different applications. Accordingly, the present research, we use SA for minimizing the sum of distance traveled and recharging cost.

Table 1 summarizes the literature on the use of EVs. An overview of the relevant research shows that majority of previous researchers have sought to minimize distance traveled as well as the costs of recharging and energy as objective function. In late 2019, researchers started to consider simultaneous impacts of C (capacity of vehicle), TW (time window), MIX (mix fleet), LRP (location routing problem), F (fixed charging time), L (linear charging time), NL (non-linear charging time), and PR (partial charging). Only few studies have been published during the indicated period, where researchers have merely considered linear charging (L) (Poonthalir and Nadarajan 2018; Wang et al. 2018). Hiermann et al. (2019) introduced a special VRP by combining conventional vehicles with EVs. EVs can avoid charging stations by using fossil fuels. This flexibility, however, leads to different decisions as one should identify the amounts of fossil fuel and electrical energy consumed by a hybrid vehicle as it goes through a particular route, and whether it needs to recharge its electrical batteries or not. In order to solve the problem, the authors designed a metaheuristic algorithm that was indeed a combination of genetic algorithm (GA) with LNS.

Table 1 A summary of literature review on EVs
Full size table

Contribution of this work

Based on the literature review and Table 1, we found that PVRP considering delivery due and mixed charging rates is yet to be comprehensively studied. The novelty of this work comes in the face of presenting a mathematical model where customers’ orders are due for delivery at a programing horizon, given that some customers must receive their orders prior to the delivery due date, while some others can wait until the end of the programing period. On the other hand, utilization of EV fleet in logistics has been increasingly regarded in recent research works, motivating us toward opting for an EV fleet for distributing the orders in multiple periods in this work. We herein attempt to fill in this research gap by presenting a mathematical model and solving it by a metaheuristic algorithm. The developed optimization model is then solved by a robust SA algorithm, with the results compared to those of a non-linear optimization algorithm implemented in GAMS software.

Materials and methods

Research workflow

Given that the present research is aimed at minimizing the sum of traveled distance and recharging costs during each period, the framework shown in Fig. 1 was followed to solve the relevant optimization problem. This was started by identifying the type of optimization problem and its assumptions. The assumptions and constraints of the problem, including the number of stations, maximum number of vehicles, continuity of the path, demand, and vehicle capacity, along with the mathematical model of the problem were designed appropriately. Some 30 sample problems with different numbers of customers, vehicles, and charging stations were considered for different periods to evaluate the developed model. Each sample problem was launched independently of the others. The mathematical model was first implemented and run in GAMS, before having it solved by the SA algorithm. The results of the two algorithms on the 30 sample problems were compared to introduce the best algorithm for this problem. In the following, we begin by introducing the mathematical model and applied constraints and then continue to explain the SA algorithm and its structure. Details of the framework are illustrated in Fig. 1.

Fig. 1
figure 1

Research framework

Full size image

Mathematical modeling

To more understanding of the proposed model for this research, we have developed an illustration model in which it describes the components of the problem and is shown in Fig. 2. In this illustration, there are two vehicles. The first vehicle starts its movement from the warehouse, and then customer visits customer C1, in addition to visiting customer C2 in this place performs recharge operations, and then goes to customer C5 and finally returns to the warehouse. However, the second vehicle performs recharge operations at F1 charging station.

Fig. 2
figure 2

Illustration of the proposed electric vehicle routing problem

Full size image

Our main goal is to provide a mathematical model of periodic routing of electric vehicles with due date, in which customers are divided into two categories of customers with due date and without due date (optional).

In this section, the assumptions of the model of this research are explained.

Assumptions:

  1. 1.

    The inputs of the problem are definitive and fixed.

  2. 2.

    Customers with a due date should be visited prematurely, but customers without due date could be visited in any period of planning horizon.

  3. 3.

    The amount of used charge is dependent on mileage.

  4. 4.

    The amount of recharge at the charging station is complete, and in the customers location, it could be partial.

Notations:

V :

set of nodes

ν′:

set of customers v′ ⊆ V

C :

set of customers without due date C ⊆ v′

V f :

set of charge stations Vf ⊆ V

H :

set of time periods

d ij :

traveling distance from node i to j

CAP :

vehicle capacity

Q :

battery capacity of the electric vehicle

h :

energy consumption rate of the electric vehicle per unit of distance

r i :

time of ready to deliver for customer i’s order

dl i :

due date delivery of customer i’s order

q i :

demand of customer i

p i :

cost of each recharge unit at node i

a :

cost coefficient per unit distance

m :

number of available vehicles

Decision variables:

\({x}_{ij}^t\) :

binary variable and equal to 1, if the electric vehicle travels from node i to node j at period t, 0 otherwise

\({r}_i^t\) :

binary variable and equal to 1, if the electric vehicle is charged from node i to node j at period t, 0 otherwise

\({l}_{ji}^t\) :

total shipped demand on path ij at period t

\({y}_i^t\) :

level of vehicle charge while reaching to node i at period t

\({w}_i^t\) :

amount of charge taken by vehicle at node i at period t

\({u}_i^t\) :

empty battery capacity of vehicle at node i at period t

Objective function

In this work, the objective function is to minimize the sum of traveled distance and cost of recharging the EVs during a particular period of time. In this regard, the first term in Eq. (1) refers to the traveled distance, while the second term denotes total recharging cost.

In fact, Eq. (1) is the objective function of the model. The objective function is included in two parts. The first part seeks to minimize total traveled distance. In addition, the second part aims to minimize total recharging cost, during each period.

$$Min z=\sum\nolimits_{i,j\in V}\sum\nolimits_{t\in H}{a.d}_{ij}.{x}_{ij}^{t}+\sum\nolimits_{i\in V}\sum\nolimits_{t\in H}{p}_{i}.{w}_{i}^{t}$$
(1)

Constraints

Various constraints were applied to solve the optimization model, as expressed in the following. Equation (2) ensures that customers with a due date are visited in the period from the end of lead time to the delivery due date. Equation (3) guarantees that the customers with no due must be visited during any of the periods. Equation 4 sets an upper bound of 1 to the times a charging station can be visited. In other words, this constraint ensures that a charging station is visited only if the vehicle needs a recharge. The fifth constraint (Eq. (5)) refers to the path continuity, according to which there exists at least one output path from each node for each input path to that node. Equation (6) guarantees that the number of utilized EVs per period will not exceed the available number of vehicles. Equations 7 and 8 evaluate the demand carried along each path during each period. These constraints eliminate the chances of sub-tours to develop. The 9th constraint (Eq. (9)) ensures that the demand carried along each path does not exceed the vehicle capacity. Equation (10) expresses that the vehicle’s battery is fully charged when the EV leaves the warehouse, while Eq. (11) evaluates the battery level at the destination based on the charge level at a previous check point. According to Eq. (12), if a recharging process is performed at a charging station in a particular period, the battery level reaches 100%. Equation (13) sets that recharging at customer location increases the battery level to at most the battery capacity (allowing partial recharging at customer location). Based on Eq. (14), the charging of the battery at customer location cannot increase the battery level beyond the battery capacity. Finally, Eq. (15) ensures that the battery level is at some feasible level (> 0) when a customer is visited. Equations (16) through (18) express the types and ranges of the decision variables.

$$\begin{array}{cc}\sum_{j\in\nu}\sum\nolimits_{t\in\left[r_i{,dl}_i\right]}x_{ij}^t=1&\;i\in\nu^{'}\backslash C\end{array}$$
(2)
$$\begin{array}{cc}\sum\nolimits_{j\in\nu}\sum\nolimits_{t\in H}x_{ij}^t=1&i\in C\end{array}$$
(3)
$$\begin{array}{cc}\sum\nolimits_{j\in\nu}\sum\nolimits_{t\in H}x_{ij}^t\leq1&i\in V_f\end{array}$$
(4)
$$\begin{array}{cc}\sum\nolimits_{j\in\nu}x_{ij}^t=\sum\nolimits_{j\in\nu}x_{ji}^t&i\in\nu,\;t\in H\end{array}$$
(5)
$$\begin{array}{cc}\sum_{j\in\nu}x_{0j}^t\leq m&t\;\in\;H\end{array}$$
(6)
$$\begin{array}{cc}\sum\nolimits_{j\in\nu}l_{ji}^t-\sum\nolimits_{j\in\nu}l_{ij}^t=q_i\sum\nolimits_{j\in\nu}x_{ij}^t&i\in\nu\cup V_f^{'},\;t\in H\end{array}$$
(7)
$$\begin{array}{cc}\sum\nolimits_{j\in\nu}l_{0j}^t-\sum\nolimits_{j\in\nu}l_{j0}^t=\sum\nolimits_{j\in\nu}q_ix_{ij}^t&i\in\nu\cup V_f^{'},\;t\in H\end{array}$$
(8)
$$\begin{array}{cc}l_{ij}^t\leq CAP.x_{ij}^t&i,\;j\in A,\;t\in H\end{array}$$
(9)
$$\begin{array}{cc}y_0^t=Q&t\in H\end{array}$$
(10)
$$\begin{array}{cc}y_j^t+h.d_{ij}.x_{ij}^t\leq y_i^t+w_i^t+Q\left(1-x_{ij}^t\right)&i,\;j\in V,\;t\in H\end{array}$$
(11)
$$\begin{array}{cc}w_i^t+y_i^t=Q.r_i^t&i\in V_f,\;t\in H\end{array}$$
(12)
$$\begin{array}{cc}w_i^t+u_i^t+y_i^t=Q&i\in v^{'},\;t\in H\end{array}$$
(13)
$$\begin{array}{cc}w_i^t\leq Q.r_i^t&i\in v^{'},\;t\in H\end{array}$$
(14)
$$\begin{array}{cc}u_i^t\leq Q.(1-r_i^t)&i\in v^{'},\;t\in H\end{array}$$
(15)
$$\begin{array}{cc}x_{ij}^t\in\left\{0,1\right\}&i,\;j\in V,\;t\in H\end{array}$$
(16)
$$\begin{array}{cc}r_i^t\in\left\{0,1\right\}&i\in V,\;t\in H\end{array}$$
(17)
$$\begin{array}{cc}l_{ji}^t,w_i^t,u_i^t,y_i^t\geq0&i,\;j\in V,\;t\in H\end{array}$$
(18)

where \({x}_{ij}^{t}\) is 1 if the vehicle travels from the point \(i\) to the point \(j\) in the time period \(t\), and 0 otherwise; \({l}_{ji}^{t}\) is total demand traveled along the path \(ij\) in the period \(t\); \({y}_{i}^{t}\) is the battery level of the EV when it reaches the node \(i\) in the period \(t\); \({w}_{i}^{t}\) is the charge loaded into the EV battery at the node \(i\) in the period \(t\); \({u}_{i}^{t}\) is the discharged capacity of the EV battery when it reaches the node \(i\) in the period \(t\); and \({r}_{i}^{t}\) is a binary variable which takes a value of 1 if the EV is charged at the node \(i\) in the period \(t\) and 0 otherwise.

SA algorithm

Simulated annealing (SA) algorithm has been inspired by the annealing process in the metallurgy. It was first introduced by Kirkpatrick et al. in 1983. The SA algorithm emulates the process of material cooling gradually down to a temperature where the material takes a stable solid form. This algorithm converges toward optimal solution in a stepwise fashion by iteratively generating new solutions and having them evaluated. For this purpose, a new neighborhood is randomly generated and evaluated at each iteration. In this method, the points near a considered point in the search space are investigated. Accordingly, if a point was found to be superior (i.e., returns a lower value of the cost function) to the considered point, it replaces it and serves as the new selected point in the search space, and if it is rather worse than the considered point (i.e., returns a higher value of the cost function), it has still chances of being selected according to a probability function. To put it simply, in order to optimize the cost function, search is monotonously led toward lower values of the cost function, although there are still chances that an increase in the cost function occurs. The acceptance of the next point is usually based on a criterion called metropolis criterion (Eq. (19)).

$$P\left\{accept\right\}=\left\{\begin{array}{lc}1&\Delta f<0\\e^{-\frac{\Delta f}c}&\Delta f\geq0\end{array}\right.$$
(19)

where P is the probability of acceptance for the proceeding point; c is a control parameter; and \(\Delta f\) denotes the change in cost.

The control parameter in SA resembles the temperature in physical phenomena. Initially, the particle (i.e., the current point in the search space) is fixed at its place by a huge level of energy (i.e., a high value of control parameter, c). This high level of energy allows the particle to avoid from a local minimum, and as the search process continues, the particle has its energy level reduced (i.e., c decreases) to an eventual point where the search leads to universal minimum. It must be noted that the chances of avoiding the local minimum decreases at lower temperatures, implying that the higher the initial level of energy, the higher the probability of ending up at a local minimum.

The SA optimization starts with a randomly generated initial solution for the decision variables and produces, again on random basis, a new solution near the initial solution using an appropriate neighborhood structure. Accordingly, an important issue in SA is the procedure for generating the neighborhood. The following three elements are required for implementing the SA algorithm (Fig. 3):

  1. 1.

    Starting point: a point in the search space from where the search process is initiated. This point is usually set on a random basis.

  2. 2.

    Motion generator: this generator is responsible for generating the next state. Accordingly, by calculating the costs at the current point and the next point, it determines the way algorithm moves toward the final solution.

  3. 3.

    A plan for annealing the parameters that determine the annealing scheme of the algorithm. This plan defines the initial and final temperatures and the rate at which the temperature decreases.

Fig. 3
figure 3

Flowchart of SA algorithm (Rajan 2010)

Full size image

Different stages of this algorithm are shown in Fig. 3.

Steps demonstrated in Fig. 3 can be explained as follows:

  1. 1.

    Generate an initial candidate solution on a random basis and evaluate the cost function, Z, for the initial candidate solution.

  2. 2.

    Randomly generate a new solution in the neighborhood of the current candidate solution and evaluate the cost function for this new solution.

  3. 3.

    Accept the new solution, if it returns a better value of the cost function.

  4. 4.

    Conditional acceptance (if the new solution is not any better than).

  5. 5.

    Update the best solution found.

  6. 6.

    Decrease the temperature and go to step 2, if needed (i.e., the stop criteria are not satisfied).

Before a problem can be solved by the SA algorithm, one should design a solution vector for the problem. For this purpose, a T × I matrix was designed where T is the number of programing horizons, and I is the number of customers. All elements of this matrix were 0 s and 1 s, with the 1 s indicating the period in which the customer i is visited (Table 1). For instance, consider 5 customers that must be visited in 3 periods. Accordingly, a random candidate solution for visiting the customers in different periods can be of the following form:

The matrix presented in Table 2 implies that the customers \({i}_{1}\) through \({i}_{5}\) are visited in periods 1, 3, 2, 2, and 3, respectively. When establishing this matrix, one should take care to assign 1 to the customers with delivery dues for the lead and delivery periods.

Table 2 Vector of customer visiting in different periods
Full size table

Following with the algorithm, one should identify a route for each vehicle and the customers at which place the recharging shall be done (Table 3). In order to assign the vehicles to different nodes and prioritize the visits and recharging cycles, a three-row matrix was used, where the first row defines the vehicle number to visit the considered node, the second row gives the visiting priority of the node, and the third row indicates whether the vehicle is to be recharged (1) or not (0) at that node. The visiting priority is a number in the range of [0, 1] whose lower value implies that the corresponding customer will be visited sooner. For example, considering 2 vehicles and customers (obtained from the previous matrix) that must be visited in the second period, Table 2 gives a random vector of customer assignment and visiting priority.

Table 3 Customer assignment and prioritization in period t2
Full size table

Solution method and results

Taguchi’s method

Taguchi’s method is one of the most popular statistical methods in the field of design of experiments (DoE) for performing sensitivity analysis on the outputs of a process. It helps optimize different parameters of a process to achieve the best possible output by performing only a fraction of all the experiments that were otherwise required to identify the optimal levels of all parameters. In this method, once finished with defining different levels for each of the parameters affecting the experiment outputs, several DoEs are proposed to the researcher, of which the researcher can opt for one depending on the selected levels and type of experiment. After performing the selected set of experiments, the results are returned back to the Taguchi’s method for analysis. The results of this analysis then led us toward understanding the effect of each factor on the dependent variable. This method compiles repeated data from the experiments into an indicator called signal-to-noise ratio (SNR). An objective of the Taguchi’s method is to maximize this SNR. Table 4 presents the levels considered for different parameters of the SA algorithm, where low, fair, and high levels are defined for each parameter. Table 5 gives a list of the experiments performed to find optimum values of different parameters. These include a total of 9 experiments. According to the table, the cost function returned the minimum value (6583.99) at the third iteration with T0 = 3 and α = 3.

Table 4 Levels of different parameters of the SA algorithm
Full size table
Table 5 Designed experiments for SA algorithm
Full size table

Parameter tuning was performed in Minitab software. Figure 4A shows that data repeating frequency was maximal in the second stage, while Fig. 4B demonstrates that the frequency is minimal in the same stage. This indicates that, among the three ranges of number of iterations, the best results were anticipated with 2000 iterations. In a similar way, optimal values of T0 and α can be found considering Fig. 4A and B, as reported in Table 5.

Fig. 4
figure 4

Results of Taguchi’s method for optimizing the parameters of SA algorithm: (A) SNR plot of SA algorithm and (B) means of means diagram

Full size image

Table 6 reports the values considered for the parameters of SA algorithm in this study. According to this table, minimum and maximum numbers of iteration have been set to 1000 and 3000, respectively, with the values of T0 and α set to range in 50–100 and 0.8–0.9, respectively. Finally, optimum values of the three parameters are indicated in the same table.

Table 6 Levels of parameters of SA algorithm
Full size table

First of all, the presented mathematical model was validated. For this purpose, a sample problem was generated and solved in GAMS. This sample is presented in Table 7. In this stage, maximum processing time was limited to 2 h, meaning that the GAMS software was set to process the problem for no longer than 2 h. The SA algorithm was implemented and run in MATLAB R2017b. Table 8 indicates dimensions of the problem in this research. As is evident from Table 8, 30 sample problems with different counts of customers, periods, charging stations, and vehicles were considered. It is worth noting that the number of customers ranged from 5 (for problems 1 and 2) to 120 (for problems 29 and 30). That is, as the problem number increased, the problem complexity increased in terms of the number of customers and vehicles. The developed problems were solved by GAMS and the SA optimization algorithm, with their results analyzed and evaluated properly.

Table 7 Dimensions of the produced problems
Full size table
Table 8 Values of cost function and processing time for running the sample problems
Full size table

Table 3 reports the results of solving the 30 sample problems by the two models. Focusing on this table, it is evident that the GAMS could return the solution for problems 1 up to problem 14. That is, any further increase in the complexity of the problem made the GAMS fail to produce the solution within the defined maximum processing time. In initial sample problems, both models returned the same or closely similar values of cost function. However, with increasing the number of customers, vehicles and charging stations, superior power of SA algorithm over GAMS became clearly evident. For instance, processing time of the GAMS solver for problem 13 was as long as 6181 s while the same problem could be solved by SA algorithm within no longer than 151 s. This was while both methods returned very close cost function values. For small-scale problems, the processing time of the GAMS code was shorter than SA, but it took much longer as the problem complexity increased, so that the processing time went beyond our measurement window from problem 14 on. In general, it was observed that the SA algorithm gives the exact solution for small-scale problems, indicating the suitability of this algorithm for such problems, so that it can be used to solve the model presented in this research. On the other hand, it was evident that the processing time for the exact solution method increased exponentially with increasing the problem size, making it infeasible to apply for large-scale problems. This was while the processing time of the metaheuristic algorithm increased so slowly with increasing the problem size, indicating its suitability for solving large-scale problems.

Figure 5 shows the evolution of processing time with GAMS and SA. As mentioned earlier, with increasing the sample problem size, the processing time increased exponentially when GAMS software was employed, while it increased at a rather slow rate with SA. As is evident from the figure, focusing on problem 14, the two models returned processing times that differed by about 6270 s, highlighting the efficiency of the SA algorithm for large-scale problems. In addition, GAMS needed some 6500 s to solve problem 14, while SA algorithm could solve the same problem within about 200 s. Ultimately, SA algorithm needed only 750 s to solve problem 30, far better than the result of GAMS. All of these results indicated high efficiency of the SA algorithm for large-scale problems.

Fig. 5
figure 5

Processing time for running the optimization model on different sample problems: (A) GAMS, and (B) SA

Full size image

In Fig. 6, it is evident that the processing time grows exponentially with increasing the problem size, indicating NP-Hard nature of the problem considered in this research. Our results show that the SA algorithm can produce similar solutions to those of GAMS for small-scale problems. With increasing the number of customers and periods, however, the processing time of GAMS software increased so much that it failed to converge to solution following several hours. This was while the SA algorithm returned much better solutions for the same problem. Therefore, SA algorithm is recommended for cases with larger numbers of customers. Figure 5 demonstrates the changes in the value of cost function with the problem size. According to this figure, it is trivial that the cost function value increases gradually with the problem size when SA algorithm is the solution method of choice. This was while the GAMS model could provide solutions for problems 1 through 14, failing to address further problems due to extended processing time.

Fig. 6
figure 6

Values of cost function for SA and GAMS

Full size image

Lack of real data on the parameters of this research represents the main limitation suffered by this study. As of the present, utilization of EVs in the logistics systems and distribution networks is very limited. Indeed, today’s EVs are mostly developed for personal transportation applications, with the EV manufacturers largely ignoring the development of EVs for product distribution applications. In general, it can be stipulated that most of the research on EV routing has been merely academic. Due to lack of required infrastructures for EV transportation in Iran, it is almost impossible to find an Iranian company working on EVs for distribution and logistics purposes.

Conclusion and further research

In this research, a mathematical model and a metaheuristic algorithm based on simulated annealing (SA) were presented for a multi-period electric vehicle (EV)–routing problem. In order to evaluate the performance of the proposed SA algorithm, its results were further compared to those of GAMS optimization model on 30 different sample problems with the same cost function. Focusing on the electrical nature of the vehicles, we assumed that the EVs can be recharged at not only the charging stations but also customer nodes where charging facilities were available. Considering the periodic nature of the problem, we assumed two groups of customers, namely those with a delivery due date and those without one. Operationally speaking, the present research possesses different aspects for executives at distribution companies. Indeed, this model can be applied if customers’ demands and the corresponding delivery dues are known beforehand. Our results indicated the superior performance of SA algorithm compared to GAMS for complex problems. The results further showed that the SA can well solve the optimization problem within reasonably short processing times, as compared to GAMS, as the problem complexity increases. The results also showed that a requirement for achieving optimal solution is proper setting of the SA algorithm parameters. All in all, this model can serve as an appropriate decision-making model for managers in the distribution and logistics industry. There are some opportunities of future research based on the findings of this work for researchers. Further researches may be conducted by focusing on considering a time window for customers in the corresponding period, application of a charging function for forecasting the recharging time, considering the parameters with associated uncertainties, and utilization of other optimization algorithms, other metaheuristic methods and comparing and benchmarking the results.