Variable neighborhood search for the travelling deliveryman problem

Abstract

A travelling deliveryman needs to find a tour such that the total waiting time of all the customers he has to visit is minimum. The deliveryman starts his tour at a depot, travelling at constant velocity. In this paper we suggest a general variable neighborhood search based heuristic to solve this NP-hard combinatorial optimization problem. We combine several classical neighborhood structures and design data structure to store and update the incumbent solution efficiently. In this way, we are able to explore neighborhoods as efficiently as when solving the travelling salesman problem. Computational results obtained on usual test instances show that our approach outperforms recent heuristics from the literature.

1 Introduction

The travelling deliveryman problem (TDP), also known as the minimum latency problem or travelling repairman problem, is a variant of the travelling salesman problem (TSP). Differently from the classical TSP, where the travelling salesman is trying to minimize the length of the tour connecting all customers, in TDP the designed tour should minimize the total time customers are waiting to be served by a deliveryman (or a repairman).

On metric space, TDP is NP-hard (Blum et al. 1994). However, there are special graphs where TDP can be solved in polynomial time. Such graph classes are paths and trees with the diameters equal to 3 (Blum et al. 1994). Regarding exact methods for general graphs, Wu et al. (2004) suggested two methods: (i) Dynamic Programming and (ii) Branch and Bound (B&B). Using B&B method for example, authors of this article were able to solve exactly 50-customer instances in less than 100 seconds. It appeared to be significantly less efficient than the B&B of solver CPLEX using the MIP formulation described below. Méndez-Díaz et al. (2008) propose a new integer linear programming model for Minimum Latency Problem and a new B&B method for solving it. Experimental results show that proposed method allow them to solve exactly instances with up to $n=40$ customers. Their method is then compared with CPLEX solver. It is shown that the CPLEX execution time is significantly longer. Abeledo et al. (2010) propose branch–and–cut–and–price for solving TDP. The largest TSPLIB instance solved exactly had $n=107$ customers.

Salehipour et al. (2011) have recently proposed a heuristic that combines greedy randomized adaptive search procedure (GRASP) and variable neighborhood descent (VND), the deterministic variant of variable neighborhood search (VNS). Their sequential VND uses the following 5 neighborhood structures: (i) swap adjacent move (1-opt); (ii) swap move; (iii) 2-opt move; (iv) Or-opt move and (v) drop/add move.

In this paper we propose a General VNS for solving TDP. We implement neighborhood structures widely used for similar combinatorial problems, but, for the first time, within General VNS framework. In order to perform search through the different neighborhoods in more efficient way, we use preprocessing and intelligent updating of the incumbent solution. Moreover, we show that the worst-case complexity of neighborhood moves that we use are the same as the complexity of those moves used in solving TSP. Computational results performed on usual test instances show that our heuristic outperforms recent heuristics, and thus, it can be considered as a new state-of-the-art heuristic for solving TDP.

The paper is organized as follows. In Sect. 2 we give combinatorial and mathematical programming formulations of the problem. Complexity results of different moves used within variable neighborhood descent are discussed in Sect. 3, while in Sect. 4 we give pseudo-codes of our implementation of GVNS. Sections 5 and 6 contain computational results and conclusions, respectively.

2 Problem formulation

Combinatorial formulation Let $G = (V, A)$ be a complete, directed and asymmetric graph, where $V = \{0, 1, \ldots , n\}$ is a set of nodes. Nodes labelled with numbers 1, 2, ..., $n$ are delivery nodes and node with label 0 is the depot. The distance $d(i,j)$ is associated with each arc $(i, j) \in A$. The TDP consists in determining the tour, i.e. Hamiltonian path on the graph $G$,

$$\begin{aligned} x = (x_{0}, x_{1}, x_{2}, x_{3}, \ldots , x_{n}), \end{aligned}$$

starting at the depot node $x_{0} = 0$, so as to minimize the total waiting time of all customers to be served. Assume that the deliveryman travels at constant velocity $v$. Then the time to reach a client $i$ is equal to the ratio between the passed distance from the depot to the client $i$ and his/her velocity $v$. The distance that the deliveryman passes to reach the client $x_{1}$ is equal to $\delta _{1} = d(x_{0},x_{1})$. Similarly, to reach the client $x_{2}$ he/she needs to pass $\delta _{2} = d(x_{0},x_{1})+d(x_{1},x_{2})$, generally to reach a client $x_{k}$, the travel distance is

$$\begin{aligned} \delta _{k} = d(x_{0},x_{1}) + d(x_{1}, x_{2}) + \cdots + d(x_{k-1}, x_{k}). \end{aligned}$$

Therefore, the corresponding time of reaching the customer $x_{k}$ is as follows:

$$\begin{aligned} t_k = \frac{\delta _k}{v}. \end{aligned}$$

Since the objective function represents the sum of all such obtained time (for all $k$), it can be formulated as

$$\begin{aligned} \sum _{k=1}^{n} t_{k}. \end{aligned}$$

It is clear that the last expression may be formulated more simply as

$$\begin{aligned} \sum _{k=1}^{n} \frac{(n-k+1)d(x_{k-1},x_{k})}{v}. \end{aligned}$$

Since $v$ is constant, its value does not influence the optimal solution. Thus, the objective function to be minimized may be presented as

$$\begin{aligned} f(x) = \sum _{k=1}^n (n-k+1) d(x_{k-1}, x_k) \end{aligned}$$

(1)

Note that the time needed to go back to the depot is not included in the objective function.

Mixed integer programming (MIP) formulation As for the TSP, the TDP can also be formulated in different ways. Fischetti et al. (1993) used the so-called flow MIP formulation. The two sets of variables are defined as

$$\begin{aligned} X_{ij}&= \left\{ \begin{array}{l@{\qquad }l} 1,&\quad \,\text{ if} \text{ deliveryman} \text{ travels} \text{ arc} \text{(i,j)} \\ 0,&\quad \text{ otherwise} \end{array}\right.\\ Y_{ij}&= \left\{ \begin{array}{l@{\quad }l} 0,&\text{ if} \text{ arc} (i,j) \text{ is} \text{ not} \text{ used}\\ n-k,&\text{ if} (i,j) bad hbox \end{array}\right. \end{aligned}$$

Then the MIP formulation for the TDP is as follows:

$$\begin{aligned} \min \sum _{i=0}^{n} \sum _{j=0}^{n} d(i,j)Y_{ij} \end{aligned}$$

(2)

subject to

$$\begin{aligned}&\sum _{j=0, j\ne i}^{n} X_{ij} = 1 \quad \quad \quad \quad i=0, 1, 2, \dots , n \end{aligned}$$

(3)

$$\begin{aligned}&\sum _{i=0, i\ne j}^{n} X_{ij} = 1 \quad \quad \quad \quad j=0, 1, 2, \dots , n \end{aligned}$$

(4)

$$\begin{aligned}&\sum _{i=1}^{n} Y_{0i} = n \quad \quad \end{aligned}$$

(5)

$$\begin{aligned}&\sum _{i=0, i\ne k}^{n} Y_{ik} - \sum _{i= 0, i\ne k}^{n} Y_{ki} = 1 \quad \quad k= 1, 2, 3, \dots , n \end{aligned}$$

(6)

$$\begin{aligned}&Y_{i0} = 0 \quad \quad \quad \quad \quad \quad \quad \quad \quad i= 1, 2, \dots , n \end{aligned}$$

(7)

$$\begin{aligned}&Y_{0i} \le n X_{0i} \quad \quad \quad \quad \quad \quad \quad i=1, 2, \dots , n \end{aligned}$$

(8)

$$\begin{aligned}&Y_{ij} \le (n-1)X_{ij} \quad \quad \quad \quad i,j=1, 2, 3, \dots , n; i\ne j \end{aligned}$$

(9)

$$\begin{aligned}&X_{ij} \in \{0, 1\} \quad \quad \quad \quad \quad \quad \quad i,j=0, 1, 2, \dots , n; i\ne j \end{aligned}$$

(10)

$$\begin{aligned}&Y_{ij} \in \{0, \dots , n\} \quad \quad \quad \quad \quad i,j=0, 1, 2, \dots , n; i\ne j \end{aligned}$$

(11)

Hence, in this formulation, there are $2n(n+1)$ variables and $n^{2}+4n+3$ constraints. Constraints (3) and (4) make a guarantee that each customer will be visited and left only once (i.e., it has one incoming and one outcoming arc). Constraints (5)–(6) are flow constraints. They assure that the final tour $X$ has no subtours (tours that do not include all $n$ clients). Constraints (7)–(9) make a logical relation between variables $X$ and $Y$. For example, if $X_{ij} = 0$, then $Y_{ij}$ should be 0 as well.

Lower bound Obviously, a minimum spanning tree (MST) of the corresponding weighted graph, may be used as a lower bounding procedure. Let us rank edges $e \in A$ of the MST in a nondecreasing order of their weights

$$\begin{aligned} d(e_{1}) \le d(e_{2}) \le \cdots \le d(e_{n}). \end{aligned}$$

Then the lower bound LB is given by

$$\begin{aligned} LB = \sum _{k=1}^{n} (n+1-k)d(e_{k}). \end{aligned}$$

(12)

We will use this formula later, as Salehipour et al. (2011) to measure quality of heuristics, as the average percentage deviation from the LB.

3 Neighborhood structures for solving TDP

VNS is a metaheuristic for solving combinatorial and global optimization problems. Its basic idea is to change neighborhood in search for a better solution (Mladenović and Hansen 1997). Its main loop consists of 3 steps: (i) Shaking or perturbation of the incumbent solution $x$, (ii) local search and (iii) neighborhood change. For various VNS variants and their successful applications see recent surveys by Hansen et al. (2008, 2010).

Usual local search procedures used for solving TSP are 2-opt, Or-opt (or 1-2-3-insertion) and 3-opt. Their advantage is in the fact that the updating of the objective function may be obtained in constant time. However, this is not the case when solving TDP, at least if usual data structure is used and no preprocessing step is performed. We first show that the complexity of $k$-opt moves in such cases is $O(n^{k+1})$ (instead of $O(n^k)$ for solving classical TSP). Then we explain the steps necessary to be done, so as the data structure to be used in order to get the same complexity for TDP as it is for TSP, i.e., $O(n^{k})$.

k-opt complexity Let us consider the solution $x$ of TDP

$$\begin{aligned} x=(x_{1}, x_{2}, \dots , x_{i-1}, x_{i}, x_{i+1},\dots , x_{j-1}, x_{j},x_{j+1}, \dots , x_n) \end{aligned}$$

The solution that belongs to 2-opt neighborhood of the solution $x$ (in solving TSP) is obtained after deleting the links between $x_{i}$ and $x_{i+1}$, and between $x_{j}$ and $x_{j+1}$. The new tour $x^{\prime }$ and its objective function value $f(x^{\prime })$ are:

$$\begin{aligned} x^{\prime }&= (x_{1}, x_{2}, \dots , x_{i-1}, x_{i}, x_{j}, x_{j-1},\dots , x_{i+2}, x_{i+1}, x_{j+1}, \dots , x_{n}), \end{aligned}$$

(13)

$$\begin{aligned} \varDelta f&= f(x^{\prime }) - f(x) =d(x_{i},x_{j})+d(x_{i+1},x_{j+1})-d(x_{i},x_{i+1})-d(x_{j},x_{j+1}). \end{aligned}$$

(14)

Clearly, $f(x^{\prime })$ is obtained after 4 additions, thus, in constant time. Unfortunately, this property does not hold when solving TDP by 2-opt. In a straightforward implementation of 2-opt for TDP, all coefficients between $x_i$ and $x_j$ in formula (1) should be changed in calculating $f(x^{\prime })$. Therefore, the difference $\varDelta f$ may be obtained in $O(j-i)$ calculations. In the worst case $j=n$ and $i=1$, and thus $\varDelta f$ is obtained in $O(n)$.

Observe also that this straightforward implementation of $k$-opt for solving TDP increases by $n$ the complexity of $k$-opt move when TSP is considered, i.e., it is in $O(n^{k+1})$. In this section, we will show that if an appropriate data structure is used, the worst-case complexity of $k$-opt in solving both TDP and TSP is the same: $O(n^{k})$.

Our list of neighborhoods consists of (i) 1-opt, (ii) move forward (insertion to the right); (iii) move backward (insertion to the left); (iv) 2-opt. We did not put 3-opt move in our list because of its large complexity $O(n^{3})$.

1-opt move is a special case of 2-opt, where the index $j$ is set to $i+2$ in (13). Let us consider four consecutive clients in the current tour $x$:

$$\begin{aligned} x_{k}, x_{k+1}, x_{k+2}, x_{k+3}. \end{aligned}$$

(15)

Then the new tour $x^{\prime }$ is obtained by swapping $x_{k+1}$ and $x_{k+2}$.

Property 1

Exploring complete 1-opt neighborhood in solving TDP is in $O(n)$.

Proof

From (1), (13) and (15) we see that the difference $\varDelta f$ between the new objective function and the old one is

$$\begin{aligned} \varDelta f&= (n-{k})(d(x_{k}, x_{k+2})-d(x_{k},x_{k+1}))\\&+ (n-k-2)(d(x_{k+1},x_{k+3}) - d(x_{k+2}, x_{k+3})) \end{aligned}$$

If $\varDelta f$ is negative, then a better tour is obtained. Clearly, finding $\varDelta f$ is in $O(1)$. Since the cardinality of 1-opt neighborhood is $n-3$, the result follows. $\square$

Move forward (mf) The solution from this neighborhood is defined by moving $k$ consecutive customer positions to the right of the tour ($k=1, 2,\dots , \ell _{\max }$). If that block of $k$ customers starts from the position $i+1$ and is inserted after the position $j$, (i.e., after customer $x_{j}$), then the tour

$$\begin{aligned} x = (x_{1}, x_{2}, \ldots , x_{i}, x_{i+1}, \ldots , x_{j}, x_{j+1}, \ldots , x_{n}) \end{aligned}$$

becomes

$$\begin{aligned} x^{\prime } = (x_{1}, \ldots , x_{i}, x_{i+k+1}, \ldots , x_{j}, x_{i+1}, \ldots , x_{i+k}, x_{j+1}, \ldots , x_n) \end{aligned}$$

Property 2

Exploring complete move-forward neighborhood in solving TDP is in $O(n^{2}\ell _{\max })$.

Proof

The difference between the new and the old objective functions is

$$\begin{aligned} \varDelta f&= k \delta (x_{i+k+1}, x_{j}) - (j-i-k) \delta (x_{i+1}, x_{i+k})\\&+ (n-i) (d(x_{i}, x_{i+k+1}) - d(x_{i}, x_{i+1}))\\&+ (n-j) (d(x_{i+k},x_{j+1}) - d(x_{j}, x_{j+1}))\\&+ (n-j+k) d(x_{j},x_{i+1}) - (n-i-k) d(x_{i+k}, x_{i+k+1}) \end{aligned}$$

where $\delta (x_{i+k+1}, x_{j})$ denotes a subtour distance from the customer $x_{i+k+1}$ to the customer $x_{j}$. Similarly, $\delta (x_{i+1}, x_{i+k})$ denotes the distance from the client’s position $i+1$ to the position $i+k$, i.e.

$$\begin{aligned} \delta (x_{i}, x_j) = \sum _{h=i}^{j-1}{d(x_{h}, x_{h+1})} \end{aligned}$$

If $i$ and $j$ are fixed then, increase of $k$ by 1 makes calculation of the new $\varDelta f$ in $O(1)$. The same holds for all $(i,j)$ pairs. Therefore, finding objective function values in complete move-forward neighborhood is $O \left(\genfrac(){0.0pt}{}{n}{2} \ell _{\max }\right) = O(n^{2} \ell _{\max })$. $\square$

Move backward (mb) This neighborhood structure is analogous to the previous one. The only difference is that the block of $k$ consecutive customers is moved to the left.

These two neighborhoods together may be considered as one, i.e., $k-insertion$ neighborhood. Therefore, together, they may be seen as an extension of Or–opt move (note that in Or-opt $k=1,2$ and 3). However, we decided to split $k$-insertion neighborhood into its two disjoint subsets. This idea is shown to be useful in solving some other optimization problems on graphs (Brimberg et al. 2008, 2009).

2–opt move. We have already explained 2-opt move (see Eqs. (13) and (14)). Now we show that the 2-opt move may be done in $O(1)$ if appropriate data structure for storing and updating current incumbent tour is used.

Property 3

Exploring complete 2-opt neighborhood in solving TDP is in $O(n^{2})$.

Proof

Let the incumbent tour be presented as

$$\begin{aligned} x = (x_{1}, x_{2}, \dots , x_{i-1}, x_{i}, x_{i+1},\dots , x_{j-1}, x_{j}, x_{j+1}, \dots , x_{n}). \end{aligned}$$

After deleting links $(x_{i}, x_{i+1})$ and ($x_{j}, x_{j+1})$, the new tour $x^{\prime }$ becomes

$$\begin{aligned} x^{\prime }=(x_{1}, x_{2}, \dots , x_{i-1}, x_{i}, x_{j}, x_{j-1},\dots , x_{i+2}, x_{i+1}, x_{j+1}, \dots , x_{n}). \end{aligned}$$

The corresponding objective function values are

$$\begin{aligned} f(x)&= (n-1)d(x_{1}, x_{2}) + \cdots + (n-i+1) d(x_{i-1}, x_{i}) +(n-i) d(x_{i}, x_{i+1})\\&+ (n-i-1) d(x_{i+1}, x_{i+2}) + \cdots + (n-j+1) d(x_{j-1}, x_{j})\\&+ (n-j) d(x_{j}, x_{j+1}) + (n-j-1) d(x_{j+1}, x_{j+2}) + \cdots + d(x_{n-1}, x_{n}) \end{aligned}$$

and

$$\begin{aligned} f(x^{\prime })&= (n-1)d(x_{1}, x_{2}) + \cdots + (n-i+1) d(x_{i-1}, x_{i}) + (n-i) d(x_{i}, x_{j})\\&+ (n-i-1) d(x_{j}, x_{j-1}) + \cdots + (n-j+1) d(x_{i+2}, x_{i+1})\\&+ (n-j) d(x_{i+1}, x_{j+1}) + (n-j-1) d(x_{j+1}, x_{j+2}) + \cdots + d(x_{n-1}, x_{n}) \end{aligned}$$

After summing these two equations we get

$$\begin{aligned} f(x) + f(x^{\prime })&= 2\sum _{k=1}^{i-1} (n-k) d(x_{k}, x_{k+1}) + 2\sum _{k=j+1}^{n-1} (n-k) d(x_{k}, x_{k+1})\\&+ (2n-i-j) \delta (x_{i+1}, x_{j-1}) + (n-i) (d(x_{i}, x_{i+1})\\&+ d(x_{i}, x_{j})) + (n-j) (d(x_{i+1}, x_{j+1}) + d(x_{j}, x_{j+1})) \end{aligned}$$

By choosing the appropriate data structures and by preprocessing (before start searching through the neighborhood), the last formula can be calculated in $O(1)$ time. Moreover, at the same time ,we determine if $x^{\prime }$ is a better solution; since $f(x)$ is known, we can also find $f(x^{\prime })$.

Though, the problem is how to calculate the above formula. So, before starting the search through the 2-opt neighborhood, we have to calculate and store two sequences $S_b(i)$ and $S_e(i)$ representing the following sums:

$$\begin{aligned} S_{b}(i)= \sum _{k=1}^i (n-k) d(x_{k}, x_{k+1}) \quad \text{ and}\quad S_{e}(i) = \sum _{k=i}^{n-1} (n-k) d(x_{k}, x_{k+1}) \end{aligned}$$

so as

$$\begin{aligned} \delta (i) = \sum _{k=1}^{i} d(x_{k}, x_{k+1}) \end{aligned}$$

All can be done in $O(n)$ time. If we have these values, then

$$\begin{aligned}&f(x) + f(x^{\prime }) = 2 S_{b}(i-1) + 2S_{e}(j+1) + (2n-i-j) (\delta (j-2) - \delta (i))\\&\quad + (n-i) (d(x_{i}, x_{i+1}) + d(x_{i}, x_{j})) + (n-j) (d(x_{i+1}, x_{j+1}) + d(x_{j}, x_{j+1})) \end{aligned}$$

obviously, this value is calculated in constant $O(1)$ time and thus, the complete 2-opt neighborhood is explored in $O(n^{2})$. $\square$

Once we find the best solution $x^{\prime }$ in the 2-opt neighborhood, we need to answer the question about the complexity of the updating move. However, it requires $O(n)$ time as it is included in complexity of searching the 2-opt neighborhood. We now give pseudo-code of the updating step.

This algorithm will be later used in 2–opt local search $N_{2-opt}(R, x^{\prime }, r)$, within Sequential VND(Seq-VND) and Mix VND (Mix-VND).

Double bridge (db) is a special case of 4–opt. For any four indices $i, j, k$ and $\ell$ ($i < j < k < \ell$), edges ($x_{i}, x_{i+1}$), ($x_{j}, x_{j+1}$), ($x_{k}, x_{k+1}$), ($x_\ell , x_{\ell +1}$) are removed. New 4 edges are then ($x_{i}, x_{k+1}$), ($x_{\ell }, x_{j+1}$), ($x_{k}, x_{i+1}$) and ($x_{j}, x_{\ell +1}$). It is very important for some combinatorial problems since it keeps the orientation of the tour. The neighborhood size of double bridge is $O(n^{4})$. However, we reduce it to $O(n^{2})$ by fixing indices $j = i+2$ and $\ell = k+2$. The double-bridge move is used only within our GVNS-2, which will be explained later in Algorithm 6.

Interchange (Exchg) When the two non-successive customers $x_{i}$ and $x_{j}$ ($i<j$), interchange their places in the tour, than the objective function value is obviously changed. The interchange move is a special case of the 4-opt as well. The size of the whole neighborhood is obviously $O(n^{2})$. We use it just to compare different multi-start local search procedures with the multi-start VND (Table 1).

4 General VNS for solving TDP

General VNS (GVNS) is a variant of VNS where VND is used as a local search routine within basic VNS scheme Hansen et al. (2008, 2010). It contains 3 parameters: (i) $t_{max}$–maximum time allowed in a search; (ii) $k_{max}$–the number of neighborhoods used in shaking; (iii) $\ell _{max}$–the number of neighborhoods used in VND. Its pseudo code is given in Algorithm 2.

The set of neighborhoods used both in shaking and VND local search are problem specific.

4.1 Initial solution

We use two ways to get an initial solution. The first is random one, i.e., it is obtained as a random permutation of $n-1$ customers. The second is the Greedy randomized procedure given in Algorithm 3. We call it Greedy-R.

In each constructive step of our Greedy-R($x,q$) a random selection of the next customer $x_{k}$ is restricted to the $q$ (a parameter) closest to the last selected customer $x_{k-1}$. If the number of customers $n$, or the number of remaining customers $n-k$ is less than $q$, then one among all remaining customers is chosen. In our implementation we always use a value of 10 for $q$ ($q$=10).

4.2 Shaking

In the VNS shaking step, the incumbent solution $x$ is perturbed to get one random solution $x^{\prime }$ from the $k^{th}$ neighborhood of $x$ ($x \in \mathcal N _k(x), k=1,\dots ,k_{max}$). Such a random solution is an initial one for the local search routine that follows. After some experiments, we decided to use the insertion neighborhood structure for the sake of shaking. In other words, our shaking consists of selecting a customer $i$ at random and inserting it between $j$ and $j+1$, where $j$ is also randomly chosen. In fact, we repeat $k$ times this random insertion move.

Note that insertion move consists of move forward or move backward moves. Therefore our shaking can be move forward or move backward if $j\ge i$ or $j \le i$, respectively. Note also that one-insertion move is a special case of Or-opt move where one, two or three consecutive vertices are inserted.

4.3 VND algorithms

Finding the right order of neighborhoods used in deterministic VND heuristic may be very important for the quality of the final solution. After extensive testing of different variants, we decided to use the following order of neighborhoods: (i) 1-opt, (ii) 2-opt, (iii) move-forward, (iv) move-backward. In Mix-VND, we additionally use (v) double-bridge neighborhood structure. The number of visited solutions from 2-opt neighborhood is also reduced: for fixed $i$ (i.e., $x_{i}$), we take only $r$ (a parameter) nearest customers as candidates for $x_{j}$ and to perform the 2-opt move. If the total number of the customers is less than $r$, than we set $r=n/2$. Hence, we need to rank all distances (columns of matrix $D$) in pre-processing step to get ranked distances $R$ and thus be able to easily find $r$ closest customers to each customer $x_{i}$.

We develop two VND variants for solving TDP: Seq-VND (see Algorithm 5) and Mix-VND (see Algorithm 6). For details regarding Nested and Mixed VND methods see Ilić et al. (2010) and Mladenović et al. (2012).

In Mix-VND (see Mladenović et al. 2012) we perform Seq-VND starting from each solution that belong to $N_{db}$ neighborhood of a current solution $x$. The $N_{db}$ neighborhood is fully explored but in the first improvement strategy. If the solution $x^{\prime \prime }$ obtained with Seq-VND heuristic is better than the current solution $x^{\prime }$, we move there ($x^{\prime } \leftarrow x^{\prime \prime }$).

The rationale of our Mix-VND procedure is to give double-bridge move a special status since it is known to be very important in solving the TSP problem (Johnson and McGeoch 1996).

4.4 GVNS algorithms

We designed here 2 GVNS variants for solving TDP. One uses sequential VND as a local search (GVNS-1 for short), and the other uses Mixed nested VND (GVNS-2). Correctness of these heuristics follows results from Markoski et al. (2011). We also implemented two variants to get initial solution: Greedy-R($x,10$) and Rand($x$). Note that Rand represents a procedure for random permutation of $n$ numbers and will not be presented here. The pseudo code of all our variants are given in Algorithm 7.

In preprocessing step we rank distances among customers $D$ in non-decreasing order of their values. A new ordered matrix $R$ is used in reducing the set of visited points of 2-opt neighborhood. As explained earlier, in our implementation the number of neighborhoods $\ell _{max}$ used within VND for solving TDP is equal to 4. So, we do not need to consider $\ell _{max}$ in Algorithm 7 as a parameter, as it is presented in Algorithm 2.

5 Computational results

Our GVNS-1 and GVNS-2 are coded in C++. Computational analysis is performed on Intel Pentium IV processor with 1.8GHz, under Linux.

Test instances. According to Salehipour et al. (2011), test instances specifically created for TDP do not exist in the literature. That is why the authors in Salehipour et al. (2011) generated their own instances but also used the instances from the TSP library to test their GRASP+VNS based heuristics.

In Salehipour et al. (2011) 140 instances were generated in total with $n$ equal to 10, 20, 50, 100, 200, 500 and 1000. For any value of $n$, 20 different instances were generated in the following way: coordinates of all the customers, including the depot, were generated at random with a uniform distribution on the interval [0,100]. For instances with 500 and 1000 customers this interval was [0,500]. The matrix $D=(d_{ij})$ was obtained by using floor function of the Euclidean distance between any two nodes $i$ and $j$.

Stopping condition. We stop our VNS based heuristic after $n$ seconds ($t_{max}=n$ seconds). In the tables below, we give report on the time when the best solution of each instance is reached.

Local search procedures. We perform extensive computational analysis to figure out the power of each neighborhood structure for solving TDP, as well as the power of our VND local search procedures. For that purposes we repeat local search, with respect to each neighborhood, 1000 times. Tests are performed on many instances. In order to save the space, here we give the results only for $n=200$ in Table 1. The % deviations from the best know solution (obtained by our GVNS methods) are reported for the best, the worst and the average solutions obtained by each local search. Or-opt presents the local search that uses insertion of 1, then 2 and then 3 consecutive vertices. 1-ins, 2-ins and 3-ins denote local search heuristics that inserts 1, 2 or 3 consecutive vertices respectively.

Table 1 Comparison of different multistart local search procedures applied on instance with 200 customers

Different local search procedures’ behavior is also presented in the so-called distance-to-target diagram given at Fig. 1. The same random instance with $n=200$ is used, with two initialization methods: random (the left part of pictures) and Randomized greedy (on the right). The best known solution of that instance is given in origin; point ($u,v$) in the diagram represents a local optima obtained by Greedy-R. $u$ and $v$ coordinates represent the Hamming distance (between the best known solution and the obtained local minima) and the % deviation of local optima value from the best objective function value, respectively.

Fig. 1

Distribution of local optima in the distance-to-target diagrams; comparison of random multistart (left) and GRASP (right) local searches w.r.t. 2-opt, Or-opt and Seq-VND neighborhoods on instance with $n$=200 customers

From Table 1, Fig. 1, we can draw the following conclusions: (i) The multi-start Sequential VND local search performs the best; (ii) It is interesting to note that the Greedy-R initialization does not improve the performance of the multi-start Seq-VND. In other words, GRASP+VND does not produce local minima of better qualities than Multistart Seq-VND; (iii) Local minima do not depend on the initialization method but on the neighborhood structure used. The exception is Exchange neighborhood structure (which appears not to be good for solving TDP anyway).

Comparison. To measure the quality of heuristics the average percentage deviation from the lower bound LB (calculated as in (12)) is used in this section as in Salehipour et al. (2011). Average deviation is calculated on 20 instances, generated for the same $n$.

Table 2 contains comparative results of the four methods: GRASP + VND, GRASP + VNS, GVNS-1 and GVNS-2. For all 4 methods the average deviation from the lower bound is reported so as their CPU time. The columns 8 and 11 give % improvement of our GVNS-1 and GVNS-2 suggested in this paper over GRASP-VNS that could be seen as the current state-of-the-art heuristic.

Table 2 Comparison on random instances

Table 3 contains the same information as Table 2, but on the instances from the TSP library. In addition, instead of % deviation above lower bound, the values of objective functions are reported. They are obtained by a single run of the each method.

Table 3 Comparison on TSP-Lib instances

It appears that:

• (i) GVNS-1 and GVNS-2 outperform both GRASP+VND and GRASP+VNS;

• (ii) There is no significant difference between the GVNS-1 and the GVNS-2. Nevertheless GVNS-2 seems to behave better for larger instances, while for the small and middle size instances, it is opposite.

Table 4 Comparison of the results obtained by branch–and–cut–and–price method proposed by Abeledo et al. (2010) and by our GVNS-1

In Table 4 the results obtained by branch–and–cut–and–price method (B&C&P) proposed by Abeledo et al. (2010) and by our GVNS-1 are compared. Note that in this case objective function is slightly different: the first edge on tour is multiplied by $n+1$, the second with $n$, etc. Finally, the edge between the last customer on tour and the depot is multiplied by 1. Values in boldface are proved to be optimal. It appears that our GVNS-1 reaches all best optimal and three best known values with much smaller CPU time.

6 Conclusions

In this paper we propose General variable neighborhood search (GVNS) based heuristic for solving Travelling deliveryman problem (TDP). Neighborhoods that we use are the classical ones explored for solving Travelling salesman problem. We show how they can be efficiently adapted for solving TDP as well. Moreover, we calculated the complexity of such adapted moves. Extensive computational results show that our two GVNS versions outperforms recent heuristic suggested by Salehipour et al. (2011). Future research may contain extension of the methodology and data structures to another similar combinatorial optimization problems. Also, the clustering of customers on the network (as in Carrizosa et al. 2011) may be tried out before routing.