1 Introduction

In 2009, transportation has caused approximately 25 % of the total anthropogenic greenhouse gas emissions in the 27 member states of the European Union (EU) while it accounts for approximately 30 % of total anthropogenic CO2 emissions in the EU with a fraction of about 71 % caused by road transportation (EU 2012). Considering the total energy consumption of the EU in 2010, a fraction of 31.7 % has been burnt up by transportation processes.

Modern technology has achieved tremendous success to make present-day vehicles, as e.g. vehicles of the type EURO V and VI, more efficient and cleaner with the effect of reducing their environmental impact. However, this progress has been overcompensated by the growth in the total transportation volume in Europe (Meyer and Fehrentz 2011). Due to the need to reduce the negative impacts of emissions and because of the fact that the currently used fuel resources are endangered to become scarce, transportation must be organized and performed in a more efficient and sustainable way. This contribution investigates an innovative so far unconsidered aspect of green transportation which is related to the ecological benefit that can be achieved by choosing vehicles of adequate size for transport demand fulfillment. Actually, we analyze potential benefits of a heterogeneous fleet consisting of vehicles out of several categories which are different with respect to fuel consumption and maximal payload.

Despite the growing official pressure to reduce anthropogenic emissions, there has only been limited research which seeks to reduce emissions (greenhouse gases, fine dust, noise, etc.) as the primary objective of vehicle routing (Figliozzi 2010). Except for CO2 all other substances can be reduced due to modern truck technology by cleaner combustion or by filtering harmful substances out. That is why the emission of CO2 is the most critical issue of pollution caused by transportation as far as global warming is concerned (EU 2012). The amount of CO2 emissions is proportional to the amount of fuel consumed for the fulfillment of tours (ICF 2006). Thus, minimizing the amount of fuel consumed for fulfilling a request portfolio is equal to minimizing the CO2 emissions required for the complete demand fulfillment. The fuel consumed for transporting goods from A to B with a vehicle C is dependent on a variety of factors as e.g. the distance between A and B, the moved weight (empty mass of the vehicle C and the actual weight of load), traffic conditions (which are highly influenced by the time chosen for travel), the performed driving style, the type of the road, the topology, the CW-value of the vehicle, the type and conditions of the tires, the speed, the acceleration, etc. (see e.g. Demir et al. 2011).

The amount of fuel needed for fulfilling a set of transportation requests depends on the applied transportation plan and in particular on the resulting flow of moved weights. Actually, the fuel consumption and consequently CO2 emissions can be reduced by keeping the actual weight of the used vehicles (Figliozzi 2010; Ubeda et al. 2010; Peng and Wang 2009) including their payload and their dead weight as low as possible.

The approach introduced in this paper presents a new “green” version of the traditional capacitated Vehicle Routing Problem (CVRP) originally investigated by Dantzig and Ramsey (1959). This new version aims at reducing CO2 emissions by offering the possibility of using different types of vehicles. Here, vehicles differ by their weight, payload and emission generation. The objective function of the considered optimization problem is given by the expected quantity of fuel consumption which is determined in dependence of the actual weight of the vehicles and on the basis of realistic values for the fuel consumption of modern trucks of different size.

The here addressed research question is as follows: To which extend does a fleet of mixed-sized vehicles enable the reduction of fuel consumption compared to the case where only a homogeneous fleet with equally sized vehicles is available?

Section 2 presents a review on relevant literature and major trends in decision support for CO2-minimal transportation. Section 3 introduces the Emission Minimization Vehicle Routing Problem with Vehicle Categories (EVRP-VC). Section 4 evaluates the EVRP-VC. Section 5 summarizes this work and proposes future avenues of research.

2 Inclusion of CO2 minimization in vehicle routing

Fundamental ideas and approaches for vehicle routing problems with the goal of CO2 emission reduction are presented in Subsect. 2.1 An overview on literature that deals with CO2 emissions respectively fuel consumption of vehicles of different types is given in Subsect. 2.2

2.1 General emission-oriented VRP approaches

Several ecologically oriented extensions of vehicle routing problems have been introduced which aim at minimizing the fuel consumption or the amount of CO2 emission. In any of these problems, the evaluation of transportation plans relies on an estimation of the quantity of fuel consumed for request fulfillment. There exists a variety of methods for estimating fuel consumption and emission of road transportation in dependence of a bunch of parameters. For an overview on methods see e.g. Frey et al. (2010). Most of the estimation methods are based on analytical emission models. The methods found in literature differ in the assumed basic principles and with respect to the parameters they take into account for estimation. A comparison of several vehicle emission models for road freight transportation can be found in Demir et al. (2011). In addition to comparing different methods for estimating fuel consumption and pollution, Demir et al. (2011) analyze the discrepancies between the results yielded by the models on the one hand and the results of measurements of on-road consumptions of real vehicles on the other hand.

Kara et al. (2007) present a model for a problem that minimizes the weighted load carried by the vehicles. They claim that their model strives for energy-minimizing of the routed vehicles but their approach does not reflect the actual energy consumed by a vehicle since it ignores some very important factors as for instance the empty vehicle mass. More recent models are based on methods for estimating fuel and pollution in dependence of specific parameters and actually consider the total weight including the dead weight of the carrying vehicles (e.g. Peng and Wang 2009). These recent models take several factors into account, e.g. the average speed (Figliozzi 2010), congestions influencing the average speed combined with acceleration rates (Figliozzi 2010), topology (Scott et al. 2010; Ubeda et al. 2010) or the payload (Jaramillo 2010; Scott et al. 2010; Peng and Wang 2009).

An overview on issues linking Green Logistics with vehicle routing and scheduling can be found in Sbihi and Eglese (2010). In this paper the authors focus on aspects of time-dependent problems, the transportation of hazardous material and the dynamic optimization of real-time models. Related to these aspects, they discuss environmental objectives as well as characteristics of vehicle routing problems that involve the consideration of additional constraints. Jabali et al. (2012) study the trade-off between minimizing CO2 emissions as opposed to minimizing total travel times. As CO2 emissions are directly related to vehicle speed, time-dependent travel times are included in their optimization models. Three different models are presented and compared: a model for the minimization of the total travel time, a model for minimizing the total CO2 emission in dependence of travel times and speed, and a cost-based model that optimizes on a weighted average of travel time, emission and fuel costs. Assuming that carrier companies can limit the speed of their vehicles, the authors discuss the emission-optimal speed taking into account the impact that congestions will have on the actual travel time and emission.

The so-called Green Single Vehicle Routing Problem introduced in the articles by Jaramillo (2010) as well as Peng and Wang (2009) aims to minimize the transportation amount of a round trip measured in the total ton miles related to the trip. In this approach, the empty weight of the vehicle is included for the determination of the total ton miles but Jaramillo (2010) does not discuss any method for calculating the fuel consumption or emission resulting from the minimized ton miles. Kuo (2010) also proposes a model for minimizing the total fuel consumption for the time-dependent vehicle routing problem where fuel consumption depends on speed, time of travel and loading weight. The author presents a simulated annealing algorithm for solving this problem. He considers a homogeneous fleet. The basic value for the time-dependent and speed-dependent fuel consumption F of a vehicle is determined for an empty vehicle. Loading is taken into account by assuming that a reference value M for extra weight in the vehicle will increase the fuel consumption by a certain fixed percentage p. The total fuel consumption including the effect of transporting a load with weight Q is then regarded as \(F\cdot(1 + p\cdot \frac{Q}{M})\). The author performs computational experiments comparing fuel consumption, transportation time and travel distance for the time-dependent vehicle routing problem. But he does not perform any experiments showing the effects of variations on the loading weight. In Kuo and Wang (2011) the problem which has been presented before in Kuo (2010) is considered once more and this time it is solved with a Tabu Search Algorithm instead of a Simulated Annealing approach.

The measure for transportation efficiency used by Suzuki (2011) is the consumption in Miles-per-Gallon (MPG) adapted by a vehicle speed parameter and a road-gradient parameter. Additionally, the effect of payload on MPG is included by applying a payload factor. In principle, Suzuki (2011) uses the same approach for estimating the effect of vehicle payload as Kuo (2010) does. Furthermore, Suzuki (2011) adds a summand to the objective function for reflecting the fuel which is needed for the idle running of a truck’s engine during stops (e.g. waiting for the opening of time windows). The idle running considered in Suzuki (2011) is due to various reasons such as heating or cooling the driver’s compartment. Although not mentioned in this paper and not relevant for the case study of Suzuki (2011), the energy per time unit, and in particular the energy consumed during waiting times, is a very important aspect for refrigerated trucks which must be tempered constantly. Suzuki (2011) performs experiments on the Traveling Salesman Problem with time windows and compares the results for fuel minimization on the basis of pure distance minimization and on the basis of his approach including the effect of payload. For a case study performed on the data of an actual US trucking company running heavy-duty trucks with 44 tons gross weight, he reports that significant savings (between 4.9 and 6.9 %) in fuel consumption have been realized by delivering heavy items in the early segments of a route while delivering light items in the later segments. The case study consists of a homogeneous fleet and does not perform any specific experiments with varying payloads for the vehicles.

Bektas and Laporte (2011) present and compare several ecological oriented extensions of the CVRP. The presented extensions are based on objective functions that account not just for travel distance, but also for the amount of greenhouse gas emissions, fuel, travel times and costs. In their paper, mathematical models are described for these extended problems with different goals, such as distance-minimizing, weighted load-minimizing, energy-minimizing and cost-minimizing, and nearly all computational experiments are performed for a single vehicle and by solving the described models with CPLEX. The results of different models are compared for some realistic problem instances with and without time windows. Although focusing strictly on the situation with one vehicle, the authors extend their experimental setting to scenarios with several vehicles at the end of the paper. In these scenarios all available vehicles are of the same type and the analysis concentrates on the comparison of the alternative usage of different homogeneous fleets. The extension of the scenarios shows that, in case of several vehicles of the same type, the results are similar to those obtained for one single vehicle. Oberscheider et al. (2013) investigate environmental impacts of timber transport. They discuss a multi-depot vehicle routing problem with pickup and delivery and time windows. For this problem, they oppose the results obtained by minimizing fuel consumption to the results obtained by minimizing driving times. They show that a significant reduction of CO2 emissions can be achieved compared to a minimization of driving times.

2.2 Investigations with different vehicle types

The remaining part of literature review in this paper restricts to papers which at least at first glance seem to discuss different vehicle types. Ubeda et al. (2010) analyze the effects of various degrees of vehicle utilization on carbon dioxide emission. Although the selection of vehicle types as a means for the efficient use of transportation resources is stressed in this paper, there are no diverse vehicle types with different characteristics considered. The authors analyze the differences in CO2 emissions between a distance and an emission minimization approach. For distance minimization a usual distance matrix representing the length of the arcs between the nodes of the routing problem is employed. For emission minimization it is assumed that the environmental effect of a vehicle traversing an arc depends on the length of the arc and the amount of load carried by the vehicle on that arc. The amount of load is represented by an emission factor which will be multiplied with the length of the arc. In this respect, this approach is similar to the approach of Kuo (2010). Ubeda et al. (2010) quantify the environmental effect by fixing values for the emission factors before starting the emission minimization process. The set of emission factors define an environmental matrix which is used in the same way as a distance matrix usually is used for distance minimization. Since the values for the amount of load carried on arcs cannot be known in advance, the authors have to settle for estimated values of the emission factors. This, of course, has a negative effect on the solution process and the quality of the obtained solutions.

Scott et al. (2010) investigate the influence of gradient and payload correction factors used within CO2 emission models. The authors test the amount of influence on solutions of shortest path problems and traveling salesman problems when applied to freight delivery. For the estimation of the fuel consumption, their study employs the COPERT model presented in Ntziachristos and Samaras (2000). This model is based on the average speed of a vehicle and includes the effect of payload and corrections for heavy vehicles. Scott et al. (2010) worked out that for the problem instances studied and for the correction factor used by them, significant influence was only found for problems with large differences in payload and hilly road networks. This is obviously due to the fact that, according to the emission model used by them, the influence of the payload on the emission factor is very low and is decreasing to zero for low gradients. Since the effect of payload is calculated as a product of a load correction factor and the gradient correction, it will even be zero for zero gradients. In this study the effect of time windows, average speed, congestion and the driving style are ignored. But the authors define different vehicle categories and discuss the influence of gradient and payload on these categories. De facto, there is no mixed fleet considered in this paper since the analysis is done for several vehicle categories independently. Gusikhin et al. (2010) study the fuel consumption of a mixed fleet composed of a heterogeneous set of vehicles with noticeable variations in fuel economy. Their investigation refers to passenger cars only and that is why they do not consider any carriage of load. In their experiments, the fuel consumed for traveling does not only differ with respect to the type of vehicle but also with respect to the type of road. Two types of roads are considered: highways and city roads. The authors compare the outcome of distance minimization with the results obtained by minimizing the fuel consumption. They demonstrate that the plans resulting from the two different minimization approaches are composed of completely different routes. The main reason for this is that distance minimization does not account for the diversity of the efficiency of the used cars whereas fuel consumption minimization employs the cars for those travel tasks on which they are most effective. Eguia et al. (2013) describe and solve a problem of minimizing the internal and external costs in a VRP setup with a heterogeneous fleet including time windows and backhauls. The internal costs are composed of driver costs, energy costs, fixed vehicle costs, maintenance costs and toll costs. The external costs are composed of climate change costs, air pollution costs, noise costs and accident costs. The authors consider the situation of a given heterogeneous fleet. In contrast to our investigation on the EVRP-VC, the authors do not analyze the benefits and drawbacks of introducing a heterogeneous fleet as opposed to a homogeneous fleet.

The approach presented in this paper can be considered as an extension of the approach of Jaramillo (2010) with respect to both, the introduction of various vehicle categories and the minimization of the estimated fuel consumption instead of the total ton-kilometers. For all vehicle categories, vehicle specific functions for fuel consumption are introduced, which rely on measurements of on-road consumptions. To the best of the authors’ knowledge there is no research in literature minimizing the CO2 emission of a mixed fleet with vehicles which differ in fuel consumption and loading capacity.

3 Emission minimization vehicle routing problem with vehicle categories

A vehicle routing problem with a heterogeneous fleet that aims at minimizing the fleet’s fuel consumption is stated informally in Subsect. 3.1 An adequate mathematical decision model is proposed in Subsect. 3.2. Subsection 3.3 reports the definition of test scenarios that are used to evaluate the model.

3.1 Informal problem outline

The here proposed and evaluated approach for the compilation of CO2-minimal routes for freight carrying trucks is based on the original CVRP (Dantzig and Ramsey 1959). We replace the total sum of traveled distances as planning criterion by an estimation of the consumed fuel as planning preference. The assumed fuel consumption depends on the weight of a vehicle during the course of its route. In order to exploit the advantages of a fleet of vehicles with different dead weights, maximal payloads and fuel efficiency, we also consider the option to employ different types of vehicles.

According to the fuel economy guide of the US Department of Energy (2008) the loaded weight (payload) influences the fuel economy of a vehicle in that way that each extra 100 lbs. carried by the vehicle would increase fuel consumption by up to 2 %. Although this supposition has been formulated for passenger vehicles, it applies in principle also to trucks carrying cargo. For heavy-duty trucks studied by the UK Department for Transport (2007), the effect of vehicle payload on MPG can be characterized by a linear function \(mpg^{\prime} = \alpha + \beta\ast L\). The function \(mpg^{\prime}\) represents the fuel consumption per mile in dependence of the payload L, with α being the consumption per mile for the empty vehicle while β represents the proportionality factor for the additional fuel consumption per mile caused by the payload. Practical experiences on the amount of fuel consumption strengthen the assumption that using a fixed contribution for the empty vehicle and a linear fuel increase for the weight of the payload yields a good approximation for the fuel consumption per distance unit. Reports on fuel consumptions can be found on bulletin boards for forwarders (e.g. Eurotransport 2013). A large collection of individual empirical data about the fuel consumption of trucks can be found in Spritmonitor (2013).

Following the just mentioned arguments, we decide to use the following function F k shown in (1) for the quantification of the expected fuel 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.

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

In Eq. (1), a k denotes the fuel consumption of the vehicle k per 100 km while b k denotes the vehicle specific fuel consumption per ton payload and 100 km. We use function F k for the estimation of the amount of consumed fuel for all our computational experiments. The quantity of emitted CO2 is proportional to the fuel consumption so that the fuel consumption minimization is equivalent to the CO2 emission minimization. In the following, models for CO2 minimization which are based on Eq. (1) will be called fuel-based models or models with a fuel-based objective function. It is important to stress that we only investigate the effect of the factors load and distance on the fuel consumption of a given truck k while all other factors potentially influencing the fuel consumption are not considered because they are assumed to remain unchanged in our investigations. Examples of such unconsidered factors might be the continuity, the speed or the topography of the operational area. Additionally, we want to mention that the shortest paths with respect to distance may differ from the shortest paths with respect to CO2 emissions. We do not discuss the generation of shortest paths for the distance matrices in our paper and that is why we assume throughout our paper that the shortest paths are identical for distance minimization and CO2 emission minimization.

Apart from the restriction to a single vehicle type, the function for fuel estimation employed by Kuo (2010) is similar to the function given in Eq. (1) above. Suzuki (2011) also makes use of such a function. For the values of fuel consumption per 100 km and fuel consumption per ton and 100 km he relies on estimations derived by the UK Department for Transport (2007) for 44-to trucks which are equivalent to class-8-trucks in the US. Ubeda et al. (2010) define five states of vehicle utilization representing the degree of exploiting the capacity of a vehicle ranging from empty, over 25 % loaded, 50 % loaded, 75 % loaded to full load. The amount of fuel consumed for traversing an arc is calculated by multiplying the travel distance (the length) of this arc by an emission factor whose value depends on the loading state of a vehicle on that arc. Looking at the values of the emission factor for capacity utilizations of 25, 50, 75 and 100 %, shows that the emission factor increases linearly in dependence of the payload. This means that Ubeda et al. (2010) in principle perform a discretization of the function used by Kuo (2010) to five values of the payload q ij .

While Suzuki (2011), Kuo (2010), Kuo and Wang (2011) and Ubeda et al. (2010) use a fuel-based function similar to Eq. (1) for estimating CO2 emissions, all other papers discussed in Sect. 2 use different approaches for estimating the load dependent CO2 emissions. They either use a weight-based or a load-based objective function. Weight-based functions assume that the amount of emitted CO2 is linearly dependent on the actual weight of the vehicle including empty weight and load (Bektas and Laporte 2011; Scott et al. 2010) and load-based functions assume that it is linear dependent on the load only (Kara et al. 2007). Figure 1 illustrates a comparison of the (a) fuel-based, (b) weight-based and (c) load-based function assuming that all three functions have the same value in case of a fully loaded vehicle.

Fig. 1
figure 1

Functions of the specific fuel consumption

In accordance with statutory EU provisions we define four different vehicle categories which are treated in different ways with respect to several regulations for road transportation. These regulations refer to license categories, acceptance tests, weekend lorry ban, blocking plates for heavy trucks, toll charges, etc. For growing truck sizes, the regulations are becoming stricter from category to category. That is why the suggested categories represent a sensible graduation in compliance with current traffic laws. The EU traffic laws have also motivated truck manufacturers to establish these vehicle categories and to offer them on the truck market. What is most important for our investigation is that the proposed vehicle categories differ with respect to the specific fuel consumption and thus CO2 emissions. For all proposed vehicle categories, Table 1 shows the entries for the gross vehicle weight (GVW), the load capacity Q k , and the parameters a k and b k for fuel consumption. The quotient between load capacity and gross vehicle weight is almost similar for vehicles out of the categories VC12,  VC7.5,  VC3.5 (0.46, 0.43, and 0.43 respectively) whereas this fraction is much better for vehicles from category VC40 (0.63). The values of the parameters a k and b k are average values which have been determined empirically based on information of carriers published in the Internet (e.g. Spritmonitor 2013; Eurotransport 2013). The values of a k and b k in Table 1 are considered to be typical for an ecologically oriented driving style and for the employment of efficient vehicles on long distance routes in an area with only moderate ascending slopes on streets with long sections on highways. The variable q in the last column of Table 1 denotes the weight of the cargo carried by a vehicle.

Table 1 Classification of vehicle categories

The values of Table 1 determine the efficiency of vehicles out of different categories in terms of their specific fuel consumption in dependence of their degree of capacity utilization. Note that, for a vehicle of category VC40, a utilization of 10 % means a carriage of 2.5 tons which corresponds to a utilization of 77 % for a vehicle out of category VC7.5. The amount of fuel needed for the transportation of one ton of payload over a distance of 100 km is denoted as net fuel consumption. For the carriage of 0.5 tons by means of a vehicle out of category VC40 the specific net fuel consumption is \((( 26 + 0.5\cdot0.36)/0.5) = 52.36\) liter per 100 km and each ton of carried goods while this specific value amounts to 19.31 l for category VC3.5. But in case of carrying 25 tons, the specific net fuel consumption for category VC40 is only 1.4 l per 100 km and ton. Figure 2 demonstrates the vehicle specific increase of fuel consumption when the load transported between two locations is steadily increasing up to 7.5 tons. It can be seen that at low loads, small vehicles out of lower categories are advantageous, whereas at high payloads large vehicles out of upper vehicle categories are to be preferred since in that case several vehicles out of a lower category would be needed for transportation.

Fig. 2
figure 2

Functions of the specific fuel consumption in dependence of the payload

The EVRP-VC represents the decision task to compile routes for arbitrarily available different-sized vehicles so that the fuel consumed by the deployed vehicles is minimal. Each customer location must be visited exactly once and it is not allowed to overload a vehicle.

3.2 Problem modeling

A mathematical formulation for the EVRP-VC is built by extending the traditional formulation for the CVRP proposed by Dantzig and Ramsey (1959). Two major extensions are needed in order to reflect the specific requirements of the EVRP-VC:

  1. 1.

    The weight q ijk of the payload transported by vehicle k along the arc (ij) must be determined for all triples (ijk). This weight is added to the vehicles’ empty load in order to determine the overall weight to be moved along arc (ij). From this weight, we can calculate the required fuel.

  2. 2.

    The objective function must be modified according to function F k in Eq. (1).

For the remainder of this article we use the indexes \(i,j\in I:=\{0,1,\dots,n\}\) to refer to locations (location 0 represents the depot). A vehicle is labeled by the index \(k\in K:=\{1,\dots,m\}\). The distance between location i and j (the length of arc (ij)) is named d ij . We use π j to refer to the demand requested by the customer at site \(j\in I. \) The demand π 0 requested at the depot is assumed to be zero.

Each vehicle of the considered fleet is described by a triple (a k b k Q k ). The fuel consumption of the empty vehicle k (per kilometer) is given by a k . With b k , we label the fuel consumption for the payload of vehicle k per ton and per kilometer. The maximal payload capacity of vehicle k is stored in the parameter Q k .

We use four decision variable families for coding feasible solutions of the EVRP-VC. The first family of binary decision variables \(y_{ik}\in\{0, 1\}\) (\(i\in I, k\in K\)) is used to represent the decision whether customer location i is served by vehicle k. The second family of binary decision variables \(x_{ijk}\in\{0, 1\}\) (\(i,j\in I, k\in K\)) is used to store the routing decisions. The payloads carried along the arcs (ij) by vehicle k are stored in the family of continuous decision variables q ijk . Finally, we use the vector of continuous decision variables u i (\(i\in I\)) to setup constraints that prevent short cycles that do not contain the depot.

$$ \sum_{i=0}^n x_{ijk} = \sum_{i=0}^n x_{jik}\quad \forall k\in K, \quad\forall j\in I $$
(2)
$$ \sum_{i=0}^n x_{ijk} = y_{jk}\quad \forall k\in K, \quad\forall j\in I $$
(3)
$$ \sum_{k=1}^m y_{jk} = 1 \quad\forall j\in I\setminus\{0\} $$
(4)
$$ \sum_{j=1}^n x_{0jk} \leq 1 \quad\forall k\in K $$
(5)
$$ u_i - u_j + n\cdot\sum_{k=1}^m x_{ijk} \leq n-1 \quad\forall i\in I, \forall j\in I\setminus\{0\} $$
(6)
$$ \sum_{j=1}^n \pi_j\cdot y_{jk} \leq Q_k\quad \forall k\in K $$
(7)
$$ \sum_{i=0}^n q_{ijk} - \sum_{i=1}^n q_{jik} = \pi_j\cdot y_{jk}\quad \forall k\in K,\quad \forall j\in I\setminus\{0\} $$
(8)
$$ q_{ijk} \leq Q_k\cdot x_{ijk}\quad \forall k\in K,\quad \forall i\in I, \forall j\in I $$
(9)
$$ q_{ijk} \geq 0 \quad\forall k\in K, \forall i\in I, \quad\forall j\in I $$
(10)
$$ u_i \geq 0\quad \forall i\in I $$
(11)
$$ x_{ijk}\in\{0,1\} \quad\forall k\in K, \forall i\in I,\quad \forall j\in I $$
(12)
$$ y_{ik}\in\{0,1\} \quad\forall k\in K,\quad \forall i\in I $$
(13)

The constraint families (2)–(13) are setup in order to code the feasible route collections for the EVRP-VC. The usual route building restrictions of a CVRP are given by the constraint families (2)–(6) including the Miller-Tucker-Zemlin formulation (6) for eliminating short-cycles that do not contain the depot (see e.g. Toth and Vigo 2002). Because of the constraint set (8) the constraint family (6) could have been omitted in this model but it has been included out of performance reasons. The general capacity constraint family (7) from the CVRP formulation is extended by the constraint sets (8), (9) and (10) for determining the weights to be moved along the arcs contained in the vehicle routes. Constraint set (8) is responsible for balancing the inbound and the outbound flow of goods at the customer locations. These equations enable the determination of the amount of the payload flow on each edge. Any transportation on unused arcs is inhibited by the constraint family (9). Otherwise it would be possible that the demanded quantities take paths differing from those of the vehicles. Finally, the transport of negative payload is excluded by the constraint family (10).

$$ \sum_{i=0}^n\sum_{j=0}^n\sum_{k=1}^m \left(d_{ij}\cdot \left(a_k\cdot x_{ijk} + b_k\cdot q_{ijk}\right)\right)\rightarrow\min $$
(14)
$$ \sum_{i=0}^n\sum_{j=0}^n\sum_{k=1}^m d_{ij}\cdot x_{ijk}\rightarrow\min $$
(15)

By using the q ijk -values and the x ijk -values we calculate the overall sum of needed fuel as described in the EVRP-VC-objective function (14). We are seeking for a route set that minimizes (14) while it respects the constraint families (2)-(13). The evaluation of a feasible CVRP-solution (which is the sum of traveled distances) is done by calculating the objective function value according to (15). A CVRP-solution minimizes (15).

Additionally to the EVRP-VC and the CVRP we consider a third model called EVRP. The EVRP strives for the minimization of fuel consumption for the case that a homogeneous fleet of vehicles of vehicle category VC40 is used. We use VC40 as the only vehicle category for the EVRP out of the following reason. It is advantageous to choose big vehicles from category VC40 since these vehicles are needed for achieving good solutions for most of the problem instances. Otherwise there is no good chance for bundling of customer requests and a lot of pendulum tours will occur for all customer requests which have a demand nearly as high as the downsized capacity of the available vehicles. If the capacity of the chosen vehicle type is even lower than the demand of one of the customers of a problem instance, then there will be no feasible solution for that instance.

The determination of a solution of the EVRP-VC, EVRP or CVRP requires the clustering of requests into tours (RTAP: request-to-tour assignment problem) and the sequencing of the requests in the tours (RSP: request sequencing problem). The EVRP and CVRP objective values are not affected by the way of assigning vehicles to routes; i.e. all feasible mappings of routes to vehicles are equivalent for the EVRP and the CVRP. The minimization of the EVRP-VC objective function value (14) requires a decision on an appropriate assignment of routes to vehicles from different vehicle categories. Thus, a third decision problem (RVAP: routes to vehicle assignment problem) must be solved. Obviously, the RVAP is correlated with the RTAP and the RSP.

3.3 Construction of test cases

The general setting valid for all scenarios is as follows: The relevant locations are positioned randomly in the square [0, 300] × [0, 300]. One depot is maintained and located at the coordinates (175,150). We define two sets of artificial test scenarios (UTILIZATION and REQUESTSIZE) in order to evaluate the proposed decision model and to reveal the potentials for emission reduction. Footnote 1

Test set UTILIZATION. This test set is designed in order to compare the CVRP, EVRP and EVRP-VC for small problem instances with an average total demand below 25 tons. In case that the total demands of all customers are less than 25 tons, the required transportation tasks can be fulfilled by a single tour of a VC40 truck. The goal of the analysis performed on the test set UTILIZATION is to show whether and to which extend the segmentation of routes into several smaller routes has the potential to reduce CO2 emissions. This is an exiting question since segmentation usually is not a means to get to improved solutions for vehicle routing problems. Segmentation in inapplicable as long as the triangle inequality is valid for the objective function of the routing problem. But for the EVRP-VC, segmentation may have a positive effect on the solution quality. For all test instances of UTILIZATION we assume that the number of available vehicles per category is chosen in that way that each instance could be solved by a homogeneous fleet out of any category; i.e. the solution space will not be restricted by a limitation of the available vehicles. It should be mentioned that the number of available vehicles for the homogeneous fleet is unlimited, too.

For the test set UTILIZATION, we investigate scenarios with three different amounts of total demands which correspond to three degrees γ of average capacity utilization of a VC40 truck: 65, 80 and 95 %. That means, the average of total demands of all customers is set to 16.25 tons (γ = 65 %), 20 tons (γ = 80 %), and 23.75 tons (γ = 95 %), respectively. It has to be ensured that an adequate part of the customers of the test instances can be served by small vehicles. That is why four intervals are defined for potential customer demands while each interval is adapted to one of the existing vehicle categories. Let DI3.5 denote the demand interval [0.1 tons, 1.5 tons] which means that customers having a demand within this interval can be served by a VC3.5 truck or any larger truck. Let DI7.5, DI12 and DI40 denote the interval [0.1 tons, 3.25 tons], [0.1 tons, 5.5 tons], [0.1 tons, max{25 tons, total demand/4}], respectively. Then, the number of customers and the individual demand quantities of these customers are chosen in a way that the total demand is almost evenly spread over the four intervals. For each interval, the actual customer demands belonging to an interval are randomly chosen and assigned to random customer locations from the area [0, 300] × [0, 300]. Overall, five location seedings are combined with five demand seedings for each of the three average capacity utilizations, which results in 3 × 25 = 75 test instances. Since each instance is alternatively solved using the CVRP, EVRP and the EVRP-VC, 225 test cases have to be run. Table 2 shows the number of customers and the sum of the customer demands for each interval in accordance to the chosen utilization degree.

Table 2 Instance composition in the UTILIZATION test set

As the actual customer demands are generated randomly and independently for each demand interval, it may occur that the total demand will exceed 25 tons, which means that one single vehicle of category VC40 is not able to fulfill all transportation tasks. This may predominantly happen in case of a utilization degree of 95 %. This is the price to be paid for a very high average utilization degree. This is fair in comparison to the smaller vehicle categories since they also have the risk that the randomly generated demand will slightly exceed their specific capacity and since, in general, capacity utilizations of 95 % or even more are not realistic also for the usage of small vehicles in the EVRP-VC.

Test set REQUESTSIZE. This collection of test sets is designed to analyze fuel reduction potentials associated with different average request weights. Each test case comprises 15 requests. Their positions are randomly fixed in the area [0, 300] × [0, 300]. Five different spatial settings are used. All demand quantities are randomly drawn from the interval [0, β], so that the average weight associated with a request is \(\frac{\beta}{2}\) tons. Test cases are generated for the maximal request weights \(\beta\in\{1,2,\ldots,7\}\). For a given maximal weight β, each of the five available request location settings is combined with five different request weight sets. The average sum of request weights is \(15\times\frac{\beta}{2}\).

The fleets assigned to each request set are configured in dependence of the maximal request weight β. In order to test the effect of introducing different vehicle categories, we assume that the number of vehicles available for each vehicle category will not be restrictive; i.e., there will be enough vehicles available from each category to generate any feasible solution of the considered test instances of the CVRP, EVRP and EVRP-VC. Overall, the set REQUESTSIZE comprises 3 × 7 × 25 = 525 test cases because the EVRP-VC-model as well as the CVRP- and EVRP-model are parameterized by the 7 × 25 = 175 data sets.

4 Evaluation of the model

This section reports computational experiments for the evaluation of the proposed EVRP-VC model and its comparison with the EVRP model and the CVRP model. The setup of the conducted experiments is described in Subsect. 4.1, followed by a presentation of results which have been achieved with CPLEX (Subsect. 4.2) for the two proposed test sets UTILIZATION and REQUESTSIZE.

4.1 Experimental setup

In order to validate and evaluate the proposed model, all 750 scenarios are processed by the CPLEX-solver. We know from previous experiments (Kopfer and Kopfer 2012) that instances of the proposed extent are in general manageable for this approach. Although we expect that this straightforward approach is not able to solve instances of high complexity, we aspire to get insights into differences between least distance solutions and least fuel solutions in case of the availability of a heterogeneous fleet with different vehicle categories.

All calculations are performed on a 64-bit Windows 7 professional system (Intel Core i5-2410 processor, 8 GB memory) using CPLEX Optimization Studio 12.4 and OPL. We set the maximal allowed solving time to 15 min (900 s). The average solving times \(T(\cdot)\) are calculated from the individually recorded solving times for each γ-value and for each β-value.

The following performance indicators are recorded and evaluated for each test set (\(\sigma\in\{\hbox{CVRP}, \hbox{EVRP}, \hbox{EVRP-VC}\}\)).

  • The average total driving distance for a given payload utilization γ is stored in DD(γσ) and the average fuel consumption of the fleet is saved in FC(γσ) accordingly. Similarly, we store the average driving distance and the average fuel consumption observed for different maximal request weights β in DD(βσ) and FC(βσ).

  • In order to compare the fuel consumption of the EVRP-VC respectively the EVRP with the CVRP for different β-values we calculate the relative variations of consumed fuel \(\Updelta FC(\beta,\hbox{EVRP-VC})\) by \(\Updelta FC(\beta,\hbox{EVRP-VC}) = \frac{FC(\beta,\hbox{EVRP-VC})-FC(\beta,\hbox{CVRP})}{FC(\beta,\hbox{CVRP})}\) respectively by the quotient \(\Updelta FC(\beta,\hbox{EVRP}) = \frac{FC(\beta,\hbox{EVRP})-FC(\beta,\hbox{CVRP})}{FC(\beta,\hbox{CVRP})}. \) The fuel consumption variation \(\Updelta FC(\gamma,\sigma)\) is determined in the same way.

  • The travel distance variations \(\Updelta DD(\beta,\sigma) = \frac{DD(\beta,\sigma)-DD(\beta,\hbox{CVRP})}{DD(\beta,\hbox{CVRP})}\) as well as \(\Updelta DD(\gamma,\sigma)\) are additionally computed.

  • We count the average number of routes for each vehicle category and save the computed average numbers in V 40(βσ), V 40(γσ),  V 12(βσ), V 12(γσ), V 7.5(βσ), V 7.5(γσ), V 3.5(βσ) and V 3.5(γ, σ) respectively. The overall number of installed routes are stored in V(βσ) and in V(γσ) respectively.

  • For each route of a deployed vehicle, its payload indicator is calculated as follows. The length of a traversed arc is multiplied with the payload weight moved along this arc. These products are summed up for all arcs in the route. The average category-specific indicators for the payload-ton-kilometers are computed and stored in L 40(γσ), L 12(γσ), L 7.5(γσ) and L 3.5(γ, σ) for the test set UTILIZATION and in L 40(βσ),   L 12(βσ), L 7.5(βσ) and L 3.5(β, σ) for the test set REQUESTSIZE.

  • The mass indicator for measuring the moved mass of a route is calculated similarly as the payload indicator. Instead of multiplying the payload with the length of a traversed arc, we multiply the total moved mass (vehicle dead weight plus payload) with the arc length. The averagely observed total values for mass-ton-kilometers are stored in M 40(γσ),   M 12(γσ), M 7.5(γσ) and M 3.5(γ, σ) for the UTILIZATION test set and analogously in M 40(βσ), M 12(βσ), M 7.5(βσ) and M 3.5(β, σ) for REQUESTSIZE.

4.2 Presentation and discussion of results

This subsection reports on the comparison of the EVRP, CVRP and the EVRP-VC for the test sets UTILIZATION and REQUESTSIZE.

4.2.1 Results from the test set UTILIZATION

All scenarios from the test set UTILIZATION have been solved by CPLEX within the granted maximal solving time. Solving an EVRP-VC instance requires significant more time than solving the corresponding EVRP or CVRP instance. In comparison to the CVRP, the computation time needed for the EVRP-VC is increasing by the factor 2.5 (for γ = 65 %), the factor 5.3 (for γ = 80 %) and by the factor 10.6 (for γ = 95 %).

Table 3 summarizes the averagely computed fuel consumptions and the average travel distances. Averaged over all problem instances of the test set UTILIZATION, the EVRP-VC is able to realize a total fuel consumption reduction of 11.31 % in comparison to the CVRP, while the averaged value for the total driving distance is increased by 28.82 % (see also Fig. 3).

Table 3 Fuel consumption and route length (UTILIZATION)
Fig. 3
figure 3

Variation of fuel consumption and travel distance in the UTILIZATION experiments

The computational experiments show that the deviations of the characteristics of the optimal solutions are relatively small in case that the CVRP and the EVRP are compared while they are relatively large when the EVRP-VC is considered. A comparison of the EVRP and the CVRP has already intensively been discussed in literature by several authors (see the literature review in Sect. 2 for details). The values reported in literature for the deviations between the travel distances and fuel consumption of the CVRP and the EVRP are similar to the observations observed in our experiments. Since these deviations have been analyzed intensively in literature and since they are relatively small compared to the deviations observed with respect to the EVRP-VC, we concentrate our analysis of the computational experiments on a comparison of the CVRP and the EVRP-VC.

Table 4 shows the average number of routes for deployed vehicles of different categories (EVRP-VC) and the total numbers V(γσ) of installed routes. It is worth to mention that VC40 trucks are used for EVRP-VC in almost all problem instances. Additionally, light vehicles are preferentially used to take over the fulfillment of requests with a low demanded weight.

Table 4 Average number of routes for different vehicle categories (UTILIZATION)

The values for the indicator measuring the payload-oriented ton-kilometers are shown in Table 5. The VC40 trucks still contribute the major part of the payload-ton-kilometers (at least 89 %) and smaller vehicles do not contribute more than 11 %. Compared to the CVRP respectively EVRP, the overall amount of payload-ton-kilometers of the EVRP-VC is significantly reduced by at least 39 % (γ = 65 %) up to 52 % (γ = 80 %) respectively by at least 24 % (γ = 65 %) up to 29 % (γ = 80 % and γ = 95 %).

Table 5 Payload-ton-km with category contribution in brackets (UTILIZATION)

Table 6 contains the computed average total mass indicator of the generated routes considering also the weight of the deployed vehicles. Again, we observe significant reductions for the EVRP-VC experiments compared to the CVRP and EVRP experiments. Although the number of generated routes is increased in the EVRP-VC experiments compared to the CVRP and EVRP experiments, we still detect significant reductions of the total moved mass. In comparison to the CVRP, this reduction amounts between 24 % in the γ = 65 %-cases and 36 % in γ = 80 %-cases.

Table 6 Mass-ton-km with category contribution in brackets (UTILIZATION)

Figure 4 contains graphical representations of optimal solutions of a problem instance UTILIZATION with a capacity utilization degree γ = 80 %. The thickness of the arcs corresponds to the capacity of the truck used for a route. An arrow indicates the driving direction along an arc. A distance minimal round trip for a VC40 truck through all customer sites is computed in the CVRP planning situation and shown in the right picture. For the EVRP-VC (left picture) five shorter round trips are determined. The big trucks are used for relative short routes that serve customers sites close to the depot. Longer routes serving customer sites far away from the depot but demanding low weights are assigned to small vehicles.

Fig. 4
figure 4

Optimal solution of the EVRP-VC (left), the CVRP (right) for a problem instance from UTILIZATION with γ = 80 % (filename: S1-80-CAPSEED1-LOCSEED5.dat)

In summary, we found that introducing and deploying a heterogeneous fleet has drastically reduced the fuel consumption in our experiments and, on the other hand, has increased the travel distances to great extent. It has been shown that segmentation is a powerful means for the improvement of plans for vehicle routing in case that fuel minimization is aspired for a heterogeneous fleet. Compared to the CVRP, the number of routes generated for the EVRP-VC is nearly increased by the factor 3. This is mainly due to the fact that different types of vehicles are needed and only to a small extend due to the fact that the travel activities are increased. The travel activities measured in total travel distances are only increased by 20.49 %. The additional distances as well as a part of the distances run by a VC40 truck in the CVRP-solutions are substituted by running small vehicles in the EVRP-VC-solutions. That is why the burden of traffic may even decrease depending on the measure which is used for quantifying the traffic burden. This can be seen at the payload indicator and the mass indicator whose values are averagely reduced by 48 and 33 %, respectively.

4.2.2 Results from the test set REQUESTSIZE

For the experiments using instances of the test set REQUESTSIZE, we have also set the maximal allowed solver running time to 900 s. All CVRP experiments and all EVRP experiments have been successfully completed with a running time below 900 s. The recorded computational times for the EVRP-VC experiments are significantly longer and in our experiments not all instances could be solved to optimality. Table 7 reports for each value of β the average computation times (in seconds) as well as the prolongation factors and Table 8 reports the number of optimally solved instances as well as the average optimality gaps (sum of all gaps for a given β-value divided by 25). The optimality gap is defined as the deviation of the best lower bound from the best identified feasible solution. Although the optimality gaps found after 900 s of computation are rather small these gaps do not reduce significantly if the maximal allowed computation time is enlarged to 3,600 s. We have checked this in computational experiments. The averaged results presented in the remainder of this section are based on the best feasible solutions found after 900 s computation time.

Table 7 Average solving times in seconds (REQUESTSIZE)
Table 8 Number of solved instances and optimality gaps (REQUESTSIZE)

The fuel consumptions, travel distances as well as the variations of fuel consumption and travel distances are shown in Table 9. The comparison of CVRP, EVRP and EVRP-VC with respect to fuel consumption and travel distance is illustrated in Fig. 5. Again, we concentrate on the comparison of the CVRP with the EVRP-VC since the observed deviations between CVRP and EVRP are relatively small. The difference between the sum of needed fuel as well as the difference between the sum of total travel distances observed for the two scenarios EVRP-VC and CVRP decrease if the average request weight increases. The experiments demonstrate that the highest fuel savings are possible if the set of used vehicles is highly heterogeneous and if the average request weight is relatively small.

Table 9 Fuel consumption and route length (REQUESTSIZE)
Fig. 5
figure 5

Variation of fuel consumption and travel distance in the REQUESTSIZE experiments

The average request weight influences the choice of vehicle categories (see Table 10). For small-weight requests (β ≤ 3) applying the EVRP-VC leads to the incorporation of a significant number of small vehicles from category VC3.5, so that the number of routes is increased by a factor larger than 4 compared to the CVRP-optimal solution. For medium-weight requests (4 ≤ β ≤ 6), the number of routes in the optimal solutions of EVRP-VC is increased by less than one. For β = 7 we even observe an increase of the number of incorporated VC40 trucks in the fuel minimal solutions (2.64 trucks) compared to the distance minimal solutions (2.60 trucks).

Table 10 Number of routes (REQUESTSIZE)

Independently from the average request weight, the payload indicator of the mixed fleet is significantly improved in comparison to the homogeneous fleet as concluded from the results shown in Table 11. Compared to the homogeneous fleet of the CVRP less than 80 % of payload-ton-kilometers are needed to fulfill all customer requests by the mixed fleet of the EVRP-VC. For very light-weighted requests (β ≤ 2) the required payload-ton-kilometers are more than halved. If the average request weight exceeds one ton (β ≥ 2) then the vehicles of category VC40 contribute the largest portion to the overall payload-ton-kilometers. The contributions of the three remaining vehicle categories to the total amount of payload-ton-kilometers is very small but its incorporation finally leads to a significant reduction of the consumed fuel and therefore results in a reduction of CO2-emissions. Similar results are observed if the mass indicator based on the sum of the vehicle weight and payload is considered (Table 12). For requests with less than 3 tons, the mass indicator is reduced by at least 30 % if EVRP-VC is applied instead of the CVRP. For larger request weights, the sum of mass-ton-kilometers is reduced by 14 % independently of the average request weight if a mixed-fleet is used in a fuel minimizing mode.

Table 11 Payload indicator in tkm with category contribution in brackets (REQUESTSIZE)
Table 12 Mass indicator in tkm with category contribution in brackets (REQUESTSIZE)

Figure 6 shows optimal solutions for a problem instance with an average request weight of 2 tons (β = 4). In the EVRP-VC solution the number of generated routes is 3. One vehicle of category VC40 is used together with one vehicle of category VC7.5 and a van of category VC3.5. In the associated CVRP solution two routes for vehicles of category VC40 are deployed. The VC40 truck serving the pendulum route in the CVRP solution is replaced by a vehicle of category VC7.5. In the EVRP-VC solution, another pendulum tour is set up and assigned to a vehicle of category VC3.5. The length of the route of the still used vehicle of category VC40 is reduced significantly. As a result of these modifications the fuel consumption is reduced by 10 % while the sum of travelled distances increases by 18 % in the EVRP-VC solution compared to the corresponding CVRP solution. Furthermore, the payload indicator is reduced by 13 % and the mass indicator is lowered by 21 %.

Fig. 6
figure 6

Optimal solution of the EVRP-VC (left), the CVRP (right) for a problem instance from REQUESTSIZE with β = 4 (filename: S2-BETA4-CAPSEED5-LOCSEED4.dat)

The performed experiments approve that the consideration of fuel minimization instead of distance minimization as optimization goal for a heterogeneous fleet impacts the way of clustering and routing observed in the generated solutions. The smallest (and therefore lightest) available vehicles are used to serve small-sized customer requests (clustering effects). Switching from travel distance minimization to the minimization of fuel consumption results in different customer request arrangements within the tour of a vehicle (routing effects). In order to keep the fuel consumption as low as possible, customer sites requiring the heaviest goods (largest quantities) are visited as early as possible in a route in order to keep traveling with heavy payload as short as possible.

4.3 Fuel Efficiency Considerations

Fuel efficiency can be measured by the number of length units that are traveled using one fuel unit. Thus, the fuel efficiency for a solution of a problem instance is given by the quotient of travel distance and fuel consumption. In the UTILIZATION test set the fuel efficiency is defined by the quotient \(\frac{DD(\gamma,\sigma)}{FC(\gamma,\sigma)}\) and in the REQUESTSIZE test set the fuel efficiency is defined by the quotient \(\frac{DD(\beta,\sigma)}{FC(\beta,\sigma)}\)

Tables 13 and 14 show the fuel efficiency values derived from the results which have been presented in Subsect. 4.2 In the CVRP, the fuel efficiency is neither affected significantly by the variation of the utilization rate γ in test set UTILIZATION nor by the maximum request weight β in test set REQUESTSIZE. Anyway, it can only vary between the values 2.86 (for a fully loaded vehicle of category VC40) and 3.86 (for an empty vehicle of category VC40). For the EVRP-VC the achieved fuel efficiency is improved compared to the equivalent CVRP solutions. The utilization degree γ as well as the maximum request weight β impact the fuel efficiency as it can be seen from Tables 13 and 14. If the average request weight increases then the size of the deployed vehicles becomes larger so that the fuel efficiency advantage is diminishing.

Table 13 Fuel efficiencies in the UTILIZATION test set
Table 14 Fuel efficiencies in the REQUESTSIZE test set

We have evaluated the proposed EVRP-VC model within several experiments with different request portfolio sizes. Referring again to the previous results, the following observations are important. First, the solutions of the EVRP-VC lead to an increase of the total number of routes compared to CVRP solutions and EVRP solutions. Second, minimizing the fuel consumption of the heterogeneous fleet implicates the generation of short routes which are suitable for vehicles with a low payload. Third, even if the minimization of the fuel is targeted then vehicles of category VC40 are needed to keep the overall amount of CO2-emissions as low as possible. If vehicles of different vehicle categories are available then the fuel minimization requires the incorporation of vehicles from all different categories.

One major drawback of the EVRP-VC-optimal solutions is that they consist of significantly more routes than the equivalent solutions of the CVRP and EVRP. It is important to note that the number of vehicles as well as the number of drivers used for the EVRP-VC are not necessarily identical to the number of generated routes. Since most of the routes of an optimal solution of the EVRP-VC for a problem instance are much shorter than the CVRP-optimal or EVRP-optimal routes of the same instance, the multiple use of vehicles (allowing one vehicle to fulfill more than one route) will in many cases reduce the number of used vehicles in the EVRP-VC solutions. If we assume the same average speed for all vehicle categories, the increase of driving hours of the EVRP-VC compared to the CVRP or EVRP will be proportional to the increase of travel distances (i.e. averagely 18.5 % in the CVRP-experiments for our test sets). The increase of driving times will be even less since smaller vehicles can realize a higher average speed. Since we do not consider any time windows and since drivers may switch to different vehicles, the number of needed drivers is determined by the amount of required driving hours and is far below the number of generated routes. Furthermore, it can be assumed that the idle time of some vehicles can be used fruitfully, e.g. by fulfilling additional requests which are not part of the problem instances considered in our experiments.

5 Conclusions and future research

The here reported research can be understood as a proof of concept to demonstrate that fuel consumption optimization and distance minimization differ a lot in case that vehicles of different size are introduced. Obviously, further research is needed to get more insight into the potentials of this approach.

Traditional goals of the operational vehicle deployment strive to minimize the totally traveled distances of the fleet. This is mainly motivated by the assumption that energy consumption and traveled distances are in a proportional relation. However, in road-based freight transportation, the weight to be moved (vehicle net weight plus payload) contributes to the overall consumed fuel. Consequently, the total fuel consumption is determined by the fact that a vehicle is traveling (moving its net weight plus the actual payload). Since available decision models ignore the influence of the actually carried gross weight for vehicles of different size, we have proposed a new class of vehicle routing problem (EVRP-VC). The EVRP-VC explicitly aims at minimizing the fuel consumption needed for the generated services. Compared to traditional vehicle routing, we replace the distance minimizing objective function by a vehicle-specific affine linear fuel consumption function. Additional constraints to determine the actual payload along a vehicle route have been established. These additional constraints (i.e. Eqs. 8, 9 and 10 in the model in Subsect. 3.2) do not affect the search space of any of the models for CVRP, EVRP or EVRP-VC. They are only needed by the EVRP and by the EVRP-VC in order to get to know and to evaluate the quantity q ijk of goods that are transported by a vehicle k over an arc (ij).

We have validated the proposed formal decision model using a mathematical solver. The potential to save fuel has been shown. The usage of heterogeneous fleets of vehicles with different payload capacities and fuel consumption opens up the exploitation of so far unused potential for saving CO2 emissions. Solutions of the EVRP-VC show that this potential can reach a significant reduction. The price to be paid for this reduction is that the total travel distances as well as the number of routes for the used vehicles increase significantly. As a consequence, additional congestions may occur and this may in turn be a factor for increasing the external costs of transportation. Admittedly, the assumption of the EVRP-VC that there will always be enough vehicles available for each vehicle category is rather unrealistic. But the optimal solution of the EVRP-VC delivers a reference value for the fuel consumption and amount of CO2 emissions in case that an idealized heterogeneous fleet would be available. This reference value will in practice often be exceeded due to the limitations of the available fleet but it can be reached by a smart strategy for sub-contracting requests to carriers operating the suitable types of vehicles.

The next step of our future research will focus on the possibility of multiple use of vehicles followed by an analysis of the impact of time windows for the EVRP-VC. In summary, the solving of the EVRP-VC is a promising and important but computationally very challenging task. The investigation of the fuel saving potentials of large request portfolios requires the configuration of adequate heuristic search procedures. This is a currently conducted research project. For balancing the aforementioned benefits and drawbacks, an extended model with an integrated cost function considering fuel consumption, travel distances and fixed costs of the vehicles is necessary. This is also a prospective research project. The influence of the request portfolio composition requires a deeper analysis. Furthermore, we will investigate how a short-term fleet adjustment can be realized at acceptable costs, e.g. by exploiting short time vehicle rental concepts.