1 Introduction

In real world applications, most of the optimization problems have more than one objective functions for optimization. Thus, one way to solve these problems (besides the multicriteria optimization, the hierarchical optimization, the goal programming and so on) is the use of an evolutionary multiobjective approach where the finding of the Pareto Front of the non-dominated solutions is needed [13]. One of the problems in the supply chain management that could be formulated as a multiobjective optimization problem is the vehicle routing problem (VRP) as a number of different objectives functions could be used. The VRP belongs to the class of NP-hard optimization problems [34]. For an overview of the VRP please see [45, 77, 78]. In real world applications in order to prove that the quality of the routes is good enough usually more than one criterion are optimized. Thus, in recent years a large number of Multiobjective Vehicle Routing problems have been published [36]. The multiobjective vehicle routing problem (moVRP) is a VRP problem where simultaneous optimization of more than one objective functions is required. For more information about moVRPs please see [43].

In recent years, the optimization of energy reduction or fuel consumption in the Vehicle Routing Problem and other problems has been studied. The calculation of the tonne-kilometers (tonne-km or tkm) of the vehicle taking into account the covering distance and the load of the vehicle could be an easy way to calculate the “Fuel Efficiency” and the “\({ CO}_2\) emissions” of a vehicle [37, 55, 56]. Considering the Leonardi’s et al. research [47] the “Efficiency of the vehicle use” can be calculated by a ratio tonne-kilometres / mass-kilometres and in order to calculate the “\({ CO}_2\) Efficiency” they assume that there are some other real route and environmental parameters that are multiplied with the “Efficiency of the vehicle use” in order to calculate the “\({ CO}_2\) Efficiency” of a vehicle. In order to calculate the mass-kilometres, the weight of the empty vehicle is added to the load of the vehicle. Another parameter that can be taken into account for the calculation of fuel consumption is the parameter of speed [5, 6, 25, 42, 49, 74]. Xiao et al. [80] propose the fuel consumption rate (FCR) for a VRP (FCVRP) in order to minimize the fuel consumption using the distance traveled and the load. The FCR and the “\({ CO}_2\) emission rate” (CER) were used by Zhang et al. [83] in order to calculate the amount of \({ CO}_2\) emissions of a vehicle. A bi-objective green vehicle routing problem was proposed in [33] in order to minimize the total traveled distance and the \({ CO}_2\) emissions. In this research it is referred that in real world problems the vehicle’s load, the vehicle’s speed, the weather conditions (head-winds or back-winds) and the traffic congestion are factors that could affect the fuel economy of a vehicle. The slope of the road (measured in grades between 0 and 10 %) could affect the \({ CO}_2\) emissions of a vehicle [12, 79]. In [17] a bi-objective pollution routing problem’s model is proposed where the first objective function minimizes the \({ CO}_2\) emissions of a vehicle and the second objective function minimizes the driving time. For two more complicated multiobjective Energy VRPs please see [41, 59]. Two other energy Pick-up and Delivery VRP models are analyzed in [50, 75]. Some other \({ CO}_2\) emissions minimizing models are presented in [10, 23, 38, 39, 48, 76]. Also, \({ CO}_2\) emissions could be minimized by creating shortest routes and by traveling with the best speed for the environment [70]. For a more extended review for the energy and green vehicle routing problems please see [44, 51].

In this paper, three parallel multi-start non-dominated differential evolution algorithms (PMS-NSDEs) are used for the solution of the proposed problems. In order to apply the differential evolution algorithm [63, 73] in multiobjective optimization problems the single objective algorithm has to be modified in such a way in order to calculate the set of non-dominated solutions. The two main issues that they should be solved in a multiobjective differential evolution algorithm are how the diversity of the solutions will be maintained and how to retain and select the best individuals [8, 57]. A number of multiobjective differential evolution algorithms have been applied mainly in continuous optimization problems and in some cases in combinatorial optimization problems [1–4, 9, 32, 40, 62, 66, 67, 71, 81, 82].

Although the differential evolution algorithm is suitable for continuous optimization problems, in the last years a number of publications concerning the application of the differential evolution algorithm in single and multiobjective routing problems have been produced. In 2009, Erbao and Mingyong [20] proposed a hybrid intelligent algorithm based on the Differential Evolution algorithm in order to solve the vehicle routing problem with fuzzy demands. In the next year (2010), the same group of authors, Mingyong and Erbao [58] using an intelligent DE algorithm (IDE) solved a vehicle routing problem with simultaneous pickups and deliveries and time windows and an open vehicle routing problem with fuzzy demands [21]. Three years later Silva et al. [72] solved the capacitated vehicle routing problem using four discrete DE algorithms. In 2014, Erbao et al. [22] solved an open vehicle routing problem with uncertain demands using the IDE algorithm but in that case it is not necessary for the vehicle to return to its initial location after the service of the costumers. In 2015, Marinakis et al. [54] solved a vehicle routing problem with stochastic demands and a probabilistic traveling salesman problem using differential evolution algorithm. Variants of DE algorithm have been used for the solution of the traveling salesman problem (TSP). In [69], Sauer proposed a discrete DE algorithm using two different local search methods for the solution of the TSP while in 2015, Psychas et al. [64] proposed two variants of the DE algorithm in order to solve the multiobjective TSP.

In this paper, for the solution of the multiobjective vehicle routing problems an improved version of the method published in [64] for the solution of the multiobjective traveling salesman problem is presented. In [64], three new trial vector equations have been presented and the produced algorithm, denoted as non dominated sorting differential evolution algorithm (NSDE), used the rank and the crowding distance to sort the solutions of the parents and the offspring of each iteration. The results of the algorithm (in the multiobjective traveling salesman problem) were compared with the results of other multiobjective differential evolution algorithms (MODE) in order to give the efficiency of the proposed methodology. In this version of the algorithm, denoted as parallel multi-start non-dominated differential evolution algorithm (PMS-NSDE), a number of common characteristics with the previous version exist (the three trial vector equations) but also there are four basic differences (improvements) of the proposed algorithm. In the proposed algorithm, more than one different initial populations are created and the step of the algorithm that sorts the parents and the offspring according to the rank and the crowding distance is in a different phase of the algorithm. Also, the VNS method that is used in the proposed research is the same with the one used in [65] and is much more sophisticated than the VNS method that was used at [64]. Finally, in the proposed algorithm there is an extra step that improves the best solutions in every iteration using the proposed VNS method [65]. Also, for this research in order to test the efficiency of the proposed algorithms the parallel multi-start NSGA II (PMS-NSGA II) algorithm is used and is compared with them. PMS-NSGA II is an improved version of NSGA II (non-dominated sorting genetic algorithm) [15, 16] and was originally proposed in [65]. A number of variants of the NSGA II algorithm have been used in the literature for solving multiobjective Vehicle Routing Problems, e.g. for solving VRP with route balancing [35], for solving multiobjective VRP problems with time windows [30] and for solving a green vehicle routing problem [33]. Multiobjective Genetic Algorithms for the solution of Multiobjective Vehicle Routing Problems have been used in [7, 61].

The structure of the paper is as follows. In Sect. 2, the optimization models of the MRFCVRPs are described. In Sect. 3, the proposed parallel multi-start algorithms are presented and analyzed. In Sect. 4, the evaluation measures used in the comparisons are presented. In Sect. 5, the computational results are presented. In Sect. 6, a method to decide the most suitable for a decision maker solution of a Pareto front is proposed and, finally, concluding remarks and the future research are given in the last section.

2 Multiobjective route based fuel consumption vehicle routing problems

In this paper, four multiobjective route-based fuel consumption vehicle routing problems (MRFCVRPs) are analyzed and formulated using three different objective functions that are given in the following. Each of the four problems is a 2-objective optimization problem. The vehicle routing problems analyzed in this research differ between them. Two of them are delivery problems and the other two are pick-up problems. Thus, from the three objective functions presented in this paper the first two are used for the delivery problems while the first and the third objective functions are used for the pick-up problems. This formulation is an improvement of the formulation that was presented in [65] where the multiobjective energy reduction vehicle routing problem was formulated and solved.

For all multiobjective route-based fuel consumption vehicle routing problems (MRFCVRPs) studied in this paper, the first objective function is common for the delivery and the pick-up problems and is used for the minimization of the time needed to travel between two customers or a customer and the depot. Thus, if \(t_{ij}^{\kappa }\) is the time needed to visit customer j immediately after customer i using vehicle \(\kappa \) and \(s_j^{\kappa }\) is the service time of customer j using vehicle \(\kappa \), then, the first objective function is [65]:

$$\begin{aligned} \min { OF}1 = \displaystyle \sum _{i=1}^{n}\displaystyle \sum _{j=1}^{n}\displaystyle \sum _{\kappa =1}^{m}(t_{ij}^{\kappa }+s_j^{\kappa })x_{ij}^{\kappa } \end{aligned}$$
(1)

where n is the number of nodes and m is the number of homogeneous vehicles and the depot is denoted by \(i=j=1\).

The second objective function is used for the minimization of the route based fuel consumption (\({ RFC}\)) taking into account, also, real life route parameters (weather conditions or uphills and downhills or driver’s behavior) [33, 47] in addition to the load and the traveled distance when the vehicle travels between two customers or a customer and the depot in the case that the vehicle performs only deliveries in its route. The vehicle should begin with full load and after a visitation to a customer the load is reduced based on the demand of the customer. If we consider that the more loaded is the vehicle the more fuel it consumes, we take the following objective function:

$$\begin{aligned} \min { OF}2= & {} \displaystyle \sum _{j=1}^{n}\displaystyle \sum _{\kappa = 1}^{m}c_{1j}x_{1j}^{\kappa }\left( 1+\frac{y_{1j}^{\kappa }}{Q}\right) r_{1j} + \displaystyle \sum _{i=2}^{n}\displaystyle \sum _{j=1}^{n}\displaystyle \sum _{\kappa = 1}^{m}c_{ij}x_{ij}^{\kappa }\left( 1+\frac{y_{i-1,i}^{\kappa }-D_i}{Q}\right) r_{ij}\nonumber \\ \end{aligned}$$
(2)

with the maximum capacity of the vehicle denoted by Q, the i customer has demand equal to \(D_i\) and \(D_1=0\), \(x_{ij}^{\kappa }\) denotes that the vehicle \(\kappa \) visits customer j immediately after customer i with load \(y_{ij}^{\kappa }\) and \(y_{1j}^{\kappa } = \sum _{i=1}^{n}D_i\) for all vehicles as the vehicle begins with load equal to the summation of the demands of all customers assigned in its route and \(c_{ij}\) is the distance from node i to node j. The parameter \(r_{ij}\) corresponds to the route parameters from the node i to the node j and it is always a positive number. Due to the fact that it may be \(r_{ij} \ne r_{ji}\) the product \(c_{ij}r_{ij}\) leads to an asymmetric formulation of the whole problem. If the values of \(r_{ij}\) is lower than 1 we consider that the route from i to j is a downhill or the wind is back-wind or the driver drives with smooth shifting. If \(r_{ij}\) is larger than 1 we consider that the route from i to j is an uphill or the wind is a head-wind or the driver drives with aggressive shifting. If the \(r_{ij}=1 \forall (i,j)\) that belongs to the route, then, the problem is a symmetric problem.

In order to calculate the \(r_{ij}\) parameter in real life problems the following method is used: Based on Cicero et al. [12] the roads where the vehicles can travel safely have slope in grades between 0 and 10 %. Also, the beaufort scale that is used for the measurement of the wind speed consists of an integer number between 0 and 12 [14]. In the proposed model, the Grade Index (\(G_{ij}\)) and the Beaufort Index (\(B_{ij}\)) are calculated in two different ways considering the road (if it is uphill or downhill) and if the wind is head-wind or back-wind taking into account Table 1.

Table 1 Grade Index and Beaufort Index
Full size table

Considering the \(G_{ij}\) and the \(B_{ij}\), the \(r_{ij}\) parameter is calculated as follows:

$$\begin{aligned} r_{ij}= \frac{G_{ij}+B_{ij}}{2} \end{aligned}$$
(3)

The third objective function is used for the minimization of the route based fuel consumption (\({ RFC}\)) in the case that the vehicle performs only pick-ups in its route. The vehicle should begin with empty load and after a visitation to a customer the load is increased based on the pick-up amount of the customer. If we consider that the more loaded is the vehicle the more fuel it consumes, we take the following objective function:

$$\begin{aligned} \min { OF}3 = \displaystyle \sum _{j=1}^{n}\displaystyle \sum _{\kappa = 1}^{m}c_{1j}x_{1j}^{\kappa }r_{1j} + \displaystyle \sum _{i=2}^{n}\displaystyle \sum _{j=1}^{n}\displaystyle \sum _{\kappa = 1}^{m}c_{ij}x_{ij}^{\kappa }\left( 1+\frac{y_{i-1,i}^{\kappa }+D_i}{Q}\right) r_{ij} \end{aligned}$$
(4)

with \(r_{ij}\) is the route parameters as in the OF2 and \(y_{1j}^{\kappa } = 0\) for all vehicles as the vehicle begins with empty load. In that case the \(D_i\) is the pick-up amount of the customer i.

The constraints of the problems are the following:

$$\begin{aligned}&\displaystyle \displaystyle \sum _{j=1}^{n}\displaystyle \sum _{\kappa =1}^{m}x_{ij}^{\kappa }=1,\quad i=1,\ldots , n\end{aligned}$$
(5)
$$\begin{aligned}&\displaystyle \displaystyle \sum _{i=1}^{n}\displaystyle \sum _{\kappa =1}^{m}x_{ij}^{\kappa }=1,\quad j=1,\ldots , n \end{aligned}$$
(6)
$$\begin{aligned}&\displaystyle \displaystyle \sum _{j=1}^{n}x_{ij}^{\kappa }-\displaystyle \sum _{j=1}^{n}x_{ji}^{\kappa }=0,\quad i=1,\ldots , n,\quad \kappa = 1, \ldots , m \end{aligned}$$
(7)
$$\begin{aligned}&\displaystyle \sum _{j=1,j \ne i}^{n}y_{ji}^{\kappa }-\sum _{j=1,j \ne i}^{n}y_{ij}^{\kappa }=D_i,\quad i=1,\ldots , n,\quad \kappa = 1, \ldots , m,\, { for}\, { deliveries} \nonumber \\\end{aligned}$$
(8)
$$\begin{aligned}&\displaystyle \sum _{j=1,j \ne i}^{n}y_{ij}^{\kappa }-\sum _{j=1,j \ne i}^{n}y_{ji}^{\kappa }=D_i,\quad i=1,\ldots , n,\quad \kappa = 1, \ldots , m,\, { for}\, { pick-ups} \nonumber \\\end{aligned}$$
(9)
$$\begin{aligned}&\displaystyle Qx_{ij}^{\kappa }\ge y_{ij}^{\kappa },\quad i,j=1,\ldots , n,\quad \kappa = 1, \ldots , m \end{aligned}$$
(10)
$$\begin{aligned}&\displaystyle x_{ij}^{\kappa } = \left\{ \begin{array}{ll} 1, &{}\quad \text{ if } (i,j) \text { belongs to the route } \\ 0, &{}\quad \text{ otherwise } \end{array} \right. \end{aligned}$$
(11)

Constraints (5) and (6) represent that each customer must be visited only by one vehicle; constraints (7) ensure that each vehicle that arrives at a node must leave from that node also. Constraints (8) and (9) indicate that the reduced (if it concerns deliveries) or increased (if it concerns pick-ups) load (cargo) of the vehicle after it visits a node is equal to the demand of that node. Constraints (10) are used to limit the maximum load carried by the vehicle and to force \(y_{ij}^{\kappa }\) to be equal to zero when \(x_{ij}^{\kappa }\) = 0 while constraints (11) ensure that only one vehicle will visit each customer.

Another differentiation of the problems is when a symmetric or an asymmetric case is studied. When the multiobjective symmetric delivery route-based fuel consumption vehicle routing problem (MSDRFCVRP) is studied, the combination of OF1 and OF2 is required considering that \(r_{ij}=1 \forall (i,j)\) that belongs to the route while when the multiobjective asymmetric delivery route-based fuel consumption vehicle routing problem (MADRFCVRP) is studied the combination of OF1 and OF2 is required considering that \(r_{ij} \ne r_{ji} \forall (i,j)\) that belongs to the route. The same holds when a problem with pick-ups is solved. More precisely, when the multiobjective symmetric pick-up route-based fuel consumption vehicle routing problem (MSPRFCVRP) is studied, the combination of OF1 and OF3 is required considering that \(r_{ij}=1 \forall (i,j)\) that belongs to the route while when the multiobjective asymmetric pick-up route-based fuel consumption vehicle routing problem (MAPRFCVRP) is solved, the combination of OF1 and OF3 is required considering that \(r_{ij} \ne r_{ji} \forall (i,j)\) that belongs to the route.

3 Parallel multi-start algorithms

In this Section, all the proposed Multiobjective algorithms are presented. The common steps of all algorithms are the solutions’ representation, the method using for producing the initial solutions and the variable neighborhood search (VNS) algorithm (in order to increase the exploitation abilities of each solution) that were presented and analyzed in detail at [65].

For all the algorithms, the solutions are represented with the path representation of the tour. Each solution (individual for the differential evolution algorithm) is represented by a n-dimensional vector in problem space and its performance is evaluated on the predefined fitness functions. For example, if we have a solution with five nodes a possible path representation would be the “1 2 3 4 5”. If these routes do not start with node 1 (the depot), we find it and put it at the beginning of the route. As we would like the size of the solution’s vector to be maintained constant for all members of the population and for all the procedures in an iteration and, finally, for all iterations we use a path representation in the solutions without using in the solution’s vector the return to the depots. The solution vector is transformed in the form of “1 2 3 1 4 5 1” with the addition of the depots only when the objective functions of the problem are calculated considering the constraints of the problem in order to find afterwards from which node the vehicle will return to the depot. Also, for all the algorithms we assume that we have X different initial populations with W solutions for each population.

Each population is separated in K sub-populations of w solutions, where K is the number of objective functions (\(w=W{/}K\)). For the calculation of the first solution of each sub-population, a different method is applied (VNS algorithm [29, 65],the Nearest Neighborhood method [46] and a variant of GRASP method [24]). The variant of GRASP algorithm works as follows: In this GRASP algorithm instead of using the restricted candidate list (RCL), we use the following procedure: Always node 1 is used as a starting node. Then, a random number (Rand) equal to 0 or 1 is generated. If \(Rand = 0 \), then, the nearest node to a node i is visited. If \(Rand = 1\), the second nearest node to a node i is visited. For the calculation of the rest solutions of each sub-population a Swap method [46], the 2-opt method [52] and a random method are used. The variant of variable neighborhood search (VNS) works as follows: initially, the 2-opt local search algorithm [46] is applied for a specific number of iterations (\(local_{max}\)). For the proposed algorithm, the \(vns_{max}\) and the \(local_{max}\) were set equal to 10 in order not to increase the computational time of the algorithm. If 2-opt improves the solution (the new solution dominates the old solution), then, 2-opt algorithm is applied for \(local_{max}\) number of iterations. On the other hand, if 2-opt is trapped in a local optimum (the new solution is dominated by the old solution or the two solutions are non-dominated between them) when \(local_{max}\) number of iterations has been reached, the 3-opt algorithm [46] is applied. The same procedure is followed when the current local search algorithm is trapped in a local optimum, by replacing the current algorithm initially with the Swap algorithm, afterwards with the 2-2 exchange algorithm, then, with the 1-0 relocate and finally, with the 2-0 relocate algorithms [46]. For more information please see [65].

3.1 Parallel multi-start non-dominated sorting differential evolution algorithms (PMS-NSDEs)

After the calculation of the initial population, the main phase of the non-dominated sorting differential evolution method is applied. The single objective differential evolution algorithm works as follows. Initially, the mutation operator produces a trial vector \(u_i(it)\) for each individual \(x_i(it)\) of the current population by mutating a target vector with a weighted differential. The trial vector, \(u_i(it)\), is generated as follows: a target vector, \(x_{i_1} (it)\), is selected from the population, such that \(i \ne i_1\). Then, two individuals, \(x_{i_2}\) and \(x_{i_3}\), are selected randomly from the population such that \(i \ne i_1 \ne i_2 \ne i_3\) [73]. Using these individuals, the trial vector is calculated by perturbing the target vector as follows:

$$\begin{aligned} u_i(it) = x_{i_1}(it) + \beta (x_{i_2}(it) - x_{i_3} (it)) \end{aligned}$$
(12)

where \(\beta \in (0,\infty ) \) is the scale factor. The upper bound of \(\beta \) is usually the value 1 because as it has been proved if the \(\beta > 1\) there is no improvement in the solutions [19, 63].

After the completion of the mutation phase of the algorithm a crossover operator Cr is, usually, applied. Then, depending on the comparison of the Cr value with a random number for each element of the solution vector, \(rand_i(0,1)\), the corresponding value is inherited either from the trial vector or from the parent. In the next generation the fitness function of the parent and of the offspring are compared and the best one survives [19, 63, 73].

The first issue that we have to solve in the algorithm was that the solutions for the problem are represented via the path representation of the tours but this representation is not suitable for a DE algorithm. Thus, for the calculation of each trial vector the solutions are transformed into a floating point in the interval [0,1] and after the calculation of the trial vector the solutions are transformed back into integer points creating new routes [53, 65].

In the proposed algorithms, the procedure starts with the mutation operator for the production of a trial vector for each individual of the current population by mutating a target vector with a weighted differential. In this research, three mutation operators are applied. All equations are the same with the ones used in [64]:

$$\begin{aligned}&u_i(it) = x_{i_1}(it) + \beta (x_{i_2}(it) - x_{i_3} (it)) \end{aligned}$$
(13)
$$\begin{aligned}&\displaystyle u_i(it) = x_{i_1}(it) + \beta (Pareto_{i_2}(it) - Pareto_{i_3} (it)) \end{aligned}$$
(14)
$$\begin{aligned}&\displaystyle u_i(it) = Pareto_{i_1}(it) + \beta (x_{i_2}(it) - x_{i_3} (it)) \end{aligned}$$
(15)

where the solutions \(x_i\) are random solutions from the population and the solutions \(Pareto_i\) are random solutions from the Pareto front. In the proposed algorithms, the crossover operator is not used as it was observed after a large number of tests using different values for \(C_r\) that the results were the best when the \(C_r\) is set equal to 1. The only difference between the three algorithms are these equations and, thus, the three different produced algorithms are denoted as PMS-NSDE1, PMS-NSDE2 and PMS-NSDE3, using Eqs. 13, 14 and 15, respectively.

The calculation of the trial vectors could produce some inefficient (due to the transformation of the solutions from continuous values (suitable for the equations of DE) to discrete values (path representation) and vice versa) and dominated from the parents’s solutions of the previous iteration. Thus, it was decided to add another phase for the calculation of the new parents in the algorithm in order to take advantage of possible good new and old solutions in the whole set of individuals. Thus, after the calculation of the trial vectors the parents-individuals \(x_{i}(it)\) and the trial vectors \(u_{i}(it)\) are combined in a new vector and, then, the members of the new vector are sorted using the rank and the crowding distance as in the NSGA II algorithm [65]. The first W individuals of the new vector are the produced solutions of the iteration it. With this procedure we give the opportunity to the solutions of the previous iteration that are dominated from the new solutions to be improved in the current iteration and we avoid to add to the next iterations inefficient solutions that will probably be produced using the equations of the trial vector. At the next step the Variable Neighborhood Search (VNS) algorithm is applied to the individuals with both the \(vns_{max}\) and the \(local_{max}\) equal to 10 [65].

The new solution of each individual is found by using the following observation. If the offspring in iteration it dominates its parent of the iteration \(it-1\), then, the parent is replaced by the offspring. On the other hand, if the parent dominates the offspring, then, the parent remains in the population. Finally, if these two solutions are not dominated between them, then, the parent remains in the population. This is performed as it is desirable to give to the individual more exploration abilities. It should be noted that the non-dominated solutions are not deleted from the Pareto front and, thus, the good solutions will not disappeared from the population. Finally, in order to improve the solutions the VNS method is applied at the best solutions with both the \(vns_{max}\) and the \(local_{max}\) equal to 10 [65]. In the next iterations in order to insert an individual in the Pareto front archive there are two possibilities. First, the individual is non-dominated with respect to the contents of the archive and second it dominates any individuals in the archive, but in this case all the dominated individuals have to be deleted from the archive. At the end of each iteration, from the non-dominated solutions from all initial populations the Total Pareto Front is updated considering the non-dominated solutions of the last initial population. A pseudocode of the algorithm is the following:

figure a

In order to test the efficiency of the proposed parallel multi-start non-dominated sorting differential evolution algorithms, a parallel multi-start NSGA II algorithm [65] is used to compare with the proposed algorithms.

4 Evaluation measures

In this paper, as the optimum Pareto Front is not known, four different evaluation measures are used for the comparison of the Pareto Fronts of the four algorithms [65]:

  • The range to which the front spreads out is described by the following equation [84]:

    $$\begin{aligned} M_k = \sqrt{\sum _{i=1}^{K}max \{\parallel p'-q'\parallel \}} \end{aligned}$$
    (16)

    where K is the number of objectives and \(p'\), \(q'\) are the values of the objective functions of two solutions that belong to the Pareto front.

  • The number of solutions of the Pareto front (L).

  • The \(\Delta \) measure includes information about both spread and distribution of each solutions [60]. For the calculation of the \(\Delta \) measure the following equation is used:

    $$\begin{aligned} \Delta = {\frac{d_f+d_l+\sum _{i=1}^{|S|-1}|dist_i-{\overline{dist}}|}{d_f+d_l+(|S|-1){\overline{dist}}}} \end{aligned}$$
    (17)

    where S is the number of the intermediate solutions between the extreme solutions, \(d_f\) and \(d_l\) are the Euclidean distances between the extreme solutions [60] and the boundary solutions [60] of the obtained non-dominated set [16], \(dist_i\) is the distance from a boundary solution i to the next boundary solution, \(i=1, 2,\ldots , (S-1)\) and \(\overline{dist}\) is the average value of all \(dist_i\) distances.

  • Coverage [68, 84]: for a pair \((A_1,B_1)\) of approximation sets of Pareto solutions of two different algorithms the fraction of solutions in \(B_1\) that are weakly dominated by one or more solutions in \(A_1\). The coverage measure (C measure) is calculated by the following equation:

    $$\begin{aligned} C(A_1,B_1) = \frac{|\{b \in B_1;\exists a \in A_1: a \le b\}|}{|B_1|}. \end{aligned}$$
    (18)

5 Computational results

The whole algorithmic approach, which was implemented in Visual C++, was tested on a set of instances. As it was mentioned previously, in the multiobjective (K-objective) VRP, K different objective functions are defined. As there are no data sets of benchmark instances available for the solution of this kind of multiobjective VRP problems, we created a number of instances as follows. Initially, we took five instances with the coordinates of 100 cities from the TSPLIB (kroA100, kroB100, kroC100, kroD100, and kroE100). The data for the capacity, the time limits and the demands were taken from the third instance (par3) of the classic Christofides benchmark instances [11] used for the solution of the capacitated vehicle routing problem (CVRP).

Thus, we created a new set of instances combining the Kro\(\#\)100 instances (where \(\#\) corresponds to A or B or C or D or E) with the par3 instance where the coordinates of 100 nodes are taken from the corresponding kro\(\#\)100 data set and the corresponding demand of each of the 100 nodes, the maximum tour length, the service time and the capacity of each vehicle were taken from the par3 instance. Also, the maximum tour length, the service time and the capacity of each vehicle were taken from the par3 instance. The combination of these five instances are used for the creation of the instances for the 2-objective functions problems. For example, in order to create a 2-objective functions asymmetric problem instance, we use for the calculation of the values of the first objective function data from the combination kroA100par3, while for the calculation of the values of the second objective function we use data from the combinations kroB100par3, kroC100par3 and kroD100par3. For the production of the route parameters (\(r_{ij}\)) Table of the second objective function the necessary data are taken from kroC100par3, kroD100par3 and kroB100par3 as follows. The route parameters of the network is an asymmetric table with positive numbers. In order to create those numbers we divide the route parameters’ Table in two parts. In the first part all elements that are in the down side from the main diagonal are calculated using the Euclidean distance between the nodes corresponding to the kroC100par3 set and in the second part all elements that are at the top of the main diagonal are calculated using the Euclidean distance between the nodes corresponding to the kroD100par3 set. Then, each element of the route parameters’ Table is divided with the corresponding element of a table created by calculating the Euclidean distance between the nodes corresponding to the kroB100par3 set.

In order to create a route for every objective function the time and the capacity constraints are needed. In case of solving a 2-objective functions symmetric problem with first objective function the OF1 and second objective function the OF2 (OF1-OF2 for the MSDRFCVRP) or the OF3 (OF1-OF3 for the MSPRFCVRP), the combination “A-B” in all Tables and Figures means that A corresponds to KroA100par3 and B corresponds to kroB100par3. Generally in a problem when the OF1 objective function is used the Euclidean distances of the corresponding nodes of the instance correspond to the time durations. In the case that a 2-objective functions asymmetric problem is selected to be solved with first objective function the OF1 and second the OF2 (OF1-OF2 for the MADRFCVRP) or the OF3 (OF1-OF3 for the MAPRFCVRP) the notation for each new generated instance in all corresponding tables includes a combination of 4 different instances. Thus, a notation “A-B-CD”, means that for the calculation of the time duration the data from kroA100par3 are used, for the calculation of the distance the data from kroB100par3 were used while for the calculation of the route parameters needed for the OF2 (or OF3) objective function, the data from kroC100par3, kroD100par3 and kroB100par3 were used as it was described previously.

The parameters of all the algorithms were selected after testing with different values and the ones selected are those that gave the best computational results, taking into account the quality of the solutions and the computational time needed to achieve these solutions and, also, taking into account the fact that we would like to test the algorithms with the same function evaluations. Thus, the selected parameters for each algorithm are given in the following:

Parallel multi-start NSDEs

  • Number of individuals for each initial population: 100.

  • Number of generations: 500.

  • Number of initial populations: 10.

  • \(\beta = 0.5\)

Parallel multi-start NSGA II

  • Number of individuals for each initial population: 100.

  • Number of generations: 500.

  • Number of initial populations: 10.

After the selection of the final parameters, the four algorithms were tested for ten combinations for the two objective functions. In the following tables the comparisons performed based on the four evaluation measures presented previously are presented and in the figures a selected number of Pareto fronts are given. More precisely, we use for evaluation measures the number of solutions (L) in the non-dominated set, the maximum extend in each dimension (\(M_k\)), the minimization of the spread of solutions (\(\Delta \)) and the Coverage (C). In all the tables except those that contain the values of the Coverage the best value for each measure from the comparison of all algorithms is signed as bold while from the comparison of the three PMS-NSDE algorithms the best values are underlined in the tables. In general, it is preferred the L, the \(M_k\) and the C measures to be as larger as possible and the \(\Delta \) value to be as smaller as possible.

Table 2 Results of the first three measures for the four algorithms in ten instances when the symmetric delivery problem using objective functions OF1-OF2 is solved
Full size table
Table 3 Results of the C measure for the four algorithms in ten instances when the symmetric delivery problem using objective functions OF1-OF2 is solved
Full size table

In Tables 2, 3, 4 and 5, the results of the four measures for the four algorithms in ten combinations of instances for the multiobjective delivery route-based fuel consumption problems are presented. More precisely, in Table 2 and in Table 4 the results of the symmetric problem (OF1-OF2 for the MSDRFCVRP) (Table 2) and of the asymmetric problem (OF1-OF2 for the MADRFCVRP) (Table 4) using the first two objective functions for the first three evaluation measures are presented, respectively. On the other hand, in Tables 3 and 5 the results for the last evaluation measure (C) for the same formulations (symmetric and asymmetric), same objective functions and same instances as in Tables 2 and 4 are presented, respectively. In Tables 6, 7, 8 and 9 the results of the four measures for the four algorithms for ten combinations of instances for the multiobjective pick-up route-based fuel consumption problem are presented. More precisely, in Tables 6 and 8 the results of the first three measures in the symmetric (Table 6) and in the asymmetric (Table 8) case are given respectively while in Tables 7 and 9 the results of the fourth measure in the symmetric (Table 7) and in the asymmetric (Table 9) case are presented, respectively. In Fig. 1, the Pareto Fronts of the symmetric delivery problem using objective functions OF1-OF2 (first part of the figure) and of the symmetric pick-up problem using objective functions OF1-OF3 (second part of the figure) for the instance “D-E” for all algorithms are presented, respectively while in Fig. 2 the Pareto Fronts of the asymmetric delivery problem using objective functions OF1-OF2 (first part of the figure) and of the asymmetric pick-up problem using objective functions OF1-OF3 (second part of the figure) for the instance “D-E-BC” for all algorithms are presented, respectively. In Fig. 3, five runs of the algorithms PMS-NSDE1 and PMS-NSGA II for the instance “A-B” of the MSDRFCVRP are presented in order to prove the stability of the algorithms. In all the Tables that present results for the C measure the notation of the algorithms PMS-NSDE\(\#\) and PMS-NSGA II have been replaced with the notations NSDE\(\#\) and NSGA II, respectively, in order to reduce the size of the Tables.

In Table 2, the results of the four algorithms solving the first two objective functions symmetric delivery problem (OF1-OF2 for the MSDRFCVRP) are presented. The PMS-NSGA II performs better than the other algorithms for the L measure (it performs better in six out of ten instances). The PMS-NSDE1 performs better for the \(\Delta \) measure (it performs better in five instances) and it has equal performance with the PMS-NSDE3 for the \(M_k\) measure. If we would like to compare the results of the three versions of the PMS-NSDE algorithms, the PMS-NSDE1 performs slightly better than the other two algorithms according to the \(M_k\) and \(\Delta \) measures and has equal performance with the PMS-NSDE2 for the L measure. According to the coverage table (Table 3) the PMS-NSDE3’s Pareto Fronts dominate the Pareto Fronts produced from the other three algorithms.

Table 4 Results of the first three measures for the four algorithms in ten instances when the asymmetric delivery problem using objective functions OF1-OF2 is solved
Full size table
Table 5 Results of the C measure for the four algorithms in ten instances when the asymmetric delivery problem using objective functions OF1-OF2 is solved
Full size table

When the asymmetric delivery problem (OF1-OF2 for the MADRFCVRP) is solved (Tables 4, 5) the results are slightly different from the previous case. The PMS-NSGA II performs better than the other three algorithms only for the L measure and taking into account the \(M_k\) and the \(\Delta \) measures the PMS-NSDE3 performs better than the other algorithms in five and four instances, respectively. In the comparison of PMS-NSDE variants, according to the number of Pareto solutions L the PMS-NSDE1 performs better in five instances and the PMS-NSDE3 performs better in six instances considering the \(M_k\) measure and in five instances considering the \(\Delta \) measure. According to the Coverage Table (Table 5), the results are different from the previous symmetric problem, thus, the PMS-NSDE2’s Pareto Fronts dominates the Pareto Fronts produced from the other three algorithms.

Table 6 Results of the first three measures for the four algorithms in ten instances when the symmetric pick-up problem using objective functions OF1-OF3 is solved
Full size table
Table 7 Results of the C measure for the four algorithms in ten instances when the symmetric pick-up problem using objective functions OF1-OF3 is solved
Full size table

A very interesting observation is derived when the results of the symmetric pick-up problem (using objective functions OF1-OF3 for the MSPRFCVRP) are presented (Tables 6, 7). The PMS-NSGA II performs better than the other three algorithms for the number of the Pareto front solutions L (better performance in 9 instances) and the PMS-NSDE3 performs better for the \(M_k\) measure (better performance in 6 instances), that is almost the same outcome as in the case when the symmetric and the asymmetric delivery problems are solved. Also, PMS-NSGA II performs better for the \(\Delta \) measure (better performance in 7 instances). From the comparison of the three variants of the PMS-NSDE we conclude that according to the number of Pareto front solutions L the PMS-NSDE2 has equal performance with the PMS-NSDE3 and they perform better than the PMS-NSDE1 in four instances, respectively. The PMS-NSDE3 performs better for the \(M_k\) and \(\Delta \) measures than the other two algorithms in seven instances respectively. This outcome is very important as we can see that the performance of the PMS-NSDE3 algorithm in these measures is equally well whether we solve an asymmetric delivery or a symmetric pick-up problem. Also According to the coverage table (Table 7), the results are different from the previous symmetric problem, thus, the PMS-NSDE1’s and the PMS-NSDE2’s Pareto Fronts dominate the Pareto Fronts produced from the other two algorithms in four instances, respectively.

Table 8 Results of the first three measures for the four algorithms in ten instances when the asymmetric pick-up problem using objective functions OF1-OF3 is solved
Full size table
Table 9 Results of the C measure for the four algorithms in ten instances when the asymmetric pick-up problem using objective functions OF1-OF3 is solved
Full size table
Fig. 1
figure 1

Pareto fronts of the four algorithms for the instance “D-E”

Full size image
Fig. 2
figure 2

Pareto fronts of the four algorithms for the instance “D-E-BC”

Full size image
Fig. 3
figure 3

Pareto fronts for the instance A-B when the symmetric delivery problem using objective functions OF1-OF2 is solved in five different runs of PMS-NSDE1 and PMS-NSGA II algorithms

Full size image

Finally, when the asymmetric pick-up problem (objective functions OF1-OF3 for the MAPRFCVRP) is solved (Tables 8, 9) the results lead us to the following conclusions. The PMS-NSGA II performs better than the other three algorithms in the number of the Pareto front solutions L (better performance in 7 instances) and for the \(\Delta \) measure (better performance in 5 instances) that is almost the same outcome as in the case when the symmetric pick-up problem is solved. The PMS-NSDE3 performs better for the \(M_k\) measure (better performance in 5 instances) and the \(\Delta \) measure (better performance in 4 instances). This outcome is very important as we can see that the performance of the PMS-NSDE3 algorithm in the \(M_k\) measure is equally well in every problem and in the \(\Delta \) measure is equally well whether we solve an asymmetric delivery or an asymmetric pick-up problem is solved. In the comparison of PMS-NSDE variants, the outcome is almost the same as in the case when the asymmetric delivery problem is solved. According to the number of Pareto solutions L the PMS-NSDE1 performs better in six instances and the PMS-NSDE3 performs better in five instances considering the \(M_k\) measure and in six instances considering the \(\Delta \) measure. According to the Coverage Table (Table 9) all the PMS-NSDE’s Pareto Fronts have equal performance.

In general, based on all Tables the PMS-NSGA II algorithm produces Pareto front with larger numbers of solutions and better distribution than the other algorithms. The PMS-NSDE3 algorithm produces more extended Pareto fronts and the Pareto fronts produced by PMS-NSDE2 dominate the fronts produced from the other algorithms. From the comparison of the three PMS-NSDE algorithms we conclude that considering the L measure the PMS-NSDE1 performs slightly better than the other two algorithms as it performs better in 42.5 % of the instances while the PMS-NSDE3 and the PMS-NSDE2 perform better in 35 and 32.5 %, respectively. Considering the \(M_k\) measure the PMS-NSDE3 performs slightly better than the others as it performs better in 55 % of the instances while the PMS-NSDE1 and the PMS-NSDE2 perform better in 25 and 20 %, respectively. Taking into account the \(\Delta \) measure the PMS-NSDE3 performs slightly better than the others as it performs better in 50 % of the instances while the PMS-NSDE1 and the PMS-NSDE2 perform better in 30 and 20 %, respectively. Finally, considering the C measure the PMS-NSDE2 performs slightly better than the other two algorithms as it performs better in 40 % of the instances while the PMS-NSDE1 and PMS-NSDE2 follow by performing better in 37.5 and 37.5 % of the instances, respectively. For the L and C measures the summation of the percentages is larger than 1 considering that in some instances two or more algorithms perform equal better.

A statistical analysis based on the Friedman test [26, 27] for all algorithms is presented in Table 10 based on the results of Tables 2, 4, 6, 8. In each row of the Table the rank of the algorithms based on the values of Tables 2, 4, 6, 8 in each instance is presented. In the last row the average ranks for all algorithms are given. In the Friedman test all the algorithms are ranked for each data set separately [18, 28] as it is shown in Table 10. Let \(r^j_i\) be the rank of the jth of k algorithms on the ith of N data sets, where in our study k is equal to 4 and N is equal to 40 (if we analyze each of the three metrics separately) and 120 (if we analyze the three metrics together). The Friedman test compares the average ranks of algorithms, \(R_j = \frac{1}{N}\sum _i r^j_i\). Under the null-hypothesis [18, 28], which states that all the algorithms are equivalent and, thus, their ranks \(R_j\) should be equal, the Friedman statistic

$$\begin{aligned} \chi _F^2 = \frac{12N}{k(k+1)}\left[ \displaystyle \sum _jR_j^2-\frac{k(k+1)^2}{4}\right] \end{aligned}$$
(19)

is distributed according to \(\chi _F^2\) with \(k-1\) degrees of freedom, when N and k are big enough. Iman and Davenport [31] showed that Friedmans \(\chi _F^2\) is undesirably conservative [18] and derived a better statistic [31]

$$\begin{aligned} F_F = \frac{(N-1)\chi _F^2}{N(k-1) - \chi _F^2} \end{aligned}$$
(20)

which is distributed according to the F-distribution with \(k-1\) and \((k-1)\times (N-1)\) degrees of freedom [18]. In our statistical analysis, both equations were used and the values found were: \(\chi _F^2 = 31.825\) and \(F_F = 14.074\) for the L metric, \(\chi _F^2 = 14.272\) and \(F_F = 5.264\) for the \(M_k\) metric and \(\chi _F^2 = 12.877\) and \(F_F = 4.688\) for the \(\Delta \) metric, while when the results of all metrics are analyzed together we found: \(\chi _F^2 = 24.93\) and \(F_F = 8.853\) respectively. From the statistical Tables and for \(\alpha = 0.05\) the critical values are for \(\chi ^2\) with \(k-1\)=3 degrees of freedom equal to 0.35. The \(F(k-1,(k-1)\times (N-1)) = F(3,40)\) is equal to 2.84 for each metric separately and when all the metrics are analyzed together the F(3, 120) is equal to 2.68. Thus, we reject the null hypothesis in any case. From this analysis, we can say that there are statistical differences between the algorithms.

6 Which solution of the Pareto front to choose?

In real world problems after the production of the Pareto front solutions the decision maker has to make the next step and to choose one solution from these solutions considering his preferences. For example, suppose that the decision maker is the president of a company that needs a fast and efficient method to help him/her to select the most suitable solution of a Pareto front. Using the following proposed method the most suitable solution, considering the preferences of the decision maker, could be selected.

Initially, the decision maker is asked to evaluate a number of K Utility Variables (UV). The number of the Utility Variables is equal to the number of the objective functions of the problem. Each one of those variables corresponds to an objective function or criterion and it can take any value between [0,1]. The values of these variables represent how useful for the decision maker is the best value of each criterion. The closer the value of the Utility Variable to zero, the less useful is the criterion for the decision maker. On the other hand, the closer the value of the Utility Variable to one, the more useful is the criterion for the decision maker. Considering that we conclude to the following results solving a multiobjective problem:

 

Pareto Front

 

Solutions

Time (min)

Fuel (lt)

1

100

2

2

70

3

3

50

5

4

30

7

5

10

10

Table 10 Results of Friedman test for all algorithm
Full size table

Considering that, for the decision maker it is very important to select a solution that results to a low fuel consumption route and, also, that for the decision maker is not so important the time needed to complete the route. Thus, the \({ Utility}\) \({ Variables}\) could be \({ UV(Fuel)}=0.9\) for the Fuel criterion and \({ UV(Time)}=0.1\) for the Time criterion. At the next step, we use the following equations in order to find each one of the coordinates of the \({ Utility}\) \({ Point}\) (\({ UP}\)) on the Pareto Front diagram (Fig. 4):

\({ UP(Time)} =\) (Max Time value − Min Time value) * (1 − \({ UV(Time)}\)) \(+\) Min Time value \(=\) (100−10) * 0.9 \(+\) 10 \(=\) 91

\({ UP(Fuel)} =\) (Max Fuel value − Min Fuel value) * (1 \(-{ UV(Fuel)}\)) \(+\) Min Fuel value \(=\) (10−2) * 0.1 \(+\) 2 \(=\) 2.8

Fig. 4
figure 4

Utility points on a Pareto front

Full size image

The \({ Utility}\) \({ Point}\) in that case is the point (91,2.8) (\({ Utility}\) \({ Point}\) 1). The last step is to find based on the Euclidean distances from the real points of the Pareto Front which solution is closer to the UP. This solution [in our example the solution (100,2)] is the solution that the decision maker must choose. If the \({ Utility}\) \({ Variables}\) were \({ UV(Fuel)}=0.1\) and \({ UV(Time)}=0.9\) (\({ Utility}\) \({ Point}\) 2) the solution that the decision maker must choose is the solution (10,10) while if the \({ Utility}\) \({ Variables}\) were \({ UV(Fuel)}=0.5\) and \({ UV(Time)}=0.5\) (\({ Utility}\) \({ Point}\) 3) the best solution is the solution (50,5).

7 Conclusions and future research

In this paper, as we could not find DE implementations for the solution of multiobjective energy vehicle routing problems in the literature (at least to our knowledge) and we would like to see its performance in a difficult multiobjective fuel consumption vehicle routing problem we have proposed a hybridized version of a Multiobjective DE for the solution of this problem. The main contribution of the paper, in addition to the proposed algorithm, is the four new multiobjective formulations of the problem using combinations of symmetric and asymmetric formulations in pick-up and delivery problems. The formulation includes real route parameters, as the direction of the wind and the behavior of the drivers, and, thus, very realistic formulations were produced. In general, in the four different problems that are presented in this paper the three versions of DE and the hybridized version of NSGA II gave equally good results. However, the behavior of the algorithms was slightly different when a symmetric and an asymmetric case was solved, as it was presented and analyzed in the computational results section. Our future research will be, mainly, focused on the application of those algorithms in other multiobjective combinatorial optimization problems.