Emissions Minimization Vehicle Routing Problem in Dependence of Different Vehicle Classes

Abstract

This contribution presents a specific objective function referring to sustainability within vehicle routing and it proposes an extension of “green” vehicle routing problems by introducing an inhomogeneous fleet. For the basic problem it is assumed that the amount of CO₂ emission depends on the distances to be travelled and on the degree to which the used vehicles are loaded. The goal of minimizing the total travel distance is contrasted with the goal of minimizing the total amount of emission. The basic problem is extended by the availability of various types of vehicles with different capacities and specific fuel consumption. This work includes a mathematical formulation of the extended problem and a small instance that illustrates the problem. Computational experiments for the basic and the extended problem formulation are performed by using CPLEX.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Introduction

The extremely high amount of emission caused by road transport gives reason for intensifying the research on ecologically oriented vehicle routing. The amount of CO₂ emission is proportional to the amount of fuel consumed for the fulfillment of tours (ICF 2006). An example for green transportation planning on the operational level is given by Kara et al. (2007). In this approach the fuel consumption related to a transportation plan depends on the flow of transported quantities. But fuel consumption and consequently CO₂ emission are a function of the actual weight of the used vehicles (Figliozzi 2010a; Ubeda et al. 2010) including their dead weight.

The approach introduced in this paper presents a new green version of the traditional Vehicle Routing Problem (VRP) (Dantzig and Ramser 1959). This new version aims at reducing CO₂ emissions by applying an objective function based on realistic values for the fuel consumption of modern trucks. This introduced version of an ecological VRP is called EVPR throughout this paper. Furthermore, the EVRP is extended by considering different types of trucks with specific CO₂ emissions. The extended problem introduced here is called the Emission Minimization Vehicle Routing Problem with Vehicle Categories (EVRP-VC).

Ecological Objectives and the Operational Environment

There are only few approaches for ecological vehicle routing and scheduling in literature. They mostly aim at minimizing the emitted CO₂ by considering e.g. the average speed (Figliozzi 2010a), average speed combined with acceleration rates (Figliozzi 2010b), topology (Scott et al. 2010; Ubeda et al. 2010) or the payload (Jaramillo 2010; Scott et al. 2010). Scott et al. (2010), Ubeda et al. (2010) analyze the carbon dioxide emission of fleets with various vehicle types and utilization rates. None of the known publications considers individual fuel consumption functions for accurately defined vehicle classes.

The model presented in this paper is 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 ton-kilometers. To the best of the knowledge of the authors, there is no approach presented in literature which considers and investigates these two extensions.

The vehicle categories (see Table 1) proposed in this paper are defined in accordance with the current regulations in the EC. The relevant regulations refer to license categories, acceptance tests and toll charges. The suggested categories represent a sensible graduation in compliance with current traffic laws. This has also motivated the manufacturers to establish these vehicle categories. The proposed vehicle categories differ with respect to the specific fuel consumption and thus CO₂ emissions. Table 1 shows the entries for fuel consumption which are empirical values based on information of carriers and of test reports for vehicles (see e.g. Spritmonitor 2012, Eurotransport 2012). The variable q in column 4 of Table 1 denotes the weight of the cargo carried by a vehicle.

Table 1 Classification of vehicle categories

Figure 1 shows a first simple example. For a given scenario, the difference between possible optimal solutions of the VRP on the left side and the EVRP-VC on the right side is demonstrated. In case of the VRP, one large vehicle serves all locations in a single tour providing the minimum distance solution. In order to minimize the CO₂ emission, the EVRP-VC generates a solution with three smaller vehicles out of several vehicle categories.

Fig. 1

Clustering and sequencing of the vehicles by different objective functions

The plan on the left side and the plan on the right side do not only differ with respect to the clustering but also with respect to the sequencing of the customers. In the left plan, customers are served in the sequence q ₈, q ₁₀, q ₉ before the vehicle returns to the depot. On the right side, an ecological oriented objective function is assumed. That is why it is possible that the solution deviates from the shortest path in order to obtain a solution with minimal emissions. In the case shown here, the weight of the customer request q ₉ is very high. As a consequence, the emission is reduced by serving this customer q ₉ first before travelling to q ₁₀.

The flexibility of sequencing the customers is increased when several sub-tours are considered instead of an entire big tour. For Example, the orientation of the tour q ₁, q ₂, q ₃ can be determined independently of the orientation of the other tours on the right side. In contrast, changing the orientation of the sub-tour q ₁, q ₂, q ₃ on the left side will affect the integration of this sub-tour in the total tour.

The comparison of the VRP, the EVRP and the EVRP-VC is illustrated using a small example. The example consists of one depot at location [0] and 7 customer locations [1,…,7]. Table 2 shows the distance between each pair of locations.

Table 2 Distance matrix D (one depot [0] and seven customers [1,…,7]); distance $d_{ij}$ in (km)

The customer demands (given in brackets) are as follows: customer 1 (0.5 t), customer 2 (1 t), customer 3 (2 t), customer 4 (4 t), customer 5 (3.5 t), customer 6 (8 t) and customer 7 (4 t). The sum of all customer demands is 21 t, i.e., all customers can be served by a single vehicle out of category VC ₄₀. The optimal solutions for the above example have been generated by our approach which will be presented in section Computational Experiments. The results are shown in Table 3. The solution for the EVRP-VC of this example is illustrated in Fig. 2.

Table 3 Solutions for the different models

Fig. 2

Vehicle routing by using the EVRP-VC

Because of the triangle inequality, the VRP and the EVRP will always use only one vehicle if there is a vehicle which is big enough to serve all customers in a single tour. That is why, and for reasons of a fair comparison, the VRP and the EVRP are using within this example only the vehicle out of category VC ₄₀, although the EVRP could possibly save fuel by using the smallest vehicle which is big enough to serve all customers. The optimal routes generated for the VRP and EVRP differ. Compared with the VRP, the EVRP-solution reduces the fuel consumption slightly by 1.5 % and increases the traveled distance by a small amount of 1.9 %. The optimal solution of the EVRP-VC shows that using trucks of different categories can reduce the amount of CO₂ emission tremendously (by 13 % compared to the EVRP and by 14.5 % compared to the VRP). On the other hand, the number of used trucks increases considerably. As a consequence, the sum of the lengths of the routes is also increasing significantly (by 22.3 and 24.7 % for the VRP and EVRP, respectively).

Model Formulation

The mathematical formulation for the EVRP-VC is built by extending a traditional VRP-formulation (Dantzig and Ramser 1959). The main extensions are:

• 1. the vehicle specific values for the load dependent fuel consumption must be considered in the objective function (if these vehicle specific values are equal for all available vehicles, the EVRP-VC turns out to be an EVRP),

• 2. the weight q _ijk of the goods transported by vehicle k from location i to location j must be known for all i, j, k and must be considered in the objective function.

Indices:

$i,\,j$ :

Locations: $i,j \in I$ where 0 represents the depot, $I = \left\{ {0,1, \ldots ,n} \right\}.$

$k$ :

Vehicles: $k \in K$ where k describes the vehicle parameters, $K = \left\{ {1, \ldots ,m} \right\}.$

Parameters:

$d_{ij}$ :

Distance between locations $i$ and $j .$

$q_{j}$ :

Demand of customer $j$ for $j = 1, \ldots ,n$.

Constants:

$a_{k}$ :

Fuel consumption of the empty vehicle $k$ per kilometer.

$b_{k}$ :

Fuel consumption for the load of vehicle $k$ per ton and kilometer.

$Q_{k}$ :

Maximum load capacity of vehicle $k.$

Variables:

$q_{ijk}$ :

Cargo of vehicle $k$ traveling between locations $i$ and $j$

$x_{ijk}$ :

1 if vehicle $k$ serves location $j$ immediately after serving location $i$,

0 otherwise.

$y_{jk}$ :

1 if location j is served by vehicle $k$,

0 otherwise.

$u_{i}$ :

Arbitrary real variable.

Objective Function:

$$ { \hbox{min} }\mathop \sum \limits_{i = 0}^{n} \mathop \sum \limits_{j = 0}^{n} \mathop \sum \limits_{k = 1}^{m} d_{ij} \cdot \left[ {a_{k} \cdot x_{ijk} + b_{k} \cdot q_{ijk} } \right] $$

(1)

Subject to:

$$ \mathop \sum \limits_{j = 1}^{n} q_{j} \cdot y_{jk} \le \, Q_{k} \quad \forall k \in K $$

(2)

$$ \sum\limits_{{i = 0}}^{n} {x_{{ijk}} } = \,\sum\limits_{{i = 0}}^{n} {x_{{jik}} } \quad \forall k \in K;\forall j \in I $$

(3)

$$ \mathop \sum \limits_{i = 0}^{n} x_{ijk} = y_{jk} \quad \forall k \in K;\forall j \in I $$

(4)

$$ \mathop \sum \limits_{k = 1}^{m} y_{jk} = 1\quad \forall j \in I\backslash \{ 0\} $$

(5)

$$ \sum\limits_{{j = 1}}^{n} {x_{{0jk}} } \le \,1\quad \forall k \in K $$

(6)

$$ u_{i} - u_{j} + n\mathop \sum \limits_{k = 1}^{m} x_{ijk} \le n - 1\quad \forall i \in I;\forall j \in I\backslash \{ 0\} $$

(7)

$$ \mathop \sum \limits_{i = 0}^{n} q_{ijk} - \mathop \sum \limits_{i = 1}^{n} q_{jik} = q_{j} \cdot y_{jk} \quad \forall k \in K; \forall j \in I \backslash \{ 0\} $$

(8)

$$ q_{ijk} - Q_{k} \cdot x_{ijk} \le \, 0\quad \forall k \in K;\forall i \in I;\forall j \in I $$

(9)

$$ q_{ijk} \ge \, 0\quad \forall k \in K;\forall i \in I;\forall j \in I $$

(10)

$$ u_{i} \ge \, 0\quad \forall i \in I $$

(11)

$$ x_{ijk} \in \{ 0,1\} $$

(12)

$$ y_{jk} \in \{ 0,1\} $$

(13)

The objective function (1) minimizes the fuel consumption. Constraints (2–7) and (11–13) are the usual restrictions of the VRP with an MTZ formulation using the variables $u_{i}$ in (Eq. 7) for subtour elimination (see e.g. Toth and Vigo 2002, p 13). The usual VRP formulation is enlarged by constraint sets (8, 9 and 10). Constraints (8) are responsible for balancing the flow of goods. These equations allow the determination of the amount of the freight flow on each edge. Constraints (9) inhibit any transportation on unused edges. 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 constraints (10).

Computational Experiments

Using the plain VRP as a basis for our investigations has the advantage that CPLEX can be used on a personal computer with 4 GB active store and a 2.6 GHz processor for solving problem instances up to a size of ten customers, four truck categories and twelve trucks to optimality within a few seconds. Additionally, focusing on the VRP has the benefit that the analysis and comparison of the models can show the pure effects of the ecological objective function and the net effect of introducing truck categories. The introduction of time windows would have made the situation and its analysis much more complicated.

For the computational experiments we assume that a heterogeneous fleet with an unlimited number of vehicles for each category of Table 1 is available. We consider 10 problem instances with one depot at location [0] and 10 customer locations [1,…,10]. The locations are equal for all instances. They have been generated randomly with the depot in the center of the distribution area. Table 4 shows the common distance matrix for all instances.

Table 4 Distance matrix (one depot [0] and ten customers [1,…, 10]); distance $d_{ij}$ in (km)

The customer demands for the considered problem instances are given in Table 5. They have been arranged in a systematical and balanced way. For instances 1–4, all customers of an instance demand identical quantities, whereas the quantities are increasing from instances 1 to 4. For instances 5–10, the demands of different customers vary within a single instance. For these instances, the total demand of all customers is increasing starting with 13.5 t and ending with 31 t. The total demands and the individual demands are equal for instances out of the pairs (5,6), (7,8) and (9,10). The instances within a single pair only differ with respect to the assignment of demands to the customers.

Table 5 Demand matrix [demand q in (to)]

The results of the experiments are shown in Table 6. Compared to the VRP, the average fuel consumption related to the 10 solutions of the EVRP can be reduced by 4.26 % from 152.46 l to 145.96 l, whereas the traveled distances on average increase by only 0.3 % from 527.2 km for the VRP to 528.9 km for the EVRP. This comparison clearly shows that, at least for the 10 instances considered in this paper, the EVRP produces solutions with slightly increased tour lengths but with a considerable decrease with respect to fuel consumption. In general, the experiments demonstrate that it is worth to investigate the characteristics and the advantages of the EVRP in more detail and to analyze the trade-off between the solutions of the VRP and the EVRP. For six instances of Table 6, the length of the routes generated for the VRP and the length of those generated for the EVRP are totally equal. The VRP-solutions and the EVRP-solutions for these six instances differ only with respect to the orientation of the generated routes. The VRP is indifferent to reversing the orientation of routes, i.e., a given solution and the solution with the reverse order for serving the customers are considered to be equal. For the EVRP this is not true because the fuel consumption depends on the actual weight of the vehicle on the legs of the entire route. That is why the EVRP-solution always chooses the orientation with less fuel consumption. This orientation is referred to as “light” orientation whereas the other one is referred to as the “heavy” one. Considering all instances of Table 6 with equal tour length, the average difference between the fuel consumption (fc) for the “heavy” orientation (shown in Table 6 as fc for the VRP) and for the “light” orientation (shown as fc for the EVRP) amounts to 5.46 l. This means that in Table 6 most of the fuel reduction (84 %) that has been achieved by switching from the VRP to the EVRP is realized by choosing the right orientation of the shortest route.

Table 6 Fuel consumption (fc) and distances (d) in dependence of the chosen objective function

The results of Table 6 which have been attained for the EVRP-VC show that a huge potential for fuel saving can be reached by introducing an inhomogeneous fleet of vehicles.

Applying the EVRP-VC, the average fuel consumption for the instances of Table 6 decreases to 115.9 l, which means a reduction of 24 % compared to the VRP. It is worth to mention that the amount of reduction varies a lot over the considered instances from 3 % (instance 10) to 60 % (instance 1). Even very similar instances differ a lot with respect to the potential of the EVRP-VC to reduce fuel consumption and to increase travel distances. See e.g. instances 9 and 10 having identical customer demands which have been assigned to the customers in a different way. The numbers of used vehicles as well as the traveled distances are increasing drastically by applying the EVRP-VC instead of the VRP. The travel distances increase on average by 16 % and the number of used vehicles is increased for seven of ten instances. For the instance 3, there are even five vehicles used instead of one vehicle for the VRP. In order to reduce the problems arising from a heterogeneous and enlarged own fleet, the remedy of subcontracting suitable requests to specialized carriers with small and cheap vehicles is recommended. This can keep the increase of costs within a limit since the regulations for smaller vehicles are much more lax to many respects.

Conclusions and Future Research

The results of the computational experiments show that it is worth to solve the EVRP additionally to the VRP and to contrast these two approaches and the solutions generated by them. Introducing heterogeneous fleets of vehicles with different capacities and fuel consumption opens up a tremendous potential for saving CO₂ emissions. Solutions of the EVRP-VC show that this potential can reach a reduction of 20 % and even more. The price to be paid for this reduction is that the total travel distances as well as the number of used vehicles increase drastically. 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 will be developed.

For a continued analysis of the relations among the VRP, EVRP and EVRP-VC, it is necessary to expand the above experiments. On the one hand, several characteristic scenarios represented by sensibly configured large sets of problem instances have to be defined and analyzed. On the other hand, powerful heuristics are needed to enable the solution of the relevant optimization models for typical medium sized and large sized problem instances. Finally, in successive research, conclusions for the configuration of vehicle fleets can be derived.