Keywords

1 Motivation and Problem Description

The usage of electric-powered vehicles (EPVs) for cargo transportation brings about new challenges for research on transportation planning [8]. One of the challenges which are frequently accepted by the research community is the small range (operating distance) of EPVs, which is caused by the limited battery capacity. The scarce energy capacity of EPVs either allows only short vehicle routes, or alternatively and in contrast to combustion-powered vehicles (CPVs), detours to recharging stations become necessary, see [12]. Furthermore, the payload of EPVs is reduced due to the high weight of the batteries. Compared to CPVs of the same size (with respect to gross weight), an increased number of EPVs is needed for fulfilling a given set of transportation tasks. Consequently, the proportion between fixed and variable costs is changing. That is why research on the fleet size and the utilization of mixed vehicle fleets require new specific investigations, e.g. [3]. Altogether, new tour planning methods considering the specific characteristics of EPVs are required.

Few trucking companies have recently started using EPVs (see e.g. [19]). Of course, they do not replace all CPVs of their fleet by EPVs. In fact, they use EPVs tentatively for getting experience in applying electric power for cargo transport on roads. That is why EPVs usually are not used in fleets consisting exclusively of EPVs. They mostly are part of a mixed fleet composed of vehicles with electric traction and conventional, i.e. combustion-powered, vehicles. Furthermore, EPVs nowadays are almost exclusively used for local traffic on short-distance routes. Apart from some exceptions, trucking companies operate EPVs in that way that they avoid recharging during their routes. Exceptions refer to planning situations where EPVs can be recharged during the service time at customer locations. However, this requires precise agreements and cooperation between the trucking companies and the operators of customer locations. Detours to charging stations are avoided since the extra traveling distance and, even more important, the loss of time would be very costly. The usage of recharging stations is excluded in our paper since for local transport recharging on tour would be economically useless due to the driver wages which have to be paid for the time when drivers and vehicles are idle.

Out of the above reasons and in contrast to most research on vehicle routing for EPVs, we assume that recharging will only be done at the depot of the trucking company. That is why the tour lengths of routes planned for EPVs have to be adapted to the maximum range which can be driven by an EPV without recharging. Moreover, it might even happen that there is no feasible transportation plan for fulfilling a given set of transportation tasks with a homogeneous fleet of EPVs since some distances between customer locations are simply too long for EPVs. Since we are considering routes which have to be completed by one driver within one day, the tour length is additionally limited for any vehicle type by the maximum permissible daily driving time prescribed by EC-regulations.

EPVs are more energy-efficient than CPVs. However, one of the major drawbacks of EPVs is that their capabilities are more restrictive than those of CPVs; e.g. EPVs have a lower range and a lower payload. Consequently, using EPVs instead of CPVs leads to a reduction of the solution space for routing and scheduling. This means that the solution quality may decrease, and e.g. in case of distance minimization, the total travel distance of the vehicles will increase. However, the amount of increase of travel distances is not known in advance without knowing the characteristics of the deployed vehicles and transportation tasks at hand. Anyway, increased travel distances of EPVs will in turn cause increased energy consumption. That is why this paper is focusing on the following research questions:

  1. 1.

    What is the effect of the reduced range and payload of EPVs (compared to CPVs) on the travel distances and on the feasibility of transportation plans?

  2. 2.

    What is the amount of energy reduction or emission reduction reachable by using EPVs instead of using CPVs?

  3. 3.

    Can the typical strengths of EPVs (low energy consumption) and CPVs (high range and payload) be exploited by a fleet which is composed of both, EPVs and CPVs?

For investigating Question 1, transportation plans for test instances with short transportation distances are considered and the traveling distances obtained by these transportation plans are opposed for CPVs on the one hand and EPVs on the other hand. Then, the transportation distances are stepwise stretched or compressed in order to explore the impact of traveling distances on transportation plans; and the demands regarding transportation tasks are also modified in order to see the impact of capacity limitations of the vehicles.

For answering Question 2, transportation plans for CPVs and EPVs are compared with respect to the average values for energy consumption and \(CO_2\) emissions. For CPVs, it is widely accepted that the following Eq. (1) is a good and reasonably simplified approximation for the expected energy consumption of a truck k carrying payload of weight \(q_{ij}\) from a location i to a location j with \(d_{ij}\) representing the travel distance for the non-stop travel between i to j [5, 6, 17].

$$\begin{aligned} F_k = a_k \cdot d_{ij} + b_k \cdot q_{ij} \cdot d_{ij} \end{aligned}$$
(1)

In Eq. (1), \(a_k\) denotes the energy consumption of a CPV k per 100 km while \(b_k\) denotes the vehicle specific energy consumption per ton payload and 100 km. In this paper, Eq. (1) is also applied for estimating the expected energy consumption for EPVs. Of course, the values for \(a_k\) and \(b_k\) substantially differ for CPVs and EPVs. Since EPVs make use of recuperation of energy whenever it is possible, the difference between energy consumptions of EPVs and CPVs is strongly sensitive to the type of use of EPVs.

Nevertheless, for an averaged prediction of the energy consumption which has to restrict to ex-ante parameters of vehicle operation, Eq. (1) can be applied to EPVs in the same way as to CPVs. For comparing the emissions of CPVs and EPVs, the generated problem instances which have been solved for answering Question 1 are reconsidered and evaluated with respect of the energy consumption of vehicles. Question 3 will be investigated by allowing fleets with both, EPVs and CPVs, to be used for tour fulfillment.

Light-Duty and Medium-Duty trucks are frequently used in distribution logistics, and within this class of trucks, vehicles with 7.5 tons gross weight and those with 18 tons gross weight are very popular and widely-used. The truck market has offered many products for these vehicles types. Moreover, there are manufacturing companies which offer EPVs of 7.5 tons gross weight (e.g. [20]) and of 18 tons gross weight (e.g. [21]). Table 1 shows the specific characteristics of CPVs and EPVs of a size of 7.5 tons gross weight and 18 tons gross weight (c.f. [18, 21, 22]). The energy consumption declared by the manufacturers for EPVs is adjusted to two different modes of usage: city traffic and overland traffic. The lower value for energy consumption in Table 1 refers to city traffic while the higher value refers to overland traffic. For the EPV with 18 tons gross weight, the manufacturer only announces values for the weight and energy consumption of a chassis without platform. In Table 1, it is assumed that a platform with a weight of 4 tons is supplemented to the chassis (with a weight of 5 tons). The values for payload and energy consumption are adapted accordingly.

Table 1. Characteristics of CPVs and EPVs
Full size table

The remainder of the paper is structured as follows. Section 2 introduces the vehicle routing problem with time windows and limitations for energy consumption (VRPTW-EC). To generate near optimal transportation plans for the VRPTW-EC an Adaptive Large Neighborhood Search (ALNS) is used. The ALNS is presented in Sect. 3. Section 4 presents the results of computational experiments and derives answers for the research questions 1 to 3. Finally the paper closes with a summary of the findings.

2 Mathematical Model

The mathematical formulation for the VRPTW-EC is built by extending the traditional VRP-formulation (see [2]). The main extensions are:

  • the implementation of time windows for customers

  • the implementation of tour length restrictions (regarding traveled time and energy consumption)

  • the consideration of different types of vehicles (regarding capacity, tour length restrictions and energy consumption)

figure a
$$\begin{aligned} \textit{minimize} z = \sum _{k\in K} \sum _{(i,j)\in I\times I}&d_{ij} \cdot x_{ijk}, \end{aligned}$$
(2)
$$\begin{aligned} \textit{subject to:} \sum _{j\in I\setminus \{0\}} x_{0jk}&= 1,&\forall k \in K,\end{aligned}$$
(3)
$$\begin{aligned} \sum _{i\in I\setminus \{n+1\}} x_{i,n+1,k}&= 1,&\forall k \in K,\end{aligned}$$
(4)
$$\begin{aligned} \sum _{i\in I} x_{ihk} - \sum _{j\in I} x_{hjk}&= 0,&\forall k \in K, h \in I\setminus \{0,n+1\},\end{aligned}$$
(5)
$$\begin{aligned} \sum _{k\in K} y_{jk}&= 1,&\forall j\in I\setminus \{0,n+1\},\end{aligned}$$
(6)
$$\begin{aligned} \sum _{j\in I} q_j \cdot y_{jk}&\le Q_k,&\forall k \in K,\end{aligned}$$
(7)
$$\begin{aligned} t_i+s_i+t_{ij}- T_k \cdot (1 - x_{ijk})&\le t_j,&\forall k \in K, (i, j)\in I \times I,\end{aligned}$$
(8)
$$\begin{aligned} \alpha _i \le t_i&\le \beta _i,&\forall i \in I,\end{aligned}$$
(9)
$$\begin{aligned} \sum _{i \in I}q_{ijk}-\sum _{i\in I\setminus \{0,n+1\}} q_{jik}&=q_j\cdot y_{jk},&\forall k \in K, j \in I\setminus \{0,n+1\}\end{aligned}$$
(10)
$$\begin{aligned} q_{ijk}-Q_k\cdot x_{ijk}&\le 0,&\forall k \in K, (i,j) \in I\times I\end{aligned}$$
(11)
$$\begin{aligned} \sum _{(i,j) \in I \times I} t_{ij}\cdot x_{ijk}&\le T_k,&\forall k\in K,\end{aligned}$$
(12)
$$\begin{aligned} \sum _{(i,j) \in I \times I} d_{ij}\cdot (a_k \cdot x_{ijk} + b_{k} \cdot q_{ijk})&\le E_k,&\forall k\in K,\end{aligned}$$
(13)
$$\begin{aligned} q_{ijk}&\ge 0,&\forall k \in K, (i,j) \in I\times I\end{aligned}$$
(14)
$$\begin{aligned} t_{i}&\ge 0,&\forall i \in I,\end{aligned}$$
(15)
$$\begin{aligned} x_{ijk}&\in \{0,1\},&\forall k \in K, (i,j) \in I \times I,\end{aligned}$$
(16)
$$\begin{aligned} y_{jk}&\in \{0,1\},&\forall k \in K, j \in I. \end{aligned}$$
(17)

The Objective (2) minimizes the tour length. Constraints (3), (4) and (5) are the flow constraints. Whereas constraints (3) require that each vehicle has to leave the starting depot 0, constraints (4) dictate that all vehicles have to reach the duplicated depot \(n+1\) at the end of the tours. Constraints (5) observe that each customer is reached and left by the same vehicle. Constraints (6) ensure that all customers are assigned to one vehicle which means that \(y_{jk}\) is equal to the value obtained by summarizing \(x_{ijk}\) for all customers i. The amount of demand must not exceed the vehicles’ capacity (constraints (7)). Constraints (8) are an adaption of the sub-tour elimination restrictions described in [7] and set the service starting time for all nodes. The time windows are restricted by constraints (9). Constraints (10) are responsible for balancing the flow of goods. These equations allow the determination of the amount of cargo flow on each edge. Constraints (11) inhibit any transportation on unused edges. Otherwise it would be possible that the demanded quantities take paths differing from those of the vehicles. Since we consider daily planning for distribution logistics, the maximum tour length is restricted due to the maximum operation times of drivers. Whereas the constraints (12) limit the tour length regarding the travel time, constraints (13) restrict the amount of energy available for tours. The transport of negative payload is excluded by constraints (14) and negative times are excluded by constraints (15). Finally, constraints (16) and (17) define the domains of the decision variables.

3 Solution Method

To solve the VRPTW-EC we propose a modified ALNS. The ALNS was introduced by Ropke and Pisinger (see [9, 11]). It proposes improving an initial solution (i.e. transportation plan) by a ruin and recreate strategy (c.f. [13]). In an iterative approach a feasible transportation plan is destroyed by a removal operator and repaired by an insertion operator until a certain stop criterion is met (e.g. maximal number of iterations). To investigate large solution spaces, an ALNS uses several removal and insertion operators that reshuffle up to 40 % of all transportation tasks per iteration. Thereby an adaptive procedure guides the selection of the removal and insertion operators. To deal with local optima, simulated annealing (SA) is used, where better solutions are always accepted and worse solutions are accepted with a predefined probability [4].

3.1 Procedure of ALNS

Algorithm 1 visualizes the procedure of an ALNS. The procedure of the ALNS starts with the generation of an initial transportation plan s (line 1). Typically, this initial transportation plan results from a construction heuristic. In our case, the initial transportation plan is generated by a savings algorithm (c.f. [1]), where customers are merged to vehicle routes based on savings of travel distances.

figure b

The initial transportation plan s is stored as the actual best known solution sBest (line 2); and the start temperature of the SA is determined (line 3). Afterward, the improvement heuristic is applied in an iterative approach (lines 4–18) until a certain number of iterations \(it_{max}\) is reached. In each iteration the ALNS modifies the initial solution s, so that a new neighbor solution \(s'\) is developed. Thereby, customers are removed from the current transportation plan and reinserted into the remaining transportation plan. To increase the diversity of the improvement heuristic a randomly chosen number q of transportation tasks in the range \([q_1,q_2]\) is reshuffled in each iteration (line 6). Simultaneously, a removal operator and an insertion operator are chosen randomly by a roulette wheel selection, where the probability to select an operator depends on its performance in earlier iterations (line 7). Whereas the well-known operators worst removal, random removal, and shaw removal [14] as well as new sequence removal are available, the used insertion operators are different versions of the regret-k heuristics [10] with and without a noise factor (c.f. [11]). The removal operators remove q transportation tasks from the initial transportation plan (line 8); and the insertion operators reinsert those transportation tasks in the transportation plan (line 9).

A neighborhood solution \(s'\) is accepted as new best solution, if its objective value \(f_{s'}\) improves the objective value of the best known solution \(f_{sBest}\) (line 10–12). To avoid stucking in local optima, an SA supervises the accepting of a neighborhood solution \(s'\) as new initial solution s, where a solution with a higher objective value is accepted always as new initial solution and a worse solution is accepted with a probability (line 13–15). Furthermore, in each iteration the temperature T is reduced by a cooling rate \(\varsigma =(0,1)\) (line 16), and the probabilities for the roulette wheel selection are adjusted (line 17; c.f. [11]). Finally, the best transportation plan is returned (line 19).

3.2 Modifications to ALNS

The modifications made to the ALNS refer to the adaptation of removal operators. The shaw removal was originally provided for the pick-up and delivery problem, where the idea is preferably to remove similar transportation tasks. To suit the VRPTW-EC, the shaw removal is slightly modified. Our version of the shaw removal rates the similarity \(\gamma (ij)\) of a transportation task i to a randomly chosen transportation task \(j \ne i\) based on Eq. (18). Thereby, the features distance between the transportation tasks \(d_{ij}\), the similarity of the time windows (\(|\alpha _i-\alpha _j|,|\beta _i-\beta _j|\)) and the demands (\(|q_i-q_j|\)) are considered. All terms of Eq. (18) are normalized to values between (0, 1]; i.e. the terms are divided by the specific maximal values. Furthermore, the individual terms are extended by weights \(\delta _1\), \(\delta _2\), and \(\delta _3\). To increase the flexibility, the weights for the individual function terms are randomly re-chosen in the range [0, 10] for each using of the shaw removal.

$$\begin{aligned} \gamma (ij)= \delta _1 \cdot \left( \frac{d_{ij}}{d_{max}}\right) + \delta _2 \cdot \left( \frac{\left| \alpha _i-\alpha _j\right| +\left| \beta _i-\beta _j\right| }{\alpha _{max}+\beta _{max}}\right) + \delta _3 \cdot \left( \frac{\left| q_i-q_j\right| }{q_{max}}\right) \end{aligned}$$
(18)

Since the problem described by the VRPTW-EC has the special feature to consider heterogeneous fleets of vehicles, removal operators that force the use of different vehicles are worth investigating. That is why we introduced the sequence removal. It removes connected parts of tours from transportation plans, in order to enable the assignment of these parts to small vehicles. Overall, we propose three versions of the sequence removal, where one of the following strategies is randomly chosen for each application of the sequence removal:

  • remove all transportation tasks of a random tour

  • remove all transportation tasks after a random edge of a random tour

  • remove all transportation tasks after the edge with the highest distance of a random tour

Regardless of which version of the sequence removal is used the procedure is repeated until at least q transportation tasks are removed from the initial transportation plan.

4 Computational Experiments

The effects of using either EPVs or CPVs for vehicle routing are demonstrated for vehicles of different size. Based on the vehicle characteristics shown in Table 1, the experiments presented in this section are performed for vehicles with 7.5 tons gross weight and for vehicles with 18 tons gross weight. CPVs and EPVs behave differently with respect to the energy needed to fulfill a set of transportation tasks. In case of EPVs the energy consumption needed for traveling strongly depends on the type of application. Especially, it is to a high degree dependent on the traffic and road conditions relevant for fulfilling transportation tasks, and most typical for EPVs, the average travel efficiency (i.e. the energy consumption per travel distance) in urban traffic deviates a lot from the average efficiency reachable for overland traffic. Actually, the efficiency of EPVs in overland traffic is much lower than the efficiency in city traffic while for CPVs the difference between city and overland traffic is not generally significant. That is why we differentiate between three types of vehicle usage: CPV (VC), EPV in city traffic (\(VE_C\)), and EPV in overland traffic (\(VE_O\)). Each type of vehicle usage is considered for vehicles of 7.5 tons gross weight and 18 tons gross weight. Altogether we consider six types of vehicle utilization in Table 2: \(VC(7.5), VE_C(7.5), VE_O(7.5), VC(18), VE_C(18), VE_O(18)\).

Table 2 shows the values for the parameters \(a_k\) (energy consumption of the empty vehicle k per kilometer) and \(b_k\) (energy consumption for the load of vehicle k per ton and kilometer) for the above six types of vehicle utilization. These parameter values are derived from Table 1 by taking the energy consumption per 100 Km for the empty vehicle and the loaded vehicles as basis. In case of EPVs, the declaration for average energy consumption announced by the manufacturers of these vehicles varies considerably between a lower bound and an upper bound. That is why we take the values declared for the lower bound as the value for \(VE_C\), and the declared upper bound as the value for \(VE_O\). Note that, although the energy consumption of EPVs in overland traffic is always higher than the energy consumption in city traffic, the value of the proportionality factor \(b_k\) (i.e. the increase of consumption per ton and km) is lower for overland traffic than for city traffic. This is caused by the values announced by the manufacturers for the average lower and upper bounds for fuel consumption and the values derived for empty and full vehicles Additionally to the parameters for energy consumption, Table 2 shows for all six vehicle types the values for the parameters \(E_k\) (energy content for vehicle k regarding tank volume or battery capacity) and \(T_k\) (maximum tour length for vehicle k in km). The duration of daily tours is restricted by the EC-regulations for maximum driving times and by the regulations for working hours. That is why an upper limit for the sum of driving times and service times is statutory for daily trips of vehicles. We include the limitation on tour durations by restricting the maximum possible tour length (sum of traveled distances). Since we assume that smaller vehicles usually handle local tours with many stops and larger vehicles will execute larger tours with less stops, we fix the maximum tour length to 450 km for 7.5-ton-vehicles and to 500 km for 18-ton-vehicles. For EPVs the maximum tour length is additionally limited due to their limited battery capacity.

Table 2. Considered vehicle types
Full size table
Table 3. Characteristics of test sets
Full size table

The generation of test instances is based on the adaptation of the well-known Solomon instances [15]. In order to adjust the customers’ demands to the capacity of the used vehicles and to adjust the tour lengths to the maximal range of the vehicles, a demand-factor and a length-factor are introduced. The demand-factor linearly and uniformly increases the demands of all customers occurring in the original Solomon instances. The length-factor linearly stretches all distances between any location pair. Additionally, the durations of the time windows of the Solomon instances are stretched according to the length-factor applied to the traveling distances. The values of the demand- and the length-factor are modified within a reasonable scope in order to investigate the effects of varying distances and weights on differently sized CPVs and EPVs. Altogether, nine test sets S-1 to S-9 have been generated (see Table 3).

In our computational experiments, the nine test sets of Table 3 are solved for each of the following scenarios for vehicle utilization:

  • (A) homogeneous fleet of CPVs

  • (B) homogeneous fleet of EPVs (city traffic)

  • (C) homogeneous fleet of EPVs (overland traffic)

  • (D) fleet of CPVs and EPVs (city traffic)

  • (E) fleet of CPVs and EPVs (overland traffic)

The scenarios (D) and (E) are implemented by using a homogeneous fleet of CPVs for solving the test sets S-1 to S-9 and subsequently replacing CPVs in the obtained solutions by EPVs whenever it is possible. A CPV can be replaced by an EPV if the tour assigned to that CPV is not too long for the range of the EPV respectively its payload is not exceeded. Furthermore, the test sets S-2, S-4, and S-7 are solved by considering various heterogeneous fleets of CPVs and EPVs.

All instances were solved by the ALNS described in Sect. 3 with a maximum of 50,000 iterations. The ALNS was implemented in a C++-application and computed on a Windows 7 PC (i7-2600 processor with 3.4 GHz, 16 GB RAM). The results obtained for the utilization scenarios (A), (B), and (C) are presented in Table 4.

To establish comparability among the energy consumption of CPVs and EPVs, both, diesel consumption and electricity consumption, are converted into the resulting values for Tank to Wheel (T2W) emissions and Well to Wheel (W2W) emissions. Whereas, the T2W rates the \(CO_2\) emissions of the energy consumed by the vehicle, the W2W also rates the \(CO_2\) emissions of the energy production. For CPVs applies that one liter diesel accords with 2.629 kg \(CO_2\) emissions for T2W respectively 3.168 kg \(CO_2\) emissions for W2W [18]. Simultaneously, one kWh equates 0.542 kg \(CO_2\) emissions for T2W and 0.57 kg \(CO_2\) emissions for W2W [23].

The entries in Table 4 show that the test sets with the lowest of the provided length-factors (0.5 in test set S1, 2.0 in test set S-4, and 2.0 in test set S-7) per fixed demand-factor and fixed vehicle size could always be solved for all three scenarios (A), (B) and (C). In case of vehicles with 7.5 tons gross weight and a demand-factor of 20 (i.e. test set S-2), all three scenarios are also solvable for a length factor with the value 1.0. All other test sets are only solvable for scenario (A), i.e. for using CPVs. Averaged over all test sets which are solvable for all scenarios, the number of used vehicles increases by 17 % respectively 18 % in case that CPVs are replaced by EPVs in city traffic respectively overland traffic. Moreover, the total travel distance increases by 10.0 % respectively 10.8 %. On the opposite side, the amount of T2W emissions decreases by 13 % respectively by 6 % if the values of [18, 23] are used for calculating the T2W-values for CPVs and EPVs. However, for one of the test sets (S-7) the total amount of emissions even increases if for overland transport CPVs are replaced by EPVs. The average values for distance decrease and emission increase in Table 4 (i.e. 13 % respectively 6 %) have to be opposed to the fact that, according to the values of [18, 23], replacing a travel distance of an empty 7.5 tons respectively 18 tons CPV by a travel distance of a corresponding EPV would imply an emission reduction 33.4 % respectively 12.2 %.

Table 4. Results of test sets for scenarios (A), (B), (C)
Full size table

Table 5 shows the results for mixed vehicle fleets in case of city traffic (scenario (D)). In scenario (D), the solutions of scenario (A) are modified by replacing CPVs by EPVs as much as possible. For each test set we consider the situation that 0, 2, 4, or an unlimited number (\(\infty \)) of EPVs are available for replacing CPVs. The quotient (u / a) in Table 5 denotes the number u of actually used EPVs divided by the number a of available EPVs.

Table 5. Results of test sets for scenario (D)
Full size table

In contrast to the results of the scenarios (B) and (C) with homogeneous electric-powered fleets (see Table 4), all test sets of Table 5 can be solved by using the mixed fleets considered in Table 5 since there are always enough CPVs available in the scenarios shown in Table 5. Increasing the number of available EPVs has the effect that an increased number of EPVs actually are used. However, averaged over all test cases, only one-third of the available EPVs are deployed since in all other cases the generated routes are too energy-consumptive for EPVs. Anyway, using mixed fleets according to Table 5 for fulfilling the routes which have been generated for a homogeneous fleet of CPVs, has the advantage that on the one hand all test sets can be solved successfully and on the other hand the \(CO_2\) emissions can be reduced compared to a pure CPV-fleet. If the number of available EPVs which are available for substituting CPVs is unrestricted (i.e. \(a = \infty \) in Table 5), then the total T2W emissions for all considered test sets are reduced by 3.2 % compared to the strict usage of CPVs only. The values shown in Table 5 refer to the usage of EPVs in city traffic. In case of overland traffic (scenario (E)) the averaged values of the columns of Table 5 deviate in the following way: the average number of used EPVs (u) is decreasing by \(8.4\,\%\); and the value for T2W emissions is increasing by \(0.9\,\%\).

Table 6. Results for a heterogeneous fleet of CPVs and EPVs
Full size table

Since the objective of all vehicle routing experiments in this paper is given by the minimization of traveling distances, the objective values and the optimal solutions do not depend on the fact whether CPVs or EPVs are used. However, since CPVs are more flexible with respect to range and payload, there will be many routes which are only executable by CPVs. That is why mixed fleets should be investigated more intensively. Table 6 shows the results of additional experiments on mixed fleets for the test sets S-2, S-4 and S-7. The additional experiments are restricted to the above test sets since these test sets are the only ones of Table 4 which can always be solved for the homogeneous scenarios (B) and (C); i.e. an arbitrary combination of CPVs and EPVs will always be able to fulfill all given transportation tasks of the test instances occurring in these test sets. In contrast to Table 5, where the number a (available EPVs for the test cases of Table 4) is introduced and stepwise increased, Table 6 shows the effects of decreasing the limit of available CPVs on the test cases of Table 4. In this case the vehicle routing algorithm is forced to use EPVs due to the lack of available CPVs. Like in Table 5, the first line for each scenario in Table 6 is equal to the first line of that same scenario in Table 4 since there are enough CPVs available for generating the same solutions as for Scenario (A). As shown in Table 6, stepwise decreasing the number of available CPVs has the effect that the total travel distances are increasing while the emissions are decreasing. In case of city traffic a limitation to five CPVs implies an increment of travel distances by 1.0 %, 0.7 %, 6.0 % and a decline of emissions by 15.5 %, 6.0 %, 4.1 % for test sets S-2, S-4, S-7 respectively. The values of Table 6 can be opposed to corresponding values for homogeneous electric-powered fleets for city traffic (Scenario (B) of Table 4). For Scenario (B) the growth of travel distances compared to a pure fleet of CPVs (Scenario (A)) is 9.8 %, 5.8 %, and 16.4 % and the reduction of emissions is 29.7 %, 12.5 %, and 5.0 %. This clearly shows the potential of a mixed fleet to reduce the emissions tremendously while the travel distances are only increasing slightly. In case of overland traffic, the results for using mixed fleets for the test sets S-2, S-4 and S-7 are similar to the results for city traffic. Compared to city traffic, the overland travel distances increase by \(0.1\,\%\) and the T2W emissions increase by \(1.5\,\%\).

5 Conclusion

The main contributions of our paper are (i) the comparison of EPVs and CPVs (ii) by considering not only the reduced range but also the reduced payload of EPVs and (iii) analyzing the benefits of mixed fleets consisting of EPVs and CPVs. The analysis of the experiments presented in this paper clearly measures, demonstrates and contrasts the specific strengths of CPVs and EPVs. Moreover it could be shown that the drawbacks of CPVs and EPVs can be mitigated by deploying a mixed fleet consisting of electric-powered as well as combustion-powered trucks.