New Hybrid Algorithm Based on BicriterionAnt for Solving Multiobjective Green Vehicle Routing Problem ()
1. Introduction
Green transportation issues are increasingly showing interest from theoretical, political and social perspectives. Transport activity has a high rate of negative effects on the environment, due to pollutants and the greenhouse effect. The consequences of its emissions are climate change and health complications, reasons why emissions from the transport sector must be reduced, the WHO reports that diesel fumes create several diseases such as lung cancer (International Agency for Cancer Research, 2012). Nevertheless, scientific works that deal with GVRP with the objective of minimizing CO2 emissions are rare and new in the literature.
Indeed, the combustion of fossil fuels in internal combustion engines produces carbon dioxide CO2, the propagation of which in the atmosphere contributes to the greenhouse effect and global warming. It should be noted that one liter of fuel produces approximately 2.4 kg of CO2 during combustion, a value which depends on the type of fuel (petrol, diesel, natural gas ...) and its density.
CO2 emissions are directly proportional to vehicle fuel consumption. [1] To quantify emissions, several calculation methods exist. Each method takes into account on average 6 to 14 different factors influencing the amount of GHG (Greenhouse Gas) emissions evaporated.
The classic VRP neglects current environmental concerns and deals primarily with economic return. It is therefore important for policy makers to apply restrictive regulations to control greenhouse gas emissions. All of these concerns have drawn the attention of researchers to the Green Vehicle Routing Problem (GVRP) [2] .
Some authors have proposed approaches and algorithms to solve the GVRP. In 2015 A. Moutaoukil et al. [3] worked on the minimization of CO2 emissions in distribution circuits with heterogeneous fleet, its strength lies in modeling a vehicle routing problem using a heterogeneous fleet, but one of the limits of this proposal lies in the high computation times which only allow small instances to be taken into account. N. Rezaie et al. [4] in 2019 studied a problem of routing green vehicles with time windows considering the heterogeneous fleet of vehicles: two metaheuristic algorithms. The comparison showed that the proposed algorithms provide high-quality solutions with regard to objective functions. The paper has some limitations. First, it can be merely applied to products (or problems) that hard time windows are suitable for them, such as newspaper, meat, vegetable, etc. Second, the practitioners must have the knowledge to use the results of this paper in the real world. Júlio César Ferreira et al. [5] in 2021 proposed for a two-objective green problem a New hybrid optimization algorithm CWNSGA-II and CWTSNSGA-II applied to the distribution of a newspaper, he has the advantage of having obtained superior results for case studies and literature instances, but the difficulty in selecting the best route from a utility function that is often not easy to set up. In 2021 Joydeep Dutta et al. [6] proposed a hybrid multi-objective evolutionary algorithm for open green vehicle routing problem through cluster primary-route secondary approach. This model suggests a solution based on the managers “decision makers” choice from a set of alternative solution.
In this article, the GVRP has been studied, where a central repository provides the demand of customers using a heterogeneous fleet of vehicles. In addition, it was assumed that the rate of fuel consumption depends on the distance traveled and the load of the vehicles as well as the type of vehicle used.
To formulate the problem, a bi-objective model of combinatorial linear programming has been proposed [7] . Thus, the model simultaneously minimizes the total transport costs and the CO2 emissions of the vehicles during a tour. In the literature, some authors have proven that even simple variants of VRP are NP-hard, like [8] [9] , not to mention the more complex variant of GVRP studied in this article.
In this paper, we make a hybridization of three heuristic approaches to solve the two-objective green vehicle routing problem. This new hybrid algorithm called BicriterionAntAPE is a general, globalizing, high-level hybridization that combines the strengths of each heuristic. The interaction between them is seen by the fact that the heuristics are launched one after the other, each taking the output produced by the previous one. In the literature, most authors use a genetic algorithm to solve the VRP. After finding interesting individual routes, routes are then improved using the 2-opt method followed by the 3-opt [10] . What is new in this article, however, is that the solution found by BicriterionAnt is improved by APE, which is easier to apply instead of the usual r-opt type methods.
Generally the VRP is an NP-hard routing problem defined on a graph
where V is a set of n nodes (customers) and E a set of m edges, consisting of a fleet vehicle of capacity Q based in a depot node. Each edge
has a traversal cost
and a demand
from customer i as as shown in Figure 1.
The objective function can be either: the minimization of the number of vehicles used, the minimization of the total distance traveled by the vehicles, the
Figure 1. Graphical presentation of the VRP.
minimization of the total duration of the routes, the minimization of the total cost of the routes (taking into account the costs of the vehicles, drivers, the minimization of penalties related to violation of constraints, particularly in the case of time windows, the maximization of gains generated by rounds the objectives of minimizing the number of vehicles and the total distance (or duration) of rounds are conflicting because the reduction in the number of vehicles most often leads to an increase in the total distance travelled.
2. Position of the Problem
Solving the multi-objective vehicle routing problem (MOVRP) by so-called exact methods presents many difficulties for medium and large-sized instances. Ant colony algorithms solve this type of problem in a reasonable time and provide good quality approximate solutions [11] .
Ant colony-based algorithms were originally proposed in [12] [13] [14] . They have been successfully applied to several combinatorial problems like the traveling salesman problem, quadratic assignment, vehicle routing, multidimensional knapsack, etc. We then extend this study to the case of multi-objective optimization problems, where the choice of a phenomenal structure is even more difficult. We propose, in this work the resolution of a case study of the GVRP with two objectives to do this, it is essential to choose the appropriate phenomenal strategy, hence the choice of the BicriterionAnt (ACO) algorithm proposed by Iredi et al. [15] .
To calculate CO2 emissions, we used the method proposed by Zhang et al. [16] . We therefore assumed two fuel consumption rates. The first is for the vehicle when unloaded (empty load) and the second is for the same vehicle when loaded to its maximum capacity. Then, taking into account the load and the distance traveled by the vehicles, the CO2 emissions per each unit of distance will be determined.
3. Literature Review
The vehicle routing problem was first introduced in the literature by Dantzig and Ramser in 1959 [17] . They work on a study dealing with the truck dispatch problem in a vehicle routing problem (VRP) with capabilities and specific constraints to serve groups of customers in different geographical locations from a central warehouse. These vehicles may or may not return to the central depot.
As pointed out by Reimann [18] , the VRP and all its variants form an important problem in logistics and have been the subject of much research, such as recently by [19] [20] [21] . When the vehicle belongs to the company, the vehicle must return to the central depot, we then speak of VRP closed; otherwise we speak of VRP Open. Sariklis and Powell [22] first introduced the term Open Vehicle Route Problem (OVRP) this was followed by several published papers on OVRP problems using multiple methods/algorithms for their solution. Dutta, Barma, Kar [23] recently applied a modified version of Kruskal’s method and a hybrid algorithm of genetic algorithms to solve OVRP.
Gutierrez et al. [24] studied a new variant of VRP where time is a random variable. Eshtehadi et al. [25] in turn have explored another facet of uncertainty in slotted VRP; they took demand and travel times as uncertain parameters, they discussed three approaches to analyze uncertainty: soft worst case, hard worst case and chance conditions.
Kopper et al. [26] proposed a mathematical method to study heterogeneous GVRPs simply targeting CO2 emissions, in this paper, different types of vehicles were taken into account as well as the consumption rates of different types of fuels used, payload and mileage.
Yang et al. [27] on the other hand proposed a multi-objective model to deal with GVRP; this mathematical model seeks to minimize operating costs and CO2 emissions while maximizing the level of customer satisfaction, unlike Masmoudi et al. [28] they considered the fill function in the problem. However, they took into account a homogeneous fleet of vehicles. They first proposed a MILP (Mixed Integer Linear Problem) model of the problem, and then developed a two-step hybrid heuristic algorithm for a home care system where a patient may need the services of several specialists at the same time.
4. Multi Objective Programming
Most real world optimization problems are complex and one of the aspects contributing to this complexity is their multi-objective nature Durillo et al. [29] . In optimization works, including multi-objective optimization, the emphasis is on finding the global optimum or Pareto front yielding the best possible values of the Deb et al. [30] . For others, multi-objective (or multi-criteria) optimization is a process aimed at systematically and simultaneously optimizing a collection of objective functions Marler et al. [31] .
In general, a multi-objective optimization problem can be defined as:
avec
Under the constraints
and
where m is the number of functions to optimize,
is the vector of decision variables,
is vector of the criteria to be optimized,
and
represent respectively m inequality constraints and p equality constraints. This set of constraints delimits a restricted space of feasible solutions that one will note D.
The image of a solution x in the criteria space is the point
with
and
representing the feasible points in the objective space.
We impose on this set a partial order relation called dominance relation that we will define in the next point.
4.1. Notion of Pareto Dominance
A solution
dominates a solution
if
,
and
.
If the solution y dominates the solution z it will be denoted
. For any pair of solutions y and z one and only one of the following cases can occur: y dominates z or y is dominated by z or aigain y and z are equivalent in the sense of dominance.
Equivalent solutions in the sense of dominance are called in what follows, equivalent solutions in the sense of Pareto or Pareto equivalent solutions or again, non-dominated solutions.
4.2. Optimization by Ant Colonies for Multi-Objective Problems
According to Dorigo et al. [32] ACO algorithms have several advantages in their applications in different, of which several discrete optimization problems are successful. The majority of these problems are NP-hard and the application of ACO algorithms has allowed finding good quality solutions in a reasonable time.
Some variants of the first ACO algorithm named Ant System [12] based on the behavior of artificial ants such as the Max-Min Ant System, Ant Colony System, or Rank-Based Ant System algorithms have emerged, these extensions were implemented due to the fact that despite the encouraging results of Ant System, it was not competitive enough against state of the art algorithms, especially for large-scale problems (such as genetic algorithms).
ACOs are part of combinatorial optimization techniques that have been designed to solve multi-objective problems often having conflicting objectives. An overview of ACO algorithms allowing multi-objective problem solving is available in Garcia-Martinez et al. [33] . These algorithms are gathered under the name of MOACO (Multiple Objective ACO). We can distinguish two families of MOACO algorithms: Pareto and Non-Pareto. MOACO algorithms based on a Pareto evaluation method (Pareto-based MOACO) consist in generating solutions on the Pareto front by applying the principles of Pareto-dominance. The best known algorithms of this family are: CPACO [34] , MOAQ [35] , PACO-MO [36] , BicriterionAnt [37] , BicriterionMC [37] and ACO-bQAP [36] .
4.3. Ant Colony Algorithm
The ACO algorithm was proposed by Dorigo to choose the shortest path in the traveling salesman problem (TSP). It implements the use of ant trail pheromones when searching for the shortest path from their nest to the food source as shown in Figure 2. In this article the BicriterionAnt version particularly caught our attention to solve our problem of touring green vehicles with two objectives.
We first present the initial algorithm Ant Colony System (ACS) which allows finding the shortest Hamiltonian cycle in a graph.
4.4. Data and Rating
● Let
be an undirected graph.
● The finite set V of vertices represents customer.
● The finite set
of edges linking the vertices together.
●
represents the edge weights
(the distance between vertex i and vertex j).
●
gives the length of the circuit u representing the total distance traveled during the tour by the ant k.
●
is the value of the pheromone trail at time t on edge
.
●
the total number of customer.
●
is the constant indicating the visibility of customer j from customer i.
4.5. Transition Choice
Each ant has a memory that will be emptied once the cycle is over, allowing it to avoid returning to a customer already visited. An ant k found in customer i at time t chooses customer j as its destination according to two parameters: the visibility
and the pheromone density
of the edge connecting it, depending on the value of
.
(1)
where
is the probability that ant k chooses j from i.
is the set of unvisited neighbors of vertex i by ant k in the current cycle,
and
are parameters that control the importance that the ant gives to an edge (intensification/diversification).
4.6. Pheromone Update
At the end of each cycle (each ant has traversed the n vertices that make up the graph), the traces of the pheromones are updated according to the formula:
(2)
where
is an evaporation coefficient such that
.
is the evaporation of the pheromone.
(3)
represents the quantity of pheromones per unit length deposited on the edge
by the kth ant between t and
, it is given by:
with,
: the length of the turn of the kth ant.
Q: a constant positive number.
5. Presentation of the BicriterionAnt algorithm
The BicriterionAnt algorithm was proposed by Iredi et al. [15] especially to solve the bi-criteria vehicle routing problem. It uses two different pheromone trail structures,
and
, one for each criterion considered.
At each generation, each of the m ants in the colony generates a solution to the problem. During the solution construction step, the ant chooses the next vertex j to visit relative to the probability
(4)
for each m ants calculate the exchange rule
as follows:
(5)
Once all the ants have built up their solutions, the pheromone trails are evaporated by the usual ACO rule. Since there are two variables for pheromone information and heuristic information, the pheromone evaporation process is performed using:
(6)
(7)
Then, each ant that has generated a solution in the Pareto front in the current cycle is allowed to update the two pheromone structures,
and
, by depositing an amount equal to:
(8)
where
is the number of ants that are updating the pheromone trails. The non-dominated solutions generated throughout the execution of the algorithm are put into an external set.
6. Adjacent Pairwise Exchange Algorithm (APE)
APE is a local search heuristic, which allows obtaining achievable results in a reasonable period of time; it is used to bring an improvement in the quality of a given solution. The APE algorithm starts with a given admissible solution, thereafter, it will search in the vicinity of the current solution for any solution to improve the current configuration. At each step of the improvement procedure, the algorithm tests whether the exchange of two adjacent sums (cities) produces a feasible solution to improve the solution and the algorithm continues in this way until we can no longer improve. APE helps the BicriterionAnt algorithm to explore the search area more strongly in order to find other solutions.
7. Algorithm k-Means
Consider a total of n customers. The demand of each customer is known in advance. The n customers are geographically dispersed over a space, and whose position of a customer is represented by its coordinates
with
. The coordinate
is gives the position of the central repository. Each customer must be served by one and only one vehicle. Each client belongs to a cluster. Customers who belong to the same cluster are served by the same vehicle, hence the total number of clusters is the total number of vehicles used.
Consider that all n clients are grouped into m clusters and their requests are
.
The number of vehicles used (the number of clusters) can be obtained by:
(9)
with
the load capacity of the vehicle.
Consider that the Euclidean distance
between any customers i of a cluster is symmetric, it can be determined by:
(10)
where
and
.
Let M be the assignment matrix, which represents which client is assigned to which cluster
if customer i is assigned to cluster j; 0 otherwise.
Thus, the problem of assigning customers to different clusters can be formulated mathematically as
(11)
(12)
(13)
It is therefore a minimization problem, which seeks to minimize the distance. Constraint (12) represents that each customer is assigned to a single cluster, and constraint (13) is the vehicle or cluster capacity constraint.
The above problem of allocating customers to different clusters can be solved by any clustering method like k-means algorithm. This algorithm finds customer clusters based on customer locations and Euclidean distances to centroids. However, the classical k-means algorithm operates on randomness. The modified k-means algorithm works well in the context of VRP by imposing some specific constraints such as:
● Instead of an arbitrary choice of the value of k, it is appropriate to choose the value of k as the number of vehicles using Equation (9).
● It is better to start by choosing the centroid of the cluster as the depot so that all clients always come to the position closest to the depot.
● It is better to focus first on customers with higher demands than others.
● Instead of choosing customers randomly for different clusters initially, it is better to calculate the Euclidean distance of each centroid and then assign it to the nearest cluster.
Figure 3 shows the structure of our hybrid algorithm BicriterionAntAPE.
8. The Main Formulas for Calculating CO2 Emissions
The main formulas for calculating CO2 emissions The Carbon Footprint makes it possible to estimate the impact of an activity on the environment. It was developed in 2004 by the ecological transition agency ADEME, which established that the emission factor for road freight transport is evaluated at 3.07 (kg CO2/tonnes.km). CO2 emission factors indicate the quantity of CO2 emitted during the combustion of a given fuel and for a unit of energy taken.
Four ways to calculate the amount of CO2 emitted during a tour or service
Figure 3. Flowchart of the hybrid BicriterionAntAPE algorithm.
according to different parameters such as energy consumption rate (TC), emission factor (EF), distance (d), vehicle capacity (CV) and the number of units transported in the vehicle (UT). One of them is the following: The energy source consumption is not known for the service in particular, and the means of transport concerns several beneficiaries. On the one hand, it is necessary to estimate consumption using average consumption and the journey, and on the other hand, to distribute the emissions among the beneficiaries. The calculation formula is
(14)
For this purpose, we assumed two fuel consumption rates. The first is for the vehicle of the type k when unloaded
, and the second is for the same vehicle when loaded to its maximum capacity
then, taking into account the type, load and distance traveled by the vehicles, the CO2 emissions per unit distance will be determined based on the equation:
(15)
where
: the CO2 emission rate,
: is the maximum load capacity of a vehicle the type k and
: is the vehicle load.
9. Description of the Problem
Our problem consists of two objective functions. The first objective seeks to minimize the overall distance of the transport and the second is that of minimizing the CO2 emissions of each vehicle during a round. In fact, the most common definition of VRP is the design of optimal routes by a fleet of homogeneous or heterogeneous vehicles located in one or more depots to serve a number of geographically dispersed customers with known demand. This general definition highlights a set of parameters that characterize VRP variants: Transport networks, customers and vehicle fleets. Additional constraints can be added to these three parameters.
10. Formulation of the Selected Problem
Following the brief description of the problem given above, we formulate the problem to be solved as follows:
(16)
(17)
(18)
(19)
(20)
(21)
(22)
(23)
(24)
(25)
(26)
(27)
(18) Each client
is visited once and once. (19) If vehicle k arrives at customer j, it must leave. (20) and (21) Each must return to the depot at the end of their tour. (22) compliance with the maximum duration T of the trips. (23) Elimination of sub-tours to ensure route connectivity. (24) Ensures that each vehicle k could carry a load less than or equal to its maximum capacity
. (25) Gets
for a value greater than zero. (26)
if the vehicle of type k visits j, and 0 otherwise . (27)
flux of the arc
loaded in the vehicle of type k ensure that the flux variables are non-negative.
To arrive at routes that produce the minimum of CO2 emissions, it is essential to build a matrix of CO2 emissions based on the estimate of CO2 emitted during the course of each ridge. In this paper, only diesel engines complying with the most recent standards in force are taken into account. For good service performance, the constraint linked to the maximum duration is set at 5 hours for vehicle rounds with an average speed of 55 km/h for urban areas.
11. Analysis of Results
To test the proposed algorithm on the instances in the literature, the Matlab R2021a software allowed us to do the coding, installed on a laptop with an Intel (R) Celeron (R) with a CPU@1.60 GHz processor and 8 GB of RAM, with a 64-bit operating system.
We applied our hybrid BicriterionAnt algorithm to solve some VRP instances from the literature such as Golden_4, Golden_8, Golden_7 proposed by Golden, Wasil, Kelly, and Chao (1998) and X-n167-k10, X-n106-k14, X-n143-k7 proposed by Uchoa, Pecin, Pessoa, Poggi, Subramanian, and Vidal (2013). For NSGAII and SPEA2 the parameters used are: Iterations = 200, Population = 100, Crossover = 0.7, mutation = 0.3.
Case Study
Here we apply our BCAntAPE hybrid method to the problem of a dairy products company has a central depot and a range of uniform delivery vehicles with a maximum capacity of ten tonnes. The demands of its 15 customers are known; we consider the distances between symmetric customers and verify the triangular inequality, as shown in Table 1.
Table 1. Matrix of distance between customers.
Table 2 gives the characteristics of the heavy duty vehicle (HDV) [38] used are:
We tested the algorithms by varying the number of ants from 4, 3, and 2. We considered the following parameters as shown in Table 3.
From the results obtained in Table 4 we see that a minimum CO2 pollution is not guaranteed for vehicles taking the shortest route. However, several common routes exist (i.e. the visit sequences are the same with different optimization goals).
Table 5 shows the results obtained by NSGAII, SPEA2, BCAnt and BCAntAPE for Golden_4, Golden_8, Golden_7, X-n167-k10, X-n106-k14 instances and X-n143-k7 relative to OF1 and OF2.
12. Performance Measures
Four metrics were used to evaluate the performance of the algorithms, in order to perform a comparative analysis between them. The metrics called M1, M2 and M3, taken from Zitzler et al. [39] , refer respectively to the evaluation of the quality, the distribution and the extension of the Pareto front generated by the algorithm. The fourth metric called Error was taken from Veldhuizen [40] and refers to the percentage of generated solutions that do not belong to the Pareto Front.
In all cases, the Euclidean distance between two points is used as the distance metric, represented by
, and F is taken as the known Pareto front and
Table 2. The characteristics of HDV.
Table 3. Parameter description table.
Table 4. The statitics of differents algorithms.
Table 5. The summary results of all the instances using BCAnt, BCAntAPE, SPEA2 and NSGAII.
as the Pareto front generated by the algorithms. The four measures used are defined below.
(28)
The metric M2 uses a set
, given a problem dependent distance value
and is calculated as follows:
(29)
The M3 metric calculates the extension of the generated Pareto front according to:
(30)
The error metric is calculated as follows:
(31)
where
takes the value 0 if the ith solution of
belongs to F, 1 otherwise.
The metrics M1, M2 and M3 have been normalized with respect to their maximum value; in this way the results obtained represent percentages which are used to compare the various algorithms in the set of test problems.
For the metric M2, the value of
was used as ten percent of the distance between the point with the best evaluation in the first objective and the point with the best evaluation in the second objective of the front F, so
represents ten percent of the distance between the extreme points of F for each particular problem.
In the used instances of the VRP problems, the BCAntAPE and NSGAII obtain better results than SPEA2 and BCAnt. As shown in Table 6, BCAntAPE for M2 has the second best average relative distance to the Pareto edge, metric M3, it gives the best result regarding the average of the Pareto edges closer to the optimal than the other algorithms. We see that BCAntAPE produced the best result for the M1 metric. Finally, he obtained the second best result in relation to the metric E.
From what precedes the algorithm proposed in this paper, the BCAntAPE has been shown to be as competitive as the other algorithms retained such as NSGAII, SPEA2 and BCAnt.
Table 6. Results of the different metrics.
13. Practical Perspectives
Through the above analyzes, several findings from this research have direct managerial insights into the delivery problem. The results show that the routes which minimize the total distance traveled by the vehicles are different from those which minimize the CO2 pollution; this can be understood by the fact that the objectives are conflicting.
In this study we also found that the optimal route reduces product CO2 by almost 7.2% compared to the worst route. Thus, taking road traffic congestion factors into account is an important way to reduce logistics costs and CO2 emissions.
14. Conclusions
This article studied the multiobjective problem of routing green vehicles. The objective of the proposed model is not only to minimize the total distance traveled by the vehicles of the fleet but also to take into account the carbon emissions of the latter while satisfying the demands of each customer, in addition to that we assumed two fuel consumption rates. The first is for the vehicle of type k when unloaded, and the second is for the same vehicle when loaded to its maximum capacity.
Depending on the characteristics of the selected model, a hybrid metaheuristic has been proposed. This hybrid metaheuristic is based on an extension of the ant colony algorithm BicriterionAnt and an APE improvement heuristic has been associated in order to solve the selected problem.
A case study on a fuel delivery problem was processed to find vehicle routes that pollute less CO2 and minimize the total distance travelled.
The application of the new BicriterionAntAPE hybrid algorithm is strongly limited to the two-objective problem only and using a single colony for both pheromone structures limits intense exploration of the search area.
Future research might focus on uncertainties for different parameters like travel time, service time, operating costs, etc.