Time-Varying Network Optimization

Front Cover
Springer Science & Business Media, May 5, 2007 - Computers - 248 pages
0 Reviews
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 kcflow 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 Definition 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 flow 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

Other editions - View all

Common terms and phrases