Keywords

1 Introduction

The Vehicle Routing Problem is one of the most famous optimization problems and its main goal is the design of the best routes in order the selected (or calculated) vehicles to serve the set of customers with the best possible way based on the selected criteria that each different variant of the problem includes. As the interest of the researchers and of the decision makers in industries for the solution of different variants of the Vehicle Routing Problem continuously increases, a number of more realistic and, thus, more complicated variants/formulations of the Vehicle Routing Problem and, in many cases with more than one objective functions, have been proposed and a number of more sophisticated algorithms [5] are used for their solutions [13]. There is a growing number of papers for solving multi-depot vehicle routing problems [6] or energy vehicle routing problems [1, 4, 17]. However, there are few papers for the solution of Multi-Depot vehicle routing problem with fuel consumption [3].

In this research, the formulation of the problem combines more than one depot, the possibility of pickups and deliveries and the simultaneous reduction of the fuel consumption in symmetric and, in the more realistic, asymmetric cases. In the first objective function (OF1), the total travel time is minimized, while in the second objective function the Fuel Consumption (FC) taking into account the traveled distance and the load of the vehicle is, also, minimized. In the second objective function we study two different scenarios, in the first scenario, we have deliveries in the customers (OF2) and, in the other, we have pickups from the customers (OF3). Also, we study a symmetric case, where except of the load and the traveled distance, we consider that there are no other route parameters or that there are perfect route conditions, and an asymmetric case, where we take into account parameters of real life, such as weather conditions or uphill and downhill routes [11, 12]. Thus, we produce four different problems, in the first one we have the minimization of the OF1 and OF2 objective functions in the symmetric case, in the second one we have the minimization of the OF1 and OF3 in the symmetric case and in the other two scenarios, we have the minimization of the corresponding combinations of objective functions in the asymmetric case. In recent years a number of evolutionary, swarm intelligence and, in general, nature inspired algorithms have been proposed for the solution of a Vehicle Routing Problem both when one or more objectives are considered.

In the following the three objective functions and the constraints of the problem are presented [8, 9, 12]:

$$\begin{aligned} \min OF1 = \sum _{i=I_1}^{n}\sum _{j=1}^{n}\sum _{\kappa =1}^{m}(t_{ij}^{\kappa }+s_j^{\kappa })x_{ij}^{\kappa } \\ \min OF2 = \sum _{h=I_1}^{I_\pi }\sum _{j=2}^{n}\sum _{\kappa = 1}^{m}c_{hj}x_{hj}^{\kappa }(1+\frac{y_{hj}^{\kappa }}{Q})r_{hj}\nonumber \end{aligned}$$
(1)
$$\begin{aligned} +\,\sum _{i=2}^{n}\sum _{j=I_1}^{n}\sum _{\kappa = 1}^{m}c_{ij}x_{ij}^{\kappa }(1+\frac{y_{i-1,i}^{\kappa }-D_i}{Q})r_{ij} \end{aligned}$$
(2)
$$\begin{aligned} \min OF3 = \sum _{h=I_1}^{I_\pi }\sum _{j=2}^{n}\sum _{\kappa = 1}^{m}c_{hj}x_{hj}^{\kappa }r_{hj} \end{aligned}$$
$$\begin{aligned}&\displaystyle +\,\sum _{i=2}^{n}\sum _{j=I_1}^{n}\sum _{\kappa = 1}^{m}c_{ij}x_{ij}^{\kappa }(1+\frac{y_{i-1,i}^{\kappa }+D_i}{Q})r_{ij} \end{aligned}$$
(3)
$$\begin{aligned}&\displaystyle \sum _{j=I_1}^{n}\sum _{\kappa =1}^{m}x_{ij}^{\kappa }=1, i=I_1,\cdots , n \end{aligned}$$
(4)
$$\begin{aligned}&\displaystyle \sum _{i=I_1}^{n}\sum _{\kappa =1}^{m}x_{ij}^{\kappa }=1, j=I_1,\cdots , n \end{aligned}$$
(5)
$$\begin{aligned}&\displaystyle \sum _{j=I_1}^{n}x_{ij}^{\kappa }-\sum _{j=I_1}^{n}x_{ji}^{\kappa }=0, i=I_1,\cdots , n, \kappa = 1, \cdots , m \end{aligned}$$
(6)
$$\begin{aligned}&\displaystyle \sum _{j=I_1,j \ne i}^{n}y_{ji}^{\kappa }-\sum _{j=I_1,j \ne i}^{n}y_{ij}^{\kappa }=D_i, i=I_1,\cdots , n, \kappa = 1, \cdots , m,\, for\, deliveries \end{aligned}$$
(7)
$$\begin{aligned}&\displaystyle \sum _{j=I_1,j \ne i}^{n}y_{ij}^{\kappa }-\sum _{j=I_1,j \ne i}^{n}y_{ji}^{\kappa }=D_i,\,\, i=I_1,\cdots , n,\,\, \kappa = 1, \cdots , m,\, for\, pick-ups \end{aligned}$$
(8)
$$\begin{aligned}&\displaystyle Qx_{ij}^{\kappa }\ge y_{ij}^{\kappa }, i,j=I_1,\cdots , n, \kappa = 1, \cdots , m \end{aligned}$$
(9)
$$\begin{aligned}&\displaystyle \sum _{i,j \in S}x_{ij\kappa }\le \ \mid S\mid -1, \text { for all } S \subseteq \{2,\cdots ,n\}, \kappa =1,\cdots ,m \end{aligned}$$
(10)
$$\begin{aligned}&\displaystyle x_{ij}^{\kappa } = \left\{ \begin{array}{ll} 1, &{} \text { if} (i,j) \text {belongs to the route } \\ 0, &{} \text {otherwise } \end{array} \right. \end{aligned}$$
(11)

The objective function (1) is used for the minimization of the time needed to travel between two customers or a customer and the depot (where \(t_{ij}^{\kappa }\) is the time needed to visit customer j immediately after customer i using vehicle \(\kappa \), \(s_j^{\kappa }\) is the service time of customer j using vehicle \(\kappa \), n is the number of nodes (\(\{I_1,I_2,...I_\pi ,2,3,...,n\}\)), m is the number of homogeneous vehicles and the depots are a subset \(\Pi =\{I_1,I_2,...I_\pi \}\) of the set of the n nodes denoted by \(i=j= I_1,I_2,...I_\pi \) (\(\pi \) is the number of homogeneous depots)). The second objective function (2) is used for the minimization of the Route based Fuel Consumption (RFC) in the case that the vehicle performs only deliveries taking into account real life route parameters (weather conditions or uphills and downhills or driver’s behavior - The parameter \(r_{ij}\) corresponds to the route parameters from the node i to the node j and it is always a positive number). The third objective function (3) 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. Constraints (4) and (5) represent that each customer must be visited only by one vehicle; constraints (6) ensure that each vehicle that arrives at a node must leave from that node also. Constraints (7) and (8) 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 (9) 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, constraints (10) are the tour elimination constraints while constraints (11) ensure that only one vehicle will visit each customer. It should be noted that the problems solved in this paper are symmetric (where \(r_{ij}=1, \ \forall (i,j)\)) or asymmetric (where \(r_{ij} \ne r_{ji}, \ \forall (i,j)\)).

In this paper, a variant of the Krill Herd (KH) algorithm, suitable for the Multiobjective Vehicle Routing Problems, the Parallel Multi-Start Non-dominated Sorting Krill Herd Algorithm (PMS-KH), is proposed for the solution of the Multiobjective Energy Reduction Multi-Depot Vehicle Routing Problem (MEMDVRP). The KH algorithm is based on simulating the herding behavior of krill individuals, using a Langrangean model [2]. The original Krill Herd algorithm was proposed for the solution of continuous optimization problems and the proposed algorithm was modified properly in order to be used for the solution of the studied problem. The algorithm is compared with four other evolutionary algorithms, the Parallel Multi-Start Non-dominated Sorting Particle Swarm Optimization (PMS-NSPSO) [10], the Parallel Multi-Start Non-dominated Sorting Differential Evolution (PMS-NSDE) [8], the Parallel Multi-Start Non-dominated Sorting Artificial Bee Colony (PMS-ABC) [12] and the Parallel Multi-Start Non-dominated Sorting Genetic Algorithm II (PMS-NSGA II) [9]. This paper is organized into three sections. In the next section, the proposed algorithm is described, while, in Sect. 3 the computational results are presented. The last section provides concluding remarks and future research.

2 Parallel Multi-Start Non-dominated Sorting Krill Herd Algorithm (PMS-KH)

Krill Herd algorithm (KH) is a relatively new swarm intelligence algorithm [2, 14,15,16] that simulates the herding behavior of krill individuals. The algorithm was proposed, initially, for the solution of global optimization problems but it can be used with the suitable modifications for the solution of any other problem [16]. The algorithm consists of three movements that simulate the hunting of the krills and the communication with each other, thus, an equation is produced that is consisted of three different movements, the foraging action, the movement influenced by other krill and the physical diffusion [14]. The equations of the Krill Herd algorithm are [2, 14,15,16]:

$$\begin{aligned} \frac{dX_{i}}{dt}= F_{i}+N_{i}+D_{i} \end{aligned}$$
(12)
$$\begin{aligned} F_{i} = V_f\beta _i + \omega _f F_{i}^{old} \end{aligned}$$
(13)
$$\begin{aligned} \beta _i = \beta _{i}^{food} + \beta _{i}^{best} \end{aligned}$$
(14)
$$\begin{aligned} N_{i}^{new} = N^{max}\alpha _i + \omega _n N_{i}^{old} \end{aligned}$$
(15)
$$\begin{aligned} D_i = D^{max}\delta \end{aligned}$$
(16)
$$\begin{aligned} X_i(t+\Delta t) = X_i(t) + \Delta t \frac{dX_i}{dt} \end{aligned}$$
(17)

where \(F_i\), \(N_i\), and \(D_i\) denote the foraging motion, the motion influenced by other krill, and the physical diffusion of the krill i, respectively. The \(F_i\) simulates the current food location and the information of previous location (Eq. 13), \(V_f\) is the foraging speed, \(\omega _f\) is the inertia weight of the foraging motion in (0,1), \(F_i^{old}\) is the last foraging motion. The \(N_i\) movement (Eq. 15) is estimated by the target effect, the local effect and the repulsive effect. The \(N^{max}\) is the maximum induced speed, \(\omega _n\) is the inertia weight of the second motion, \(N_i^{old}\) is the last motion influenced by other krill. The physical diffusion (Eq. 16) is a random process where \(D^{max}\) is the maximum diffusion speed and \(\delta \) is a random number. Finally, the time-relied position from time t to \(t+\Delta t\) is given by Eq. 17.

In the Parallel Multi-Start Non-dominated Sorting Krill Herd algorithm (PMS-KH), initially, a set of krills (possible solutions) (X) are randomly placed in the solution space. As the studied problem is a variant of the Vehicle Routing Problem, the solution should represent a number of routes that vehicles follow. However, as the equations of the Krill Herd algorithm are suitable for global optimization problems, we transformed suitably the initial solutions. Then, we used the equations of the KH algorithm, described previously, and we transformed back the solutions in order to calculate the objective functions. In every iteration, the non-dominated solutions are found.

As the use of the equations for the calculation of the KH algorithm, could produce some inefficient solutions (due to the transformation of the solutions from continuous values to discrete values and vice versa), it was decided to add another phase for the calculation of the new positions in the algorithm in order to take advantage of possible good new and old positions in the whole set of solutions. Thus, the solutions of the last two iterations (iteration it and \(it+1\)) 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 as it was modified in [7]. The first W solutions of the new vector are the produced solutions of the iteration \(it+1\). The distribution of the new solutions is performed based on the values of the rank and the crowding distance. The new solutions are evaluated by each objective function separately. A Variable Neighborhood Search (VNS) algorithm is applied to the solutions with both the \(vns_{max}\) and the \(local_{max}\) equal to 10 [7]. The personal best solution of each krill is found by using the following observation. If a solution in iteration \(it+1\) dominates its previous best solution of the iteration it, then, the previous best solution is replaced by the current solution. On the other hand if the previous best solution dominates the current solution, then, the previous best solution remains the same. Finally, if these two solutions are not dominated between them, then, the previous best solution is not replaced. It should be noted that the non-dominated solutions are not deleted from the Pareto front and, thus, the good solutions will not be disappeared from the population. In the next iterations, in order to insert a new solution in the Pareto front archive, there are two possibilities. First, the new solution is non-dominated with respect to the contents of the archive and secondly it dominates any solution in the archive. In both cases, all the dominated solutions, that already belong to the archive, have to be deleted from the archive. At the end of each iteration, from the non-dominated solutions from all populations the Total Pareto Front is updated considering the non-dominated solutions of the last population. The algorithm terminates when a predefined maximum number of iterations reached.

3 Computational Results

The whole algorithmic approach was implemented in Visual C++ and was tested on a set of benchmark instances. The data were created according Rapanaki et al. [11, 12] research and the size of each benchmark instance is equal to 100 nodes. Also, the algorithms were tested for ten instances for the two objective functions (OF1-OF2 or OF1-OF3) five times [11]. For the comparison of the four algorithms, we use four different evaluation measures: the range to which the front spreads out (\(M_k\)), the number of solutions (L), the combination of the spread and distribution of the solutions (\(\Delta \)) and the coverage measure, where the fraction of solutions in one algorithm that are weakly dominated by one or more solutions of the other algorithm is calculated (C). It is preferred the L, \(M_k\) and C measures to be as larger as possible and the \(\Delta \) value to be as smaller as possible (for analytical presentation of the measures please see [8]). The results of the proposed algorithm are compared with the results of the Parallel Multi-Start Non-dominated Sorting Particle Swarm Optimization (PMS-NSPSO) [10], the Parallel Multi-Start Non-dominated Sorting Differential Evolution (PMS-NSDE) algorithm [8], the Parallel Multi-Start Non-dominated Sorting Artificial Bee Colony (PMS-ABC) algorithm [12] and the Parallel Multi-Start Non-dominated Sorting Genetic Algorithm II (PMS-NSGA II) algorithm [9].

Table 1. Average results and best runs of all algorithms used in the comparisons in the asymmetric problems.
Full size table
Table 2. Average Results and Best Runs of all algorithms used in the comparisons in the symmetric problems.
Full size table
Table 3. 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
Table 4. 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
Table 5. Results of the C measure for the four algorithms in ten instances, when an Asymmetric Pick-up problem using objective functions OF1-OF3 is solved
Full size table
Table 6. Results of the C measure for the four algorithms in ten instances when a Symmetric Pick-up problem using objective functions OF1-OF3 is solved
Full size table
Table 7. Comparisons of all algorithms in all measures
Full size table
Fig. 1.
figure 1

Pareto fronts of the four algorithms for the instances “A-C-BD” and “B-C”.

Full size image

In Tables 1, 2, 3, 4, 5, 6, 7 and in Fig. 1, the computational results of the proposed algorithm are presented. Initially, in Tables 1 and 2 the computational results of the best execution of the proposed algorithm are compared with the computational results of the other four algorithms in the three evaluation measures in the asymmetric and symmetric cases, respectively. As in the proposed algorithm, the algorithms used in the comparisons, were executed five times and the computational results of the best execution were used for the comparisons. In Tables 3, 4, 5 and 6 the comparisons in the four different problems for the coverage measure are presented. Finally, in Table 7 a comparison of all algorithms in all measures is presented. In Fig. 1 four selected representative Pareto fronts of the four algorithms are given.

Generally, based on all Tables and Figures we can say that the proposed algorithm gave very competitive results compared to four well known algorithms from the literature. The proposed algorithm compared to the PMS-ABC algorithm gives superior results in three out four measures and inferior results in the Coverage measure. However, with all other algorithms used in the comparisons, the proposed algorithm gives superior results in Coverage measure and competitive results in all other measures. The PMS-ABC algorithm gives superior results in the Coverage measure compared to all other algorithms and inferior results compared to all other algorithms in the other three measures. The best results in all other measures are produced by PMS-NSGA II algorithm with slightly better results from the three other algorithms (PMS-PSO, PMS-DE and PMS-KH) and much better results than the PMS-ABC algorithm. The PMS-NSGA II could be the most efficient algorithm if its results in the Coverage measure were competitive with the results of any of the other four algorithms. Also, as it can be seen from Figure (1), the Pareto fronts produced by PMS-NSGA II are inferior from the ones of all the other algorithms. In total, the proposed algorithm (PMS-KH) is the most stable algorithm taking into account all the measures used in the comparisons.

4 Conclusions and Future Research

In this paper, we proposed an algorithm (PMS-KH) for solving four newly formulated multiobjective fuel consumption multi-depot vehicle routing problems (symmetric and asymmetric pick-up and symmetric and asymmetric delivery cases). The proposed algorithm was compared with other four algorithms, the PMS-ABC, the PMS-NPSO, the PMS-NSDE and PMS-NSGA II. In general, in the four different problems, the PMS-KH algorithm performs slightly better than the other four algorithms in most measures, as we analyzed in the Computational Results section. As expected, the behavior of the algorithms was slightly different when a symmetric and an asymmetric problem was solved. Our future research will be, mainly, focused on PMS-KH algorithm in other multiobjective combinatorial optimization problems.