Time-varying network optimization

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.

List of Figures	p. ix
List of Tables	p. xiii
Preface	p. xv
1 Time-Varying Shortest Path Problems	p. 1
1 Introduction	p. 1
2 Concepts and problem formulation	p. 2
3 Properties and NP-completeness	p. 5
4 Algorithms	p. 8
4.1 Waiting at any vertex is arbitrarily allowed	p. 9
4.2 Waiting at any vertex is prohibited	p. 14
4.3 Waiting time is subject to an upper bound	p. 15
5 How to take care of the "zero"?	p. 19
6 Speedup to achieve an optimal time/cost trade-off	p. 21
7 Additional references and comments	p. 24
2 Time-Varying Minimum Spanning Trees	p. 27
1 Introduction	p. 27
2 Concepts and problem formulation	p. 28
3 Arc series-parallel networks	p. 31
3.1 Complexity	p. 32
3.2 A pseudo-polynomial algorithm	p. 33
4 Networks containing no subgraph homomorphic to K[subscript 4]	p. 41
4.1 Properties and complexity	p. 41
4.2 An exact algorithm	p. 43
5 General networks	p. 52
5.1 Strong NP-hardness	p. 52
5.2 Heuristic algorithms	p. 57
5.3 The error bound of the heuristic algorithms in a special case	p. 62
5.4 An approximation scheme for the problem with arbitrary waiting constraints	p. 64
5.4.1 Creating a spanning reducible network	p. 64
5.4.2 Numerical experiments	p. 65
6 Additional references and comments	p. 66
3 Time-Varying Universal Maximum Flow Problems	p. 69
1 Introduction	p. 69
2 Definition and problem formulation	p. 71
3 The time-varying residual network	p. 74
4 The max-flow min-cut theorem	p. 80
5 A condition on the feasibility of f-augmenting paths	p. 81
6 Algorithms	p. 89
7 Additional references and comments	p. 104
4 Time-Varying Minimum Cost Flow Problems	p. 107
1 Introduction	p. 107
2 Concepts and problem formulation	p. 108
3 On the negative cycle	p. 110
4 Successive improvement algorithms	p. 113
4.1 Waiting at any vertex is prohibited	p. 113
4.2 Waiting at any vertex is arbitrarily allowed	p. 120
4.3 Waiting at a vertex is constrained by an upper bound	p. 124
5 How to fine-tune the algorithms in special cases?	p. 130
6 The time-varying maximum (k, c)-flow problem	p. 131
7 Additional references and comments	p. 134
5 Time-Varying Maximum Capacity Path Problems	p. 135
1 Introduction	p. 35
2 NP-completeness	p. 136
3 Algorithms	p. 138
4 Finding approximate solutions	p. 145
5 Additional references and comments	p. 149
6 The Quickest Path Problem	p. 151
1 Introduction	p. 151
2 Problem formulation	p. 152
3 NP-hardness	p. 153
4 Algorithms	p. 155
5 The static k-quickest path problem	p. 157
6 Additional references and comments	p. 165
7 Finding the Best Path with Multi-Criteria	p. 167
1 Introduction	p. 167
2 Problem formulation	p. 168
3 The MinSum-MinSum problem	p. 171
4 The MinSum-MinMax problem	p. 173
5 Additional references and comments	p. 174
8 Generalized Flows and Other Network Problems	p. 175
1 Introduction	p. 175
2 Time-varying networks with generalized flows	p. 175
2.1 Notation, assumptions, and problem formulation	p. 176
2.2 Time-varying generalized residual network and properties	p. 178
2.3 Algorithms for the time-varying maximum generalized flow problem	p. 182
3 The time-varying travelling salesman problem	p. 192
4 The time-varying Chinese postman problem	p. 197
4.1 NP-hardness analysis	p. 198
4.2 Dynamic programming	p. 199
5 Additional references and comments	p. 206

Mevcut:*

Bound With These Titles

On Order

Özet

Özet

Table of Contents