Keywords

1 Introduction

The generalized vehicle routing problem with stochastic demands (GVRPSD) combines the vehicle routing problem with stochastic demands (VRPSD) with the generalized vehicle routing problem (GVRP) and is a stochastic combinatorial optimization problem.

In the GVRPSD we are given a weighted complete undirected graph \(G=(V,E)\) with a set of nodes \(V\) and a set of edges \(E\). The edges \((i,l)\in E\) are weighted with distances \(d_{il}\ge 0\). The set of nodes is partitioned into \(m\) disjoint subsets or clusters \(C=\{C_0,C_1,\dots ,C_m\}, C_0,\dots ,C_m\subseteq V,\) such that \(C_0\cup C_1 \cup \dots \cup C_m=V\). Node \(v_0\in V\) is a dedicated depot and the only node of cluster \(C_0\). Each other cluster \(C_j,\forall j=1,\dots ,m\) has an associated demand \(\xi _j\) which is a random variable following a known discrete probability distribution, i.e., we know for each cluster \(C_j\) the probability \(p_{jk}=P(\xi _j=k)\) that cluster \(j\) has a demand of \(k\ge 0\). Furthermore, we are given a vehicle with a limited capacity \(Q\). For avoiding the necessity of multiple visits we assume that \(p_{jk}=0,\ \forall j=1,\dots ,m,\ \forall k>Q\). The aim is to find a route visiting exactly one node from each cluster \(C_1,\dots ,C_m\) exactly once and thereby distributing goods according to the clusters’ actual demands. The current load of the vehicle decreases each time a cluster demand is satisfied but is refilled to \(Q\) each time it returns to the depot. The amount of how much the load gets decreased by visiting cluster \(j\) is dependent on the actual realization of \(\xi _j\), which becomes known only upon arrival. Possibly, the vehicle will get empty, i.e., the current load becomes zero and the vehicle has to restock at the depot before continuing the route. Such an event is called a stockout. A common approach for solving such stochastic optimization problems is the use of a-priori routes, which has already been used for several probabilistic problems [3, 4, 13]. A-priori tours are planned before the actual realizations of the random variables are known but taking their probability distributions into account. The aim of the problem is to minimize the expected length of the tour under all possible a-posteriori tours.

In the literature there are several restocking strategies described for the VRPSD which can be adapted to the GVRPSD as well. The by far most common is the standard restocking policy [7, 12, 15, 20] where on each stockout the vehicle returns to the depot, refills its load, and continues its tour at the last visited node. Another method for handling stockouts is re-optimization [22]: whenever a stockout occurs the vehicle returns to the depot and then the tour through the remaining clusters is re-planned. Apart from the re-optimization approach, which can be problematic when implemented in practical applications, the preventive restocking policy [4, 16, 17, 24] is the most cost efficient.

In the preventive restocking method return trips to the depot can also be performed before an actual stockout occurs. It originates from the observation that a repeated visit of the same node after a restocking is usually expensive and can often be avoided if the restocking is done after servicing the preceding cluster. Especially on instances where the triangle inequalities hold, a restocking from the preceding cluster is always more cost efficient. Another advantage from using the preventive restocking strategy is that it is sufficient to plan one giant tour through all clusters when the problem is not further constrained. Yang et al. [24] proved this property for the VRPSD and it can be directly applied to the GVRPSD as well. Along with that proof they also proposed an evaluation procedure for the giant tour representation, which we will discuss in Sect. 3.

Like the GVRP this problem can be applied to the field of healthcare logistics, in which medical supplies are delivered to districts and the distributing company does not know beforehand how much supply is needed. If it does not matter to which hospital in each district these supplies are delivered this problem can be modelled as a GVRPSD. Another application domain is urban waste management, where refuse collecting vehicles gather waste from districts returning it to a central landfill site and the total amount of waste is not known beforehand.

In this work we describe a variable neighborhood search (VNS) [10] approach for the GVRPSD with preventive restocking. We use the giant tour representation and an evaluation procedure similar to the one used for the VRPSD [24], which is based on dynamic programming (DP). In addition to this solution evaluation procedure we also propose a multi-level evaluation scheme which iteratively approximates the quality of a solution candidate until it can be discarded as being inferior or the exact objective is obtained. In the next section the related work for this problem is discussed. Section 3 is dedicated to the solution representation and the associated evaluation procedure including the multi-level evaluation scheme. The actual variable neighborhood search and its operators are described in Sect. 4. We present computational results for this approach in Sect. 5 and draw conclusion of our work along with thoughts on future work in Sect. 6.

2 Related Work

To the best of our knowledge the GVRPSD has not been considered in the literature so far. However, there are many related problems which have been broadly discussed like the VRPSD, which is a special case of the GVRPSD but each cluster is a singleton. Especially the work by Yang et al. [24] and Bianchi et al. [4], which both used the preventive restocking strategy, has been inspiring to the approach for the GVRPSD presented here. Yang et al. [24] showed that planning multiple tours cannot lead to a better solution in the VRPSD. They also presented an evaluation procedure based on dynamic programming for the giant tour representation. The same evaluation is also used by Bianchi et al. [4] who developed several metaheuristics and an approximate delta evaluation for the VRPSD. The most recent work for the VRPSD utilizing the preventive restocking policy is by Marinakis et al. [17] who also applied the same evaluation procedure and presented a clonal selection algorithm. They reported promising results on their benchmark set and compared their algorithm to two versions of a particle swarm optimization [16], to a differential evolution, and a genetic algorithm.

Another related problem is the GVRP, which is the special case of the GVRPSD with deterministic demands. There are usually capacity or distance constraints on the used vehicles and therefore several routes have to be devised. There are several exact and heuristic solution approaches in the literature [1, 2, 8, 18, 19]. Since we are considering a giant tour approach the generalized traveling salesman problem (GTSP) is also closely related. The GTSP was originally introduced independently in [11, 21, 23]. In Fischetti et al. [5, 6] integer linear programming models are formulated and analyzed. For our construction heuristic we use one of their formulations.

3 Solution Representation and Evaluation

In the introduction we mentioned that it is sufficient to plan one giant tour through all clusters and therefore we use a solution representation based on the sequence of clusters that are visited in the tour. From this permutation of clusters we compute the expected cost using a DP algorithm based on the DP for the VRPSD [24]. We adapt it to the GVRPSD by also considering that we only have to visit one node per cluster. The worst case run-time complexity remains \(\mathcal {O}(|V|Q^2)\).

First we describe the notations used in the DP. The function used for the recursion \(f_{ij}(q)\) is defined for all \(q=0,\dots ,Q\), \(j=0,\dots ,m\), \(i=0,\dots ,|C_{j}|\) and can be interpreted as the remaining cost of the tour after servicing the \(i\)-th node of cluster \(j\) with the residual vehicle capacity \(q\). We also define an auxiliary function \(b_j(l)\) which returns the \(l\)-th node of cluster \(j\). Let us assume that the clusters of the tour we want to evaluate are relabeled such that the tour is \(t=(C_0,C_1,\dots ,C_m,C_0)\). Then the DP recursion is given by:

$$ f_{ij}(q)=\min \{f_{ij}^p(q),f_{ij}^r(q)\}$$
$$ \forall q=0,\dots ,Q, j=0,\dots ,m, i=0,\dots ,|C_{j}| $$

and the boundary condition

$$ f_{im}(q)=d_{b_m(i),0},\quad \forall q=0,\dots ,Q,\ i=0,\dots ,|C_m|$$

The basic principle of this recursion is that for each node \(i\) and each vehicle load \(q\) it is computed if it is more cost-efficient to proceed directly to the next cluster which costs \(f_{ij}^p(q)\) or to make a preventive restock which costs \(f_{ij}^r(q)\). The total expected cost of the tour \(t\) is then given by the value of \(f_{0,0}(Q)\). For our VNS such an expensive solution evalution is inconvenient for larger instances with a large vehicle capacity. In the next section we describe a method to potentially reduce the run-time of the solution evaluation within the VNS framework, which can also be applied to other metaheuristics.

3.1 Multi-level Evaluation Scheme

In this section we describe a multi-level evaluation scheme (ML-ES) to iteratively estimate the exact objective value of a solution candidate with increasing accuracy until we either know that it cannot be better than the best solution found so far or we know its exact value. The basic idea is to scale down both the vehicle capacity and the probability distribution of the demand for each cluster accordingly. Since the time needed for the solution evaluation is quadratically dependent on \(Q\), a large performance gain in terms of run-time is expected when \(Q\) is decreased.

In our ML-ES there are \(\log _2Q\) levels of approximation, where level \(0\) is the exact evaluation and \(\log _2Q\) is the roughest approximation level. Starting with level 0, increasing the level by one means to scale down the vehicle capacity \(Q\) and all demand distributions \(p_{jk}\) by a factor of two. We introduce a new vehicle capacity \(Q^i\) and new probabilities \(p_{jk}^i\) subject to level \(i\), which are defined in the following way:

$$\begin{aligned} Q^0&= Q \end{aligned}$$
(1)
$$\begin{aligned} p_{jk}^0&= p_{jk}&\forall j=1,\dots ,|C|,\ k=0,\dots ,Q \end{aligned}$$
(2)
$$\begin{aligned} Q^i&= \left\lceil \frac{Q^{i-1}}{2}\right\rceil&\forall i=1,\dots ,\lceil \log _2Q\rceil \end{aligned}$$
(3)
$$\begin{aligned} p_{jk}^i&= p_{j,2k}^{i-1} + p_{j,2k+1}^{i-1}&\forall j=1,\dots ,|C|,\ k=0,\dots ,Q^i, \\&&\forall i=1,\dots ,\lceil \log _2Q\rceil \nonumber \end{aligned}$$
(4)

Figure 1 shows exemplarily for one cluster how the probability distribution for the demand changes at each level.

Not only is level \(i\ge 1\) an approximation, but its objective value is also a lower bound for the objective value of the preceding level \(i-1\), which we will show next.

Fig. 1.
figure 1

An exemplary demand probability distribution and its different levels of approximation.

Full size image

Lemma 1

With increasing level \(i\) the ratio of the scaled expected demand of each cluster to the vehicle capacity \(Q^i\) is non-increasing.

Proof

We have to show for each cluster \(j\) and each demand \(0\le k\le Q\) that

$$\frac{\sum _{k=0}^{Q^i}kp_{jk}^i}{Q^i}\le \frac{\sum _{k=0}^{Q^{i-1}}kp_{jk}^{i-1}}{Q^{i-1}},\quad \forall i=1,\dots ,\lceil \log _2Q\rceil $$

is valid. Suppose to the contrary that for one cluster \(j\) and one demand \(k\) the following holds:

$$\begin{aligned} \frac{kp_{jk}^i}{Q^i}=\frac{k(p_{j,2k}^{i-1}+p_{j,2k+1}^{i-1})}{\frac{Q^{i-1}}{2}}&> \frac{2kp_{j,2k}^{i-1}+(2k+1)p_{j,2k+1}^{i-1}}{Q^{i-1}}=\frac{kp_{jk}^{i-1}}{Q^{i-1}} \\ 2kp_{j,2k}^{i-1}+2kp_{j,2k+1}^{i-1}&> 2kp_{j,2k}^{i-1}+2kp_{j,2k+1}^{i-1}+p_{j,2k+1}^{i-1} \\ 0&> p_{j,2k+1}^{i-1} \end{aligned}$$

Obviously, this is a contradiction because all probabilities must be non-negative. Therefore, as no \(\frac{kp_{jk}^i}{Q^i}\) can be larger than \(\frac{kp_{jk}^{i-1}}{Q^{i-1}}\) for any cluster \(j\) this also holds for the sum over all demands, which proves the Lemma. \(\quad \square \)

Theorem 1

Let \(c^i(t)\) be the objective value of a tour \(t\) on approximation level \(i\). For each tour \(t\) it holds that \(c^i(t)\le c^{i-1}(t), \forall i=1,\dots ,\lceil \log _2Q\rceil \).

Proof

Due to Lemma 1 it follows that the total expected relative demand of all clusters on level \(i\) is smaller or equal to that of level \(i-1\). So we can possibly service more customers before a restocking is needed and therefore the resulting objective \(c^i(t)\) value is a lower bound to the exact objective value \(c^0(t)\) and to the objective value at the preceding level \(c^{i-1}(t)\). \(\quad \square \)

Algorithm 1 describes our ML-ES in pseudocode, where \( DP (t,i)\) executes the DP described above with the scaled vehicle capacity and probability distributions according to (1–4). Algorithm 1 returns either the exact objective value of \(t\) if \( DP (t,0)\) is executed or a lower bound to the exact value otherwise. In the latter case the solution candidate can immediately be discarded because we know that it cannot be better than the best solution found so far.

figure a

4 Variable Neighborhood Search

The proposed VNS follows the general variable neighborhood search scheme as described in [9]. The underlying variable neighborhood descent (VND) considers three neighborhood structures which are well-known for the TSP: 1-shift, 2-opt, and Or-opt. As a shaking procedure for diversification we perform \(k^2\) moves in the \(k\)-th neighborhood with \(k=1,\dots ,3\).

4.1 Initial Solution

For finding an initial solution two types of construction heuristics are considered. The first, farthest insertion, is well-known for the classical traveling salesman problem and suited for Euclidean instances only. It builds iteratively a tour by starting at the depot cluster and inserting the cluster which is farthest away from the last inserted cluster at the best possible position. For that purpose we have to define distances between clusters, which is done by computing the geometric centers of clusters by taking the average of the \(x\)- and \(y\)-coordinates of its nodes. Then the distance between two clusters is the Euclidean distance between their centers.

An alternative but much more time-consuming method for finding a starting solution is solving the GTSP relaxation of the problem. From the solution of the GTSP relaxation we extract the cluster sequence which is then our initial solution. The GTSP is solved exactly by using a branch-and-cut algorithm with CPLEX and the E-GTSP formulation described in [6].

4.2 Neighborhood Structures

Three types of neighborhood structures are used in the VND part, which are searched with a best improvement step function in the order they are described here.

1-shift: A cluster is shifted to another position of the tour.

2-opt: A subsequence of the tour is inverted.

Or-opt: First two, then three consecutive clusters are shifted to another position of the tour. Note that Or-opt usually starts by shifting only one cluster in the tour but we covered this case by our first neighborhood structure and omit it here.

5 Computational Results

The VNS is implemented in C++ and for the GTSP starting solution CPLEX in version 12.5 is used. All our tests were carried out on a single core of an Intel Xeon with 2.53 GHz and 3GB RAM. We created Euclidean instances for the GVRPSDFootnote 1 based on instances for the GVRP [2] by assigning the original demand values to be the expected demands and deciding independently at random for each cluster if it is a low spread or a high spread cluster. For low spread clusters the set of possible demands is \(\pm 10\,\%\) of the expected value and for the high spread it is \(\pm 30\,\%\). All of these demand values are considered equally likely, so we assumed a uniform distribution over these values. We do not consider demand values smaller than zero or larger than \(Q\). Due to space limitations the numerical results presented in this section are based on a representative selection of 37 instances out of the originally proposed 158 instances. These instances are selected such that a comparison to an existing exact method is possible. The full result tables can be found at our website (see Footnote 1).

In the following tables the column Instance contains the name of the instance, followed by the number of nodes \(n\) and the number of clusters \(m\). Additionally the expected number of restocks \(E[nr]\) are presented. Then the results for the different configurations are given with their (average) objective values, their standard deviations (\( sd \)) if applicable and either the total run-time in seconds \(t[s]\) for the deterministic configurations or the average time when the best solution is identified \(t^*[s]\).

First we compare the results of the different starting solutions, farthest insertion (FI) and GTSP, with a subsequent VND using the neighborhood structures and the order described in Sect. 4.2. Table 1 shows the (deterministic) numerical results for these configurations. Additionally it contains a third configuration where the ML-ES is used along with the GTSP starting solution.

Table 1. Results for the different configurations of the VND.
Full size table
Table 2. Comparison of the proposed VNS with an exact integer L-shaped method.
Full size table

The results indicate that both starting solutions produce similarly good results for the instances with up to 75 nodes. However, when considering larger instances with 76 nodes and more, FI is not competitive anymore. When starting from an inferior solution produced by FI the VND needs too much time and could not even be completed within the time limit of 10000 s. When comparing run-time we also see the advantage of using the GTSP over the FI; for most of the instances, especially for the larger ones, it pays off to invest more time to get a better starting solution so that the subsequent VND does not need so many iterations. We also applied the ML-ES to the GTSP + VND configuration and we observe a huge drop in run-time. It is clear that the resulting solution is the same as in the GTSP + VND configuration but the run-time could be reduced substantially. Only by using the ML-ES the VND is about 10 times faster on average with a peak speedup factor of 75 for instance P-n76-k4-C26-V2. During our tests when a solution is evaluated using ML-ES the procedure could be terminated in the top 30 % of the approximation levels where the acceleration is the largest.

Next we show how average results over 30 independent runs of the VNS with the GTSP starting solution and the ML-ES compares to an exact algorithm. The exact algorithm is the integer L-shaped method [14] applied to the GVRPSD which is a two-level approach based on a mixed integer programming model for the GTSP. Within a branch-and-cut framework it iteratively adds cuts generated in the lower level setting a lower bound on the restocking costs in the upper level. Due to space limitation this method is not described here in more detail. For the exact algorithm the optimality gap (\( gap \)) and the time needed is stated in the table.

Table 2 shows the numerical comparison with the exact method. The high optimality gaps on the medium to large instances show that the GVRPSD is a hard problem but on the instances where the L-shaped method is able to find a proven optimal solution the VNS also finds it in substantially less time. In the extreme case of instance A-n34-k5-C12-V2 the VNS found an optimal solution in all 30 runs about 865 times faster than the exact algorithm. However, since the L-shaped method guarantees the optimality of the solution we cannot directly compare the run-time of these algorithms. Our tests further showed that in the VNS the ML-ES can be terminated within the top 4 % of the approximation levels which is even better than for the VND.

6 Conclusions and Future Work

In this work a variable neighborhood search approach for the generalized vehicle routing problem with stochastic demands under the preventive restocking policy is presented. The problem has not yet been considered so far in the literature although many real world problems can be modelled in this way. An initial attempt to solve this hard stochastic combinatorial optimization problem was made. Therefore, concepts from both, the related VRPSD and the GTSP, are used. The solution representation and the solution evaluation method that had proved to work well for the VRPSD were adapted to the GVRPSD. On top of that a multi-level evaluation scheme was used to substantially reduce the time needed for evaluating a solution candidate. The computational results show that the VNS with the GTSP initial solution and the ML-ES is able to find optimal or near-optimal solutions in short times. Future work can include the development and improvement of the exact algorithm for the GVRPSD to get optimal solutions to more instances. In a following step also the combination of the techniques presented here, especially the ML-ES, and the methods used for solving this problem exactly should be investigated. Although the ML-ES is primarily developed for the GVRPSD applications to other similar problems like the VRPSD are also possible and could lead to a significant performance gain.