## Time-Varying Network OptimizationNetwork ?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

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 |

### Other editions - View all

### Common terms and phrases

a(xi algorithm alternating number arc capacities arc x,y arrival artiﬁcial arc assume bounded waiting Cap(P completes the proof consider da(y deﬁned Deﬁnition delete denote departure diamond diamond D diﬀerent dynamic Chinese path dynamic f-augmenting path dynamic programming dynamic residual network exactly Example exists a path feasible dynamic f-augmenting feasible path ﬁnd ﬁrst flow ﬂow value formula graph induction integer iteration labelled Lemma Max-Flow Min-Cut Theorem maximum capacity path maximum dynamic f-augmenting minimum spanning tree negative cycle NP-complete NP-hard obtain optimal solution original network path P(s path P(s,y Qa(e quickest path SDFP-ZW Section series-parallel network shortest dynamic f-augmenting shortest path problem solve Sort all values source vertex subnetwork subpath Theorem time-varying maximum time-varying network transit cost travelling salesman problem traverse TVMCP-AW TVSP TVSP-AWT TVUMF problem TVUMF-BW unit of ﬂow update vertex x w(xi waiting time constraint zero waiting