### Uncertain Programming Model for Chinese Postman Problem with Uncertain Weights

• • #### ABSTRACT

IChinese postman problem is one of the classical combinatorial optimization problems with many applications. However, in application, some uncertain factors are frequently encountered. This paper employs uncertain programming to deal with Chinese postman problem with uncertain weight Within the framework of uncertainty theory, the concepts of expected shortest route, α -shortest route, and distribution shortest route are proposed. After that, expected shortest model, and α -shortest model are constructed. Taking advantage of properties of uncertainty theory, these models can be transf-ormed into their corresponding deterministic forms, which can be solved by classical algorithm..

• #### KEYWORD

Chinese Postman Problem , Uncertainty Theory , Uncertain Programming

• ### 1. INTRODUCTION

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.

### 2. PRELIMINARIES

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 abc .

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 ξ1, ξ2, …,ξn be independent uncertain variables with uncertainty distributions Φ1, Φ2, …,Φn respectively. If the function f (x1, x2, …,xn) is strictly increasing with respect to x1, x2, …,xm and strictly decreasing with respect to xm+1, xm+2, …,xn, then

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

is an uncertain variable with inverse uncertainty distribution

Example 2: Let ξ1, ξ2, ξ3 are independent uncertain variables with uncertainty distributions Φ1, Φ2, Φ3, respectively. Since the function

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

is strictly increasing with respect to x1, x2 and strictly decreasing with respect to x3 , the inverse uncertainty distribution of x1 + x2) / x3 is

Furthermore, assume the function fx1, x2, …,xn？ is strictly increasing with respect to x1, x2, …,xm and strictly decreasing with respect to (xm+1, xm+2, …,xn . It has been proved by Liu and Ha (2010) that the uncertain variable ξ = f (x1, x2, …,xn) 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

### 3. PROBLEM DESCRIPTION

In general, a deterministic network is denoted as N = (V, A) , where V = {v1, v2, …,vn} is a finite set of vertices, and A = {(vi, vj) | vi, vjV} is the set of edges. Let w = {wij | (vi, vj) ∈ 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 wij 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 = {e12 = 2, e16 = 3, e23 = 3, e25 = 2, e26 = 2, e34 = 3, e35 = 2, e45 = 2, e56 = 4}. Then the shortest route is v1v2v6v2v3v2v5v3v4v5v6v1 . 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 wij is replaced by a nonnegative uncertain variable ξij . We can denoted the network with uncertain weight as N = (V, A, ξ), where ξ = {ξ ij | (vi, vj) ∈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 vi to vj in route

xij = 1; otherwise, xij = 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.

### 4. MODELS FOR UCPP

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 wij = 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 wij = 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 wij = 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, ξ ).

### 5. NUMERICAL EXPERIMENT

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. ### 5.1 Expected shortest route

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 v1v2v6v2v3v2v5v3v4v5v6v1, and f (w) = 26.5.

According to Theorem 3, the expected shortest route

in uncertain network N = (V, A, ξ ) is v1v2v6v2v3v2v5v3v4v5v6v1, and f (ξ ) = 26.5. ### 5.2 α -shortest route

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 v1v2v6v2v3v2v5v3v4v5v6v1, and f (w) = 36.5.

According to Theorem 4, the α -shortest route

in uncertain network N = (V, A, ξ ) is v1v2v6v2v3v2v5v3v4v5v6v1, 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 ξ12= (1, 2, 3), ξ16= (0, 1, 2), ξ23= (1, 2, 3), ξ25= (1, 2, 3), ξ26= (0, 1, 2), ξ34= (1, 2, 3), ξ35= (1, 2, 3), ξ45= (0, 1, 2), ξ56= (2, 3, 4). According to Dijkstra algorithm, and Fleury algorithm, we obtain distribution shortest route is: v1v2v6v2v3v2v5v3v4v5v6v1, f (ξ) = (8, 19, 30), and its uncertainty distribution is ### 6. CONCLUSION

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.

### >  APPENDIX

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 v0 in G , and set T0 = v0 .

Step 2: Suppose that a trail Ti = v0e1v1e1v1 has been chosen. Then choose an edge ei+1A but ei+1 ？ {e1, e2,…, ei} in such a way that

(i) ψG = (vi+1, vi);

(ii) unless there is no alternative, ei+1 is not a cut edge of Gi = G-{e1, e2,…, ei}.

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 ξ(x0, v)

Step 1: Set l(x0) = 0, l(v) = (vx0), V0 = { x0} and i = 0 .

Step 2: For any vV?Vi, replace l (v) by min {l(v), l(xi) + ξ(xi, v)}. Compute

l(xi) + ξ(xi, v)} and let xi+1 denote a vertex for which this minimum is attained, and chalked up xi denoted l(v) of the vertex v come from xi. Set Si+1 = Si ？ {xi+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|2).

• [Figure 1.] Network. • [Table 1.] List of notations and assumptions. • [Table 2.] List of ξij. • [Table 3.] List of E [ξij]. • [Figure 2.] Network N. • [Table 4.] List of Φij-1(0.9). • [Figure 3.] Network N. • [Table 5.] List of α -shortest route. • [Figure 4.] Uncertainty distribution of f(ξ). 