1 Introduction

There has been a growing demand in the developed countries for reducing the adverse effects of transport activities on nature and human life, and liberating city centers from emissions. Governments have started encouraging the adoption of alternative fuel vehicles (AFVs) by offering new incentives (Wyman, 2018) or by restricting the sales of internal combustion engine vehicles (ICEVs) to eliminate them in the future (Edelstein, 2016; Khan, 2016). Consequently, the utilization of AFVs has become an emerging trend in the transport sector. The electric vehicles (EVs), in particular, have attracted great attention in logistics operations as they cut dependency on fossil fuels, hence lessen the air pollution. In addition to zero-emission and noise, the main operational and financial advantages of EVs over ICEVs are low electricity prices compared to fossil fuels, high efficiency of the electric motor and transmission system, regenerative breaking, and reduced maintenance costs (Wu et al., 2015). On the other hand, operating EVs in logistics poses several challenges such as limited battery capacity and short driving range, scarcity of recharging stations, and long recharging times (Keskin & Çatay, 2018). Because of these additional complexities, route planning of EVs has recently gained popularity in the vehicle routing problem (VRP) literature, coining the name the electric VRP (EVRP).

EVRP is an extension of VRP where an EV fleet is utilized instead of ICEV. Conrad and Figliozzi (2011) introduced an EVRP where the EVs are allowed to recharge their battery at selected customer locations during the delivery service. The recharge duration is assumed constant. Schneider et al. (2014) addressed EVRP with time window (EVRPTW) by relaxing this assumption but adopting a full-recharge strategy. The full-recharge assumption was later relaxed by Bruglieri et al. (2015) and Keskin and Çatay (2016) and partial recharges at any quantity were allowed, which constitutes the realistic and practical case.

In this paper, we address the load-dependent EVRPTW (LD-EVRPTW) with partial recharges by taking into consideration the energy consumption related to the weight of the cargo carried on the vehicle. LD-EVRPTW is expected to offer more realistic route plans as compared to other routing models for companies that carry heavy goods such as appliances, machinery, hardware, liquids (Zachariadis et al., 2015), which comprises the main motivation of our study. Similar to the literature on EVRPTW, we adopt a hierarchical objective function where the primary objective is to minimize the fleet size whereas the secondary objective is to minimize the total energy consumption. We model this problem using two different mathematical programming formulations, one is linear whereas the other is non-linear. Since the large-size problems are not tractable, we propose a large neighbourhood search (LNS)-based matheuristic approach to solve them effectively. Our LNS method benefits from an optimal repair procedure which employs a commercial solver to solve the non-linear model. Finally, we analyse the influence of the cargo load on the routing decisions through an extensive numerical study.

The contributions of this study can be summarized as follows:

  • We extend EVRPTW by considering the load weight which varies throughout the journey of the EV and introduce the LD-EVRPTW.

  • We present linear and non-linear mathematical programming formulations of the problem, and show that the non-linear model performs better in terms of solution quality and run time.

  • We develop an effective LNS-based matheuristic method to solve the LD-EVRPTW by adapting the destroy and repair operators from the literature and introducing new ones to tackle the more complex structure of the problem including an optimal repair mechanism.

  • We validate the performance of the proposed method using the benchmark instances and show that the route plans, hence the operational costs, may change substantially in the load-dependent case.

The remainder of the paper is organized as follows: Sect. 2 reviews the related literature. Section 3 introduces the problem, formulates two alternative mathematical programming models, and tests their effectiveness. Section 4 presents the proposed LNS-based matheuristic method. Section 5 describes the experimental study and discusses the results. Finally, concluding remarks are provided in Sect. 6.

2 Related literature

EVRP with time window (EVRPTW) was presented by Schneider et al. (2014) where a full-recharge strategy was adopted. The authors developed the mathematical programming formulation of the problem and proposed a hybrid variable neighbourhood search (VNS) and tabu search (TS) algorithm to solve it. Different variants of EVRP and EVRPTW were addressed in several studies including the cases of partial recharge (Bruglieri et al., 2015; Keskin & Çatay, 2016), mixed fleet (Sassi et al., 2015; Goeke & Schneider, 2015; Hiermann et al., 2016; Kopfer & Vornhusen, 2019; Hiermann et al., 2019), location routing (Li-Ying & Yuan-Bin, 2015; Paz et al., 2018; Schiffer & Walther, 2017; Yang & Sun, 2015), different type of chargers at the stations (Çatay & Keskin, 2017; Felipe et al., 2014; Keskin & Çatay, 2018; Li-Ying & Yuan-Bin, 2015; Sassi, et al., 2015), non-linear charging function (Froger et al., 2019; Montoya et al., 2017), battery swapping (Hof et al., 2017; Jie, et al., 2019; Liao et al., 2016; Masmoudi et al., 2018; Paz et al., 2018; Wang et al., 2018; Yang & Sun, 2015), wireless charging systems along the roads (Li et al., 2018), flexible time windows (Taş, 2020), two-echelons (Breunig et al., 2019; Jie et al., 2019) and pick-up and delivery problem (Grandinetti et al., 2016; Madankumar & Rajendran, 2018). Desaulniers et al. (2016) also studied EVRPTW and proposed a branch-price-and-cut algorithm to solve four different recharging strategies. Some recent studies have dealt with the availability of recharging stations and queueing for recharging service (Froger et al., 2017; Keskin et al., 2019; Kullman et al., 2019). A comprehensive review of the EV technology and survey of the EVRP variants may be found in Pelletier et al. (2016), Pelletier et al. (2017), and Erdelić and Carić (2019).

Apart from distance traveled by the vehicle, there are other factors that affect the energy consumption on the road, such as the weight of the vehicle, its speed, auxiliary equipment (internal factors) as well as road gradient and ambient temperature (external factors). These factors have been often neglected within the VRP literature either because they make the problem too complex to solve or the driving range is not an issue as the vehicles will easily refuel at a close-by gas station. To the best of our knowledge, Kara et al. (2007) is the first study that proposed a load-dependent cost function for the capacitated VRP (CVRP), which is calculated by multiplying the distance of the arc with the load of the vehicle when traversing it. Xiao et al. (2012) considered the effect of cargo load on the fuel consumption within the context of fuel consumption CVRP (FCVRP) and developed a simulated annealing (SA) algorithm with a hybrid exchange rule to solve the problem. Zachariadis et al. (2015) extended the load-dependent VRP (LDVRP) by considering simultaneous pick-ups and deliveries and proposed a local-search algorithm to solve it.

Fukasawa et al. (2016) proposed two mixed-integer linear programming formulations for the LDVRP and solved them using branch-and-cut and branch-cut-and-price algorithms. Corberán et al. (2018) considered the effect of load weight on the chinese postman problem (CPP). They introduced two formulations for the problem and solved large-size instances using iterated local search (ILS) and VNS algorithms. Liu and Jiang (2019) addressed the LDVRP with time windows (LDVRPTW) and proposed a constraint relaxation-based algorithm.

The internal and external factors may play a more important role in the operational efficiency of the EVs as they can increase their energy consumption considerably, causing frequent visits to recharging stations which are scarce. Several articles investigated the influence of ambient temperature (Liu et al., 2018; Neubauer & Wood, 2014; Yuksel & Michalek, 2015; Yuksel et al., 2016), driver behavior (Guo et al., 2020; Neubauer & Wood, 2014; Wu et al., 2015), terrain (Asamer et al., 2016), speed (Morlock et al., 2019) on the EV energy consumption. However, the effects of these factors on routing decisions have received little attention in the VRP literature. Among them, Rastani et al. (2019) investigated the influence of ambient temperature on the fleet composition and route plans in the EVRPTW. Goeke and Schneider (2015) considered a mixed fleet of EVs and ICEVs, and formulated a nonlinear mixed integer model using the energy consumption model of Demir et al. (2012) that incorporates speed, road gradient, and load. This model is based on an augmented set of recharging stations, and determining the numbers of dummy stations requires additional computational effort. The authors developed an ALNS approach and analyzed three cost functions under different scenarios to provide managerial insights using instances adapted from the pollution routing problem (PRP) dataset of Demir et al. (2012).

In Table 1, we summarize the relevant literature by classifying the studies with respect to the main features of the problems that they addressed and solution methodologies that they proposed. Column “Load” reports whether the load effect is considered in the corresponding study. “Energy Cost Function” and “Objective Function” columns show the nature of the energy consumption and objective functions. The numbers given under the Objective Function column are explained in Table 2. “Recharger Technology” denotes the charging infrastructure in the stations, which includes single, multiple, or wireless charging technology stations (WCS) as well as battery swapping stations (BSS). “Recharge Amount” column indicates whether the batteries are fully or partially recharged. The following column presents the solution methodology, where A- and EVO- VNS, HC, DP, WSM, and CG stand for adaptive- and evolutionary-VNS, heuristic concentration, dynamic programming, weighted sum method, and column generation, respectively. The studies that only presented the solutions from a mixed-integer programming solver are reported as MIP. Finally, the last two columns show whether time windows and station location decisions are considered in the corresponding problem.

Table 1 Overview of the related literature
Full size table
Table 2 Classification of the objective functions in Table 1
Full size table

3 Problem description and model formulation

We tackle EVRPTW where a homogeneous fleet of EVs serve a set of customers with known demands, time windows, and service times. As opposed to previous studies which assume that the energy on the battery is consumed proportional to the distance traveled, we consider the additional energy consumption associated with cargo weight. The partial recharge strategy is adopted where the duration of recharge depends on the amount of energy transferred. Since it is a common practice in the real world to operate within the first phase of recharging where the energy transferred is a linear function of the recharge duration in order to prolong the battery life (Pelletier et al., 2017), we assume a linear charging function. Furthermore, we assume that the EV can be recharged at most once between two consecutive customers, which is the practical case in most last-mile operations. Without loss of generality, we consider a pick-up problem where the load of the EV increases during the journey as it visits the customers. Since EVs can be recharged overnight, they depart from the depot with full battery.

3.1 Energy consumption model

The energy consumption of an EV on the road depends on different factors such as its shape, mass, road gradient, acceleration, etc. The power demand of a vehicle can be obtained by using tractive power requirements placed on the vehicle at the wheels as follows (Demir et al., 2012):

$$ F = Ma + Mgsin\theta + 0.5C_{d} \rho Av^{2} + MgC_{r} cos\theta $$
(1)
$$ P_{tract} \left( {kW} \right) = Fv/1000 $$
(2)

Equation (1) calculates the tractive effort \(F\) where \(M\) is the total weight of the vehicle, including its curb weight and the cargo weight \(\left( {kg} \right)\), \(a\) is the acceleration \(\left( {m/sec^{2} } \right)\), \(g\) is the gravitational constant, \(\theta\) is road gradient, \(C_{d}\) is the coefficient of aerodynamic drag, \(\rho\) is the air density in \(\left( {kg/m^{3} } \right)\), \(A\) is the frontal area, \(v\) is the speed \(\left( {m/s} \right)\), and \(C_{r}\) is the coefficient of rolling resistance. The tractive power requirement can be converted to second-by-second battery power output \(\left( {kW} \right)\) as follows:

$$ P = P_{tract} /\mu_{tf} + { }P_{acc} $$
(3)

where \(\mu_{tf}\) is the vehicle’s drive train efficiency that includes the energy losses between electric motor and battery as well as the energy losses in transforming energy to the wheels. \(P_{acc}\) shows the power demand associated with the auxiliary equipment such as air conditioning, audio system, cabin lights, which are neglected in this study. Then, the energy consumption in \(\left( {kWh/km} \right)\) can be calculated as follows:

$$ E = P/v $$
(4)

To demonstrate how cargo load may affect the routing decisions we present an illustrative example in Fig. 1. Our example consists of a network that includes a depot (node 0), one recharging station, and four customers whose demands have a weight equal to their ID number (e.g., customer 3 has a demand that weighs 3 units). The time windows are omitted for the sake of simplicity. The battery capacity of the EV is considered 120 units. The EV starts its trip from the depot empty and picks up the customers’ demand by visiting them and then returns to the depot. The distances given next to the arcs are symmetric, and the speed of the EV is constant and equal to one (one unit distance is traveled in one unit of time). The consumption rate of an empty vehicle is assumed as one unit of energy per unit distance travelled, and the additional consumption corresponding to carrying one unit of cargo is assumed to be 0.05 unit of energy per unit distance. The recharging rate is 2 time units per unit of energy.

Fig. 1
figure 1

Illustrative example with one depot (charging station) and 4 customers

Full size image

Figure 2 illustrates the optimal solutions for the load-independent and load–dependent cases. The battery states of charge (SoCs) of the EV arriving at and departing from a node are indicated in red and the cargo loads at departure from the customers are shown in blue. The energy consumptions along the arcs are provided next to the corresponding arc. Figure 2a depicts the optimal solution for the load-independent case. In this case, since the effect of the cargo load is neglected, the energy consumption on an arc is equal to its distance as the energy consumption per unit distance is equal to one. We observe that the EV can serve all the customers without needing any recharge throughout its tour. Figure 2b shows the optimal solution for the load-dependent case. In this case, the EV needs to visit the recharging station after serving customer 2, the amount of energy recharged is 18.4 units and its duration is 2 × 18.4 = 36.8. Total energy consumption is 138.4 whereas it is 115 if the load is neglected. Note that neglecting the load did not only underestimate the cost in this case but it provided a route on which the EV would run out of battery. Note also that in the existence of time windows, one EV may not be able to serve all customers in a single tour and an additional vehicle may be needed.

Fig. 2
figure 2

Optimal routes for the illustrative example: (a) load-independent case, (b) load-dependent case

Full size image

3.2 Mathematical models

In this section we present two alternative mathematical formulations of the LD-EVRPTW: Model 1 is a mixed-integer linear program whereas Model 2 involves a non-linear objective function with a set of linear constraints.

3.2.1 Model 1

For ease of understanding we use the mathematical notation and modeling convention in the literature (Keskin & Çatay, 2016; Rastani et al., 2019; Schneider et al., 2014). We define \(V = { }\left\{ {1, \ldots ,n} \right\}\) and F as the set of customers and recharging stations, respectively. Vertex \(0\) denotes the depot where each EV departs from and return to at the end of its tour. We create dummy copies of the depot in order to keep track of the battery SoC of each vehicle upon their return. Let \(AD\) denote the set of arrival depots and \(V_{0} = V \cup \left\{ 0 \right\}\), \(V_{AD} = V \cup AD\), \(V_{0,AD} = V \cup \left\{ 0 \right\} \cup AD\). Then, the problem can be represented on a complete directed graph \(G = \left( {N,A} \right)\) with the set of arcs \(A = {\text{ \{ }}\left( {i,j} \right){|}i,j \in N,{ }i \ne j\}\), where set \(N = V_{0,AD} \cup F\) is the total set of nodes on the network.

The energy consumption depends on the distance traveled and the total weight of the EV, which includes the weight of the cargo. Each customer \(i \in V\) is associated with service time \(s_{i}\), time window \(\left[ {e_{i} ,l_{i} } \right]\), and demand \(q_{i}\). All EVs have a battery capacity of \(Q\) and a cargo capacity of \(C\). At each recharging station, one unit of energy is transferred in \(g\) time units. \(d_{ij}\) represents the direct distance from node \(i\) to \(j\). Travel time from customer \(i\) to customer \(j\) is denoted by \(t_{ij}\) if the journey is direct and \(\hat{t}_{ijs} = t_{is} + t_{sj} - t_{ij}\) is the extra travel time if it is via station \(s\). Note that \(\hat{t}_{ijs}\) does not include the recharging time at station \(s\). \(w\) represents the amount of additional energy required in order to move one unit of cargo. The total energy consumption of an EV traveling from customer \(i\) to customer \(j\) is calculated as \(\left( {h + wu_{i} } \right)d_{ij}\), where \(u_{i}\) is the weight of the load on the vehicle upon departure from customer \(i\).

The decision variables \(y_{i} ,y_{ijs}\), and \(Y_{ijs}\) keep track of battery SoC at arrival at customer/depot \(i\), at arrival at station \(s\) on route \(\left( {i,s,j} \right)\), and at departure from station \(s\) on route \(\left( {i,s,j} \right)\), respectively. \(\tau_{i}\) denotes the time when the service starts at customer \(i\). The binary decision variable \(x_{ij}\) takes a value of \(1\) if a vehicle travels from customer \(i\) to customer \(j\); and \(0\) otherwise. The binary decision variable \(z_{ijs}\) is equal to \(1\) if the journey from customer \(i\) to customer \(j\) is via station \(s\).

The problem can be formulated as mixed-integer linear program as follows:

$$ {\text{Min }}\left( {y_{0} - y_{AD} } \right) + \mathop \sum \limits_{{i \in V_{0} }} \mathop \sum \limits_{{j \in V_{AD} }} \mathop \sum \limits_{s \in F} \left( {Y_{ijs} - y_{ijs} } \right) $$
(5)
$$ \begin{gathered} {\text{subject}}\;{\text{to}} \hfill \\ y_{0} {\text{ }} = {\text{ }}Q{\text{ }} \hfill \\ \end{gathered} $$
(6)
$$ \mathop \sum \limits_{{\begin{array}{*{20}c} {j \in V_{AD} } \\ {j \ne i} \\ \end{array} }} x_{ij} = 1\quad \forall i \in V $$
(7)
$$ \mathop \sum \limits_{{\begin{array}{*{20}c} {i \in V_{0} } \\ {i \ne j} \\ \end{array} }} x_{ij} = 1\quad \forall j \in V_{AD} $$
(8)
$$ \mathop \sum \limits_{{\begin{array}{*{20}c} {i \in V_{0} } \\ {i \ne j} \\ \end{array} }} x_{ij} - \mathop \sum \limits_{{\begin{array}{*{20}c} {i \in V_{AD} } \\ {i \ne j} \\ \end{array} }} x_{ji} = 0\quad \forall j \in V $$
(9)
$$ \mathop \sum \limits_{s \in F} z_{ijs} \le x_{ij} \quad \forall i \in V_{0} , j \in V_{AD} , i \ne j $$
(10)
$$ \begin{aligned} \tau_{i} + \left( {t_{ij} + r_{i} } \right)x_{ij} + & \mathop \sum \limits_{s \in F} \left( {\hat{t}_{ijs} z_{ijs} + g\left( {Y_{ijs} - y_{ijs} } \right)} \right) \\ & - l_{0} \left( {1 - x_{ij} } \right) \le \tau_{j} \quad \quad \forall i \in V_{0} , j \in V_{AD} , i \ne j\\ \end{aligned} $$
(11)
$$ e_{j} \le \tau_{j} \le l_{j} \quad \forall j \in N $$
(12)
$$ 0 \le y_{j} \le y_{i} - ( {h + wu_{i} } )d_{ij} + M( {1 - x_{ij} + \mathop \sum \limits_{s \in F} z_{ijs} } )\quad \forall i \in V_{0} , j \in V_{AD} , i \ne j $$
(13)
$$ y_{j} \le Y_{ijs} - \left( {h + wu_{i} } \right)d_{sj} + M\left( {1 - z_{ijs} } \right)\quad \forall i \in V_{0} , j \in V_{AD} , s \in F,i \ne j $$
(14)
$$ 0 \le y_{ijs} \le y_{i} - \left( {h + wu_{i} } \right)d_{is} + M\left( {1 - z_{ijs} } \right)\quad \forall i \in V_{0} , j \in V_{AD} ,s \in F, i \ne j $$
(15)
$$ y_{ijs} \le Y_{ijs} \le Qz_{ijs} \quad \forall i \in V_{0} , j \in V_{AD} ,s \in F, i \ne j $$
(16)
$$ y_{j} \le Q\mathop \sum \limits_{{\begin{array}{*{20}c} {i \in V_{0} } \\ {i \ne j} \\ \end{array} }} x_{ij} \quad \forall j \in V_{AD} $$
(17)
$$ u_{j} \ge u_{i} + q_{j} x_{ij} - C\left( {1 - x_{ij} } \right)\quad \forall i \in V_{0} , j \in V_{AD} , i \ne j $$
(18)
$$ 0 \le u_{i} \le C\quad \forall i \in V_{0,AD} $$
(19)
$$ x_{ij} \in \left\{ {0,1} \right\}\quad \forall i \in V_{0} , j \in V_{AD} , i \ne j $$
(20)
$$ z_{ijs} \in \left\{ {0,1} \right\}\quad \forall i \in V_{0} , j \in V_{AD} ,s \in F, i \ne j $$
(21)

The objective function (5) minimizes the total energy consumption. Since the EVs are assumed to recharge overnight, constraints (6) set their initial battery SoC to full. Constraints (7) and (8) impose the connectivity of customer visits whereas the flow conservation at each vertex is ensured by constraints (9). Constraints (10) make sure that customer \(j\) is served after customer \(i\) if the vehicle travels from \(i\) to \(j\) by recharging its battery en-route. Time feasibility of arcs emanating from the customers (the depot) is guaranteed by Constraints (11) whereas the time window restrictions are established by Constraints (12). Constraints (11) and (12) also prevent the formation of sub-tours. Constraints (13) keep track of the SoC when the vehicle travels from customer \(i\) to customer \(j\) without recharging en-route. Constraints (14) determine battery SoC at the arrival at customer \(j\) if the vehicle visits a recharging station after it has departed from customer \(i\). Constraints (15) check the SoC at the arrival at a station if the vehicle recharges en-route. Here, \(M\) is a sufficiently large constant and can be \(M = { }Q + ( {h + w\mathop \sum \limits_{i \in V} q_{i} } ) \times {\text{max}}_{{i \in V_{0} , j \in V_{AD} }} \left\{ {d_{ij} } \right\}\). Constraints (16) set the upper bound for battery SoC when departing from a station. Constraints (17) allow positive battery SoC at the arrival at customer \(j\), when customer \(j\) is visited. Constraints (18) keep track of the load of the vehicle throughout its tour. Constraints (19) ensure the non-negativity of the load on the vehicle and guarantee that the cargo capacity is not exceeded. Finally, constraints (20) and (21) define the binary decision variables.

3.2.2 Model 2

In Model 1, the objective function minimizes the total energy consumption calculated in terms of the changes in battery SoCs. Alternatively, the total energy consumption can be calculated by multiplying the lengths of the arcs traversed by the energy consumption rate per unit distance which vary by the weight of cargo carried onboard. Since the cargo load of an EV and the arcs traversed are associated with decision variables, the resulting objective function is nonlinear. The constraints, hence the feasible region, remain the same; however, \(AD = \left\{ {n + 1} \right\}\) since copies of the depot are no longer necessary to keep track of the battery SoC of the EVs when they return to the depot. The mixed-integer nonlinear program can be formulated as follows:

$$ {\text{Min}} \mathop \sum \limits_{{i \in V_{0} }} \mathop \sum \limits_{{j \in V_{n + 1} }} \left[ {(h_{ij} + wu_{i} d_{ij} } \right)x_{ij} + \mathop \sum \limits_{s \in F} \left( {\hat{h}_{ijs} + wu_{i} \hat{d}_{ijs} } \right)z_{ijs} ] $$
(22)

subject to (6)−(7), (9)−(21)

Since all constraints are linear, the feasible region is convex. A local minimum of a convex function on a convex feasible region is also a global minimum (Bertsekas et al., 1999). In order to check the convexity of the objective function, consider a small instance that involves only a depot and a customer. The objective function can be formulated as follows:

$$ {\text{Min}} \left( {h_{0,1} + wu_{0} d_{0,1} } \right)x_{0,1} + \left( {h_{1,0} + wu_{1} d_{1,0} } \right)x_{1,0} $$
(23)

Since the distances are symmetric, we let \(d = d_{0,1} = d_{1,0}\) and \(h = h_{0,1} = h_{1,0}\) for simplicity. Hessian matrix comprises geometric information about the surface \(z = f\left( {x,y} \right)\) and is defined as follows:

$$ H_{f} \left( {x,y} \right) = \left[ {\begin{array}{*{20}c} {f_{xx} } & {f_{xy} } \\ {f_{yx} } & {f_{yy} } \\ \end{array} } \right] $$

where all of the second partial derivatives of function f exist at any point. Let \(H\) show the hessian matrix of the function in Eq. (23):

$$\begin{array}{*{20}{c}}& {\begin{array}{*{20}{c}} {x_{0,1}}&{x_{1, 0}}&{u_0}&{u_1} \end{array}} \\ {\begin{array}{*{20}{c}} {x_{0, 1}} \\ {x_{1, 0}} \\ {u_0} \\ {u_{1}} \end{array}}&{\left[ {\begin{array}{*{20}{c}} 0&0&wd&0 \\ 0&0&0&wd \\ wd&0&0&0 \\ 0&wd&0&0 \end{array}} \right]} \end{array}$$

We calculate the eigenvalues of \(H\) in order to obtain the geometric information about the surface of our objective function. If all the eigenvalues are positive (negative), the function is convex (concave). If some of the eigenvalues are positive and some are negative, the function is neither convex nor concave, and it will have a saddle point. We calculate \(\det \left( {H - I\lambda } \right) = 0\), where λ represent the eigenvalues, as follows:

$$\begin{aligned} {\text{det}}&\left({\left[ {\begin{array}{*{20}{c}} 0&0&wd&0 \\ 0&0&0&wd \\ wd&0&0&0 \\ 0&wd&0&0 \end{array}} \right]}-{\left[ {\begin{array}{*{20}{c}} -\lambda&0&0&0 \\ 0&-\lambda&0&0\\ 0&0&-\lambda&0 \\ 0&0&0&-\lambda \end{array}} \right]}\right) = \text{det}\left({\left[ {\begin{array}{*{20}{c}} -\lambda&0&wd&0 \\ 0&-\lambda&0&wd\\ wd&0&-\lambda&0 \\ 0&wd&0&-\lambda \end{array}} \right]}\right) \\ &= \left( {\lambda ^{2} - \left( {wd} \right)^{2} } \right)^{2} = 0 \to \lambda = \pm wd \end{aligned}$$

\(w\) and \(d\) are positive scalars, thus \(\lambda\) values can be positive or negative. Hence, the objective function is neither convex nor concave. Consequently, the solution obtained by solving Model 2 provides a local minimum.

3.2.3 Analysis on the performance of the proposed models

To investigate the performances of Models 1 and 2 we solved the small-size EVRPTW dataset of Schneider et al. (2014). This dataset consists of 36 instances involving 5, 10, and 15 customers generated based on the VRPTW instances of Solomon (1987). The instances are classified according to the geographic distribution of the customers: clustered (c-type), random (r-type), and half clustered half random (rc-type). Furthermore, in type-1 problems (i.e., subsets r1, c1, rc1) the planning horizon is short, and the customers have narrow time windows compared to long planning horizon and wide time windows in type-2 problems (i.e., r2, c2, rc2). All instances were solved using Gurobi 9.0 with a 2-h time limit. The results are reported in Table 3. In this table, “#Veh”, “EC”, “t(sec)”, and “Gap (%)” refer to the fleet size, energy consumption, run time (in seconds), and the reported optimality gap by Gurobi, respectively. “%ΔEC” shows the percentage deviation of the energy consumption in Model 1 from that in Model 2. Note that the deviation is calculated for solutions with the same fleet size and a positive number indicates that Model 2 provides a better result. “Avg” stands for average.

Table 3 Table 3 Comparison of results obtained using Models 1 and 2Comparison of results obtained using Models 1 and 2
Full size table

The results show that the nonlinear Model 2 is capable of providing better solutions in shorter run time. It outperforms Model 1 in two instances in terms of #Veh and in two instances in terms of EC (shown in bold). Moreover, Model 2 required 84% less computational effort than Model 1 on the average. Although Model 2 does not guarantee a global minimum, the results reveal that it is more promising than Model 1 in terms of both the solution quality and run time.

The optimality gap for Model 2 in 34 out of 36 instances is 0 since Gurobi found the optimal solution; however, for Model 1 Gurobi stops when it reaches the time limit (7200 s) in 12 instances. We also increased the computational time for the two instances namely “r202c15-s6” and “rc204c15-s7” to 10 h using Model 2. The instance “r202c15-s6” proved that the provided solution in Table 3 is optimal in 2 h and 23 min. However, for the instance “rc204c15-s7”, it cannot decrease the gap that much and after 10 h it provides the same solution reported in Table 3 with the optimality gap of 14.53%. Encouraged by the performance of Model 2 on small-size problems, we selected a total of 18 instances involving 25- and 50- customers and performed additional tests to investigate the tractability of the problem. In the 25-customer instances Gurobi was able to solve only one out of 9 instances to optimality and the average optimality gap is 61.90%, whereas none of the 50-customer instances was solved optimally and the average optimality gap is 78.91%. These results show the complexity of the problem and highlight the need for a heuristic method to solve not only large-size but medium-size instances as well.

4 Solution methodology

Since the problem is intractable for large-size instances, we develop an LNS-based matheuristic approach to solve it. Introduced by Shaw (1998) LNS attempts to improve an incumbent solution using an iterative destroy-and-repair framework. In every iteration, some customers are removed from the solution using a destroy mechanism and reinserted into the routes using a repair algorithm to generate a new, hopefully better solution. This procedure is repeated for a predetermined number of iterations. LNS and adaptive LNS (ALNS) have been successfully applied to many VRP variants including EVRPs and EVRPTWs (Goeke & Schneider, 2015; Hiermann et al., 2016; Keskin & Çatay, 2016, 2018; Keskin et al., 2019; Schiffer et al., 2018; Wen et al., 2016).

In this study, we generate the initial solution by adopting the insertion heuristic of Keskin and Çatay (2016) to the load-dependent case where the cost of inserting a customer into a route is calculated as \(\left( {h + wu_{i} } \right)d_{ik} + \left( {h + wu_{k} } \right)d_{kj} - \left( {h + wu_{i} } \right)d_{ij}\). This insertion cost is calculated for all the customers that are not visited yet, and the minimum cost insertion is performed by ensuring that the constraints associated with the vehicle cargo capacity, battery SoC, customer time windows, and maximum tour duration are not violated. If an EV runs out of energy, a station may be inserted to make the tour energy feasible. We use first-feasible station insertion algorithm which will be described in Sect. 4.2. If no customer can be feasibly inserted into the route, a new route is initialized, and the procedure is repeated until all customers are served.

Our LNS employs several destroy and repair mechanisms adapted from the literature as well as new mechanisms that are designed to deal the more complex structure of the problem, including an optimal repair mechanism. In each iteration, a customer removal algorithm is applied to a feasible solution to remove a subset of customers from the routes. If any station is no longer needed in the partial solution, they are removed from the solution as well. Next, we apply a customer insertion algorithm that inserts all the removed customers to repair the solution with the aim of obtaining a new improved solution. Stations may be inserted to maintain the energy feasibility along the route. Solutions are accepted using simulated annealing rule. This procedure is repeated for a pre-determined number of iterations. Note that the set of stations that can be visited between any two customers is reduced by using the dominance rules presented in Bruglieri et al. (2016).

4.1 Destroy operators

The current feasible solution is destroyed by removing \(\gamma \) customers. We use worst-consumption, random worst-consumption, shaw, random worst-time, random, random route, and greedy route removal procedures of Keskin and Çatay (2016) by modifying them for the load-dependent problem. At every iteration, one of these destroy operators is selected randomly.

  • Worst-consumption removal algorithm selects the customers with high energy consumption imposed on the route by visiting that customer. We utilize the following selection criterion that calculates the energy consumption based on the distance travelled and cargo load: \(\left( {h + wu_{i} } \right)d_{ik} + \left( {h + wu_{k} } \right)d_{kj} - \left( {h + wu_{i} } \right)d_{ij}\).

  • Random worst-consumption removal sorts the customers with respect to the associated energy consumptions, considers a subset of \(\sigma \times \gamma\) customers with the highest costs to select \(\gamma\) customers randomly, and removes them. Here, \(\sigma\) is a constant used to determine the size of the customer subset.

  • Shaw removal evaluates similar customers with respect to their energy consumption, earliest service time, being in the same route, and their demand. It randomly selects customer \(i\) and calculates the relatedness measure as \(R_{ij} = { }\phi_{1} h_{i} d_{ij} + { }\phi_{2} \left| {e_{i} - e_{j} } \right|{ } + { }\phi_{3} l_{ij} + { }\phi_{4} \left| {D_{i} - D_{j} } \right|\) to determine other customers that are similar. \(\phi_{1}\)-\(\phi_{4}\) are the shaw parameters, \(l_{ij} = { } - 1\) if \(i\) and \(j\) are in the same route, 1 otherwise. Small \(R_{ij}\) means high similarity. Using the non-decreasing order of the customers according to their relatedness values with customer \(i\), the first \(\gamma\) customers in the list are removed from the solution.

  • Random worst-time removal algorithm is a special case of shaw removal where \(\phi_{1} ,{ }\phi_{3} ,{ }\phi_{4}\) are set equal to 0. The customers are sorted in the non-decreasing order of their relatedness values. Then, from a subset of top \(\sigma \times { }\gamma\) customers in the list, \(\gamma\) customers are randomly selected and removed from the solution.

  • Random removal mechanism selects \(\gamma\) customers randomly and removes them from the solution.

  • Random route removal algorithm selects \(\omega\) routes randomly and removes them from the solution.

  • Greedy route removal mechanism sorts the routes in the non-decreasing order of the number of customers visited, and removes the first \(\omega\) routes that serve the least number of customers.

Note that the route removal algorithms attempt to reduce the fleet size.

4.2 Repair operators

We adapt random greedy, regret-2, random time-based, random greedy with noise function, and regret-2 with noise function repair algorithms of Keskin and Çatay (2016) and Demir et al. (2012) for our load-dependent problem. In addition, we propose exhaustive greedy, exhaustive time-based, exhaustive time-based with noise function, and random time-based with noise function algorithms.

  • Random greedy insertion selects a customer randomly and inserts it in the position that increases the energy consumption the least.

  • Random greedy with noise function insertion is an extension of the random greedy insertion mechanism with a degree of freedom. We use the same noise function presented in Demir et al. (2012). The insertion cost using the freedom degree is calculated as \(NewCost=ActualCost+ \overline{d }\mu \epsilon \), where \(\overline{d }\) represents the maximum distance in the network, \(\mu \) is the noise parameter used for diversification, and \(\epsilon \) is a random number between [− 1, 1].

  • Exhaustive greedy insertion considers all possible insertion positions for all customers that are not inserted yet and selects the customer-position matching which leads to least increase in energy consumption.

  • Exhaustive time-based insertion calculates the difference between the route duration after and before inserting a customer as the insertion cost. For all customers, the insertion costs in all possible positions are calculated and the customer with the least insertion cost is inserted in the associated position.

  • Random time-based insertion is similar to the exhaustive time-based algorithm. Instead of considering all unvisited customers, it first selects a customer randomly, and then inserts it in its best position with respect to time-based insertion cost.

  • Regret-2 insertion aims at avoiding higher costs in the subsequent iterations. It calculates the difference between the cost of the best insertion and the second-best insertion for all customers, and insert the customer with the largest difference in the associated position.

Note that regret-2 with noise function, exhaustive time-based with noise function, random time-based with noise function are extensions of regret-2, exhaustive time-based and random time-based insertion mechanisms, respectively, using a similar noise function.

As we mentioned earlier, the unnecessary stations are removed from the partial solution obtained using the destroy operator. During the repair procedure, the insertion of a customer may not be feasible with respect to battery SoC. In that case, we first attempt to increase the recharge quantity if a station is visited prior to arriving at that customer. If the energy recharged at the station cannot be increased or no station is visited en-route, we apply a station insertion operator to make the insertion feasible. We modify the greedy station insertion and best station insertion operator of Keskin and Çatay (2016) and multiple station insertion operator of Rastani et al. (2019), and applied them for the load-dependent problem. Note that at most one station can be inserted between two consecutive customers in a route.

  • Greedy-station insertion considers the first customer (or depot) where the EV arrives at with negative SoC and checks the insertion of the best station in the preceding arcs backward. The first station which makes the problem feasible is inserted.

  • Best-station insertion algorithm determines the first customer (or depot) where the EV arrives at with negative SoC, evaluates the insertion costs on all the arcs from that customer backward along the route, and performs the insertion of the best station (which increases the consumption least) in its best position.

  • Multiple-station insertion algorithm inserts multiple stations into a route when the insertion of a single station cannot make the route feasible. A station is inserted on the arc traversed immediately before arriving at the customer (or depot) with a negative SoC where the vehicle is recharged up to the maximum level allowed by the battery capacity and time windows restrictions of the succeeding customers. If the SoC is still negative at that customer or if the vehicle runs out of energy before reaching the inserted station, we attempt to insert another station prior to the last customer visited before traveling to the recently inserted station. This procedure is repeated until the route becomes energy feasible.

A station insertion algorithm is selected randomly when the repair procedure leads to infeasible route with respect to battery SoC. If one of the first-feasible station insertion or best-station insertion algorithms is selected but cannot create a feasible route, we resort to the multiple-station insertion algorithm. Furthermore, we remove all stations in the solution after every \(\beta \) iterations and apply the best-station insertion algorithm in an attempt to improve the solution.

4.3 Repair-opt insertion operator

We introduce a repair operator that attempts to insert the removed customers in the partial solution optimally along with the recharging stations, if needed. In this procedure, after the customers are removed from the solution, we feed the partial solution to a commercial solver and solve the mathematical programming model to insert them in their best positions in the solution. We refer to this operator as repair-opt procedure and implement it by employing Model 2. We call repair-opt in the LNS framework after performing η iterations because: (i) it is expensive in terms of computational time, (ii) it is more promising if it is applied after the algorithm has converged to a good solution. Furthermore, in order to accelerate the solution time, we provide an upper bound on the number of vehicles. This upper bound is determined according to the feasible solution obtained using the LNS procedure and becomes tighter as the procedure progresses. The contribution of the proposed optimal repair mechanism on the performance of LNS is investigated in the experimental study.

5 Experimental study

We performed our computational tests using the dataset of Schneider et al. (2014) and Desaulniers et al. (2016) for the small- and large-size instances, respectively. The data characteristics are as described in Sect. 3.2.3. Schneider et al. (2014) generated 56 large-size instances based on the VRPTW instances of Solomon (1987). Desaulniers et al. (2016) modified them to maintain feasibility for the case where the vehicles are allowed to recharge at most once during their tours. We used this dataset in order to investigate the sensitivity of the results under different recharging scenarios. We focused on type-1 instances in the large-size dataset and omitted type-2 instances since wide time window constraints have minor influence on the recharging decisions. (Desaulniers et al., 2016; Keskin & Çatay, 2018).

In order to deal with a realistic vehicle cargo capacity and customer demands, we assumed an electric truck based on the specifications provided in Demir et al. (2012). Since the payload of this vehicle is 3650 kg, we converted the demand values to reasonable weights by multiplying each by “3650/original capacity” of the vehicle in order to observe the effect of cargo weight on energy consumption. We assumed a drive train efficiency of 0.9 as EVs are more efficient than internal combustion engine vehicles. Furthermore, since the EVs in the original data are assumed to consume one unit of energy per unit distance/time traveled, we used Eq. (4) to calculate the actual energy consumption of an empty vehicle (i.e., a truck with 6350 kg curb-weight) per unit distance and scaled it to \(h=1\). We used the same approach to determine the energy consumption \(w\) associated with unit load carried. For the sake of simplicity, we considered a flat terrain where road gradients are zero and the vehicle speed is constant and equals to 16.67 m/s.

The small-size instances were solved using Gurobi 9.0 with a 2-h time limit. LNS was coded in Python 3.7.1 and all runs were performed on an Intel Core(TM) i7-8700 processor with 3.20 GHz speed and 32 GB RAM. We performed five runs for each instance. Based on some preliminary experiments on a subset of instances, we observed that performing LNS for 1000 and 6000 iterations for the small- and large-size instances, respectively, provided good solutions in reasonable computational time. The values of the remaining parameters are given in Appendix A.

5.1 Results for small-size instances

We first consider the small-size instances to validate the performance of the proposed method and to investigate the influence of the cargo load on route plans. The results are reported in Table 4. In this table, the columns under “Gurobi” present the results provided by Gurobi and the columns under “LNS” give the results obtained by the proposed LNS algorithm. “Load Independent” column reports the results for the case that does not take into account the increased energy consumption associated with the cargo carried whereas column “Load Dependent” shows the results for the case that considers the load on the vehicle. The comparison of the result under these two columns exhibits the influence of the load on the fleet size and energy consumption. “#Veh”, “t (sec)”, and “EC” refer to the fleet size, average run time (in seconds), and total energy consumption, respectively, as defined in Sect. 3.2.3, and “%ΔEC” shows the percentage increase in the energy consumption for the load-dependent case as compared to the load-independent case.

Table 4 Results for small-size instances
Full size table

The results show that Gurobi solved all the instances optimally except “rc204c15-s7” in the load-independent case, and “rc204c15-s7” and “r202c15-s6” in the load-dependent case. We observe that the existence of the load factor in the model required a larger fleet in one instance (“rc102c10- s4”) and resulted in an increase in the energy consumption in all instances, as expected. Furthermore, the energy consumption may be significantly higher when the cargo load is taken into account and the difference increases as the problem size increases. The actual energy consumption is 7.13% more on the average and can be up to 34.84% more due to the cargo load. When we compare the results found by our LNS approach to those of Gurobi, we see that LNS matches the optimal solutions (or the upper bounds in two instances) in all the instances except “r202c15-s6”. This constitutes an exceptional instance where a single EV serves all 15 customers in the optimal solution, which is difficult to identify heuristically.

5.2 Results for large-size instances

We solved the large-size instances for both load-independent and load-dependent cases using LNS. The results are provided in Table 5. We observe that the fleet size increases by two vehicles in one instance and by one vehicle in 15 instances (shown in bold) in the load-dependent case compared to the load-independent case. Furthermore, in the remaining 13 instances, EC increases by 13.11% on the average and can be as large as 31.63%. We believe that these significant differences in the energy consumptions and fleet sizes reveal the importance of considering cargo weight for more accurate route planning of EVs.

Table 5 Results for large-size instances
Full size table

5.3 Sensitivity analysis

In this section, we first investigate the contribution of the repair-opt operator in LNS to the performance of the algorithm. Next, we analyze the sensitivity of the results to the single-recharge policy where an EV is allowed to recharge its battery at most once during its tour. This may be a practical case in urban logistics since the stations are scarce and may be unavailable, and the delivery companies do not want to waste the often-expensive vehicle and driver time with recharging.

5.3.1 Contribution of the insertion operators to algorithmic performance

In order to investigate the contribution of the insertion operators on the algorithmic performance we select 12 instances and re-solved them by removing one of the insertion operators at a time. We performed 5 runs and summarized the results in Table 6 in comparison with those reported in Table 5. “#Veh (%)” and “EC (%)” in Table 6 represent the average increase in fleet size and energy consumption when the corresponding insertion operator is omitted. These results show that the proposed LNS algorithm benefits from all of the insertion operators and the contribution of an operator to minimizing the fleet size and energy consumption can be as much as 3.69% (regret-2 insertion) and 6.82% (exhaustive greedy insertion), respectively, on average.

Table 6 Average increases in fleet size and energy consumption upon removing an operator
Full size table

5.3.2 Contribution of repair-opt operator to algorithmic performance

Since the repair-opt operator is key component of the proposed method, we considered the LD-EVRPTW and re-solved all the instances by removing the repair-opt operator from the LNS to further investigate its role in the performance of the algorithm. We performed the LNS algorithm for 15,000 and 25,000 iterations to solve small- and large-size instances, respectively, as they showed a good compromise between the solution quality and computational effort. Note that the numbers of iterations were substantially smaller and set to 1000 and 6000 for small- and large-size problems, respectively, when LNS included the repair-opt.

We performed our tests on the 5-, 10-, 15-, and 100-customer instances. The results are summarized in Table 7. “#Better #Veh” and “#Better EC” reports the number of instances where LNS with repair-opt operator obtains a better solution with regard to the number of vehicles and energy consumption, respectively, and “#Inst” shows the number of instances solved. “%ΔEC " represents the average percentage deviation in the energy consumption when LNS is performed without repair-opt operator as compared to with repair-opt. A negative value indicates the contribution of repair-opt to the solution quality.

Table 7 Summary of results obtained without and with using repair-opt operator
Full size table

The results show that the repair-opt operator allowed LNS to converge to better solutions in 8 small-size instances out of 36: in two instances it reduced the fleet size whereas in six instances it decreased the total energy consumption. In the large-size instances, the LNS equipped with repair-opt achieved smaller fleet size in two instances and provided savings in energy consumption in 17 instances. Note that the results with repair-opt were achieved with shorter computation times. The detailed results are reported in Appendix B. In light of these results, we conclude that the repair-opt procedure enhances the overall performance of the proposed LNS method.

5.3.3 Analysis of single-recharge strategy

To investigate the impact of the single-recharge (SR) strategy on the route plans and costs we solved all large-size problems by limiting the en-route recharges by one. Note that the results we provided earlier were obtained under the multiple recharge (MR) strategy where the EVs can recharge their batteries as many times as they need, but only once between two consecutive customers. Table 8 compares the results of the MR and SR strategies for the LD-EVRPTW. We observe that the SR strategy frequently leads to the utilization of additional vehicles in the fleet (in 18 out of 29 instances, as shown in bold). It also increases the energy consumption by up to 18.46%. These results show that the companies that adopt the SR strategy should re-evaluate this strategy by accounting accurately the trade-offs between driver/vehicle times and vehicle acquisition/fuel costs.

Table 8 Comparison of results for multiple- and single-recharge strategies
Full size table

6 Conclusions and future research directions

In this paper, we addressed EVRPTW with partial recharges by taking into account the energy consumption associated with the cargo carried on the vehicle. We formulated two different mathematical models of the problem and compared their performances on small-size instances. For solving the large-size instances, we developed an LNS method by proposing new destroy and repair operators as well as a new repair mechanism based on an exact method.

Our numerical tests showed how the fleet size and/or energy consumption increase in comparison to the case where the load factor is neglected and revealed the importance of considering cargo weight of the vehicles for more accurate route planning. Specifically, we observed that the energy consumption can increase by up to 31% (in realistic large-size instances) because of the weight of the cargo carried on the vehicle. Furthermore, additional vehicles are often needed in order to provide service without disruption. Our experiments also revealed the contribution of the proposed repair-opt algorithm on the performance of the LNS algorithm.

Future research on this topic may consider the road gradient. A loaded vehicle going uphill will consume significantly more energy. On the other hand, when it travels downhill it can recharge its battery through energy recuperation from the wheels. However, the recuperation brings additional complexities to the problem.