| Transportation is involved in daily life, and is an important research branch of operation research. With the development of the society, the transportation system is getting more and more complex, the current way to solve transportation problem can't improve performance of the transportation system. So, by system science, we start from the highest grade, and then take on more and more practical jobs. Out of this consideration, current transportation system is optimized in such three grades as transportation network design, road orientation and real-time control of traffic light. This dissertation constitutes four chapters:Chapter 1 is introduction. City transportation system is very complex, but in the point of its main body, it can be reduced to the following three grades, that is, road network design, management and utilization of road, and distribution and management of traffic flow.Deficiencies in transportation ability have encumbered badly the normal motion of passengers and all kinds of goods in natural space. To settle this bottleneck, investment must be increased for the construction of basic establishment, but fund is not enough not only in developing countries, but also in developed countries. Transportation network design problem is defined as: under the restriction of limited fund, how can the network be optimum in certain objective by improving some current roads or constructing new roads?Management and utilization of road aims to manage the capacity of current roads, which is realized by assigning orientation to driveway. Different orientation way brings different capacity. An orientation is reasonable if after orientating the driveway, the arc number in the two opposite direction of any cutest is not more than 1.The best way to lead traffic flow out of an intersection is appointing a sophisticated traffic policeman at the intersection. Many scholars have put forwardsome scheme to settle this problem. At first, mathematical model is adopted, for example, continuous traffic flow model in [17]. However complex and fine the model is, it can't still simulate the real situation, especially in current complex transportation system with much randomicity. Thus, a model with determinability can hardly descript the traffic situation in the roads, and then can't lead traffic flow effectively. After Zadeh[18,19] constructed a. whole new fuzzy set theory, a powerful tool has been applied to traffic control.Network design problem(NDP) is discussed in chapter 2. In section 1, the theory, current situation and description of NDP are introduced firstly. Morlok brought forward NDP for the first time in 1973[26,27].NDP is to improve the network system by adding new roads or improving existing roads. The former is called continuous NDP, while the latter is named as discrete NDP. The objective of both of them is to minimize the cost and fund.In section 2, two algorithms for finding cutsets that will be used in this dissertation are introduced in brief. One is Liner-Time-per-Cutset algorithm[31], which is used to find all the cutsets; the other is Cactus algorithm[32], which can find all the minimum cutsets in polynomial time.In section 3, we define single domination problem of bipartite and weighted bipartite, and prove that they are NP-hard, then one heuristic algorithm for the latter is put forward.In section 4, two heuristic algorithms for NDP are given that corresponds to two algorithms in section 2. Current popular method for NDP adopts bi-level programming. This kind of method mixes all the variables into a mathematical programming, which makes the process not clear. In this dissertation, the method to solve NDP is reduced into two steps.In section 5, the two heuristic algorithms in section 4 are analyzed and a numerical example is given. Algorithms I has no loop. The process to find cutset occupies most of the time. This algorithm can't be applied to complex network. Algorithm II need many loops, and is independent with certain problem. Also,Theorem 2.2 Algorithm II ends in limited steps.In chapter 3, reasonable orientation problem is focused. In section 1, current transportation system is appraised, thereout, we point out the necessity of orientation, and put forward reasonable orientation that is based on balance:Definition 3.1.2 An orientation of a road network is called reasonable if this orientation makes the driveway number difference between two opposite directions of any effective section not more than 1.In section 2, we transform the practical problem into mathematical model, give mathematical formation of definition 3.1.2 after analyzing, and then put forward much property of reasonable orientation. And we have,Definition 3.2.2 Suppose D(G) is orientation of G, then D(G) is called reasonable if \f[S,S] - f[S,S]\ < 1 for any cutset [S,S ] of D(G).Property 3.2.5 If G{VJ<) has reasonable orientation, then it has such reasonable orientation that the difference of arc number between any vertex pair is not more than 1.Theorem 3.2.9 If G has orientation relative to edges of//such that for any cutset [ S, S ] of G and edges of H, the difference of arc number between two oppositedirection relative to S is not more than 1, then G has reasonable orientation.Lemma 3.2.10[36] For a digraph, if the difference between out-degree and in-degree of each vertex is 0, then it can be reduced to the union of arc-disjoint directed cycles.Theorem 3.2.13 If a road network has reasonable orientation, so does its corresponding simple logistic graph.Theorem 3.2.15 A road network has reasonable orientation if and only if its connected simplified graph has.Theorem 3.2.17 Given connected simplified graph G, we subdivide any one multiple edge for all the adjacent vertex pairs one by one, and obtain a simple graph G', then G has reasonable orientation iff G' has.In section 3, reasonable orientation problem of edge set relative to a graph is studied. We make research on reasonable orientation in wide range, and provide the necessary condition for a graph having reasonable orientation.Theorem 3.3.4 If there exists reasonable orientation of edge set M relative to G(V, E), then in graph G'(V, M u ￡'), the vertex number of any E' -path betweentwo vertices a,fi must be even, which are ends of any edge in E'.Corollary 33.6 For a reasonable orientation of G(V,E), graphG'(F,A/uF) induced by the corresponding ±ledge set M in G(V,E) has no cycle with odd vertices.In section 4, we put forward the mathematical programming model of reasonable orientation. To start with, an nxm matrix X represents a orientation iff it satisfies(3.4.1)= u;y = i,2,...,wXy = 1 or -1, if / is incident with j xu = 0, otherwiseThen, we obtain the following DC programming,y-i m(3.4.4) sj,?. =u; / = l,2,..., mi=\-BJ=hbiJ;i = l,2,...,n,j = l,2,...,mm-k< Y^Xy < k;\/S c V and[S, V\ S] is a cutset of GieS j=\Optimal equilibrium orientation describes orientation of a graph in detail by quantity. Optimality shows the non-reasonability is smallest while equilibrium accounts for non-equilibrium is smallest.Theorem 3.7.16 An orientation is reasonable, if its non-reasonability is not more than 1 and non-equilibrium equals to the number of its cutset.The model of optimal equilibrium orientation is the following DC programming:j=\ 1-1SJ.= 1,2,...,m-B' |
PDF Full Text Request