Generalized Pyramidal Tours for the Generalized Traveling Salesman Problem

Abstract

In this paper, we introduce the notion of l-quasi-pyramidal and l-pseudo-pyramidal tours extending the classic notion of pyramidal tours to the case of the Generalized Traveling Salesman Problem (GTSP). We show that, for the instance of GTSP on n cities and k clusters with arbitrary weights, l-quasi-pyramidal and l-pseudo-pyramidal optimal tours can be found in time $O(4^ln^3)$ and $O(2^lk^{l+4}n^3)$, respectively. Consequently, we show that, in the most general setting, GTSP belongs to FPT for parametrizations induced by these special kinds of tours. Also, we describe a non-trivial polynomially solvable subclass of GTSP, for which the existence of l-quasi-pyramidal optimal tour (for some fixed value of l) is proved.

1 Introduction

The Traveling Salesman Problem (TSP) is the famous combinatorial optimization problem having many valuable applications in operations research and attracting interest of scientists for decades (see e.g. [14, 19, 21]).

It is known that TSP is strongly NP-hard and hardly approximable in its general setting [22]. At the same time, the problem remains intractable in metric and Euclidean settings, but can be approximated well in these cases, admitting fixed-ratio algorithms for an arbitrary metric [10] and Polynomial Time Approximation Schemes (PTAS) for Euclidean spaces of any fixed dimension [1]. Many generalizations of TSP, e.g. Cycle Cover Problem [13, 15, 16], Peripatetic Salesman Problem [2, 12], have the similar approximation behaviour.

Algorithmic issues of finding optimal restricted tours, for several kinds of restrictions, e.g. precedence constraints, are also actively investigated (see, e.g. [4, 5, 9]). Among others, restriction of TSP to considering so called pyramidal tours (see e.g. [8]) seems to be especially popular. A pyramidal tour respects the initial order defined on the nodeset of a given graph and, for some r, has the form

$$1=v_{i_1},v_{i_2},\ldots ,v_{i_r}=n,v_{i_{r+1}},\ldots ,v_{i_n},$$

where $v_{i_j}<v_{i_{j+1}}$ for any $j\in \{1,\ldots ,r-1\}$ and $v_{i_j}>v_{i_{j+1}}$ for any $j\in \{r+1,\ldots ,n-1\}$.

It is widely known [18] that an optimal pyramidal tour can be found in time of $O(n^2)$ for any weighting function. Recently it was shown [6] that, for the Euclidean setting, an optimal pyramidal tour can be found in time $O(n\log ^2n)$. In papers [11, 20], several generalizations of pyramidal tours, for which optimal tour can also be found efficiently were introduced. Despite their fame, pyramidal tours have one shortcoming. Known settings of TSP and its generalizations, for which the existence of optimal pyramidal tours is proven, remain very rare so far. Actually, they are mostly exhausted with settings satisfying the well known sufficient conditions by Demidenko and van der Veen (see e.g. [14]) and some other special cases [3, 7, 19].

The contribution of this paper is two-fold. First, we introduce (in Sect. 2) notion of generalized pyramidal tours, we call them l-quasi- and l-pseudo-pyramidal, extending the classic notion of pyramidal tours and results of [20] to the case of Generalized Traveling Salesman Problem (GTSP). We show that l-pseudo-pyramidal and l-quasi-pyramidal optimal tours can be found in time $O(2^lk^{l+4}n^3)$ and $O(4^ln^3)$, respectively. Then, in Sect. 3, we describe a non-trivial polynomially solvable subclass of GTSP, for which the existence of on optimal l-quasi-pyramidal tour (for some fixed l) is proved.

2 Generalized Pyramidal Tours

We proceed with the common setting of the Generalized Traveling Salesman Problem (GTSP). An instance of the GTSP is defined by a complete edge-weighted graph $G=(V,E,w)$ with weighting function $w:E\rightarrow \mathbb {R}_+$, and by a given partition $V_1\cup \ldots \cup V_k=V$ of the nodeset $V=V(G)$ of the graph G. Feasible solutions are cyclic tours $\tau =(v_{i_1},\ldots ,v_{i_k})$ visiting each cluster $V_i$ once. Hereinafter, we call such routes Clustered Hamiltonian tours or CH-tours. The problem is to find a CH-tour of the minimum weight¹.

In this section, we extend the well-known notion of a pyramidal tour to the case of partial orders defined implicitly by the orderings of clusters. Indeed, (linearly) ordered finite set $(V_1,\ldots ,V_k)$ of clusters induces a partial order on the nodeset V of the graph G as follows: For any $u\in V_{i}$ and $v\in V_{j}$, $u \prec v$ if $i<j$.

Definition 1

Let $\tau$ be a CH-tour

$$v_{1},v_{i_1},\ldots ,v_{i_r}, v_k, v_{j_{k-r-2}},\ldots ,v_{j_1},\ 0\le r\le k-2$$

such that $v_t\in V_t$ for any t. We call $\tau$ an l-quasi-pyramidal tour, if $i_p-i_q\le l$ and $j_{p'}-j_{q'}\le l$ for any $1\le p<q\le r$ and $1\le p'<q'\le k-r-2$.

The following theorems extend the results proposed in [20] for the classic TSP.

Theorem 1

For any weighting function $w:E\rightarrow \mathbb {R}_+$, a minimum cost l-quasi-pyramidal CH-tour can be found in time of $O(4^ln^3)$.

Fig. 1.

Path from u to v through the clusters $V_{t_j}$, $t_j\in S$.

Proof

We start with some necessary notation. For any integers $i>j$, we use the common shortcuts [j, i], [j, i), and (j, i) for intersections with $\mathbb {N}$ of the sets $\{j,\ldots ,i\}$, $\{j,\ldots ,i-1\}$, $\{j+1,\ldots ,i-1\}$, respectively. For any nodes $u\in V_i$ and $v\in V_j$, $i\ne j$, and an arbitrary subset $S\subset [i-l,i)\setminus \{1,j\}$ or $S\subset [j-l,j)\setminus \{1,i\}$, let g(v, S, u) be the weight of a shortest $(|S|+1)$-edge path from u to v visiting all the clusters $\{V_t:t\in S\}$ (see Fig. 1). Values of the function g can be easily calculated recursively, since $g(v,\varnothing ,u)=w(\{v,u\})$ and

$$\begin{aligned} g(v,S,u)\left\{ \begin{array}{rcl} =\min \limits _{m\in S}\min \limits _{v'\in V_m}\{g(v,S\setminus \{m\},v')+w(\{v',u\})\},&{} \text{ if } &{} S\subseteq [j-l,j)\setminus \{1,i\},\\[1ex] =\min \limits _{m\in S}\min \limits _{v'\in V_m}\{w(\{v,v'\})+g(v',S\setminus \{m\},u)\},&{} \text{ if } &{} S\subseteq [i-l,i)\setminus \{1,j\}. \end{array}\right. \end{aligned}$$

(1)

Further, for any $1\le j<i\le k$, let f(u, v, T) be the weight of a shortest path P from $u\in V_i$ to $v\in V_j$ visiting all the clusters with numbers from $([1,i)\cup [1,j))\setminus T,$ where $T\subseteq ([i-l,i)\cup [j-l,j))\setminus \{1,i,j\}$, and the path P has the form

$$ u=v_{i_0},v_{i_1},\ldots ,v_{i_r}=\bar{v}=v_{j_0},v_{j_1},\ldots ,v_{j_s}=v, $$

for pairwise defferent indexes $i_0,\ldots , i_r,j_1,\ldots ,j_s$, such that $\bar{v}\in V_1$, $i_t<i$ for $1\le t\le r$, $j_{t'}<j$ for $0\le t'\le s-1$, and

$$\begin{aligned} i_q-i_p\le & {} l,\quad (0<p<q\le r),\\ j_{p'}-j_{q'}\le & {} l,\quad (0\le p'<q'\le s). \end{aligned}$$

As with the function g, values of the function f can be obtained recursively. We start with values $f(u,v,(1,t))=w(\{u,v\})$ for any $u\in V_1$ and $v\in V_t$, $2\le t\le l+2$. All other necessary values f(u, v, T) for any $u\in V_i$, $v\in V_j$ and any $T\subset ([i-l,i)\cup [j-l,j)) \setminus \{1,i,j\}$ can be computed in ascending order by i and $j<i$ as follows. Let m be the maximum number of the cluster (excluding i and j) visited by the path P. If $m>j$, then f(u, v, T) can be calculated by formula

$$\begin{aligned} f(u,v,T)=\min _{S\subseteq [m-l,m)\setminus (T\cup \{1,j\})}\,\min _{u'\in V_m}\{g(u,S,u')+f(u',v,T\cup S)\}, \end{aligned}$$

(2)

and otherwise by

(3)

Finally, we obtain f(u, v, T) for any $u\in V_k$ and $v\in V_{k-1}$ and for any $T\subseteq [k-l-1,k-1)$. Weight of an optimal l-quasi-pyramidal tour (see Fig. 2) is given by

$$\begin{aligned} \min _{T\subseteq [k-l-1,k-1)}\,\min _{u\in V_k}\min _{v\in V_{k-1}}\{f(u,v,T)+g(v,T,u)\}. \end{aligned}$$

We compute a naïve upper bound for time complexity of the algorithm. At first, we calculate the necessary values g(v, S, u) by formula (1) in time $O(2^ln^3)$. Then, the initial values f(u, v, (1, t)) can be computed in $O(n^2)$. Further, for any fixed u, v and T, the complexity of Eqs. (2) and (3) does not exceed $O(2^ln)$. Since, formulas (2) and (3) are invoked at most $O(2^ln^2)$ times, the overall time complexity bound is $O(4^ln^3)$, which completes our proof.

Fig. 2.

Constructing a minimum weight l-quasi-pyramidal tour

Remark 1

Evidently, result of Theorem 1 can be considered in the context of parameterized complexity. Actually, Theorem 1 claims that, in the most general setting, GTSP is fixed-parameter tractable with respect to parametrization induced by quasi-pyramidal tours.

In Sect. 3, we describe a subclass of geometric GTSP, each of whose instance has l-quasi-pyramidal optimal tours for some fixed l. Nevertheless, this class seems to be very specific, and the scheme proposed can hardly be extended to more general settings. To overcome this gap, we propose a more common notion of pyramidal-like tours. We call them pseudo-pyramidal.

Definition 2

Let $\tau$ be a CH-tour $v_{1},v_{i_1},\ldots ,v_{i_r}, v_k, v_{j_{k-r-2}},\ldots ,v_{j_1}$ such that $v_t\in V_t$ for any t. We call $\tau$ an l-pseudo-pyramidal tour, if $i_p-i_{p+1}\le l$ and $j_{q}-j_{q+1}\le l$ for any $1\le p\le r-1$ and $1\le q\le k-r-3$.

It easy to verify that any l-quasi-pyramidal tour is an l-pseudo-pyramidal as well.

Theorem 2

For any weighting function $w:E\rightarrow \mathbb {R}_+$, a minimum cost l-pseudo-pyramidal CH-tour can be found in time of $O(2^lk^{l+4}n^3)$.

Fig. 3.

Auxiliary graph $H_{\theta ,u}$ induced by the tour $\theta =\{1,i_1,\ldots ,i_{k-1}\}$ and the node $u\in V_1$

Proof

Our argument consists of two stages.

At the first stage, we enumerate all l-pseudo-pyramidal tours in an auxiliary complete graph $H=K_k$ with vertex set $\{1,\ldots ,k\}$, which we call graph of clusters. Denote the set of these tours by $\varTheta _l$.

Then, at the second stage, for any tour $\theta =(1,i_1,\ldots ,i_{k-1})\in \varTheta _l$ and any node $u\in V_1$, we find a shortest u-u-path $\rho (\theta ,u)$ in the appropriate auxiliary $(k+1)$-partite graph $H_{\theta ,u}$, which is defined as follows. Denote parts of $H_{\theta ,u}$ by $\pi _0,\ldots ,\pi _k$. Then, as it is shown at Fig. 3, $\pi _0=\pi _k=\{u\}$ and, for any $j\in [1,k)$, $\pi _j$ coincides with the cluster $V_{i_j}$ of the graph G, i.e. $\pi _j=V_{i_j}$. For any $j\in [0,k)$, the subgraph $H_{\theta ,u}\langle \pi _j\cup \pi _{j+1}\rangle$ induced by $\pi _j$ and $\pi _{j+1}$ is a complete bipartite graph. The edges of the graph $H_{\theta ,u}$ inherit the edge weights of the given graph G.

Evidently, any u-u-path in the graph $H_{\theta ,u}$ is equivalent to the appropriate CH-tour in the graph G. Therefore, a minimum cost l-pseudo-pyramidal CH-tour in the graph G is defined by a shortest path $\rho (\theta ^*,u^*)$, i.e.

$$ w(\rho (\theta ^*,u^*))=\min \{w(\rho (\theta ,u)):\theta \in \varTheta _l, u\in V_1 \}. $$

The time complexity of both stages does not exceed the product of the complexity $T(\varTheta _l)$ of the l-pseudo-pyramidal tours enumeration procedure for the graph H (construction of the set $\varTheta _l$), the size of $V_1$, and the complexity of the shortest-path problem in graphs $H(\theta ,u)$, i.e. $O(k\cdot n^2)$. Hence, the overall time complexity will be at most $T(\varTheta _l)\cdot O(n^3),$ since, without loss of generality, we can assume that $|V_1|=\min \{|V_i|:i\in [1,k]\}\le n/k$.

To estimate $T(\varTheta _l)$ we augment the dynamic programming procedure developed in [20].

We introduce two sets $\varTheta _l^+$ and $\varTheta _l^-$ of partial simple (possibly closed) paths in the graph H. Each element of $\varTheta _l^+$ is a path $\theta ^+=(i_1,\ldots ,i_c)$ such that $i_p-i_{p+1}\le l$ for any $p\in [1,c)$. Similarly, each element $\theta ^-=(j_1,\ldots ,j_d)\in \varTheta _l^-$ satisfies the equation $j_{q+1}-j_q\le l$ for any $q\in [1,d)$.

The current state of the recursive procedure is encoded by a triple (i, S, E), whose entries is defined as follows. The number $i\in [1,k-1]$ denotes depth of recursion. The set $S=\{p_1,\ldots ,p_m\}$ consists of signed pairs $(i,j)\in [1,k]^2$ such that

• (i) $p_1=(1,s)^+$ and $p_2=(t,1)^-$ for some $\{s,t\}\subset [1,k]$

• (ii) there exists a set $\varTheta (i,S)$ of partial paths $\theta _1,\ldots ,\theta _m$, for which

  • $\theta _a$ is a simple path from $i_a$ to $j_a$

  • $\theta _a\in {\left\{ \begin{array}{ll} \varTheta ^+_l\text{, } \text{ if } p_a=(i_a,j_a)^+\\ \varTheta ^-_l\text{, } \text{ if } p_a=(i_a,j_a)^-\end{array}\right. }$

  • let $I_a$ be the nodeset of the path $\theta _a$; then, $I_1\cap I_2=\{1\}$, and $I_a\cap I_b=\varnothing$ for any other a and b

  • $I_1\cup \ldots \cup I_m=[1,i]$.

Finally, the set E is an arcset of the l-pseudo-pyramidal tour to be constructed (for the convenience, we store edges of this tour with their bypass directions). Denote

$$ Q=\bigcup \bigl \{\{i_a,j_a\}:p_a\in S\bigr \}. $$

The recursion starts from the following set of initial states (see Fig. 4)

$$\bigl \{(k-1, \{(1, s)^+, (t, 1)^-\},\{(s, k), (k, t)\}):\{s,t\}\subset [1,k)\bigr \}.$$

Any time, when $i>1$, there are the following six options. Consider them separately.

Case 1. There exists $p=(i,i)^+\in S$ (or $(i,i)^-$). In this simple case, we make a recursive call with the state $(i-1,S\setminus \{p\},E)$ immediately.

Case 2. There exists $p_a=(i,j)^+\in S$. Then, in the path $\theta _a\in \varTheta ^+_l$, the node i has a successor $t\in [i-l,i-1]$. We make a recursive call with the state

$$(i-1, (S\cup \{(t, j)^+\})\setminus \{p_a\}, E\cup \{(i, t)\})$$

for any $t\in [i-l,i-1]\setminus (Q\setminus \{j\})$.

Case 3. There exists $p_a=(i,j)^-\in S$. Then, in the path $\theta _a\in \varTheta ^-_l$, there is a successor $t\in [1,i-1]$, and we call the recursion with the state

$$(i-1, (S\cup \{(t, j)^-\})\setminus \{p_a\}, E\cup \{(i, t)\})$$

for each $t\in [1,i-1]\setminus (Q\setminus \{j\})$.

Case 4. There is $p=(j,i)^+\in S$. This can be treated similarly to Case 3.

Case 5. There is $p=(j,i)^-\in S$. This is similar to Case 2.

Case 6. In this case, $i\not \in Q$, and we should try iteratively all elements of the set S. Suppose, i belongs to path $\theta _a$ assigned to the pair $p_a=(i_a,j_a)^+\in S$ such that $s\in [1,i-1]$ is its predecessor, and $t\in [i-l,i-1]$ is a successor. Then we should call the recursion with the state

$$(i-1,S\cup \{(i_a,s)^+,(t,j_a)^+\},E\cup \{(s,i),(i,t)\})$$

for each $s\in [1,i-1]\setminus (Q\setminus \{i_a\}$) and $t\in [i-l,i-1]\setminus (Q\setminus \{j_a\})$. Similarly, for the pair $p_a=(i_a,j_a)^-$, we make a recursive call with states

$$(i-1,S\cup \{(i_a,s)^-,(t,j_a)^-\},E\cup \{(s,i),(i,t)\})$$

for each $s\in [i-l,i-1]\setminus (Q\setminus \{i_a\}$) and $t\in [1,i-1]\setminus (Q\setminus \{j_a\})$.

If $i=1$, then $S=\{(1,1)^+,(1,1)^-\}$, and the state (1, S, E) is final. In this case, E contains arcs of an l-pseudo-pyramidal tour, which can be decoded in time O(k).

Since, as it is shown in [20] the time complexity of the recursive procedure above is $O(2^l k^{l+3})$, the overall complexity bound of finding the minimum cost l-pseudo-pyramidal tour is

$$ O(2^l k^{l+3})\times O(k)\times O(n^3)=O(2^lk^{l+4}n^3). $$

Thus, the theorem is proved.

Fig. 4.

Example of the initial recursion state

Remark 2

As with Theorem 1, Theorem 2 states that, for any weighting function, GTSP belongs to FPT with respect to parameters k and l. Also, since $O(2^l(\log n)^{l+4}n^3)$ asymptotically does not exceed $2^{O(l^3)}\cdot O(n^4)$, the problem has FPT algorithms with respect to parameter l only any time when $k=O(\log n)$.

3 Polynomial Time Solvable Subclass of GTSP on Grid Clusters

In this section, we describe a polynomially solvable subclass of the Generalized Traveling Salesman Problem on Grid Clusters, GTSP-GC for short. In this special case of the GTSP, an undirected edge-weighted graph $G=(V, E, w)$ is given where the set of vertices V correspond to a set of points in the planar rectangular grid. Every nonempty $1\times 1$ cell of the grid forms a cluster. The weighting function is induced by distances between the respective points with respect to some metric. To simplify it, we consider Euclidean distances, but similar results can be easily obtained for some other metrics, e.g. for $l_1$. In Fig. 5, we present an instance of the Euclidean GTSP-GC with 6 clusters.

Fig. 5.

An instance of the Euclidean GTSP-GC and its optimal solution

For two special cases of the problem, when the number k of clusters is $O(\log n)$ or $n - O(\log n)$, polynomial time approximation schemes (PTAS) were proposed in [17]. Meanwhile, the question of a systematic description of polynomial time solvable subclasses of GTSP-GC, which is closely related to complexity analysis of the Hamiltonian cycle problem on grid graphs, is still far from its complete answer.

Let H and W be height and width (number of rows and columns) of the given grid, respectively. We consider a special case of the GTSP-GC, for which one of these parameters, say H does not exceed 2 (while the other one is unbounded). We call this case GTSP-GC(H2). We show that any instance of GTSP-GC(H2) has an l-quasi-pyramidal optimal CH-tour for some l independent on n. Therefore, this subclass of GTSP-GC is polynomially solvable due to Theorem 1.

Our argument is based on the Tour straightening transformation (Algorithm 1), which is closely related to the well-known class of local search heuristics and is introduced in the following.

To describe the transformation, assign to columns of the grid defining the given instance of GTSP-GC(H2), integer numbers $1,2,\ldots , W$ (from the left to the right). Consider an arbitrary CH-tour $\tau$. Assigning to each node $v_i$ of $\tau$ the number $c_i$ of the column it belongs to, obtain a sequence $\sigma$ of column numbers presented in the order induced by the tour $\tau$. Without loss of generality, assume that $\sigma$ has the form

$$\begin{aligned} 1=c_1,c_2,\ldots ,c_r=W,c_{r+1}\ldots ,c_s\end{aligned}$$

(4)

for some appropriate numbers r and s.

Fig. 6.

Segment of $\tau$ with t-zigzag

Suppose, for some integer number t, whose value will be specified later, there exist indices

$$\begin{aligned} 1\le p<q\le r,&\text{ such } \text{ that } c_p-c_q\ge t-1,\ \text{ or } \end{aligned}$$

(5)

$$\begin{aligned} r+1\le p'<q'\le s,&\text{ such } \text{ that } c_{q'}-c_{p'}\ge t-1 . \end{aligned}$$

(6)

In this case, we say that the tour $\tau$ has a t-zigzag (Fig. 6). Obviously, any l-quasi-pyramidal tour contains no t-zigzags, for $t\ge l$. Algorithm 1 replaces all segments of the tour $\tau$ having t-zigzags with subtours of a special kind.

Fig. 7.

Replacing t-zigzag with tour segments of the special kind

To specify the value of t, notice that the weight of eliminated segments of $\tau$ has an evident lower bound

$$t+2(t-1)+t-2=4t-4.$$

Meanwhile, the weight of their replacement in Step 7 at any iteration of Algorithm 1 is at most $2t + 2F(Y,S_2)$, where $F(Y,S_2)$ is an optimum value of the 2-medians clustering objective function for a sample Y taken from the line segment $S_2=\{y:0\le y\le 2\}$.

To estimate an upper bound for $F(Y,S_2)$ we need the following technical lemma.

Lemma 1

For any sample $\xi =(p_1,\ldots , p_n)$, $p_i\in S_1=\{p: 0\le p\le 1\}$ there exist numbers $m_1$ and $m_2\in S_1$ such that

$$\begin{aligned} F(\xi ,S_1)=\sum _{i=1}^n\min \{|p_i-m_1|,|p_i-m_2|\}\le n/6. \end{aligned}$$

(7)

We give a short sketch of the proof of Lemma 1 postponing its full version to the forthcoming paper. Without loss of generality, we assume that any sample $\xi =(p_1,\ldots ,p_n)$ contains points $p_i$ in ascending order. Moreover, we assume that any cluster $C=\{i_1,\ldots ,i_\mu \}\subset [1,n]$ inherites this property, i.e. $p_{i_1}\le \ldots \le p_{i_\mu }$ and $p_i\le p_j$ holds for any partition $C_1\cup C_2=[1,n]$ and any $i\in C_1$ and $j\in C_2$. Then, for the median m of a $\mu$-points cluster C we obtain

$$\begin{aligned} \sum _{t=1}^\mu |p_{i_t}-m|=\sum _{t=1}^{\lfloor \mu /2 \rfloor } (m-p_{i_t})\ +\sum _{t=\lceil \mu /2 \rceil +1}^\mu (p_{i_t} - m)= - \sum _{t=1}^{\lfloor \mu /2 \rfloor } p_{i_t}\ + \sum _{t=\lceil \mu /2 \rceil +1}^\mu p_{i_t}. \end{aligned}$$

Therefore, for a given sample $\xi$, the value $F(\xi ,S_1)$ depends on the choice of a partition $C_1\cup C_2 = [1,n]$ ultimately and obeys the equation

$$\begin{aligned}&\quad F(\xi ,S_1)=\min \left\{ \sum _{i\in C_1} |p_{i}-m_1| + \sum _{i\in C_2} |p_{i}-m_2|:C_1\cup C_2=\mathbb {N}_n\right\} \\&= \min \left\{ - \sum _{i=1}^{\lfloor \mu _1/2 \rfloor } p_{i}\ + \sum _{i=\lceil \mu _1/2 \rceil +1}^{\mu _1} p_{i} - \sum _{i=1}^{\lfloor \mu _2/2 \rfloor } p_{i+\mu _1}\ + \sum _{i=\lceil \mu _2/2 \rceil +1}^{\mu _2} p_{i+\mu _1}:\mu _1+\mu _2=n\right\} . \end{aligned}$$

Thus, $\sup _{\xi \in S_1^n}F(\xi ,S_1)$ coincides with an optimum value $q^*(n,S_1)$ of linear program (8)

(8)

Applying to program (8) the recurrent variable elimination technique, it is easy to verify that $q^*(n,S_1)\le n/6$, which completes the sketch of our proof.

Getting back to discussion of Algorithm 1, we obtain from Lemma 1 that

$$F(Y,S_2)\le 2\cdot q^*(2t+4,S_1)\le 2\cdot (2t+4)/6.$$

Therefore, at any iteration of Algorithm 1, the tour $\tau '$ becomes cheeper if

$$ 2t+4t/3+8/3\le 4t-4,\ \ \text{ i.e. } t\ge 10. $$

Fig. 8.

Cluster ordering

Further, let the cells of the grid be ordered as in Fig. 8 (i.e., top-down and left-right). For $t=10$, any CH-tour of the given GTSP-GC(H2) instance can be transformed to l-quasi-pyramidal CH-tour for $l=20$ without increasing its weight. Hence, we have proved the following theorem.

Theorem 3

Any instance of GTSP-GC(H2) has an optimal 20-quasi-pyramidal CH-tour.

As a consequence of Theorems 1 and 3, we obtain that GTSP-GC(H2) can be solved to optimality in time $O(n^3)$.

4 Conclusion

In this paper, the new notions of l-quasi-pyramidal and l-pseudo-pyramidal tours extending the classic notion of pyramidal tours are introduced. We show that, similar to the case of pyramidal tours and TSP, an optimal l-quasi-pyramidal tour for the Generalized Traveling Salesman Problem can be found efficiently (for an arbitrary weighting function). Also, we describe a non-trivial polynomially solvable geometric special case of GTSP. Each instance of the problem in question has an l-quasi-pyramidal tour as an optimal solution. Actually, an instance of this problem is defined by the unit 2-row rectangular grid on the Euclidean plane. However, the trick with 2-medians can not be applied straightforward even to the case $h=3$, we believe that we can soon prove the existence of l-pseudo-pyramidal optimal tours for the case of GTSP-GC(Hh) defined by a grid of an arbitrary fixed height h.