1 Introduction

The routing problems are a much-studied family of combinatorial optimization problems, and have a wide range of applications that include network surveillance, household refuse collection, snow removal, street sweeping, school bus routing.

Considering an application on road network rescue, Zhu and Pan [16] proposed the restricted Chinese postman problem with total penalty (RPCPP), which is defined on an undirected graph \(G=(V,E;w,p)\) with a weight function \(w:E\rightarrow {{\mathbb {R}}}^{+}\) satisfying the triangle inequality, and a penalty function \(p:E\rightarrow {{\mathbb {R}}}^{+}_{0}\). This problem is to find a tour C traversing each vertex \(v\in V\) at least once, such that the value \(w(C)+p(E\setminus C)\) is minimized, where \(w(C)=\sum _{e\in C}w(e)\), and \(p(E{\setminus } C)=\sum _{e\in E{\setminus } C}p(e)\). In 2021, a 1.5-approximation algorithm was designed by Zhu and Pan [16] to solve the RPCPP. Other related routing problems and their applications can be found in [1,2,3, 5, 10].

In the case that a given weight function satisfies the triangle inequality, there are two types of special cases of the RPCPP, which are described as follows: The Chinese postman problem (CPP) [11] is to find a tour on a given undirected graph traversing each edge at least once, such that the weight of this tour is minimized. Clearly, the CPP with the triangle inequality holds is a special case of the RPCPP, where \(p(e)\ge 2w(E)\) for each edge \(e\in E\). Edmonds and Johnson [6] designed a polynomial time exact algorithm to solve the CPP.

In comparison, the metric traveling salesman problem (metric TSP) [15, p.30] is to find a cycle on a given complete graph traversing each vertex exactly once, such that the weight of this cycle is minimized. The metric TSP is another special case of the RPCPP, where G is a complete graph and \(p(\cdot )\equiv 0\). Christofides [15] presented a 1.5-approximation algorithm to solve the metric TSP. In 2021, Karlin et al. [12] reconsidered the metric TSP and designed a \((1.5-\varepsilon )\)-approximation algorithm for some \(\varepsilon > 10^{-36}\).

In real life, it is common for multiple vehicles to work in parallel. Frederickson et al. [7] addressed the CPP and the metric TSP with multiple vehicles and min–max objective, namely, the min–max k -Chinese postman problem (MM-CPP) and the min–max k -traveling salesman problem (MM-TSP).

The MM-CPP and the MM-TSP are defined as follows: Given an undirected graph \(G=(V, E; w)\) with a depot \(r\in V\), an integer \(k\in {{\mathbb {Z}}}^{+}\), and a weight function \(w:E\rightarrow {{\mathbb {R}}}^{+}\) that satisfies the triangle inequality, the MM-CPP is to find k tours starting at r, and collectively traversing each edge \(e\in E\) at least once, such that the maximum of the weights of tours is minimized. Employing a splitting method, Frederickson et al. [7] designed a (\(2-\frac{1}{k}\))-approximation algorithm to solve the MM-CPP. When replacing a given undirected graph with a complete graph, the MM-TSP is to find k cycles starting at r, and collectively covering all vertices in V, such that the maximum of the weights of cycles is minimized. Reemploying a splitting method, Frederickson et al. [7] presented a (\(\frac{5}{2}-\frac{1}{k}\))-approximation algorithm to solve the MM-TSP.

Moreover, the CPP and the metric TSP with multiple vehicles and min-sum objective were studied by Frieze [14] and Pearn [8]. There, the two problems are referred to as the min-sum k -Chinese postman problem (MS-CPP) and the min-sum k -traveling salesman problem (MS-TSP), which are defined as follows: In a given undirected graph \(G=(V, E; w)\) with a depot \(r\in V\) and an integer \(k\in {{\mathbb {Z}}}^{+}\), by adding two constraints that each edge in G must be serviced by exactly one postman and all the k postmen must be involved in the delivery service, the MS-CPP is to find k tours starting at r, and collectively traversing each edge \(e\in E\) at least once, such that the sum of weights of tours is minimized. Using a lower bound algorithm in [4] for the capacitated arc routing problem, Pearn [14] showed that the MS-CPP can be solved optimally. By replacing a given undirected graph with a complete graph, the MS-TSP is to find k cycles starting at r and collectively covering all vertices in V, and satisfying that each cycle contains at least 3 edges, such that the sum of weights of cycles is minimized. Modifying Christofides’ algorithm [15, p.32] for solving the metric TSP, Frieze [8] designed a 1.5-approximation algorithm to solve the MS-TSP.

Motivated by the extensive application in practices of the problems mentioned above, we consider the restricted min–max k -Chinese postman problem with penalties (MM-RPCPP) and its a variant, which are defined as follows: Given an undirected graph \(G=(V,E;w,p)\) with a depot \(r\in V\), an integer \(k\in {\mathbb Z}^{+}\), a weight function \(w:E\rightarrow {{\mathbb {R}}}^{+}\) that satisfies the triangle inequality, and a penalty function \(p:E\rightarrow {{\mathbb {R}}}^{+}_{0}\), (1) the MM-RPCPP is asked to find a set \({{\mathcal {C}}}=\{C_{1},\ldots ,C_{k}\}\) of k tours starting from r and collectively covering all vertices, such that the value \(f({{\mathcal {C}}})=w_{\max }({{\mathcal {C}}})+p(E\setminus {{\mathcal {C}}})\) is minimized, where \(w_{\max }({{\mathcal {C}}})=\max \{\sum _{e\in C}w(e)\mid C\in {{\mathcal {C}}}\}\) and \(p(E{\setminus } {{\mathcal {C}}})=\sum _{e\in E{\setminus } {{\mathcal {C}}}}p(e)\), and (2) The restricted min-sum k -Chinese postman problem with penalties (MS-RPCPP) is asked to find a set \({{\mathcal {C}}}=\{C_{1},\ldots ,C_{k}\}\) of k tours satisfying the constraint mentioned above and that each edge appears in at most one tour and each tour contains at least one edge, such that the value \(h({{\mathcal {C}}})=w({{\mathcal {C}}})+p(E\setminus {{\mathcal {C}}})\) is minimized, where \(w({{\mathcal {C}}})=\sum _{C\in {{\mathcal {C}}}}\sum _{e\in C}w(e)\), and \(p(E\setminus {{\mathcal {C}}})\) is defined in (1). Without loss of generality, we assume \(k\le |E|\) in the paper.

The MM-RPCPP and the MS-RPCPP are multiple-vehicle extensions of the RPCPP respectively. For the MM-RPCPP, the MM-CPP is the special case \(p(e)> 2\cdot w(E)\) for each edge \(e\in E\), and the MM-TSP is another special case that G is a complete graph and \(p(\cdot )\equiv 0\). For the MS-RPCPP, the CPP with the triangle inequality holds is the special case that \(k=1\) and \(p(e)> 2\cdot w(E)\) for each edge \(e\in E\), and the metric TSP is another special case that \(k=1\), G is a complete graph and \(p(\cdot )\equiv 0\). In addition, the MS-RPCPP is closely related to the MS-CPP and the MS-TSP, while it is not a generalization of them.

The MM-RPCPP and the MS-RPCPP may have applications in the real world. For example, an extension of the application in [16] is described as follows: Given a road network, k vehicles and some rescue workers, we need to arrange workers to transfer people on some roads to the road ends in advance, and then plan vehicle routings to rescue people who lie on the residual network. It is of interest to know how to plan vehicle routings to minimize the time spent by workers and vehicles, where the time spent on each road by workers corresponds to a penalty and the time spent on each road by any vehicle corresponds to a weight. In order to minimize the rescue time, we can arrange vehicles in parallel to rescue people, this question can be reduced to the MM-RPCPP. In addition, we further consider another variant of the RPCPP, that is the MS-RPCPP.

To the best of our knowledge, these two problems that we propose have not been considered in the literature. The contribution of this paper is to present two approximation algorithms with constant factors to solve the MM-RPCPP and the MS-RPCPP, respectively.

This paper is organized as follows: In Sect. 2, we present some preliminaries to facilitate the descriptions of algorithms. In Sect. 3, we design a \((\frac{7}{2}-\frac{2}{k})\)-approximation algorithm to solve the MM-RPCPP. In Sect. 4, we present a 2-approximation algorithm to solve the MS-RPCPP. In Sect. 5, we provide our conclusion and further work.

2 Preliminaries

Given a graph \(G=(V, E)\), a walk P connecting a vertex \(v_{i_1}\) and a vertex \(v_{i_{k+1}}\) is an alternating sequence \(P = v_{i_1}e_{i_1}v_{i_2}e_{i_2}v_{i_3}\cdots v_{i_{k}}e_{i_{k}}v_{i_{k+1}}\) such that, \(k\ge 1\) and \(e_{i_j}=v_{i_{j}}v_{i_{j+1}}\in E\) for each integer \(j\in \{1,\ldots ,k\}\). If \(v_{i_1}=v_{i_{k+1}}\), the walk P is called a tour. In addition, a walk P is said to be a path if the vertices in P are all distinct. Similarly, a tour P is called a cycle if the vertices in P are all distinct.

On a weighted graph \(G=(V, E;w)\), the distance \(d_{G}(u, v)\) of two vertices u and v is the weight of a shortest path connecting u and v. The eccentricity \(\delta _{G}(v)\) of a vertex v is \(\max _{u\in V}d_{G}(u, v)\).

We say that an undirected graph \(G=(V, E)\) is connected if there is a path connecting u and v for any \(u, v\in V\); Otherwise, G is disconnected. An undirected graph without a cycle (as a subgraph) is called a forest. We call a connected forest a tree.

A subgraph of a graph \(G=(V, E)\) is a graph \(G'=(V',E')\) with \(V'\subseteq V\) and \(E'\subseteq E\). If \(E'=\{uv \in E\mid u,v\in V'\}\), then \(G'=G[V']\) is the subgraph of G induced by \(V'\). Similarly, if \(V'=\{u,v\in V\mid uv\in E'\}\), then \(G'=G[E']\) is the subgraph of G induced by \(E'\). We call a subgraph \(G'\) of G spanning if \(V' = V\). A subgraph \(G'\) is called a spanning tree if \(G'\) is a tree and spanning.

Given a graph \(G=(V, E)\), an Euler tour in G is a tour that traverses each edge \(e\in E\) exactly once. In addition, a graph G is Eulerian if this graph G admits an Euler tour.

For any weighted graph \(G=(V, E;w)\), we say that the weight function \(w(\cdot )\) satisfies the triangle inequality when \(w(xz)\le d_{G}(x, y)+d_{G}(y, z)\) for any xz \(\in \) E, \(x,y,z\in V\). Let \(n=|V|\) and \(m=|E|\) denote the numbers of vertices and edges in a given graph \(G=(V,E)\), respectively. For any tour C of G, we denote \(E_{C}\) the subset of edges in E that is traversed by C.

In our algorithms to solve the MM-RPCPP and the MS-RPCPP, we need the following lemmas.

Lemma 1

[16] Given an undirected connected graph \(G=(V, E;w, p)\) as an instance of the RPCPP, there exists a \(\frac{3}{2}\)-approximation algorithm (referred as RPCPP algorithm) for solving the RPCPP in time \(O(n^{3})\).

Lemma 2

[9] Given an undirected connected graph \(G=(V,E;w)\) with a depot \(r\in V\), a positive integer k and a subset \(F\subseteq E\), there exists an algorithm (referred as MST-DC algorithm) which can determine a minimum weight subset \(F'\subseteq E\) such that \(G[F\cup F']\) is connected and has at least k edges incident to the depot r, or output that there is no such solution, in running time \(O(n^{2})\).

3 The restricted min–max k-Chinese postman problem with penalties

In this section, we consider the restricted min–max k -Chinese postman problem with penalties (MM-RPCPP). Note that the MM-RPCPP is \(\textsf{NP}\)-hard since the MM-CPP and the MM-TSP are known to be \(\textsf{NP}\)-hard [7]. When \(k=1\), the MM-RPCPP becomes the RPCPP, we can use the RPCPP algorithm to solve the MM-RPCPP to obtain a \(\frac{3}{2}\)-approximation solution. Thus, we assume \(k\ge 2\) in the section.

The strategy to solve the MM-RPCPP is described as follows:

  1. (1)

    Determine a tour in G, satisfying that some objective value as small as possible.

  2. (2)

    Partition the above tour into k walks, and then extend walks to k tours satisfying that the maximum tour weight as small as possible.

Using the strategy mentioned above, we design an approximation algorithm (Algorithm 1) in the following.

figure a

On an auxiliary graph \(G'=(V,E;w',p)\) of a given graph \(G=(V, E;w, p)\), it is clear that the function \(w'\) satisfies the triangle inequality, because of the weight function w satisfying the triangle inequality. Using the RPCPP algorithm and Lemma 1, we can find a feasible solution for an instance \((G';w',p)\) of the RPCPP. The specific result is described as follows:

Lemma 3

Given an auxiliary graph \(G'=(V,E;w',p)\), the RPCPP algorithm is a \(\frac{3}{2}\)-approximation algorithm in time \(O(n^{3})\) to solve the RPCPP problem.

According to the algorithm \({{\mathcal {A}}}_{MM}\), we first get the following lemma.

Lemma 4

\(w_{\max }({{\mathcal {C}}})\le \frac{w(C)}{k}+2(2-\frac{2}{k})\delta _{G}(r) .\)

Proof

We first consider any tour \(C_{j}\), \(j\in \{2,\ldots , k-1\}\). Because the weight function \(w:E\rightarrow {{\mathbb {R}}}^{+}\) satisfies the triangle inequality, we obtain \(w(v_{i_{p'(j)}}v_{i_{p'(j)+1}})\) \(\le d_{G}(r, v_{i_{p'(j)}})+d_{G}(r, v_{i_{p'(j)+1}})\). By the definition of \(\delta _{G}(r)\) in Step 2 of the algorithm \({\mathcal {A}}_{MM}\), we can get \(d_{G}(r, v_{i_{p'(j)}})+d_{G}(r, v_{i_{p'(j)+1}})\le 2\delta _{G}(r)\), implying that

$$\begin{aligned} d_{G}(r, v_{i_{p'(j)}})+w(v_{i_{p'(j)}}v_{i_{p'(j)+1}})+d_{G}(r, v_{i_{p'(j)+1}})\le 4\delta _{G}(r). \end{aligned}$$

Thus, we obtain

$$\begin{aligned} \min \{s_{j}+d_{G}(r,v_{i_{p'(j)}}), w(v_{i_{p'(j)}} v_{i_{p'(j)+1}})-s_{j}+d_{G}(v_{i_{p'(j)+1}}, r)\}\le 2\delta _{G}(r). \end{aligned}$$

Similarly, the above inequality still holds by replacing j with \(j-1\).

It is easy to see that, the case resulting in the maximum weight of any tour \(C_{j}\) is that the tour starts depot r and follows the shortest path to reach \(v_{i_{p'(j-1)}}\), and then follows tour C to \(v_{i_{p'(j)+1}}\), and finally follows the shortest path back to r. And in this situation, we have \(s_{j-1}+d_{G}(r,v_{i_{p'(j-1)}})\le 2\delta _{G}(r)\), and \(w(v_{i_{p'(j)}} v_{i_{p'(j)+1}})-s_{j}+d_{G}(v_{i_{p'(j)+1}}, r)\le 2\delta _{G}(r)\). Hence, we obtain

$$\begin{aligned} w(C_{j})\le 2\delta _{G}(r)+\frac{1}{k}(w(C)-4\delta _{G}(r))+2\delta _{G}(r). \end{aligned}$$
(1)

For other cases of tour \(C_{j}\), i.e., \(j\in \{1,k\}\), the above inequality (1) is easily proved. Therefore, for any \(j\in \{1,\ldots ,k\}\), we have \(w(C_{j})\le 2\delta _{G}(r)+\frac{1}{k}(w(C)-4\delta _{G}(r))+2\delta _{G}(r)\), implying \(w_{\max }({{\mathcal {C}}})\le \frac{w(C)}{k}+2(2-\frac{2}{k})\delta _{G}(r)\). \(\square \)

According to Algorithm 1, Lemma’s 3 and 4, we obtain a result for the MM-RPCPP as follows:

Theorem 1

The algorithm \({{\mathcal {A}}}_{MM}\) is a \((\frac{7}{2}-\frac{2}{k})\)-approximation algorithm to solve the MM-RPCPP and it runs in time \(O(n^3)\).

Proof

It is clear that the algorithm can correctly indicate whether there is a feasible solution to the MM-RPCPP. We need only consider the case that there are feasible solutions for the MM-RPCPP in the following.

For any instance \(G=(V,E;w,p)\) of the MM-RPCPP and its auxiliary graph \(G'=(V,E;w',p)\), let \({{\mathcal {C}}}^{*}\) denote an optimal solution for the instance \(G=(V,E;w,p)\) of the MM-RPCPP, \(E_{{{\mathcal {C}}}^{*}}\) denote the subset of edges collectively traversed by all tours in \({{\mathcal {C}}}^{*}\). And let \(C^{*}\) and \(f'(C^{*})=w'(C^{*})+p(E\setminus C^{*})\) denote an optimal solution and optimal value for the instance \((G';w',p)\) of the RPCPP, respectively.

By the algorithm \({{\mathcal {A}}}_{MM}\), it is clear that \(E_{C}\subseteq E_{{{\mathcal {C}}}}\), so we obtain

$$\begin{aligned} p(E\setminus {{\mathcal {C}}})\le p(E\setminus C). \end{aligned}$$

Using Lemma 4, we have

$$\begin{aligned} w_{\max }({{\mathcal {C}}})\le \frac{w(C)}{k}+2\left( 2-\frac{2}{k}\right) \delta _{G}(r). \end{aligned}$$

From Lemma 3, we know that the RPCPP algorithm can generate a feasible solution C for the instance \((G';w',p)\) of the RPCPP, satisfying \(w'(C)+p(E{\setminus } C)\le \frac{3}{2}(w'(C^{*})+p(E{\setminus } C^{*}))\).

Because all tours in \({{\mathcal {C}}}^{*}\) have a common depot r, it is easy to merge them into a tour, i.e., a feasible solution for the instance \((G';w',p)\) of the RPCPP. Hence, we obtain

$$\begin{aligned} w'(C^{*})+p(E\setminus C^{*})\le & {} w'({{\mathcal {C}}}^{*})+p(E\setminus {{\mathcal {C}}}^{*}) \nonumber \\\le & {} k\cdot w'_{\max }({{\mathcal {C}}}^{*})+p(E\setminus {{\mathcal {C}}}^{*}) \nonumber \\= & {} k\cdot \frac{w_{\max }({{\mathcal {C}}}^{*})}{k}+p(E\setminus {{\mathcal {C}}}^{*}) \nonumber \\= & {} w_{\max }({{\mathcal {C}}}^{*})+ p(E\setminus {{\mathcal {C}}}^{*}). \end{aligned}$$

Therefore, we obtain

$$\begin{aligned} w'(C)+p(E\setminus C)\le & {} \frac{3}{2}(w'(C^{*})+p(E\setminus C^{*})) \nonumber \\\le & {} \frac{3}{2}w_{\max }({{\mathcal {C}}}^{*})+ \frac{3}{2}p(E\setminus {{\mathcal {C}}}^{*}). \end{aligned}$$

Due to all tours in \({{\mathcal {C}}}^{*}\) collectively traversing each vertex \(v\in V\) at least once, we have \(\delta _{G}(r)\le \frac{1}{2}w_{\max }({{\mathcal {C}}}^{*})\). Therefore, we obtain

$$\begin{aligned} f({{\mathcal {C}}})= & {} w_{\max }({{\mathcal {C}}})+p(E\setminus {{\mathcal {C}}}) \nonumber \\\le & {} \frac{w(C)}{k}+2\left( 2-\frac{2}{k}\right) \delta _{G}(r)+p(E\setminus C) \nonumber \\= & {} w'(C)+p(E\setminus C)+2\left( 2-\frac{2}{k}\right) \delta _{G}(r) \nonumber \\\le & {} \frac{3}{2}w_{\max }({{\mathcal {C}}}^{*})+\frac{3}{2}p(E\setminus {{\mathcal {C}}}^{*})+\left( 2-\frac{2}{k}\right) w_{\max }({{\mathcal {C}}}^{*}) \nonumber \\\le & {} \left( \frac{7}{2}-\frac{2}{k}\right) w_{\max }({\mathcal {C}}^{*})+\frac{3}{2}p(E\setminus {{\mathcal {C}}}^{*}) \nonumber \\\le & {} \left( \frac{7}{2}-\frac{2}{k}\right) f({{\mathcal {C}}}^{*}). \end{aligned}$$

This shows that the algorithm \({{\mathcal {A}}}_{MM}\) is a \((\frac{7}{2}-\frac{2}{k})\)-approximation algorithm to solve the MM-RPCPP.

The complexity of the algorithm \({{\mathcal {A}}}_{MM}\) can be determined as follows: (1) Using the RPCPP algorithm [16], the running time of Step 1 is \(O(n^{3})\) that determines a tour C. (2) Using Dijkstra’s algorithm [13] to compute the eccentricity of depot r, the running time of Step 2 is \(O(n^{3})\). (3) Steps 4-5 need at most time \(O(n^{3})\) to convert the tour C to a feasible solution \({{\mathcal {C}}}\). Hence, the running time of the algorithm \({\mathcal {A}}_{MM}\) is \(O(n^{3})\). \(\square \)

4 The restricted min-sum k-Chinese postman problem with penalties

In this section, we consider the restricted min-sum k -Chinese postman problem with penalties (MS-RPCPP). Note that the MS-RPCPP is \(\textsf{NP}\)-hard since it is a generalization of metric TSP, where the metric TSP is known to be \(\textsf{NP}\)-hard [15, p.30].

From the description of the MS-RPCPP, we obtain a result in the following.

Lemma 5

Any optimal solution \({{\mathcal {C}}}^{*}\) to the MS-RPCPP, satisfies that all tours in \({{\mathcal {C}}}^{*}\) collectively traverse each edge at most twice.

Proof

Given any instance \(G=(V,E;w,p)\) to the MS-RPCPP, we know that each edge \(e\in E\) appears in at most one tour \(C\in {{\mathcal {C}}}^{*}\), where \({{\mathcal {C}}}^{*}\) is any optimal solution of the MS-RPCPP. Now, we only need to consider any tour \(C\in {{\mathcal {C}}}^{*}\).

Suppose the tour C traversing some edge e at least three times, we can construct a new Eulerian subgraph by simply deleting the two copy edges of the edge e on the Eulerian subgraph corresponding to C. It is clear that any Euler tour \(C_{e}\) on the new Eulerian subgraph also traverses all edges in \(E_{C}\). As a result, we can replace C with \(C_{e}\) in \({{\mathcal {C}}}^{*}\), which can reduce the weight of \({{\mathcal {C}}}^{*}\), to get a better solution. This contradicts the optimality of \({{\mathcal {C}}}^{*}\). \(\square \)

By Lemma 5, the strategy to solve the MS-RPCPP is described as follows:

  1. (1)

    Find a connected spanning subgraph which has at least k edges incident to the depot, satisfying that the weight (with respect to function \(\max \{0, w(\cdot )-p(\cdot )\}\)) of the subgraph is minimized.

  2. (2)

    Partition the above subgraph into k subgraphs, and then construct a tour for each subgraph.

According to the above strategy, we design an algorithm (Algorithm 2) in the following.

figure b

By Algorithm 2, we obtain the following result for the MS-RPCPP.

Theorem 2

The algorithm \({{\mathcal {A}}}_{MS}\) is a 2-approximation algorithm to solve the MS-RPCPP and it runs in time \(O(n^2)\).

Proof

It is clear to see that the algorithm can correctly indicate whether there is a feasible solution to the MS-RPCPP. We need only consider case that there are feasible solutions for the MS-RPCPP in the following.

For any instance \(G=(V,E;w,p)\) of the MS-RPCPP, let \({{\mathcal {C}}}^{*}\) denote an optimal solution of instance G to the MS-RPCPP, \(E_{{{\mathcal {C}}}^{*}}\subseteq E\) denote the subset of edges traversed by tours in \({{\mathcal {C}}}^{*}\).

For an optimal solution \({{\mathcal {C}}}^{*}\) to G as an instance of the MS-RPCPP, by using Lemma 5, we obtain a fact that all tours in \({{\mathcal {C}}}^{*}\) collectively traverse each edge in E at most twice, meaning that the number of edges in \(E_{{{\mathcal {C}}}^{*}}\) incident to r is at least k, and \((V, E_{1}\cup (E_{{\mathcal {C}}^{*}}{\setminus } E_{1}))\) is a spanning connected subgraph of G. For the subset \(E_{1}\), Step 2 produces a subset \(E_{S}\subseteq E_{2}\) of minimum weight with respect to \(w''\) so that \(G_{1,S}=(V, E_{1}\cup E_{S})\) is connected, and has at least k edges incident to the depot r. This implies that

$$\begin{aligned} w''(E_{S})\le w''(E_{{{\mathcal {C}}}^{*}}\setminus E_{1}). \end{aligned}$$

For the set \({{\mathcal {C}}}\) of tours produced at Step 5, since \(E_{1}, E_{S}\subseteq E_{{{\mathcal {C}}}}\) and \(E_{1}\cap E_{S}=\emptyset \), we have \(p(E{\setminus } E_{{{\mathcal {C}}}})\le p(E)-p(E_{1})-p(E_{S})= p(E_{2})-p(E_{S})\), which means

$$\begin{aligned} p(E_{S})+p(E\setminus E_{{{\mathcal {C}}}})\le p(E_{2}). \end{aligned}$$

It follows that

$$\begin{aligned} w(E_{1})+w(E_{S})+p(E\setminus {{\mathcal {C}}})= & {} w(E_{1})+w''(E_{S})+p(E_{S})+p(E\setminus E_{{{\mathcal {C}}}}) \nonumber \\\le & {} w(E_{1})+w''(E_{{{\mathcal {C}}}^{*}}\setminus E_{1})+p(E_{2}) \nonumber \\= & {} w(E_{1})+w(E_{{{\mathcal {C}}}^{*}}\setminus E_{1})-p(E_{{\mathcal {C}}^{*}}\setminus E_{1})+p(E_{2}) \nonumber \\= & {} w(E_{{{\mathcal {C}}}^{*}})+w(E_{1}\setminus E_{{\mathcal {C}}^{*}})+p(E_{2}\setminus E_{{{\mathcal {C}}}^{*}})\nonumber \\< & {} w(E_{{{\mathcal {C}}}^{*}})+p(E\setminus E_{{{\mathcal {C}}}^{*}})\le h({{\mathcal {C}}}^{*}). \end{aligned}$$

where the penultimate inequality follows from \(w(E_{1}{\setminus } E_{{{\mathcal {C}}}^{*}})< p(E_{1}{\setminus } E_{{{\mathcal {C}}}^{*}})\) because \(w(e)< p(e)\) for all \(e\in E_{1}\) (Fig. 1).

Thus, we obtain

$$\begin{aligned} h({{\mathcal {C}}})= & {} w({{\mathcal {C}}})+p(E\setminus {{\mathcal {C}}}) \nonumber \\= & {} 2(w(E_{1})+w(E_{S}))+p(E\setminus {{\mathcal {C}}}) \nonumber \\\le & {} 2h({{\mathcal {C}}}^{*}). \end{aligned}$$

This shows that the algorithm \({{\mathcal {A}}}_{MS}\) is a 2-approximation algorithm to solve the MS-RPCPP.

The complexity of the algorithm \({{\mathcal {A}}}_{MS}\) can be determined as follows: (1) Using the MST-DC algorithm [9], the running time of Steps 1-2 is \(O(n^{2})\) that computes \(E_{1}\) and \(E_{S}\). (2) Using the BFS method [13, p.28-29] to partition the graph \(G_{1,S}\) into k subgraphs \(H_{1},\ldots ,H_{k}\), the running time of Step 3 is \(O(n^{2})\). (3) Applying an algorithm in [6] to determine an Euler tour, the running time of Step 4 is O(m) due to \(\bigcup _{i=1}^{k}E(H_{i})=E_{1}\cup E_{S}\). Hence, the running time of the algorithm \({{\mathcal {A}}}_{MS}\) is \(O(n^{2})\). \(\square \)

Fig. 1
figure 1

The interpretation of \(w(E_{1})+w(E_{{\mathcal {C}}^{*}}{\setminus } E_{1})=w(E_{{{\mathcal {C}}}^{*}})+w(E_{1}{\setminus } E_{{{\mathcal {C}}}^{*}})\) and \(-p(E_{{{\mathcal {C}}}^{*}}{\setminus } E_{1})+p(E_{2})= p(E_{2}{\setminus } E_{{{\mathcal {C}}}^{*}})\)

Full size image

5 Conclusion and further work

In this paper, we consider the restricted min–max k -Chinese postman problem with penalties (MM-RPCPP) and the restricted min–sum k -Chinese postman problem with penalties (MS-RPCPP), respectively. We obtain the following two main results:

  1. (1)

    We design a \(\left( \frac{7}{2}-\frac{2}{k}\right) \)-approximation algorithm in time \(O(n^{3})\) to solve the MM-RPCPP.

  2. (2)

    We present a 2-approximation algorithm in time \(O(n^{2})\) to solve the MS-RPCPP.

In further work, we shall study other restricted routing problems with penalties. In particular, we intend to study the following problem (that we call the budgeted restricted Chinese postman problem with penalties).

Given an undirected graph \(G=(V,E;w,p)\) with a depot \(r\in V\) and a budget \(B\in {{\mathbb {R}}}^{+}\), each edge has a weight, a traverse time and a penalty, it is asked to find a set of tours starting from r and collectively covering all vertices, such that the maximum traverse time of tours is at most B. The objective is to minimize the sum of weights of all tours plus the total penalty paid for uncovered edges.