Exploiting sets of independent moves in VRP

Most heuristic methods for VRP and its variants are based on the partial exploration of large neighborhoods, typically by means of single, simple moves applied to the current solution. In this paper we define an extended concept of independent moves and show how even a very standard heuristic method can significantly improve when considering the simultaneous application of carefully chosen sets of moves. We show in particular that, when choosing a set such that the total cost variation is equal to the sum of the variations induced by each single move, the quality of solutions obtained is in general very high. When compared with numerical results obtained by some of the best available heuristics on challenging, large scale, problems, our simple algorithm equipped with the application of optimally chosen independent moves displayed very good quality.

We are grateful to both reviewers and the associate editor for their stimulating comments on the first version of this paper: answering those comments helped us to significantly improve the quality of this paper.

Authors and Affiliations

1. Fleetmatics Research, Via Paisiello 20, 50144, Firenze, Italy

   Tommaso Bianconcini, David Di Lorenzo, Alessandro Lori & Leonardo Taccari

2. DINFO, Università degli Studi di Firenze, via di S. Marta 3, 50139, Firenze, Italy

   Fabio Schoen

Corresponding author

Correspondence to Fabio Schoen.

Disclaimer

Some of the authors are affiliated with Fleetmatics, a Verizon company, which is a leading global provider of mobile workforce solutions for service-based businesses. The views set forth in this article do not necessarily represent the views of Fleetmatics, Verizon or any of their respective affiliates.

Appendix

In this section we will provide the conditions required in order to safely combine sets of legal moves. First we show that, under suitable conditions, each of the moves considered in TSIS is legal.

Proposition 2

Given a well-formed solution s, a relocate(v,{y,z}) move m that moves the order v into the edge \(\{y,z\}\in E_s\), with \(v\ne y\), \(v \ne z\), is legal.

Proof

By definition of the relocate operator, \(R_m = \{ \{u,v\}, \{v,w\}, \{y,z\}\}\) where u and w are the two nodes adjacent to v, and \(I_m = \{\{y,v\}, \{v,z\}, \{u,w\}\}\). It is easy to verify that \(R_m \subseteq E_s\), and \(I_m \cap (E_s {\setminus } R_m) = \emptyset\), even in the case where \(u = y\) and/or \(w=z\), otherwise s could not be a well-formed solution. It is also trivial to verify that the move preserves the degree of the involved nodes.

Finally, suppose by contradiction that the move creates subtours when applied on a well-formed solution s. Let T be the set edges comprising such subtour. Note that, if \(\{y,v\} \in T\), then also \(\{v,z\} \in T\), otherwise the degree of v would not be preserved. Then three cases can happen

• \(T \cap I_m = \emptyset\). Then also \(T \subseteq E_s\), so s is not a well-formed solution.

• \(\{u, w\} \in T\). Then consider the set \(T' = (T {\setminus } \{u, w\}) \cup \{\{u,v\} \cup \{v,w\}\). Since this operation replaces the arc \(\{u, w\}\) with the pair \(\{u,v\}\) and \(\{v,w\}\), also \(T'\) contains a tour. But we can see that by construction \(T' \subseteq E_s\), so s is not a well-formed solution.

• \(\{y,v\} \in T\) and \(\{v,z\} \in T\). Then consider \(T' = (T {\setminus } \{ y, v\} {\setminus } \{v,z\}) \cup \{y,z\}\). Following the same reasoning as the previous case, we can see that also \(T'\) contains a tour, and that \(T' \subseteq E_s\), so again s is not a well-formed solution.

Proposition 3

Given a well-formed solution s, an exchange(v,y) move that swaps two orders v and y is legal.

Proof

By definition of the exchange operator, \(R_m = \{\{u,v\}, \{v,w\}, \{x,y\}, \{y,z\}\}\) where u, w and x, z are the nodes adjacent to v and y, respectively, and \(I_m = \{\{u,y\}, \{y,w\}, \{x,v\}, \{v,z\}\}\). It is easy to verify that \(R_m \subseteq E_s\), and \(I_m \cap (E_s {\setminus } R_m) = \emptyset\), even in the case where \(w = x\) and/or \(u=z\), otherwise s could not be a well-formed solution.

The move preserves the degree of the involved nodes, and does not create subtours. The proof is trivial and follows the exact same structure as the one for the relocate operator. \(\square\)

Proposition 4

Given a well-formed solution s, a relocate-pair({v,w},{y,z}) move m that relocates the edge \(\{v,w\}\in E_s\) into the edge \(\{y,z\}\in E_s\) is legal.

Proof

Let us denote by \(u \ne w\) the other node adjacent to v in \(E_s\) (i.e., \(\{u,v\} \in E_s\)) and analogously \(x \ne u\) is adjacent to w. Then this move is defined through

and the proof proceeds similarly to the previous one. \(\square\)

Notice that in the definition of this move we chose to insert edge \(\{v,w\}\) both in \(R_m\) and in \(I_m\). This will prove useful in order to to ensure that the edge \(\{v,w\}\) remains in \(E_s\) when combining this move with other ones, as we will see later.

Proposition 5

Given a well-formed solution s, an exchange-pairs({v,w},{y,z}) move that swaps two edges \(\{v,w\}\in E_s\) and \(\{y,z\}\in E_s\) is legal.

The proof is omitted, as trivial and similar to the previous ones. As before, we assume that both edges \(\{v,w\}\) and \(\{y,z\}\) appear both in \(R_m\) and in \(I_m\) in order to ensure that they are not removed by other moves, when we will combine them.

Theorem 1

A set M of legal moves of the type relocate, exchange, relocate-pair, exchange-pairs with no edge overlap over a well-formed solution s is independent in the sense of Definition  3.

Proof

We need to show that the solution obtained after applying all the moves in M does not contain subtours. To do so, consider any sequence of moves in M, in any order. The first move \(m_1\) can be applied to s, and \(m_1(s)\) is still well-formed, by hypothesis and hence does not contain subtours.

Consider the n-th move in the sequence and consider the \(n-1\) moves applied before. Let \(s_{n-1}\) denote the solution obtained after the application of these moves, and assume that it does not contain subtours. The n-th move can be applied since the edges affected by \(m_n\) are, by hypothesis, non-overlapping with all the other ones, so the edges in \(R_{m_n}\) belong to \(s_{n-1}\) and \(I_{m_n}\) do not. Then by Propositions 2–5 move \(m_n\) is legal, \(s_n\) is well-formed, so it does not contain subtours. The claim follows by induction. \(\square\)

1.1 Extension to 2-opt moves

In the previous subsection we have proved that several classes of moves can be safely combined. More specifically, it is always safe to combine non-overlapping relocate, exchange, relocate-pair, and exchange-pairs moves, due to the fact that the only requirements for them to be legal is that the edges in \(R_m\) are in the solution they are applied to (and those in \(I_m\) are not). More complex moves require some additional pre-conditions in order to avoid sub-tours. For 2-opt moves, these conditions depend on the relative order of the nodes in the tour.

Let us define a path p as an ordered sequence of nodes which are pairwise adjacent in the solution s. A path is simple if no node appears more than once in it. For any two nodes u, v in the same route, the path p induces a partial ordering \(\prec _p\) such that \(u\prec _p v\) if u precedes v in the path p. Observe that u and v are not required to be adjacent.

Proposition 6

Given a well-formed solution s, a 2-opt({u,v},{y,z}) move m over s, defined as \(R_m = \{\{u,v\},\{y,z\}\} \subset E_s\) and \(I_m = \{\{u,y\},\{v,z\}\} \not \subset E_s\), with u, v, y, z belonging to the same tour (route), is legal if and only if there is a simple path p where \(u \prec _p v \prec _p y \prec _p z\).

Proof

If a simple path p with \(u \prec _p v \prec _p y \prec _p z\) exists, then cutting the edges \(R_m=\{\{u,v\},\{y,z\}\}\) in the tour creates two disconnected components: a path \(P_1\) that contains u and z at the two ends, and a path \(P_2\) with v and y at the two ends. The nodes u, v, y, z have degree 1 after the cut. Inserting the edges \(I_m = \{\{u,y\},\{v,z\}\}\) fulfills the degree condition, and it reconnects the two components, creating a single tour. Thus the move is legal.

Let us now assume that there is no simple path p over the considered route with \(u \prec _p v \prec _p y \prec _p z\). Since u must be adjacent to v, and y to z, it is easy to verify that there must be a path q such that \(v \prec _q u \prec _q y \prec _q z\). If such path exists, removing the edges \(R_m=\{\{u,v\},\{y,z\}\}\) creates two disconnected components: a path \(p_1\) with endpoints v and z, and a path \(p_2\) with endpoints u and y. Inserting the edges \(I_m = \{\{u,y\},\{v,z\}\}\) fulfills the degree condition, but it does not reconnect the components, creating two disconnected subtours. Then the precedence must hold, and the claim follows. \(\square\)

When combining 2-opt moves, then, we must pay particular care to maintain the necessary and sufficient condition in Proposition 6. To show how this can be achieved, let us start with the definition of nested 2-opt moves (see Fig. 3).

Definition 4

Given two 2-opt moves \(m_i = \texttt {2-opt}(\{u_i,v_i\},\{y_i,z_i\})\) and \(m_j = \texttt {2-opt}(\{u_j,v_j\},\{y_j,z_j\})\) over the same route of a solution s, let \(\bar{p}_i\) be the set of nodes in the simple path that connects \(v_i\) to \(y_i\) not passing through the depot, and let \(\bar{p}_j\) be the set of nodes in the path that connects \(v_j\) to \(y_i\) not passing through the depot. Three cases can occur:

• if \(\bar{p}_i \subset \bar{p}_j\), we say that \(m_i\) is nested into \(m_j\);

• if \(\bar{p}_i \cap \bar{p}_j = \emptyset\), we say that \(m_i\) and \(m_j\) are disjoint;

• if \(\bar{p}_i \cap \bar{p}_j \ne \emptyset\), but neither is nested in the other, we say that \(m_i\) and \(m_j\) are intertwined.

The move \(m_i\) (that removes the dashed edges) is nested in \(m_j\) (that removes the dotted edges). Applying both moves on s (left) does not introduce subtours (right)

Full size image

Two 2-opt moves are intertwined if neither is nested into the other. Applying simultaneously two intertwined 2-opt moves does not guarantee the absence of subtours, as shown in Fig. 4.

Applying intertwined moves on a solution s (left) does not guarantee the absence of subtours (right). In this example, two intertwined moves create a disconnected subtour (the four nodes in the middle), although both of them are legal if applied singularly

Full size image

Definition 5

Let \(\bar{E} \subseteq E_s\) be a set of edges belonging to the same route. Consider any partial ordering on the nodes of the edges in \(\bar{E}\) and a simple directed path following that order that connects all the nodes in the route.

We say here that a move preserves the relative order of \(\bar{E}\) if, after its application to s, the edges in \(\bar{E}\) still belong to the same tour, and it is still possible to find a path over such tour so that the chosen partial ordering of the nodes of the edges in \(\bar{E}\) is preserved.

Note that no partial ordering can be defined on edges that belong to different tours.

Two preliminary results are needed before we can finally prove how 2-opt moves can be safely combined with the others.

Lemma 1

Given a well-formed solution s, a move m of the type relocate, exchange, relocate-pair, exchange-pairs, preserves the relative order of any pair of edges \(\{u,v\}\), \(\{x,y\}\) not affected by the move.

Proof

Consider a legal relocate move m that moves the order b with adjacent nodes a, c into the edge \(\{f,g\}\). Assume that a simple path p induces the ordering \(u \prec _p v \prec _p x \prec _p y\). We can distinguish two cases:

• p does not include the edges in \(R_m\). Then the same path also exists in m(s), so the order is trivially preserved.

• p includes \(\{a,b,c\}\). Assume that p is defined as \(p = (u, v, \dots , a, b, c, \dots , x, y)\). Then consider in m(s) the path \(q = (u, v, \dots , a, c, \dots , x, y)\), where the edge \(\{a,c\}\) has been inserted by applying m. Over q, \(u \prec _q v \prec _q x \prec _q y\).

• p includes \(\{f,g\}\). Assume that p is defined as \(p = (u, v, \dots , f, g, \dots , x, y)\). Then consider in m(s) the path \(q = (u, v, \dots , f, b, g, \dots , x, y)\), where the edges \(\{f,b\}\) and \(\{b,g\}\) have been inserted by applying m. Over q, \(u \prec _q v \prec _q x \prec _q y\).

Analogous arguments can be applied to show the claim holds also for the other types of moves. \(\square\)

Lemma 2

Given a well-formed solution s, a legal 2-opt move m preserves the relative order of any two edges \(\{u,v\}\), \(\{x,y\}\)

if they belong to the same of the two connected components in \(E_s{\setminus } R_m\).

Proof

Assume that a simple path p induces the ordering \(u \prec _p v \prec _p x \prec _p y\). Taking into account the move m, we can distinguish two cases:

• p does not include the edges in \(R_m\). Then the same path also exists in m(s), so the order is trivially preserved.

• p include both edges in \(R_m = \{\{a,b\},\{c,d\}\}\). Assume w.l.o.g. that p is defined as \(p = (u, v, \dots , a, b, \dots , c,d, \dots , x, y)\). Then consider in m(s) the path \(q = (u, v, \dots , a, c, \dots , b, d, \dots , x, y)\), where the nodes between a and d are reversed due to the application of the move. Over q, \(u \prec _q v \prec _q x \prec _q y\).

The case where p includes only one of the edges in \(R_m\) is excluded by the hypothesis that \(\{u,v\}\), \(\{x,y\}\) lie in the same connected component of \(E_s{\setminus } R_m\). Then the claim follows. \(\square\)

We can now show that, if we restrict ourselves to nested moves, as in Fig. 3, the following result holds:

Theorem 2

Given a set M of legal moves of the type relocate, exchange, relocate-pair, exchange-pairs, 2-opt with no edge overlap over a well-formed solution s, if all pairs \(m_i,m_j\) of 2-opt moves are non-intertwined, then the set is independent.

Proof

We need to show that the solution obtained after applying all the moves in M does not contain subtours. To do so, consider any sequence of moves in M, in any order. The first move of the sequence \(m_1\) can be applied to s, and \(m_1(s)\) is still well-formed, by hypothesis, thus no subtour exists. Moreover, by Lemmas 1–2 the relative order of any two edges affected by any other 2-opt move \(m_k\) with \(k > 1\) is preserved (since all 2-opt are pairwise nested in s), so all pairwise non-intertwined 2-opt moves are still so.

Let \(m_n\) be the n-th move in the sequence, and

let \(s_{n-1}\) denote the solution obtained after the application of the first \(n-1\) moves. By inductive assumption, \(s_{n-1}\) does not contain subtours, the relative order of any two edges affected by any 2-opt move \(m_k\) with \(k > n-1\) is preserved, and all pairs of 2-opt moves that were non-intertwined on s, are still so in \(s_{n-1}\). Then:

• If the n-th move is not a 2-opt, it can be legally applied since the edges affected by \(m_n\) are, by hypothesis, non-overlapping with all the other moves in M, so the edges in \(R_{m_n}\) still belong to \(s_{n-1}\), and those in \(I_{m_n}\) do not. The solution \(s_n\) does not contain subtours. By applying Lemma 1, the order of any two edges not affected by \(m_n\) is preserved and all pairwise non-intertwined 2-opt moves are still so.

• If on the contrary the n-th move is a 2-opt, it can be applied without introducing subtours, since the relative order of the edges in \(R_{m_n}\) is preserved in \(s_{n-1}\) by the inductive assumption. We must now show that the order is preserved also in \(s_n\). Consider any 2-opt move \(m_k\) with \(k > n+1\). By the inductive assumption, \(m_n\) and \(m_k\) are still non-intertwined in \(s_{n-1}\) so the move \(m_n\) preserves the order of the two edges in \(R_{m_k}\) by Lemma 2. By applying the same lemma, all non-intertwined moves are still so in \(s_n\).

The claim follows by induction. \(\square\)

1.2 Extension to 2-opt \(^*\) moves

The classes of moves that can be combined can be further extended to include the 2-opt* operator.

Proposition 7

Given a well-formed solution s, a 2-opt* move m over s, defined as \(R_m = \{\{u,v\},\{y,z\}\} \subset E_s\) and \(I_m = \{\{u,y\},\{v,z\}\} \not \subset E_s\), with \(\{u,v\}\) and \(\{y,z\}\) belonging to two different tours (routes), is legal.

Proof

Let us consider only the subset of \(E_s\) that contains the two tours with the nodes u, v and y, z, respectively. Cutting the edges \(R_m=\{\{u,v\},\{y,z\}\}\) creates a tree with the depot as the root node, and four linear branches with the nodes u, v, y, z as leaves. Inserting back in the solution the edges \(I_m = \{\{u,y\},\{v,z\}\}\) reestablishes the degree condition and reconnects the dangling branches, thus obtaining two tours, connected by the depot, which contain the nodes u, y and v, z, respectively. The solution is well-formed. \(\square\)

The additional assumption here is that the edges in \(R_m\) must be in two different routes. To safely combine them, then, it is sufficient to ensure that no route is affected by more than one 2-opt*. Concerning the interaction with 2-opt moves, similar steps to what is shown in the previous subsection can be followed.

Definition 6

Given a 2-opt move \(m_i = \texttt {2-opt}(\{u_i,v_i\},\{y_i,z_i\})\) and a 2-opt \(^*\) move \(m_j = \texttt {2-opt}^*(\{u_j,v_j\},\{y_j,z_j\})\) with \(\{u_i,v_i\},\{y_i,z_i\},\{u_j,v_j\}\) belonging to the same route of a solution s, and \(\{y_j,z_j\})\) belonging to a different one, let \(\bar{p}_i\) be the set of nodes in the simple path that connects \(v_i\) to \(y_i\) not passing through the depot. Two cases can occur:

• if \(\{u_j,v_j\} \subset \bar{p}_i\), we say that \(m_j\) is nested into \(m_i\);

• if \(\{u_j,v_j\} \not \subset \bar{p}_i\), we say that \(m_i\) and \(m_j\) are disjoint.

Lemma 3

Given a well-formed solution s, a legal 2-opt* move m preserves the relative order of any pair of edges \(\{u,v\}\), \(\{x,y\}\) in the same tour in s, if there is a tour in m(s) that still contains them both.

Proof

Consider the path \(p = (u, v, \dots , x, y)\) that induces the ordering \(u \prec _p v \prec _p x \prec _p y\). Let m be a legal 2-opt* move. The set \(R_m\) consists of two edges, belonging to different routes. If \(\{u,v\}\), \(\{x,y\}\) still belong to the same tour in m(s), then p does not include the edge in \(R_m\) – otherwise they would be in two different routes. This means that p also exists in m(s), and the order is preserved. \(\square\)

Theorem 3

Given a set M of non-overlapping legal moves over a well-formed solution s, if:

• all pairs \(m_i, m_j \in M\) of 2-opt moves are non-intertwined (either one is nested in the other, or they are disjoint).

• for each route in s, there can be at most one 2-opt* affecting any edge of that route, and it must be disjoint from all the 2-opt moves over that route.

then the set is independent.

Proof

We need to show that the solution obtained after applying all the moves in M does not contain subtours.

An induction proof that follows the same idea used in Theorem 2 can be used. For sake of readability, we will omit the details. To prove the thesis, it is sufficient to guarantee, applying Lemmas 1, 2 and 3, that at each step of the induction:

• the relative order of any two edges affected by any 2-opt is preserved

• all pairwise non-intertwined 2-opt moves are still so

• for any 2-opt* move \(m\in M\), the edges \(R_m\) are still in different routes

• all pairs of 2-opt* and 2-opt moves are still disjoint.\(\square\)

Reprints and permissions