As it is known, the motivation for the Chinese postman problem (CPP) came from the job of a postman. Starting the post office, the postman must cover each street in his area at least once, and then end up at the same place where he began his route. Subject to this condition, the postman wishes to seek the shortest way to complete his assigned route of streets. This problem is known as the CPP, since it was first considered by a Chinese mathematician, Kuan (1962).

The CPP is one of the classical problems of network optimization. There are many real-world situations that can be reduced as CPP. For example, a driver of a watering car or a garbage truck, he wishes to choose his route in such a way that traverses as little as possible. It is important to study this problem both from theoretical and practical points of view. The deterministic CPP has been well studied and many efficient algorithms have been developed by many researchers, such as Edmonds and Johnson (1973), Minieka (1979), Lin and Zhao (1988), Nobert and Picard (1996), Pearn and Chou (1999), etc.

However, because of failure, the lack of history data, or other reasons, some uncertain factors will appear in many situations. For example, because of the weather, traffic, the time costed for the postman on the road is uncertain. As a result, it is not suitable to employ classical approaches in these situations.

Fortunately, in order to deal with human data, such as empirical estimation, uncertainty theory was proposed by Liu (2007). From then on, uncertainty theory has provided a new approach to deal with uncertain factors in programming problems. Liu (2012) said that “when the sample size is too small (even no-sample) to estimate a probability distribution, we have to invite some domain experts to evaluate their belief degree that each event will occur. Since human beings usually overweight unlikely events, the belief degree may have much larger variance than the real frequency and then probability theory is no longer valid. In this situation, we should deal with it by uncertainty theory.

In this paper, the weight data can only be obtained from expert’s empirical estimation. We regard weight as uncertain variable. Obviously, we cannot get a shortest route in the normal sense. We introduce the concepts of expected shortest route, α -shortest route, and distribution shortest route for uncertain Chinese postman problem (UCPP). After that, the expected shortest model, and α -shortest model for UCPP are constructed.

Within the framework of uncertainty theory, these models can be transformed into their corresponding deterministic forms. The transformed models can be solved based on Fleury algorithm and Dijkstra algorithm.

The remainder of this paper is organized as follows. Section 2 presents some basic concepts and properties selected from uncertainty theory. In Section 3, the uncertain Chinese postman problem is described. In Section 4, expected shortest model and α -shortest model are proposed, and derives the method to find their solutions. Section 5 gives an example to illustrate the proposed method. The last section concludes this paper with a brief summary.

In order to describe uncertain phenomena, especially expert data and subjective estimation, Liu (2007) proposed uncertainty theory in 2007. From then on, uncertainty theory has received great attention. For instance, Liu (2008) proposed uncertain processes which is a sequence of uncertain variables indexed by time or space. Later, in order to deal with differentiation and integration of functions of uncertain processes, uncertain calculus was initialized by Liu (2009a). Based on uncertain calculus, Liu (2008) introduced uncertain differential equation. After that, Chen and Liu (2010) proved the existence and uniqueness theorem for uncertain differential equations. Furthermore, uncertainty theory was also applied to uncertain inference (Liu, 2010a; Gao et al., 2010), uncertain risk analysis and uncertain reliability analysis (Liu, 2010b), uncertain statistics (Liu, 2010c), uncertain control (Liu, 2010a; Zhu, 2010), and uncertain finance (Liu, 2009a; Peng and Yao, 2011).

As a type of mathematical programming involving uncertain variables, uncertain programming was founded by Liu (2009b). Also, the models of uncertain programming on system reliability design, machine scheduling problem, facility location problem, project scheduling problem, vehicle routing problem and so on, were given by Liu (2009b), respectively. After that, Bhattacharyya et al. (2010) introduced a novice solution methodology for multi-objective optimization problems having the coefficients in the form of uncertain variables. Huang (2011) introduced a risk curve and developed a meanrisk model for uncertain portfolio selection. Furthermore, Rong (2011) proposed two models of economic order quantity for inventory based on uncertainty theory. At nearly the same time, Gao (2011) investigated the shortest problem with uncertain arc lengths.

In this section, we introduce some foundational concepts and properties of uncertainty theory, which will be used throughout this paper.

Let Γ be a nonempty set, L is a σ -algebra over Γ. Each element Λ∈L is called an event. M{Λ} is a function from L to [0, 1]. In order to ensure that the number M{Λ} has certain mathematical properties, Liu (2007, 2010c) presented the following four axioms: normality, duality, subadditivity, and product axioms. If the first three axioms are satisfied, the function M{Λ} is called an uncertain measure. The triplet？ Γ, L, M？ is called an uncertainty space.

Definition 1: (Liu, 2007) An uncertain variable is a measurable function ξ from an uncertainty space ？Γ, L, M？ to the set of real numbers, i.e., for any Borel set B of real numbers, the set

{ξ ∈B} = {γ ∈Γ | ξ (γ) ∈B}

is an event.

Definition 2: (Liu, 2007) An uncertain variable ξ can be characterized by its uncertainty distribution Φ : ？ →[0, 1] , which is defined as follows

Φ(x) = M {γ ∈Γ | ξ (γ) < x}.

Then the inverse function Φ^?1 is called the inverse uncertainty distribution of c.

Example 1: The zigzag uncertain variable ξ = Z(a, b, c) has an uncertainty distribution

where a, b, c are real numbers with a ≤ b ≤ c .

Definition 3: (Liu, 2007) Let ξ be an uncertain variable. Then the expected value of ξ is defined by

provided that at least one of the two integrals is finite.

Theorem 1: (Liu, 2010c) Let ξ₁, ξ₂, …,ξ_n be independent uncertain variables with uncertainty distributions Φ₁, Φ₂, …,Φ_n respectively. If the function f (x₁, x₂, …,x_n) is strictly increasing with respect to x₁, x₂, …,x_m and strictly decreasing with respect to x_m+1, x_m+2, …,x_n, then

ξ = f (x1, x2, …,xn)

is an uncertain variable with inverse uncertainty distribution

Example 2: Let ξ₁, ξ₂, ξ₃ are independent uncertain variables with uncertainty distributions Φ₁, Φ₂, Φ₃, respectively. Since the function

f (x1, x2, x3) = (x1 + x2) / x3

is strictly increasing with respect to x₁, x₂ and strictly decreasing with respect to x₃ , the inverse uncertainty distribution of x₁ + x₂) / x₃ is

Furthermore, assume the function f ？ x₁, x₂, …,x_n？ is strictly increasing with respect to x₁, x₂, …,x_m and strictly decreasing with respect to (x_m+1, x_m+2, …,x_n . It has been proved by Liu and Ha (2010) that the uncertain variable ξ = f (x₁, x₂, …,x_n) has an expected value

We can calculated that the inverse distribution of the zigzag uncertain variable ξ ∼ Z (a, b, c)

Also,

Theorem 2: (Liu, 2010c) Let ξ and η be independent uncertain variables with finite expected values. Then for any real numbers a and b, we have

In general, a deterministic network is denoted as N = (V, A) , where V = {v₁, v₂, …,v_n} is a finite set of vertices, and A = {(v_i, v_j) | v_i, v_j ∈V} is the set of edges. Let w = {w_ij | (v_i, v_j) ∈ A} is the set of edge weights. Then a deterministic weighted network can be denoted as N = (V, A, w). A route of N is a cycle that traverses each edge of N at least once. The Chinese postman problem is just to find a shortest route.

Obviously, each w_ij is positive crisp value in N = (V, A), and the shortest route weight is a function of w, which is denoted as f (w) in this paper. For a network N = (V, A, w), f (w) can be obtained by any classical algorithm. In this paper, we employ the algorithm based on Fleury algorithm and Dijkstra algorithm.

The following example illustrates how to obtain f (w) by Fleury algorithm and Dijkstra algorithm.

Example 3: The network N = (V, A, w) is shown in Figure 1, and w = {e₁₂ = 2, e₁₆ = 3, e₂₃ = 3, e₂₅ = 2, e₂₆ = 2, e₃₄ = 3, e₃₅ = 2, e₄₅ = 2, e₅₆ = 4}. Then the shortest route is v₁ → v₂ → v₆ → v₂ → v₃ → v₂ → v₅ → v₃ → v₄ → v₅ → v₆ → v₁ . That is f (w) = 2 + 2 × 2 + 2× 3 + 2 + 2 + 3 + 2 + 4 + 3 = 28 .

However, in practical, because of the lack of history data, some uncertain factors will appear. In this situation, the weight data can only be obtained from the postman’s empirical estimation. Then how can we deal with this kind of uncertain factor? Fortunately, uncertainty theory provides a new tool to deal with uncertain information, especially subjective estimation.

In this paper, the weights of edges in uncertain network are not precisely known and they are specified as uncertain variables. That is, each weight w_ij is replaced by a nonnegative uncertain variable ξ_ij . We can denoted the network with uncertain weight as N = (V, A, ξ), where ξ = {ξ _ij | (v_i, v_j) ∈A }. Uncertainty theory is applied to characterized a route under uncertain weight. Before starting model construction, some notations and assumptions are listed in Table 1.

By the knowledge of graph theory, if network N has no vertices of odd degree (i.e., the number of edges of N incident with the vertex), then there exists a cycle that traverses each edge exactly once. The cycle is just the shortest route. If network N has vertices of odd degree, then any cycle that traverses each edge at least once, must traverses some edges more than once. And we can assume that traverses each edge at most twice.

Thus,

is a route if and only if

Remark 1: If there exists a edge from v_i to v_j in route

x_ij = 1; otherwise, x_ij = 0. The first constraint requires that the route is cycle, and the second constraint requires that the route traverses each edge of N at least once.

Clearly, the shortest route weight in uncertain networkis an uncertain variable. Then, for uncertain network N = (V, A, ξ ), a key problem is how to obtain the shortest optimal route.

Expected value is the average value of uncertain variable in the sense of uncertain measure, and represents the size of uncertain variable. Now, we give the concept of expected shortest route for uncertain Chinese postman problem.

Definition 4: Let N = (V, A, ξ ) be an uncertain network,

a route. Then

is called expected shortest route (ESR) if

Holds for route

where

stands for the total weight of expected shortest route

and

stands for the total weight of route

Furthermore, we give the concepts of α -shortest route and distribution shortest route, which are the shortest route under some confidence level.

Definition 5: Let N = (V, A, ξ ) be an uncertain network,

a route. Then

is called α -shortest route (α -SR) if

For route

and α is a predetermined confidence level. The meaning of α -shortest route can be summarized as follows. Given an α ∈(0, 1), we hope to get a smallest weight W and a route R^*, where uncertain variable w

is less than W with confidence level α.

Definition 6: Let N = (V, A, ξ ) be an uncertain network,

a route. Then

is called distribution shortest route (DSR) if

For route

and for any W ∈ ?.

For any weight W, distribution shortest route R^* is the shortest route which is larger than W with the largest confidence level.

Then, a key problem is how to get expected shortest route, α -shortest route, and distribution shortest route. In the following sections, we will give the answers.

In this section, we will construct expected shortest model and α -shortest model based on the concepts of expected shortest route and α -shortest route proposed in above section. Taking advantage of some properties of uncertainty theory, these models can be transformed into their corresponding deterministic forms.

Theorem 3: Let N = (V, A, ξ) be an uncertain network, Then the expected shortest route is just the shortest route of

where

and w_ij = E [ξ_ij].

Proof: According to Definition 4, the expected shortest model can be presented as follows:

Note that, ξ_ij, i, j = 1, 2,…, n, are independent, according to Theorem 2, the model (1) is equivalently to the following deterministic model:

In fact, the model (2) describes the shortest route in network N = (V, A, w), where

and w_ij = E [ξ _ij]. The theorem is proved.

Theorem 3 provided a effective method to obtain expected shortest route in uncertain network N = (V, A, ξ ) . T-he method can be summarized as follows:

Step 1: Calculate E[ξ_ij], for each weight ξ_ij in N = (V, A, ξ ) ;

Step 2: Construct a deterministic network N = (V, A, w), whose edge weights w_ij = E [ξ _ij] ;

Step 3: Employ Fleury algorithm and Dijkstra algorithm to get the shortest route in uncertain network N = (V, A, ξ).

The shortest route we get in Step 3 is just the expected shortest route in N = (V, A, ξ).

Theorem 4: Let N = (V, A, ξ) be an uncertain network, ξ_ij have regular uncertainty distributions Φ_ij, i, j = 1, 2, …, n, respectively. Then the α -shortest route is just the shortest route of

where

and

Proof: According to Definition 5, the α -shortest route

is the optimal solution to the following α -shortest model:

Since ξ_ij have regular uncertainty distributions Φ_ij, i, j =1, 2,…,n, respectively, model (3) can be equivalently transformed to the following deterministic model:

Clearly, model (4) is equivalent to

Clearly, model (5) describes the shortest route in network

where

and

Hence the theorem is proved.

Theorem 4 provided a effective method to obtain α -shortest route in uncertain network N = (V, A, ξ ) . The method can be summarized as follows:

Step 1: Calculate

for each weight ξ_ij in N = N = (V, A, ξ );

Step 2: Construct a deterministic network N = (V, A, w), whose edge weights

Step 3: Employ Fleury algorithm and Dijkstra algorithm to get the shortest route in uncertain network N = (V, A, w).

The shortest route we get in Step 3 is just the α - shortest route in N = (V, A, ξ ).

In this section, we give an example to illustrate the methods as mentioned above. We summarize the problem as follows. Suppose that the postman must cover nine streets. Now, the task for the postman is to make the route plan such that the total weight (may be time or expense) on the route is minimized. At the beginning of the task, the postman needs to obtain the basic data, such as traffic condition. In fact, since the plan is made in advance, we usually cannot obtain these data exactly. U-sually, we obtain these uncertain data by means of expert's empirical estimation. Assume that the uncertain network N = (V, A, ξ) is shown in Figure 1, and all uncertain variables ξ_ij are zigzag uncertain variables listed in Table 2.

Step 1: Calculate E [ξ_ij] of ξ_ij listed in Table 3.

Step 2: From the data in Table 3, we construct a deterministic weighted network is shown in Figure 2.

Step 3: Employ Fleury algorithm and Dijkstra algorithm to the network N in Figure 2, the shortest route R^* is v₁ → v₂ → v₆ → v₂ → v₃ → v₂ → v₅ → v₃ → v₄ → v₅ → v₆ → v₁, and f (w) = 26.5.

According to Theorem 3, the expected shortest route

in uncertain network N = (V, A, ξ ) is v₁ → v₂ → v₆ → v₂ → v₃ → v₂ → v₅ → v₃ → v₄ → v₅ → v₆ → v₁, and f (ξ ) = 26.5.

Step 1: Calculate Φ_ij^?1(0.9) of ξ_ij listed in Table 4.

Step 2: From the data in Table 4, we construct a deterministic weighted network is shown in Figure 3.

Step 3: Employ Fleury algorithm and Dijkstra algorithm to the network N in Figure 3, the shortest route R^* is v₁ → v₂ → v₆ → v₂ → v₃ → v₂ → v₅ → v₃ → v₄ → v₅ → v₆ → v₁, and f (w) = 36.5.

According to Theorem 4, the α -shortest route

in uncertain network N = (V, A, ξ ) is v₁ → v₂ → v₆ → v₂ → v₃ → v₂ → v₅ → v₃ → v₄ → v₅ → v₆ → v₁, and f (ξ ) = 36.5.

Choosing different α , we obtain Table 5.

Repeating this process, we can obtain the uncertainty distribution Ψ (x) of f (ξ) in a numerical sense, which is drawn by MATLAB in Figure 4.

Specially, if the uncertain network N = (V, A, ξ) is shown in Figure 1, and ξ₁₂= (1, 2, 3), ξ₁₆= (0, 1, 2), ξ₂₃= (1, 2, 3), ξ₂₅= (1, 2, 3), ξ₂₆= (0, 1, 2), ξ₃₄= (1, 2, 3), ξ₃₅= (1, 2, 3), ξ₄₅= (0, 1, 2), ξ₅₆= (2, 3, 4). According to Dijkstra algorithm, and Fleury algorithm, we obtain distribution shortest route is: v₁ → v₂ → v₆ → v₂ → v₃ → v₂ → v₅ → v₃ → v₄ → v₅ → v₆ → v₁, f (ξ) = (8, 19, 30), and its uncertainty distribution is

In this paper, the concepts of expected shortest route, α -shortest route, and distribution shortest route for uncertain Chinese postman problem are proposed. What’s more, expected shortest model and α -shortest model are constructed. And these models can be transformed to their deterministic form, then we can use Dijkstra’s algorithm and Fleury’s algorithm to find their solutions. At last, an example is given to illustrate the methods.

Given an weighted graph G = (V, A), the Fleury algorithm and Dijkstra algorithm can be summarized as follows.

Fleury Algorithm

Step 1: Choose a vertex v₀ in G , and set T₀ = v₀ .

Step 2: Suppose that a trail T_i = v₀e₁v₁ …e₁v₁ has been chosen. Then choose an edge e_i+1 ∈ A but e_i+1 ？ {e₁, e₂,…, e_i} in such a way that

(i) ψ_G = (v_i+1, v_i);

(ii) unless there is no alternative, e_i+1 is not a cut edge of G_i = G-{e₁, e₂,…, e_i}.

Step 3: Stop when Step 2 can no longer be implemented.

Fleury algorithm is an efficient algorithm with the complexity O(|A|).

Dijkstra Algorithm

Let G be a graph with n vertices. Throughout the algorithm, each vertex v carries a label l (v) which is an upper bound on ξ(x₀, v)

Step 1: Set l(x₀) = 0, l(v) = ∞ (v≠ x₀), V₀ = { x₀} and i = 0 .

Step 2: For any v∈ V?V_i, replace l (v) by min {l(v), l(x_i) + ξ(x_i, v)}. Compute

l(x_i) + ξ(x_i, v)} and let x_i+1 denote a vertex for which this minimum is attained, and chalked up x_i denoted l(v) of the vertex v come from x_i. Set S_i+1 = S_i ？ {x_i+1} .

Step 3: If i = n?1, stop. If i < n ?1 , replace i by i+1 and go to Step 2.

Dijkstra algorithm is an efficient algorithm with the complexity O(|V|²).