Uncertain Programming Model for Chinese Postman Problem with Uncertain Weights

  • cc icon
  • 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

    image

    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

    image

    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

    image

    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

    image

    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

    image

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

    image

    Also,

    image

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

    image

    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,

    image

    is a route if and only if

    image

    Remark 1: If there exists a edge from vi to vj in route

    image

    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,

    image

    a route. Then

    image

    is called expected shortest route (ESR) if

    image

    Holds for route

    image

    where

    image

    stands for the total weight of expected shortest route

    image

    and

    image

    stands for the total weight of route

    image

    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,

    image

    a route. Then

    image

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

    image

    For route

    image

    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

    image

    is less than W with confidence level α.

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

    image

    a route. Then

    image

    is called distribution shortest route (DSR) if

    image

    For route

    image

    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

    image

    where

    image

    and wij = E [ξij].

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

    image

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

    image

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

    image

    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

    image

    where

    image

    and

    image

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

    image

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

    image

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

    image

    Clearly, model (4) is equivalent to

    image

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

    image

    where

    image

    and

    image

    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

    image

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

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

    image

    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

    image

    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

    image

    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

    image

    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

    image

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

  • 1. Bhattacharyya R., Chatterjee A., Kar S. (2010) Uncertainty theory based novel multi-objective optimization technique using embedding theorem with application to R&D project portfolio selection [Applied Mathematics] Vol.1 P.189-199 google doi
  • 2. Chen X., Liu B. (2010) Existence and uniqueness theorem for uncertain differential equations [Fuzzy Optimization and Decision Making] Vol.9 P.69-81 google doi
  • 3. Edmonds J., Johnson E. L. (1973) Matching, Euler tours and the Chinese postman [Mathematical Programming] Vol.5 P.88-124 google doi
  • 4. Gao X., Gao Y., Ralescu D. A. (2010) On Liu’ s inference rule for uncertain systems, International Journal of Uncertainty [Fuzziness and Knowledge-Based Systems] Vol.18 P.1-11 google doi
  • 5. Gao Y. (2011) Shortest path problem with uncertain arc lengths [Computers and Mathematics with Applications] Vol.62 P.2591-2600 google doi
  • 6. Huang X. X. (2011) Mean-risk model for uncertain portfolio selection [Fuzzy Optimization and Decision Making] Vol.10 P.71-89 google doi
  • 7. Kuan M. K. (1962) Graphic programming using odd or even points [Chinese Mathematics] Vol.1 P.273-277 google
  • 8. Lin Y. X., Zhao Y. C. (1988) A new algorithm for the directed Chinese postman problem [Computers and Operations Research] Vol.15 P.577-584 google doi
  • 9. Liu B. (2007) Uncertainty Theory google
  • 10. Liu B. (2008) Fuzzy process, hybrid process and uncertain process [Journal of Uncertain Systems] Vol.2 P.3-16 google
  • 11. Liu B. (2009a) Some research problems in uncertainty theory [Journal of Uncertain Systems] Vol.3 P.3-10 google
  • 12. Liu B. (2009b) Theory and Practice of Uncertain Programming google
  • 13. Liu B. (2010a) Uncertain set theory and uncertain inference rule with application to uncertain control [Journal of Uncertain Systems] Vol.4 P.83-98 google
  • 14. Liu B. (2010b) Uncertain risk analysis and uncertain reliability analysis [Journal of Uncertain Systems] Vol.4 P.163-170 google
  • 15. Liu B. (2010c) Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty google
  • 16. Liu B. (2012) Why is there a need for uncertainty theory? [Journal of Uncertain Systems] Vol.6 P.3-10 google
  • 17. Liu Y. H., Ha M. H. (2010) Expected value of function of uncertain variables [Journal of Uncertain Systems] Vol.4 P.181-186 google
  • 18. Minieka E. (1979) The Chinese postman problem for mixed networks [Management Science] Vol.25 P.643-648 google doi
  • 19. Nobert Y., Picard J. C. (1996) An optimal algorithm for the mixed Chinese postman problem [Networks] Vol.27 P.95-108 google
  • 20. Pearn W. L., Chou J. B. (1999) Improved solutions for the Chinese postman problem on mixed networks [Computers and Operations Research] Vol.26 P.819-827 google doi
  • 21. Peng J., Yao K. (2011) A new option pricing model for stocks in uncertainty markets [International Journal of Operations Research] Vol.8 P.18-26 google
  • 22. Rong L. X. (2011) Two new uncertainty programming models of inventory with uncertain costs [Journal of Information and Computational Science] Vol.8 P.280-288 google
  • 23. Zhu Y. (2010) Uncertain optimal control with application to a portfolio selection model [Cybernetics and Systems] Vol.41 P.535-547 google doi
  • [Figure 1.] Network.
    Network.
  • [Table 1.] List of notations and assumptions.
    List of notations and assumptions.
  • [Table 2.] List of ξij.
    List of ξij.
  • [Table 3.] List of E [ξij].
    List of E [ξij].
  • [Figure 2.] Network N.
    Network N.
  • [Table 4.] List of Φij-1(0.9).
    List of Φij-1(0.9).
  • [Figure 3.] Network N.
    Network N.
  • [Table 5.] List of α -shortest route.
    List of α -shortest route.
  • [Figure 4.] Uncertainty distribution of f(ξ).
    Uncertainty distribution of f(ξ).