Online covering salesman problem

Abstract

Given a graph $G=(V,E,D,W)$, the generalized covering salesman problem (CSP) is to find a shortest tour in G such that each vertex $i\in D$ is either on the tour or within a predetermined distance L to an arbitrary vertex $j\in W$ on the tour, where $D\subset V$,$W\subset V$. In this paper, we propose the online CSP, where the salesman will encounter at most k blocked edges during the traversal. The edge blockages are real-time, meaning that the salesman knows about a blocked edge when it occurs. We present a lower bound $\frac{1}{1 + (k + 2)L}k+1$ and a CoverTreeTraversal algorithm for online CSP which is proved to be $k+\alpha$-competitive, where $\alpha =0.5+\frac{(4k+2)L}{OPT}+2\gamma \rho$, $\gamma$ is the approximation ratio for Steiner tree problem and $\rho$ is the maximal number of locations that a customer can be served. When $\frac{L}{\texttt {OPT}}\rightarrow 0$, our algorithm is near optimal. The problem is also extended to the version with service cost, and similar results are derived.

1 Introduction

The Covering salesman problem(CSP) was firstly proposed by Current and Schilling (1989). It can be stated as follows: identify the minimum cost tour of a subset of n given cities such that every city not on the tour is within some predetermined covering distance standard, $L_i$, of a city that is on the tour. The CSP can be viewed as a generalization of the traveling salesman problem (Garey and Johnson 1990). If $L_i =0$ or $L_i< \min _j p_{ij}$, where $p_{ij}$ denotes the shortest distance between vertices i and j, the CSP reduces to a TSP (thus, it is NP-hard).

Current and Schilling (1989) referred to several real world examples, such as the routing of rural health care delivery teams, where not all the cities are required to be visited. The application also includes the humanitarian aid, police patrolling, sensor location and so on (Hachicha et al. 2000; Ha et al. 2013; Flores-Garza et al. 2015; Naji-Azimi et al. 2012; Yang et al. 2014)

Recently, it has some new applications as the blooming of online shopping. Due to the promotion of e-commerce company, the amount of orders will increase dramatically, which usually leads to delay of delivery. In order to speed up the delivery, the salesman usually visits part of the customers and visit one of the several third-party convenient stores nearby in order to complete the delivery within some promised deadline, say two or three hours, as some express company Shunfeng and DHL do. In the above practical case, the salesman only visit a subset of vertices to cover the remainder customer vertices.

Traveling on the urban traffic network, the salesman suffers a lot from the uncertain travel time. It is usually induced by the uncertain traffic blockages which may be from the the traffic accident, rush hour or bad weather. Taking the uncertain traffic blockages into account, we propose the online covering salesman problem. Assuming that a blockage can be known when it occurs, we try to design a robust online routing algorithm for the salesman to complete the delivery as soon as possible.

1.1 Literature review

After Current and Schilling, some extensions of the CSP have appeared in the literature. Considering the application in concert tour planning, Golden et al. (2012) defined a generalized version of CSP, where each vertex i needs to be covered $k_i$ times, and there is a cost associated with each visited vertex. The cost may come from the fixed cost associated with a concert.

Current and Schilling (1994) introduced two bi-criterion routing problems: the median tour problem(MTP) and the maximal covering tour problem(MCTP). In both problems the tour must visit only p of the n vertices on the network, and they both have one goal to minimize the total tour length. In MTP, the other goal is the minimization of the total distance from each demand at the vertices to their nearest stop on the tour. In MCTP, the other goal is to maximize the total demand within some given distance. Another generalization and closely related problem discussed in Gendreau et al. (1997) is the covering tour problem (CTP). Here, given an undirected graph $G=(V\cup W, E)$, the vertices in V can be on the tour, the vertices in $T\subset V$ must be visited while the vertices in W must be covered. Like the CSP, a vertex i not on the tour must be within a predefined covering distance $L_i$ of a vertex on the tour. When $T\cup W=\phi$, the CTP reduces to a CSP, and when the subset of vertices that must be on the tour consists of the entire vertex set $T=V\cup W$, the CTP reduces to the TSP.

After these fundamental works, there are also some variations considering multiple vehicles (Hachicha et al. 2000; Ha et al. 2013; Flores-Garza et al. 2015), capacity constraints (Naji-Azimi et al. 2012), disk covering constraint (Yang et al. 2014), random demands (Tricoire et al. 2012). The application includes the humanitarian aid, police patrolling, sensor location and so on. CSP is also related to several famous routing problems, such as the prize collecting TSP(PCTSP) (Bienstock et al. 1993), selective TSP (Laporte and Martello 1990), clustered TSP (Chisman 1975). The interested readers could refer the survey by Gutin and Punnen (2002).

Most of the above works gave an exact solution or a heuristic solution for the problems. As to the approximation algorithm, Slavik (1997) focused on the tree cover problem and covering tour problem, where all the vertices in the graph are visited or covered. The algorithm was based on LP relaxation rounding operations, and the algorithm is proved to be $\frac{3}{2}\rho$-approximation where $\rho$ is maximum of locations from which a customer can be served. Safra and Schwartz (2006) proved various geometric covering problems related to the TSP cannot be efficiently approximated to within any constant factor unless $P = NP$. It includes the TSP with neighborhood, group steiner tree, the minimum watchman problem and so on. All the problems are defined in the Euclidean plane. For the version considering the penalty of the unvisited cites, which is actually the PCTSP. Based on Christofides’ algorithm (Christofides 1976) for TSP as well as a method of rounding of linear programming(LP) relaxation to integers, PCTSP was proved to be 2.5-approximation (Bienstock et al. 1993) and the ratio was improved to be $2-\frac{1}{n}$ by Goemans et al. (1992).

For the previous research, the online TSP with online edge blockages may be the most related. Liao and Huang (2014) studied the online TSP in complete weighted graphs, called covering Canadian traveler problem (cCTP). An algorithm with competitive ratio as $O(\sqrt{k})$ was proposed, where k is also the upper bound of number of blockages. If the salesman only visits a subset of vertices, the problem is called Steiner TSP(sTSP). In our own paper (Zhang et al. 2015), we studied the sTSP with online edge blockages, and proposed a near optimal polynomial strategy with competitive ratio $k+4$ while the lower bound was proved to be $k+1$. The version with advance information was also studied (Zhang et al. 2016), where the traveler can get the information a time units in advance.

The original version of cCTP(or sTSP) is the Canadian traveler problem(CTP), which is the Shoretest path problem with online edge blockages. It is introduced by Papadimitriou and Yannakakis (1991). It is PSPACE-complete to find an online algorithm with a constant competitive ratio for CTP (Papadimitriou and Yannakakis 1991). When the number of blocked edges is at most k, the variation is denoted as k-CTP. The best competitive ratio for k-CTP is $2k+1$ by Zhu et al. (2003) and Westphal (2008) independently. Zhang et al. (2013) also extended k-CTP to the case of multiple travelers.

1.2 Our results

Motivated by delivery in urban traffic network, we studied the covering salesman problem with online edge blockages, which has a wide application in operations society nowdays. For the version without service cost, we present a lower bound $\frac{1}{1 + (k + 2)L}k+1$, the online algorithm is proved to be $k+\alpha$ competitive, $\alpha =0.5+\frac{4kL}{\texttt {OPT}}+2\gamma \rho$. When $\frac{L}{\texttt {OPT}}\rightarrow 0$, our algorithm is near optimal. We also extend the analysis to the version with service cost.

The remainder of the paper is organized as follows. Section 2 gives the problem formulation and some fundamental assumptions. In Sect. 3, we present a lower bound for online covering salesman problem. In Sect.  4, the CoverTreeTraversal algorithm is proposed and the competitive ratio is proved. Sect. 5 extends the analysis to online covering salesman problem with service cost, where the service fee is charged by the third-party for the service per parcel. We summarizes the main conclusions of this work and proposes some future research problems in Sect. 6.

2 Preliminary

Given an edge-weighed graph $G=(V,E,D,W)$, where $|V|=n$ and $|E|=m$ and $D\subset V$ is the collection of customer vertices, $W\subset V$ is the collection of the convenient stores vertices. The edge weight w(u, v) represents the traversal time, or the distance, between the two vertices for edge $(u, v) \in E$. In the paper, we assume there are at most k edge blockages, and let $\delta =<e_1, e_2,\ldots , e_k>$ denote the sequence of these online blocked edges. Each of the blocked edge is revealed to the salesman once it occurs. We try to find a tour with minimum travel time to guarantee each vertex $v\in D$ is either on the tour or within a distance L to some vertex in W on the tour. Starting from a depot s, we seek a minimum cost closed tour that vertex $i\in D$ is either on the tour or within a distance L to an arbitrary vertex $j\in E$ on the tour. We call this problem online Covering Salesman Problem(online CSP) with edge blockages.

This way, the instance of the online can be denoted as a quintuple $I = (V,E,D,W,\delta )$ (or simplified as a couple $I = (G, \delta ))$. For an algorithm $\mathcal {A}$, the competitive ratio is $c_{\mathcal {A}}=\sup _{I}\frac{\mathcal {A}(I)}{OPT(I)}$, where $\mathcal {A}(I)$ is the total travel time derived by algorithm $\mathcal {A}$ for instance I, and OPT(I) is the corresponding optimal value. The lower bound of this problem is $\beta =\inf _{\mathcal {A}} c_{\mathcal {A}}$. Note that $\beta \ge 1$ for our problem.

Our discussion is based on the assumptions that the remainder graph is connected after deleting the blocked edge and the traversed edge will not be blocked later.

3 Lower bound

Recall that $\delta$ denotes the sequence of online blocked edges that will be revealed to the salesman during the traversal. Due to the oblivious adversary, the realtime information is equivalents to the case that every blockage $e=(u,v)$ is revealed exactly when the salesman is at u or v.

Theorem 1

For online CSP, $\beta \ge \frac{1}{1 + (k + 2)L}k+1$ .

Proof

We prove this lower bound of $k + 1$ by showing that for any online algorithm, there is an instance $I = (V, E, D, W, \delta )$ of online CSP, such that the competitive ratio of the algorithm on the instance I is almost $k + 1$. In the instance I, the graph $G = (V, E, D)$ is shown in Fig. 1, with $D = \{s, v_{k+2}, v_{k+3}, \ldots , v_{2k+2}\}$, $V \backslash D = \{v_1 , v_2, \ldots , v_{k+1}\}$, $W=V$, and $E = \{\{s, v_i\}, \{v_i, v_{k+1+i}\}, \{v_{k+1+i}, v_{2k+3}\} | 1 \le i \le k + 1\}$. The edge weights are, for $1 \le i \le k + 1$.

$$\begin{aligned} \left\{ \begin{array}{l} w(s,{v_i}) = 1\\ w({v_i},{v_{k + 1 + i}}) = \epsilon \\ w({v_{k + 1 + i}},{v_{2k + 3}}) = \epsilon \end{array} \right. \end{aligned}$$

(3.1)

where $\epsilon$ is an arbitrary small positive number.

Fig. 1

Special unweighted graph

For any online algorithm $\mathcal {A}$, from depot s, if the salesman chooses to traverse edge $(s, v_i)$, for some i such that $1 \le i \le k + 1$, then edge $(v_i, v_{k+1+i})$ is blocked by the adversary when the salesman arrives at vertex $v_i$. Clearly the salesman has to go back to depot s afterward, and uses $\mathcal {A}$ to choose another edge $(s, v_j)$ to traverse, for some j such that $1 \le j \le k + 1$; if $j= i$, then edge $(v_j, v_{k+1+j})$ is blocked when the salesman arrives at vertex $v_j$. And so on for the first k distinct attempts by the salesman to traverse exactly k out of the $k + 1$ edges of form $(s, v_i)$, $i = 1, 2, . . . , k + 1$, the corresponding k edges of form $(v_i, v_{k+1+i})$ are blocked in sequence, denoted as $\delta$.

1) If $\epsilon >L$, the salesman will succeed to arrive at $v_{2k+3}$ in his $(k + 1)$st try. Then he will visit every vertex with demand and return to s, resulting a closed tour. Due to Eq. 3.1, the cost of algorithm $\mathcal {A}$ is

$$\begin{aligned} \mathcal {A}(G,\delta )= & {} 2k + 1 + \epsilon + 2(k + 1)\epsilon + \epsilon + 1\\= & {} 2k + 2 + 2(k + 2)\epsilon \end{aligned}$$

The optimal closed tour for adversary on the $G=(V,E-\delta ,D)$ is

$$\begin{aligned} \mathrm{{OPT}}(G,\delta )= & {} 1 + \epsilon + 2(k + 1)\epsilon + \epsilon + 1\\= & {} 2 + 2(k + 2)\epsilon \end{aligned}$$

From all above,

$$\begin{aligned} \frac{\mathcal {A}(G,\delta )}{{\mathrm{{OPT}}(G,\delta )}} = \frac{{2k + 2 + 2(k + 2)\epsilon }}{2 + 2(k + 2)\epsilon } \le 1 + \frac{k}{1 + (k + 2)L}=c_{\mathcal {A}} \end{aligned}$$

Hence, $c_{\mathcal {A}}\ge \frac{1}{1 + (k + 2)L}k+1$ holds for all $\mathcal {A}$.

2) If $\epsilon \le L$, the salesman visit vertex $v_i$ means that $v_{k+1+i}$ has been covered. The salesman will go to s instantly, and the travel time is

$$\begin{aligned} \begin{array}{l} \mathcal {A}(G,\delta ) = 2k + 2; \end{array} \end{aligned}$$

The offline salesman will visit $v_{2k+3}$ to cover D, and the optimal offline traversal time is

$$\begin{aligned} \begin{array}{l} \mathrm{{OPT}}(G,\delta ) = 1 + \epsilon + 2\epsilon + \epsilon + 1=2 + 4\epsilon . \end{array} \end{aligned}$$

For this scenario,

$$\begin{aligned} \frac{{\mathcal {A}(G,\delta )}}{{\mathrm{{OPT}}(G,\delta )}} \le \frac{{2k + 2}}{{2 + 4\epsilon }} \le k + 1=c_{\mathcal {A}}, \end{aligned}$$

where $\epsilon \ge 0$. Hence, $c_{\mathcal {A}}\ge k+1$ holds for all $\mathcal {A}$.

Hence, we have $\beta \ge \min \left\{ \frac{1}{1 + (k + 2)L}k+1, k+1\right\} =\frac{1}{1 + (k + 2)L}k+1$. This proves the theorem. $\square$

4 CoverTreeTraversal algorithm

In this section, we will introduce the CoverTreeTraversal algorithm for the online Covering Salesman Problem (online CSP). The algorithm includes two parts. The first part is to get an approximation solution of Covering Steiner Tree(CST) w.r.t. D via the linear programming relaxation. The second part is to execute Deep-First-Search(DFS) traversal to visit all the customer vertices on the CST or the subtrees induced by the blockages.

4.1 LP relaxation for CST

In this section, we compute a tree by the LP relaxation of CST. The Steiner Tree is a special case of Covering Steiner tree with covering distance $L=0$. Since the Steiner tree problem is NP-hard, CST is also NP-hard.

For the initial solution, we define the covering matrix A as follows: $A=(a_{ij})$, where${({a_{ij}})_{i,j\in V}} = \left\{ \begin{array}{l} 1\quad 0\le l(i,j)< L,i\in D,j \in W\\ 1\quad i=j,i\in D\\ 0\quad otherwise \end{array} \right.$, where l(i, j) is the travel time between i and j. Vertex i can be served at set a[i], where $a[i]= \{ j \in W\left| {{a_{ij}} = 1} \right. \}\cup \{i\}$. We also define that $\rho = \mathop {\max }\limits _{i \in D} \{ \left| a[i] \right| \}$, i.e. one customer can be served on at most $\rho$ vertices. In most of practical cases, $\rho$ is at most two or three. Now we give the integer programming of CSP, with the depot as vertex 0.

$IP_1$: CSP

$$\begin{aligned} {Z_1}&= \mathrm{{min }}\sum \nolimits _{i \in V} {\sum \nolimits _{j \in V} {{c_{ij}}{x_{ij}}} } \nonumber \\ s.t.\quad&(a)\quad \sum \nolimits _{i \in V} {{x_{ij}}} - \sum \nolimits _{k \in V} {{x_{jk}}} = 0,\quad \forall j \in V\nonumber \\&(b)\quad \sum \nolimits _{i \in {V/S}} {{x_{ij}}} \ge {y_j},\quad \forall j \in V,S \subset V,\left| {S \cap \{ j,0\} } \right| = 1\nonumber \\&(c)\quad \sum \nolimits _{j \in a[i]} {{a_{ij}}} {y_j} \ge 1,\quad \;\forall i \in D\nonumber \\&(d)\quad {y_j} \in \{ 0,1\} ,\quad \forall j \in V\nonumber \\&(e)\quad {x_{ij}} \in \{ 0,1\},\quad \forall i,j \in V \end{aligned}$$

(4.1)

Remove the constraint (a) of Eq. 4.1, the remainder forms the integer programming of CST we call it $IP_2$, i.e.

$$\begin{aligned} IP_2:\left\{ Z_2=\mathrm{{min }}\sum \nolimits _{i \in V} {\sum \nolimits _{j \in V} {{c_{ij}}{x_{ij}}} }|(b)-(e)\right\} \end{aligned}$$

(4.2)

Clearly, $Z_2\le Z_1$ since the lack of (a).

$LP_2$ is the linear programming relaxation of $IP_2$ as follows:

$$\begin{aligned} LP_2:\left\{ Z_2^* = \min \sum \nolimits _{i \in V} {\sum \nolimits _{j \in V} {{c_{ij}}{x_{ij}}} }|(b),(c),0\le {y_i} \le 1 ,0\le {x_{ij}} \le 1\right\} \end{aligned}$$

(4.3)

We give an approximation algorithm, say LP-CST, for CST. The idea is to select a subset of vertices in $D\cup W$ to satisfy the covering constraint, and connect all the selected vertices as a tree.

Lemma 1

$\forall i\in D$, there is at least one vertex in T covering it.

Proof

Due to $\left| a[i] \right| \le \rho$ and $\sum \nolimits _{j = 1}^n {{a_{ij}}y_j^*} = \sum \nolimits _{j \in a[i]} {y_j^*} \ge 1$ due to constraint (c). Then there is at least one vertex, say ${j_0}$, that $y_{{j_0}}^* \ge 1/\rho$, then $\overline{{y_{j_0}}} = 1$, $j_0\in T$. It proves that at least one vertex, $j_0$, covers vertex i. $\square$

Let $T\subset V$, define $y_j$ as follows: ${y_j}=1$ if $j \in {T}$; otherwise, ${y_j}=0$. Consider the following problem,

$$\begin{aligned}&\begin{aligned} {IP_3:Z_3}({T})&= \mathrm{{min }}\sum \nolimits _{i \in V} {\sum \nolimits _{j \in V} {{c_{ij}}{x_{ij}}} } \\ s.t.\quad&(b)\quad \sum \nolimits _{i \in {V/S}} {{x_{ij}}} \ge {y_j},\quad \forall S \subset V,\forall j \in S\\&(e)\quad {x_{ij}} \in {N^ + },\quad \forall i,j \in V \end{aligned} \end{aligned}$$

(4.4)

$$\begin{aligned}&LP_3:\left\{ Z_3^*({T})= \mathrm{{min }}\sum \nolimits _{i \in V} {\sum \nolimits _{j \in V} {{c_{ij}}{x_{ij}}} }|(b),{x_{ij}} \ge 0\right\} \end{aligned}$$

(4.5)

Lemma 2

$Z_3^* (T) \le \sum \limits _{i,j \in V} {c_{ij} \overline{x_{ij} } }.$

Proof

$\forall i,j\in V$, $\overline{x_{ij} } = \rho x_{ij}^* \ge 0$ holds. Due to this, constraint (e) is satisfied. For the definition of $\overline{x_{ij} }$, we have $\sum \nolimits _{i \in {V/S}} {\overline{x_{ij} } } = \rho \sum \nolimits _{i \in {V/S}} {x_{ij} ^* } \ge \rho y_j^* \ge \rho \frac{1}{\rho } = 1$. Hence, constraint (b) is satisfied and $(\overline{x_{ij} } )_{i,j \in V}$ is a feasible solution to $LP_3$, and $Z_3^* (T) \le \sum \limits _{i,j \in V} {c_{ij} \overline{x_{ij} } }$. This proves the theorem. $\square$

Theorem 2

Algorithm LP-CST is $\gamma \rho$ approximation, where $\gamma$ is the approximation ratio of Steiner tree problem.

Proof

According to Theorem 2 of Wolsey (1980), there is an approximation algorithm Z with $\frac{Z}{{Z_3^*(T)}} \le \gamma$ if $\frac{{Z}}{{Z_3(T)}} \le \gamma$ holds. Thus, from $l(T)\le \gamma Z_3(T)$, we get $l(T)\le \gamma Z_3^*(T)$ holds.

$$\begin{aligned} \begin{aligned} l(T) \le \gamma Z_3^* (T) \le \gamma \sum \limits _{i,j \in V} {c_{ij} \overline{x_{ij} } } = \gamma \rho Z_2^* \le \gamma \rho Z_2 \le \gamma \rho Z_1 \end{aligned} \end{aligned}$$

(4.6)

This proves the theorem. $\square$

From all above, we get a covering Steiner tree, with the approximation ratio as $\gamma \rho$, where $\gamma$ is at least 1.39 in general graph (Byrka et al. 2010). We can also approximate CST by solving $LP_1$ directly to select a subset of vertices, computing a tour to cover the selected vertices by Christiofides’ algorithm for TSP (Christofides 1976), and deleting the redundant copy of edges in the TSP tour to get a tree. Similar as the analysis of LP-CST algorithm, we can derive that $l(T)\le \frac{3}{2}Z_3^* (T) \le \frac{3}{2}\sum \limits _{i,j \in V} {c_{ij} \overline{x_{ij} } } = \frac{3}{2}\rho Z_1^* \le \frac{3}{2}\rho Z_1$.

4.2 CoverTreeTraversal

For the algorithm CoverTreeTraversal, we first get a CST from LP-CST, called T. Then, the salesman will try to execute a DFS traversal to visit all the customer vertices on the CST. During the traversal, the salesman will encounter at most k blockages which will cut the original CST into at most $k+1$ subtrees. Let $\Omega$ be the collection of subtrees which are not visited. Initially $\Omega =\{T\}$. The salesman will try to execute DFS traversal on each subtree, and connect each subtree via a shortest path chain, which we call a jump. We treat the traversal between two jumps as an iteration.

Let Q denote all the customer vertex unvisited. We remark that the service depot is always considered unvisited to force the salesman to return to the service depot, $s\in Q$.

In one typical iteration of the algorithm, the salesman stands at $d_0$, and computes the shortest paths from all vertices in $a[d_0]$ to all the vertices in $a[d_1]$, where $d_1\in Q$ and in some subtree $T_i\in \Omega$, i.e. $d_1\in Q\cap T_i$. Denote a shortest one of all the above shortest paths as $P(d_0',d_1')$, where $d_0' \in a[d_0]$ and $d_1'\in a[d_1]$. Please note that $d_0'$ and $d_1'$ may not be on any subtree in $\Omega$ and they may already be served. We define the shortest path chain as P$=P_1:P_2:P_3$, where $P_1(d_0,d_0')$, $P_2(d_0',d_1')$ and $P_3(d_1',d_1)$. Please note that $l(P_1)$, $l(P_3)\le L$.

Fig. 2

LB-SubtreeTraversal 1. The salesman’s trace in Case 1 in blue line. $e_1=(u_1,v_1)$ cuts the $T_i$ into two subtrees. The part connected to $u_1$ is the new $T_i$ on which the salesman continues the DFS traversal. and the other part $T_i^1$ is added into $\Omega$ after chopping the leaves which are not customer vertex, where $v_1\notin D$ are chopped. After $e_2=(u_2,v_2)\in T_i$ is encountered, add subtree $T_i^2$ in $\Omega$ and return to $x\in T_i$, which is new $d_0$ in the next iteration. The trace in Case 2.1.1 (blue line) includes no customer vertex on $T_j$, and the salesman returns to $d_0$ and starts a new iteration (Color figure online)

During the traversal, once the salesman visits a customer in Q, called v, update $Q=Q-a[v]$, $\forall v\in Q$. If the salesman arrives at $d_1$, then executes the DFS traversal on the subtree $T_i$; otherwise if the salesman is blocked on P, the salesman travels depending on the location of the blockage on P.

The details are listed as follows:

Case 1 A new edge blockage $e_1=(u_1,v_1)$ is revealed after the salesman reaches $d_1$ (Fig. 2a, and the salesman is considered reaching $d_1$. Note that $d_0=d_1=s$ in the first iteration. If $e_1\in T_i$, then $T_i$ is broken down into two smaller subtrees by removing the edge and subsequently updated to be one of the two smaller subtrees that contains $d_1$. The other subtree, say $T_i^1$ is added into $\Omega$ after chopping the leaves not in D. The salesman continues his DFS traversal on the subtree $T_i$ until all the customer vertex in $T_i$ has been visited, and he stands on some vertex in D, say x. Note that during the DFS traversal, new edge blockages can be revealed. When a new blocked edge is in $T_i$, it is processed in the same manner repeatedly. The iteration ends with the salesman standing at x.

Fig. 3

LB-SubtreeTraversal 2. The salesman does DFS traversal on $T_j$ from $u_1$, and the trace in Case 2.1.2 (blue line) includes one customer vertex x on $T_j$. x is the $d_0$ in the new iteration. In Case 2.2, the salesman retraces to $d_0$ and starts a new iteration (Color figure online)

Case 2 A new edge blockage $e_1=(u_1,v_1)$ is revealed on P.

Case 2.1  If $e_1$ is on another subtree $T_j\in \Omega$ , update $T_j$ as the small subtree that contains $u_1$, and add the other subtree $T_j^1$ that contains $v_1$ into $\Omega$. The salesman executes DFS traversal on $T_j$ from $u_1$ and returns to $u_1$ at the end of traversal. Note that during the DFS traversal, new edge blockages can be revealed. When a new blocked edge $e_2=(u_2,v_2)$ is in $T_j$, it is processed in the same manner repeatedly as in Case 1.

Case 2.1.1 If $T_j$ includes no destination at the end of DFS traversal (see Fig. 2b), the salesman returns to $d_0$, the iteration terminates.

Case 2.1.2 When the salesman visited the last destination on $T_j$ (see Fig. 3a), called x, update x as $d_0$, the iteration terminates.

Case 2.2 If e is not in any subtree in $\Omega$ (see Fig. 3b), the salesman returns to $d_0$, update $a[d_0]$, the iteration terminates.

Lemma 3

In each iteration, $l(P_2)\le 0.5 \texttt {OPT}$, where $P_2=P(d_0',d_1')$.

Proof

For an arbitrary vertex $d_0\in D$, according to the definition of $a[d_0]$, the offline salesman has to visit one of the vertex in $a[d_0]$. Similarly, for $d_1\in Q$, the offline salesman has to visit one of the vertex in $a[d_1]$. Since $P_2$ is the shortest path connected $a[d_0]$ and $a[d_1]$, $l(P_2)=l(P(d_0',d_1'))=min\{l(P(i,j))|i\in a[d_0],j\in a[d_1]\}\le 0.5 \texttt {OPT}$. This proves the lemma. $\square$

Recall that P is a shortest path chain including $P_1$, $P_2$ and $P_3$, where $l(P_1),l(P_3)\le L$ and $l(P_2)\le 0.5\texttt {OPT}$. Hence, $l(\texttt {P})\le 0.5 \texttt {OPT}+2L$.

The travel time of the salesman including two parts, one is the traversal time on the subtrees, the other is the jumping time on P.

Lemma 4

In an iteration , the jumping time of a salesman is

$$\begin{aligned} \left\{ \begin{matrix} l(\texttt {P}) &{} \quad Case&{}1 \\ 2l(\texttt {P})&{} \quad Case&{}2.1.1\\ l(\texttt {P})&{} \quad Case&{}2.1.2\\ 2l(\texttt {P}) &{} \quad Case&{}2.2\\ \end{matrix}\right. \end{aligned}$$

Proof

The salesman travels along P and arrives at $d_1'$ in Case 1, it is clear that the jumping time is $l(\texttt {P})$. In Case 2.1.1, the salesman encounters a blockage on some other subtree $T_j$, and there is no unvisited vertex in $T_j$, the salesman returns to $d_0$, the jumping time is at most $2l(\texttt {P})$. In Case 2.1.2, the salesman encounters a blockage on some other subtree $T_j$, and there is some vertex in Q, called $x\in T_j\cap Q$, the salesman stop at x, the jumping time is at most $l(\texttt {P})$. The salesman also returns to $d_0$ in Case 2.2, the jumping time is at most $2l(\texttt {P})$.

This proves the lemma. $\square$

Theorem 3

For online CSP, CoverTreeTraversal is polynomial time and the competitive ratio is $k+\alpha$, where $\alpha =0.5+\frac{4kL}{\texttt {OPT}}+2\gamma \rho$.

Proof

Solving the linear programming to get the steiner vertex set is proved polynomial. The approximation algorithm for Steiner tree is based on linear programing, and it is also polynomial. Computing the shortest path between every pair of vertex in Q is at most $O(|V|^3)$, and computing P in each iteration needs $O(k|V|^3)$, the entire DFT traversal is $O(|V|^2)$. Hence, algorithm CoverTreeTraversal is polynomial time.

The traveling includes two parts, one is the DFS traversal in T and the other is the jumping on $\texttt {P}$. From the two cases in algorithm CoverTreeTraversal, the salesman travels on every edge in $T_i\in \Omega$ at most twice, $t_d\le 2l(T)\le 2\gamma \rho \texttt {OPT}$. Due to Lemma 4, the jumping time per subtree is at most $2l(\texttt {P})$. Note that there will be at most k times jumping for encountering blockages and one more to go back to s. The last jumping costs at most l(P). Hence, the total jumping time is $t_j\le 2kl(\texttt {P})+l({P})$.

The total cost of CoverTreeTraversal algorithm is $t=t_d+t_j\le 2l(T)+k(4L+\texttt {OPT})+0.5\texttt {OPT} \le (k+0.5+2\gamma \rho )\texttt {OPT}+4kL$.

Hence, the competitive ratio is

$$\begin{aligned} \begin{aligned} c_A =\frac{t}{\texttt {OPT}} \le \frac{(k+0.5+2\gamma \rho )\texttt {OPT}+4kL}{\texttt {OPT}} =k+0.5+\frac{4kL}{\texttt {OPT}}+2\gamma \rho =k+\alpha , \end{aligned} \end{aligned}$$

(4.7)

where $\alpha =0.5+\frac{4kL}{\texttt {OPT}}+2\gamma \rho$ and $\gamma \ge 1.39$. This proves the theorem. $\square$

When $\frac{L}{\texttt {OPT}}\rightarrow 0$, our algorithm is near optimal.

5 Online CSP with service cost

In this section, we will study a more practical scenario considering the service cost for the covered customers. The service cost may be charged by the third-party convenient store per parcel, or comes from the waiting time for customers who are not on the tour. Hence, the total online delivery time is the sum of the travel time and the service cost.

The service cost can be seen as the penalty charged. Once a vertex in D is visited, there is no penalty; if it is covered, it is charged $w_i$ depends on weight(number) of orders on the vertex. It comes to prize collecting TSP that has to follow the covering constraint.

5.1 Lower bound

Theorem 4

For online CSP with service cost, $\beta \ge \min \left\{ \frac{1}{1+(k+2)L}k+1,\frac{1}{1+0.5(k+2)w}k+1\right\}$ .

Proof

The proof is similar to Theorem 1. Consider the instance in Fig. 1. Suppose that all the vertices in D has the same amount of orders, then the penalty w is uniform. If $\epsilon > L$, the salesman has to visit every customer in D. $c_{\mathcal {A}}\ge \frac{1}{1 + (k + 2)L}k+1$ holds for an arbitrary algorithm $\mathcal {A}$. If $\epsilon \le L$, for $2\epsilon <w$, it is cheaper to visit the vertice in D, and the online delivery time is $\mathcal {A}(I)\le 2k+2+2\epsilon +2\epsilon +2(k+1)\epsilon$ while $\texttt {OPT}= 2+2\epsilon +2(k+1)\epsilon$, and derive $c_{\mathcal {A}}>k+1$ as $\epsilon \rightarrow 0$; for $2\epsilon \ge w$, the choice is to cover the vertices in D, and the online delivery time is $\mathcal {A}(I)\le 2k+2$ while $\texttt {OPT}= 2+4\epsilon +(k+1)w$, and derive $c_{\mathcal {A}}>\frac{1}{1+0.5(k+2)w}k+1$.

Hence, $\beta \ge \min \{\frac{1}{1+(k+2)L}k+1,\frac{1}{1+0.5(k+2)w}k+1\}$. This proves the theorem. $\square$

Please note that $\beta \ge \frac{1}{1+(k+2)L}k+1$ for $w=0$, which is same with the case without service cost.

In the following subsection, we will show LP-CST also woks when the service cost is considered, and then apply the CoverTreeTraversal algorithm in Sect. 4.2 to solve the problem with service cost.

5.2 Competitive analysis

For the problem with service cost, we give the integer programming formulation and do the linear programming relaxation to lead to the approximate initial solution. For each vertex $i\in D$, the penalty $w_i$ is charged if it is covered without visiting.

Recall the covering matrix A in Sect. 4.1 with covering range L. Again let $\rho =\mathop {\max }\limits _{i \in D} \{ \left| a[i]\right| \}$, $s=0$ as the depot. The service cost for vertex $i\in D$ is $(1-y_i)w_i$, where $y_i=1$ means this vertex is visited, and the total service cost is $t_s=\sum _{i\in D}{(1-y_i)w_i}$. $IP_0$ (Eq. 5.1) is the integer programming of CSP with service cost. Omitting the constraint (a) leads to integer programming of CST with service cost $IP_1^{'}$(Eq. 5.2). The linear relaxation of $IP_1^{'}$ induces $LP_1^{'}$. We get $LP_2$ (Eq. 4.3) from $LP_1^{'}$ by leaving the service cost. Then we can use the LP-CST in Sect. 4.1 to get a CST.

$$\begin{aligned}&IP_0:\left\{ Z_0=\mathrm{{min }}\sum \nolimits _{i \in V} {\sum \nolimits _{j \in V} {{c_{ij}}{x_{ij}}} } + \sum _{i\in D}{(1-y_i)w_i}|(a)-(e)\right\} \end{aligned}$$

(5.1)

$$\begin{aligned}&IP_1^{'}:\left\{ Z_1^{'}=\mathrm{{min }}\sum \nolimits _{i \in V} {\sum \nolimits _{j \in V} {{c_{ij}}{x_{ij}}} } +\sum _{i\in D}{(1-y_i)w_i}|(b)-(e)\right\} \end{aligned}$$

(5.2)

$$\begin{aligned}&LP_1':\left\{ Z_1^{*'}=\mathrm{{min}}\sum _{i \in V} {\sum _{j \in V} {{c_{ij}}{x_{ij}}} } + \sum _{i\in D}{(1-y_i)w_i}|(b)-(c),0\le {y_i} \le 1, 0\le {x_{ij}}\right\} \qquad \quad \end{aligned}$$

(5.3)

Clearly, $Z_1^{'}\le Z_0$ for the lack of (a). $Z_1^*<Z_1^{'}$ since $LP_1^{'}$ is the linear programming relaxation of $IP_1^{'}$. Omitting the service cost, we get $LP_2$ in Eq. 4.3, with $Z_2^{*'}=Z_2^*=\mathrm{{min}}\sum _{i \in V} {\sum _{j \in V} {{c_{ij}}{x_{ij}}} }$.

LP-CST algorithm will select a subset of vertices, say T, to construct a Steiner tree by a $\gamma -$approximation algorithm. Recalling $LP_3$ and $IP_3$ (Eq. 4.4 and 4.5), the total cost of the CST is at most $\gamma Z_3^{*}(T)+\alpha \sum _{i\in D}{(1-y_i)w_i}$.

Theorem 5

The LP-CST algorithm is $\gamma \rho$ approximation, where $\gamma$ is an approximation ratio of Steiner tree.

Proof

Recall Eq. 4.6, we have

$$\begin{aligned} t\le & {} \gamma Z_3^{*} (T) + \sum \nolimits _{i \in D} {(1 - \overline{y_i } )w_i } \\\le & {} \gamma \sum \limits _{i,j \in V} {c_{ij} \overline{x_{ij} } }+ \sum \nolimits _{i \in D} {(1 - \overline{y_i } )w_i } \\\le & {} \gamma \sum \limits _{i,j \in V} {\rho c_{ij} x_{ij}^* }+ \frac{\rho }{{\rho - 1}}\sum \nolimits _{i \in D} {(1 - y_i^* )w_i } \\\le & {} \gamma \rho Z_1^{*'}\le \gamma \rho Z_1 \le \gamma \rho Z_0 \end{aligned}$$

This proves the theorem. $\square$

We apply the CoverTreeTraversal algorithm to the online CSP with service cost. With similar analysis, we can get the following theorem.

Theorem 6

For Covering sTSP with service cost, the CoverTreeTraversal algorithm is polynomial time and $k+\alpha$-competitive, where $\alpha =\frac{{4L}}{{OPT}} + 2\gamma \rho$ .

6 Conclusion

We studied the covering salesman problem with online edge blockages, which a good match to the instant delivery routing problem in urban traffic network. For the version without service cost, we present a lower bound $\frac{1}{1 + (k + 2)L}k+1$, the online algorithm is proved to be $k+\alpha$ competitive, where $\alpha =0.5+\frac{4kL}{\texttt {OPT}}+2\gamma \rho$. We also extend the analysis to the version with service cost. The competitive ratio is still at most $k+\alpha$, and the lower bound is $\min \left\{ \frac{1}{1+(k+2)L}k+1,\frac{1}{1+0.5(k+2)w}k+1\right\}$, where w is the uniform penalty for each vertex in D. When $\frac{L}{\texttt {OPT}}\rightarrow 0$, our algorithm is near optimal.

A more careful analysis for the competitive ratio of CovereTreeTraversal can considered in the future research. We can also assume that there is no blockage between the costumer vertex and the third-party vertex since they are always in a small neighborhood. With these assumption, the algorithm will have a better performance. Another interesting work is to consider a more general service cost function, which includes two parts. One part is that the fixed cost to active a third-party service site and the other part is the changeable cost charged per parcel. In this case, the service cost is the sub modular function, which may be more interesting.