Uncertain Programming Model for Chinese Postman Problem with Uncertain Weights
- Author: Zhang Bo, Peng Jin
- Organization: Zhang Bo; Peng Jin
- Publish: Industrial Engineering and Management Systems Volume 11, Issue1, p18~25, 01 March 2012
-
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
-
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 fromL to [0, 1]. In order to ensure that the numberM {Λ} 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 functionM {Λ} 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 setB 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 distributionwhere
a ,b ,c are real numbers witha ≤b ≤c .Definition 3: (Liu, 2007) Letξ be an uncertain variable. Then the expected value ofξ is defined byprovided 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 (x 1,x 2, …,x n )is strictly increasing with respect to x 1,x 2, …,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ξ 1,ξ 2,ξ 3 are independent uncertain variables with uncertainty distributions Φ1, Φ2, Φ3, respectively. Since the functionf (x1, x2, x3) = (x1 + x2) / x3
is strictly increasing with respect to
x 1,x 2 and strictly decreasing with respect tox 3 , the inverse uncertainty distribution ofx 1 +x 2) /x 3 isFurthermore, assume the function
f ?x 1,x 2, …,x n ? is strictly increasing with respect tox 1,x 2, …,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 1,x 2, …,x n ) has an expected valueWe 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 numbersa andb , we haveIn general, a deterministic network is denoted as
N = (V ,A ) , whereV = {v 1,v 2, …,v n } is a finite set of vertices, andA = {(vi ,vj ) |vi ,vj ∈V } is the set of edges. Letw = {wij | (vi ,vj ) ∈A } is the set of edge weights. Then a deterministic weighted network can be denoted asN = (V ,A ,w ). A route ofN is a cycle that traverses each edge ofN at least once. The Chinese postman problem is just to find a shortest route.Obviously, each
wij is positive crisp value inN = (V ,A ), and the shortest route weight is a function ofw , which is denoted asf (w ) in this paper. For a networkN = (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 networkN = (V, A, w ) is shown in Figure 1, andw = {e 12 = 2,e 16 = 3,e 23 = 3,e 25 = 2,e 26 = 2,e 34 = 3,e 35 = 2,e 45 = 2,e 56 = 4}. Then the shortest route isv 1 →v 2 →v 6 →v 2 →v 3 →v 2 →v 5 →v 3 →v 4 →v 5 →v 6 →v 1 . That isf (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 asN = (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 ofN incident with the vertex), then there exists a cycle that traverses each edge exactly once. The cycle is just the shortest route. If networkN 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 fromvi tovj in routexij = 1; otherwise,xij = 0. The first constraint requires that the route is cycle, and the second constraint requires that the route traverses each edge ofN 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: LetN = (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: LetN = (V, A, ξ ) be an uncertain network,a route. Then
is called
α -shortest route (α -SR) ifFor 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 weightW and a routeR* , where uncertain variablew is less than
W with confidence levelα .Definition 6: LetN = (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 routeR* is the shortest route which is larger thanW 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 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 ), whereand 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: CalculateE [ξij ], for each weightξ ij inN = (V, A, ξ ) ;Step 2: Construct a deterministic networkN = (V, A, w ), whose edge weightswij =E [ξ ij ] ;Step 3: Employ Fleury algorithm and Dijkstra algorithm to get the shortest route in uncertain networkN = (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 routeis 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 networkN = (V, A, ξ ) . The method can be summarized as follows:Step 1: Calculatefor each weight
ξij inN =N = (V, A, ξ );Step 2: Construct a deterministic networkN = (V, A, w ), whose edge weightsStep 3: Employ Fleury algorithm and Dijkstra algorithm to get the shortest route in uncertain networkN = (V ,A ,w ).The shortest route we get in Step 3 is just the
α - shortest route inN = (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 : CalculateE [ξ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 networkN in Figure 2, the shortest routeR* isv 1 →v 2 →v 6 →v 2 →v 3 →v 2 →v 5 →v 3 →v 4 →v 5 →v 6 →v 1, andf (w ) = 26.5.According to Theorem 3, the expected shortest route
in uncertain network
N = (V, A, ξ ) isv 1 →v 2 →v 6 →v 2 →v 3 →v 2 →v 5 →v 3 →v 4 →v 5 →v 6 →v 1, andf (ξ ) = 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 networkN in Figure 3, the shortest routeR* isv 1 →v 2 →v 6 →v 2 →v 3 →v 2 →v 5 →v 3 →v 4 →v 5 →v 6 →v 1, andf (w ) = 36.5.According to Theorem 4, the
α -shortest routein uncertain network
N = (V, A, ξ ) isv 1 →v 2 →v 6 →v 2 →v 3 →v 2 →v 5 →v 3 →v 4 →v 5 →v 6 →v 1, andf (ξ ) = 36.5.Choosing different
α , we obtain Table 5.Repeating this process, we can obtain the uncertainty distribution Ψ (
x ) off (ξ ) 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:v 1 →v 2 →v 6 →v 2 →v 3 →v 2 →v 5 →v 3 →v 4 →v 5 →v 6 →v 1,f (ξ ) = (8, 19, 30), and its uncertainty distribution isIn 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 0 inG , and setT 0 =v 0 .Step 2: Suppose that a trail
T i =v 0e 1v 1 …e 1v 1 has been chosen. Then choose an edgee i +1 ∈A bute i +1 ? {e1, e2,…, ei} in such a way that(i)
ψ G = (v i +1,vi );(ii) unless there is no alternative,
e i +1 is not a cut edge ofGi =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 withn vertices. Throughout the algorithm, each vertexv carries a labell (v ) which is an upper bound onξ (x 0,v )Step 1: Set
l (x 0) = 0,l (v ) =∞ (v ≠x 0),V 0 = {x 0} andi = 0 .Step 2: For any
v ∈V ?Vi , replacel (v ) by min {l (v ),l (xi ) +ξ (x i,v )}. Computel (xi ) +ξ (x i,v )} and letxi+1 denote a vertex for which this minimum is attained, and chalked upxi denotedl (v ) of the vertexv come fromxi . SetSi+1 =Si ? {xi+1 } .Step 3: If
i =n ?1, stop. Ifi <n ?1 , replacei byi +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(ξ).