Time-Varying Network Optimization

Springer Science & Business Media, May 5, 2007 - Computers - 248 pages
Network ?ow optimization problems may arise in a wide variety of important ?elds, such as transportation, telecommunication, computer networking, ?nancial planning, logistics and supply chain management, energy systems, etc. Signi?cant and elegant results have been achieved onthetheory,algorithms,andapplications,ofnetwork?owoptimization in the past few decades; See, for example, the seminal books written by Ahuja, Magnanti and Orlin (1993), Bazaraa, Jarvis and Sherali (1990), Bertsekas (1998), Ford and Fulkerson (1962), Gupta (1985), Iri (1969), Jensen and Barnes (1980), Lawler (1976), and Minieka (1978). Most network optimization problems that have been studied up to date are, however, static in nature, in the sense that it is assumed that it takes zero time to traverse any arc in a network and that all attributes of the network are constant without change at any time. Networks in the real world are, nevertheless, time-varying in essence, in which any ?ow must take a certain amount of time to traverse an arc and the network structure and parameters (such as arc and node capacities) may change over time. In such a problem, how to plan and control the transmission of ?ow becomes very important, since waiting at a node, or travelling along a particular arc with di?erent speed, may allow one to catch the best timing along his path, and therefore achieve his overall objective, such as a minimum overall cost or a minimum travel time from the origin to the destination.

What people are saying -Write a review

We haven't found any reviews in the usual places.

Contents

 TIMEVARYING SHORTEST PATH PROBLEMS 1 2 Concepts and problem formulation 2 3 Properties and NPcompleteness 5 4 Algorithms 8 41 Waiting at any vertex is arbitrarily allowed 9 42 Waiting at any vertex is prohibited 14 43 Waiting time is subject to an upper bound 15 5 How to take care of the zero ? 19
 4 Successive improvement algorithms 113 42 Waiting at any vertex is arbitrarily allowed 120 43 Waiting at a vertex is constrained by an upper bound 124 5 How to finetune the algorithms in special cases? 130 6 The timevarying maximum kcﬂow problem 131 7 Additional references and comments 134 TIMEVARYING MAXIMUM CAPACITY PATH PROBLEMS 135 2 NPcompleteness 136

 6 Speedup to achieve an optimal timecost tradeoff 21 7 Additional references and comments 24 TIMEVARYING MINIMUM SPANNING TREES 27 2 Concepts and problem formulation 28 3 Arc seriesparallel networks 31 31 Complexity 32 32 A pseudopolynomial algorithm 33 4 Networks containing no subgraph homomorphic to K4 41 42 An exact algorithm 43 5 General networks 52 52 Heuristic algorithms 57 53 The error bound of the heuristic algorithms in a special case 62 54 An approximation scheme for the problem with arbitrary waiting constraints 64 542 Numerical experiments 65 6 Additional references and comments 66 TIMEVARYING UNIVERSAL MAXIMUM FLOW PROBLEMS 68 2 Deﬁnition and problem formulation 71 3 The timevarying residual network 74 4 The maxflow mincut theorem 80 5 A condition on the feasibility of faugmenting paths 81 6 Algorithms 89 7 Additional references and comments 104 TIMEVARYING MINIMUM COST FLOW PROBLEMS 107 2 Concepts and problem formulation 108 3 On the negative cycle 110
 3 Algorithms 138 4 Finding approximate solutions 145 5 Additional references and comments 149 THE QUICKEST PATH PROBLEM 150 2 Problem formulation 152 3 NPhardness 153 4 Algorithms 155 5 The static kquickest path problem 157 6 Additional references and comments 165 FINDING THE BEST PATH WITH MULTI CRITERIA 167 2 Problem formulation 168 3 The MinSumMinSum problem 171 4 The MinSumMinMax problem 173 5 Additional references and comments 174 GENERALIZED FLOWS AND OTHER NETWORK PROBLEMS 175 21 Notation assumptions and problem formulation 176 22 Timevarying generalized residual network and properties 178 23 Algorithms for the timevarying maximum generalized ﬂow problem 182 3 The timevarying travelling salesman problem 192 4 The timevarying Chinese postman problem 197 41 NPhardness analysis 198 42 Dynamic programming 199 5 Additional references and comments 206 Copyright