1 Introduction

The vehicle routing problem (VRP) is one of the most important and widely studied within the context of combinatorial optimization. It includes many relevant issues of transportation logistic, e.g., the pickup and delivery of materials, a problem of particular interest for industries concerned with the efficient management of returned goods for recycling, re-manufacturing or reuse.

In some variants of the VRP the delivery of products is mandatory, while the collection can be postponed. Traditionally, the VRP has been defined as mono-objetive and solved using exact methods. In [34], a single-VRP with unrestricted backhauls, in which a profit value is associated for each satisfied collect demand, is solved with an exact branch-and-bound algorithm. Later works [14, 15] presented a branch-and-cut algorithm to solve the same problem, and a branch-and-price algorithm to solve five variants of the VRP with delivery and selective pickups with time windows. Recently, mono-objective versions of the VRP have been solved using heuristics, most of them based on local search such as simulated annealing [25] and tabu search [13, 23]. These general procedures explore the space of the solution to find good solutions with a reasonable computational time [12].

Several practical VRPs are multiobjective by nature, due to the inherent necessity of considering aspects other than the minimization of the total cost [28], such as customer satisfaction, labor regulations, or other aspects of the problem [21]. There are however few works that treat the VRP as multiobjective, in particular those problems involving pickup and delivery services [20].

In terms of multiobjective approaches, metaheuristics such as genetic algorithms [8, 30], tabu search [9, 16, 26], memetic algorithms [10] and simulated annealing [5, 31, 36] have been widely used to generate approximately efficient solutions for multiobjective problems. In general, algorithms based on local search perform well in multiobjective combinatorial problems [3, 18, 35] and could be applied to VRPs.

We discuss in this work an adaption on the VRP in order to treat its multiobjective nature with fixed deliveries and optional collections. More specifically, the objectives are defined as the minimization of route costs and of collection demands not fulfilled. We also propose a multiobjective version of the iterated local search (ILS) heuristic. The MOILS approach is applied to a set of instances containing between 50 and 199 customers plus the depot, and is compared to other approaches available in the literature [3, 4, 6, 19].

2 Problem description

The multiobjective VRP with fixed delivery and optional collections consists in defining a set of routes that minimize the transportation cost and the number of collections not carried out, attending all delivery demands. Each customer must be visited by one vehicle, and partial execution of demands is not allowed.

2.1 Mathematical formulation

The mathematical formulation is a generalization of the model proposed in [23] for the VRP with simultaneous pickup and delivery (VRPSPD), obtained by transforming a constraint into an objective.

Let \(G = (V, A)\) be a complete graph, with \(V = \{0, 1, 2, \ldots , n\}\) the set of vertices and \(A = \{(i,j) : i,j \in V, i \ne j\}\) the set of edges. The vertex \(0\) represents the depot and the others represent the customers. Each edge \((i,j)\) has an associated value \(c_{ij} \ge 0\) that represents the cost for reaching vertex \(j\) from vertex \(i\). Each customer \(i\) has a demand \(d_{i}\) for delivery and a demand \(p_{i}\) for collection. There are \(\overline{k}\) homogeneous vehicles available, each with capacity \(Q\). The parameter \(y_{ij}\) is the sum of the collected load between the depot and the node \(i\) (included) driven to node \(j\). The parameter \(z_{ij}\) is the sum of the load delivered to customers after node \(i\) (excluded) driven to node \(j\). We use the edge variable \(x_{ij}^k\), which is equal to one if edge \((i,j)\) is traveled by vehicle \(k\) and zero otherwise, and the choice variable \(\ell _j\), which is equal to one if pickup demand of customer \(j\) is satisfied, and zero otherwise.

The objectives of this problem can be expressed as:

$$\begin{aligned}&\text{ minimize} \left\{ \begin{array}{ll}&\sum \nolimits ^{\overline{k}}_{k=1}\sum \nolimits ^{n}_{i=0}\sum \nolimits ^{n}_{j=0}c_{ij}x^{k}_{ij}\\&\sum \nolimits ^{n}_{j=1}p_{j}(1 - \ell _{j}) \end{array}\right.&\end{aligned}$$
(1)
$$\begin{aligned} \text{ Subject} \text{ to:}&\sum ^{n}_{i=0}\sum ^{\overline{k}}_{k=1}x^{k}_{ij} = 1,&j = 1,\ldots ,n \end{aligned}$$
(2)
$$\begin{aligned}&\sum ^{n}_{i\!=\!0}x^{k}_{ij} \!-\! \sum ^{n}_{i\!=\!0}x^{k}_{ji} \!=\! 0,&j \!=\! 0,\ldots ,n \quad \mathrm and \quad k \!=\! 0,\ldots ,\overline{k} \end{aligned}$$
(3)
$$\begin{aligned}&\sum ^{n}_{j=1}x^{k}_{0j} \le 1,&k = 1,\ldots ,\overline{k} \end{aligned}$$
(4)
$$\begin{aligned}&\sum ^{n}_{i=0}z_{ij} - \sum ^{n}_{i=0}z_{ji} = d_{j},&\forall j \ne 0 \end{aligned}$$
(5)
$$\begin{aligned}&\sum ^{n}_{i=0}y_{ij} - \sum ^{n}_{i=0}y_{ji} = p_{j}\ell _{j},&\forall j \ne 0 \end{aligned}$$
(6)
$$\begin{aligned}&y_{ij} + z_{ij} \le Q \sum ^{\overline{k}}_{k=1}x^{k}_{ij},&i, j = 0,\ldots ,n \end{aligned}$$
(7)
$$\begin{aligned}&x_{ij}, \ell _{j} \in \{0, 1\},&i, j = 0,\ldots ,n \end{aligned}$$
(8)
$$\begin{aligned}&y_{ij}, z_{ij} \ge 0,&i, j = 0,\ldots ,n \end{aligned}$$
(9)

The two objective functions (1) are the total cost of the routes and the collections not carried out, and have to be minimized. The constraints model the following requirements: each point of demand must be visited by only one vehicle (2); the same vehicle arrives and departs from each client (3); a maximum of \(\overline{k}\) vehicles can be used (4); all delivery demands must be met (5); when variable \(\ell _j\) is equal to one, the pickup demand of customer \(j\) must be satisfied (6); all demands should be transported on the arcs included in the solution (7). In addition, (8) represents the integrality restriction and (9) a non-negativity constraint for collection and delivery demands.

2.2 Multiobjective iterated local search

The iterated local search (ILS) algorithm is based in the idea that the local search procedure can be improved from the generation of new solutions for the starting point by perturbing visited local optimal solutions [22].

Some heuristic approaches found in literature to solve the VRP with simultaneous pickup and delivery indicate that the use of ILS is a good alternative [32]. Some of its advantages are: the existence of few adjusting parameters when compared to the evolutionary methods, simplicity, robustness, effectiveness and the ease of implementation [22].

In this section, we present an adaptation of the ILS for the solution of combinatorial optimization multiobjective problems. This approach, called the multiobjective iterated local search (MOILS), is presented in Algorithm 1.

figure a

First, the MOILS constructs two initial solutions (line 1) by efficient hybrid algorithm based on ILS and random variable neighborhood descent (RVND), proposed in [27]. These solutions represent the extremes of the front, one being a point of maximum transportation cost and the other a point of minimum transportation cost, where no collections are performed. When all collection demands should be attended the problem is reduced to the mono-objective VRPSPD, and when no collection demand is attended it is reduced to the mono-objective capacitated VRP (CVRP).

The algorithm executes \(maxIter\) iterations (lines 3–15), where one non-dominated solution, in the front set, is selected (line 4) to be exploited (lines 6–14). The selection procedure is based on the crowding-distance [6], which allows less explored regions to have higher selection priority. In this work, the crowding-distance is calculated in a different manner, with the value of the extreme solutions equal to twice the distance between this point and the nearest solution. We have proposed this modification in order to guarantee the exploration of the two initial solutions (equivalent to the CVRP and VRPSPD solutions) in early iterations and to give advantage to more intermediate solutions after the iterative process starts generating more non-dominated points.

Given a selected solution, the algorithm executes \(maxCount\) iterations to explore it. In each iteration, this solution is perturbed and local search is applied, according to the ILS. Here, perturbation is done in two phases. In the first, the collection status (attempt or not attempt) of some customers randomly selected is changed. When the pickup demand ceases to be fulfilled, the respective customer can remain in the same position of the route. Otherwise, the load stored by the vehicle that will satisfy this demand must be verified. If its capacity is exceeded, the customer is inserted in the first viable position found. When no viable position is found, this customer is included in a new route. In the second phase, the algorithm applies one of the following perturbation mechanisms randomly chosen: Multiple Swap that reallocate different customers of the different routes randomly selected; Multiple Shift that exchanges two customers of distinct routes; and Ejection Chain that relocates a customer from route \(R_{1}\) to route \(R_{2}\), a customer from \(R_{2}\) to \(R_{3}\), and so on.

The local search phase explores the neighborhood of a solution with the objective of finding other non-dominated solutions for the problem. We have used the random variable neighborhood search (RVND) refinement method [27]. We implemented 12 types of movements to define the neighborhood, six inter-route and six intra-route. The inter-route movements are: (1) Shift(1,0), (2) Shift(2,0), that relocate a customer or two adjacent customers, (3) Swap(1,1), (4) Swap(2,1), (5) Swap(2,2) that interchange two customers, or two adjacent customers with one customers or with others two adjacent customers, and (6) Crossover that removes two arcs \((i,j)\) and \((i^{\prime },j^{\prime })\) and inserts two new arcs \((i,j^{\prime })\) and \((i^{\prime },j)\). The intra-route movements are: (1) Or-opt, (2) Or-opt 2, (3) Or-opt 3 that relocate one customer, or two or three adjacent customers, (4) 2-opt that removes two non-consecutive arcs \((i,j)\) and \((i^{\prime },j^{\prime })\) and replaces by the arcs \((i,i^{\prime })\) and \((j,j^{\prime })\), (5) Exchange two customers, and (6) Reverse the direction of the route, aimed at reducing the load of the vehicle. Figure 1 shows examples of these operations, in which the highlighted arcs and customers indicate the changes in the original solution.

Fig. 1
figure 1

Neighborhood structures

Full size image

The best improvement strategy was used in all neighborhood structures. The computational complexity of each one of these moves is \(O(n^2)\), except to reverse that is \(O(n)\). After RVND executions, the algorithm verifies if it is possible to attempt the pickup demands of some customers. The collection of one customer is carried out only if this demand does not exceed the capacity of the vehicle and if it can remain in the same position of the route.

The solution generated in the perturbation and local search procedures is then included in the front (line 9). The updating phase verifies if a specific solution \(s\) is non-dominated by any solution, then it is inserted in the set and the solutions dominated by it are eliminated. The variable \(count\) represents the number of iterations that one solution is explored without generating a new non-dominated solution. If one solution is inserted in the front then \(count\) is restarted (line 11), otherwise it is increased by one unit (line 14).

3 Experimental results

3.1 Test problems and performance metrics

To evaluate the performance of the MOILS, an experiment was set upFootnote 1 considering 14 problem instances ranging from 50 to 199 customers plus the depot [29]. The travel cost is calculated as the Euclidean distance between the points. Problems 1–5 have randomly placed cities in the plane, while problems 11 and 12 have cities appearing in clusters, in which the depot is not centered.

These instances were solved using the following approaches:

  1. 1.

    the MOILS, as described in Sect. 2.2. After preliminary testing, the constants were set as \(maxIter = 100\) and \(maxCount = 15\).

  2. 2.

    \(\epsilon \)-constrained approach (\(P_{\epsilon }\)) [4] using the ILS as the base algorithm, in order to compare the performance of our proposed MOILS against that of an adapted single-objective iterated local search. Preliminary testing suggested the use of \(50\) as the number of iterations for this method [22];

  3. 3.

    non-dominated Sorting Genetic Algorithm II (NSGA-II) [6], which is a standard evolutionary multiobjective algorithm. The implementation used crossover and mutation operators already adapted for VRPs [19], with a population size of \(500\) evolving over \(250\) iterations;

  4. 4.

    indicator-Based Multi-Objective Local Search (IBMOLS) [3], a local search-based method for multiobjective optimization included to provide a better comparison baseline. The implementation used the epsilon binary indicator, employed the same local search operators as the MOILS and the RM population generation method with the mutation based on perturbation mechanism of the MOILS. Preliminary testing suggested using a scale factor of \(0.1\), population size of \(10\) and \(50\) generation.

To evaluate the relative performance of these approaches, three performance metrics were considered: the hypervolume (S), standardized to the interval \((0,1)\) independently for each problem; the Coverage of Two Sets [37]; and the cardinality (Card) of the final solution set returned. Both the S and CS-metrics return values representing percentages, while the Cardinality metric provides absolute values.

The free parameters of the algorithms used were adjusted in order to provide each method with approximately the same run time. No significant differences were detected in the runtime of the algorithms tested (\(p>0.05\)).

3.2 Statistical design

We have employed statistical tests designed to detect significant differences and to estimate their magnitude for each quality metric. The data used was composed of the metrics calculated for the final Pareto-fronts obtained on eight independent runs of each algorithm on each problem.

For each metric, the experiment was designed as a randomized complete block design (RCBD) with the algorithms as levels of the experimental factor, and the problems as a blocking factor [24]. By treating the problems as blocks, it was possible to model and remove the effects of different instances on the performance of the algorithm, and obtain an overall performance difference across all test instances used. The null hypotheses of absence of differences among the algorithms evaluated over all problems were considered against two-sided alternatives. To avoid the assumptions of the F test, the more versatile Gore test [11], a more robust alternative for the ANOVA, was employed.

After testing for significance, least squares estimators of the block (instance) effects were obtained [24] and subtracted from the samples, thus allowing a problem-independent estimation of the effect size for each algorithm. The estimations of effect size were calculated by means of the Hodges–Lehmann (HL) estimator of the median of differences between two independent samples [17]. A more detailed description of the statistical methods is available in an earlier work [1].

3.3 Results and discussion

The results obtained for the experimental comparison are summarized in Table 1, which reports the mean and standard deviation values of the three metrics considered in each problem; and Table 2, where the results of the statistical analysis are summarized and the magnitude of the statistically significant differences are presented.

Table 1 Mean values and standard deviations (in the parentheses) for the performance metrics used
Full size table
Table 2 Estimated difference in average performance between the row and column algorithms for the performance metrics
Full size table

For the hypervolume, all algorithms presented a relatively solid performance in most problems, as shown in Table 1, with the \(P_\epsilon \) returning slightly smaller values than the other three methods. The statistical analysis reported in Table 2 confirms this observation, showing that all algorithms presented small but statistically significant differences, with the MOILS showing the best results (\(11~\%\) superior to the \(P_\epsilon \), \(8~\%\) better than the NSGA-II and \(6~\%\) superior to the IBMOLS). This result indicates that the proposed approach was generally able to obtain better fronts, either by returning a well-spread set of solutions, or points that were closer to the real Pareto-optimal front.

The average differences obtained for the cardinality metric were also relatively modest. Table 1 shows that, for each particular problem, all algorithms returned approximately the same mean number of solutions, with no large trends being easily discernible. Table 2 shows that, when integrated over all problems, small but statistically significant differences were observed, with the MOILS returning on average \(2.56\) more solutions than the \(P_\epsilon \), \(4.32\) more than the NSGA-II, and \(6.06\) more than the IBMOLS.

The differences in performance observed for the coverage metric were considerably large. By examining the results in Table 2, it can be easily seen that the MOILS was able to outperform the \(P_\epsilon \) by an average of \(0.7\), the NSGA-II by \(0.32\) and the IBMOLS by \(0.13\). This is a strong indicator of superiority, since it means that, on average, the fronts found by the MOILS were able to dominate, on average, about \(70~\%\) of the ones yielded by the \(P_\epsilon \) method, \(32~\%\) of those obtained by the NSGA-II and \(13~\%\) of the fronts returned by the IBMOLS. To simplify the reporting of the relative coverage values, a generalized version of the Coverage of Two Sets, called Coverage of Many Sets [2], was employed to generate the data shown in Table 1. Instead of quantifying how much a given algorithm covers another, this generalized metric instead measures how much a given algorithm covers the union of the final fronts returned by all algorithms except itself.

Figure 2 shows two representative examples of fronts obtained by the algorithms. Since the true Pareto-optimal front is not known for the problems considered, it is not possible to objectively evaluate the absolute quality of the fronts obtained. However, the extreme point of the fronts obtained for the case in which all pickups are performed is equivalent to the corresponding VRPSPD instance. Table 3 shows a comparison of the extreme point of the non-dominated fronts obtained by the MOILS with the best known results for this problem [32], showing that, at least for the extreme points, the MOILS approach is able to find solutions that are generally very close to the best available in the literature.

Fig. 2
figure 2

Typical fronts obtained by the algorithms on selected problems

Full size image
Table 3 Comparison with best known single-objective results for the VRPSPD
Full size table

4 Conclusions

We proposed an adaptation of the mathematical formulation for the multiobjective VRP with fixed delivery and optional collections, which takes into account the total cost of the solution and the number of pickups performed. A multiobjective version of the iterated local search algorithm (MOILS) was proposed and compared on a test set of 14 benchmark problems against the \(P_{\epsilon }\), NSGA-II and IBMOLS approaches. The results obtained show that the MOILS was able to significantly outperform the three methods, obtaining superior values for coverage, hypervolume and cardinality across the set of test problems used.