List of Figures ................................................ ix
List of Tables ............................................... xiii
Preface ........................................................ xv
1. TIME-VARYING SHORTEST PATH PROBLEMS .......................... 1
1. Introduction ................................................. 1
2. Concepts and problem formulation ............................. 2
3. Properties and NP-completeness ............................... 5
4. Algorithms ................................................... 8
4.1. Waiting at any vertex is arbitrarily allowed ............ 9
4.2. Waiting at any vertex is prohibited .................... 14
4.3. Waiting time is subject to an upper bound .............. 15
5. How to take care of the "zero" ? ............................ 19
6. Speedup to achieve an optimal time/cost trade-off ........... 21
7. Additional references and comments .......................... 24
2. TIME-VARYING MINIMUM SPANNING TREES ......................... 27
1. Introduction ................................................ 27
2. Concepts and problem formulation ............................ 28
3. Arc series-parallel networks ................................ 31
3.1 Complexity .............................................. 32
3.2 A pseudo-polynomial algorithm ........................... 33
4. Networks containing no subgraph homomorphic to K4 ........... 41
4.1. Properties and complexity .............................. 41
4.2. An exact algorithm ..................................... 43
5. General networks ............................................ 52
5.1. Strong NP-hardness ..................................... 52
5.2. Heuristic algorithms ................................... 57
5.3. The error bound of the heuristic algorithms in a
special case ........................................... 62
5.4. An approximation scheme for the problem with arbitrary
waiting constraints .................................... 64
5.4.1 Creating a spanning reducible network ............ 64
5.4.2 Numerical experiments ............................ 65
6. Additional references and comments .......................... 66
3. TIME-VARYING UNIVERSAL MAXIMUM FLOW PROBLEMS ................ 69
1. Introduction ................................................ 69
2. Definition and problem formulation .......................... 71
3. The time-varying residual network ........................... 74
4. The max-flow min-cut theorem ................................ 80
5. A condition on the feasibility of f-augmenting paths ........ 81
6. Algorithms .................................................. 89
7. Additional references and comments ......................... 104
4. TIME-VARYING MINIMUM COST FLOW PROBLEMS .................... 107
1. Introduction ............................................... 107
2. Concepts and problem formulation ........................... 108
3. On the negative cycle ...................................... 110
4. Successive improvement algorithms .......................... 113
4.1 Waiting at any vertex is prohibited .................... 113
4.2 Waiting at any vertex is arbitrarily allowed ........... 120
4.3 Waiting at a vertex is constrained by an upper bound ... 124
5. How to fine-tune the algorithms in special cases? .......... 130
6. The time-varying maximum (k,c)-flow problem ................ 131
7. Additional references and comments ......................... 134
5. TIME-VARYING MAXIMUM CAPACITY PATH
PROBLEMS ................................................... 135
1. Introduction ............................................... 135
2. NP-completeness ............................................ 136
3. Algorithms ................................................. 138
4. Finding approximate solutions .............................. 145
5. Additional references and comments ......................... 149
6. THE QUICKEST PATH PROBLEM .................................. 151
1. Introduction ............................................... 151
2. Problem formulation ........................................ 152
3. NP-hardness ................................................ 153
4. Algorithms ................................................. 155
5. The static k-quickest path problem ......................... 157
6. Additional references and comments ......................... 165
7. FINDING THE BEST PATH WITH MULTI-CRITERIA .................. 167
1. Introduction ............................................... 167
2. Problem formulation ........................................ 168
3. The MinSum-MinSum problem .................................. 171
4. The MinSum-MinMax problem .................................. 173
5. Additional references and comments ......................... 174
8. GENERALIZED FLOWS AND OTHER NETWORK
PROBLEMS ................................................... 175
1. Introduction ............................................... 175
2. Time-varying networks with generalized flows ............... 175
2.1. Notation, assumptions, and problem formulation ........ 176
2.2. Time-varying generalized residual network and
properties ............................................ 178
2.3. Algorithms for the time-varying maximum generalized
flow problem .......................................... 182
3. The time-varying travelling salesman problem ............... 192
4. The time-varying Chinese postman problem ................... 197
4.1. NP-hardness analysis .................................. 198
4.2. Dynamic programming ................................... 199
5. Additional references and comments ......................... 206
List of Figures
1.1. Convert a network into one without parallel arcs and
loops ...................................................... 3
1.2. A subpath of the shortest path is not a shortest path ...... 5
1.3. A shortest path is not a simple path ....................... 6
1.4. A time-varying network constructed from Knapsack ........... 8
1.5. Example 1.2 ............................................... 12
2.1. An example of a dynamic spanning tree ..................... 29
2.2. An arc series-parallel network ............................ 32
2.3. An example to illustrate Algorithm TMST-SP ................ 38
2.4. An example to illustrate Algorithm TMST-SP (continued) .... 41
2.5. Optimal solutions of the example .......................... 41
2.6. A reducible graph which is not edge series-parallel ....... 43
2.7. Two special cases of reducible networks ................... 43
2.8. l and e are conjunction vertices, while P(a, e) is
a dangling path, cycle C(e,g,h) is a dangling cycle,
and D(P(s, w, l), P(s, f, l)) is a diamond ................ 44
2.9. Directions of flow into or out from a path, where у and z
are two conjunction vertices .............................. 44
2.10. Directions of flow into or out from a diamond, where
у and z are two conjunction vertices ..................... 46
2.11. A diamond is changed into a path ......................... 47
2.12. A network constructed from MSC ........................... 54
2.13. The spanning tree is splitted into subtrees .............. 54
2.14. A time-varying network created from MSC .................. 56
2.11. A network for error bound analysis ....................... 61
2.16. The optimal solution ..................................... 62
2.17. The solution obtained by A-TMST .......................... 62
2.18. A network with multi-period structure .................... 63
3.1. A time-varying maximum flow ............................... 72
3.2. The structure of the constructed network for TVUMF ........ 73
3.3. The original network of Example 3.2 ....................... 77
3.4. The initial network ....................................... 78
3.5. Example 3.2 (continued) ................................... 78
3.6. Example 3.2 (continued) ................................... 79
3.7. Example 3.2 (continued) ................................... 79
3.8. How to determine the departure time at a vertex such that
the resulted f-augmenting path is feasible under the bounded
waiting time constraint ................................... 82
3.9. Two paths after the reconstruction ........................ 83
3.10. Splitting vertex x into several dummy vertices to represent
its states at different times ............................ 84
3.11. The feasibility condition for Case II .................... 85
3.12. The initial network of Example 3.4 ....................... 91
3.13. Example 3.4 (continued) .................................. 92
3.14. Example 3.4 (continued) .................................. 93
3.15. Example 3.4 (continued) .................................. 93
3.16. Example 3.4 (continued) .................................. 94
3.17. Example 3.4 (continued) .................................. 94
3.18. Example 3.5 .............................................. 99
3.19. Example 3.5 (continued) ................................. 100
3.20. Example 3.5 (continued) ................................. 100
3.21. Example 3.5 (continued) ................................. 100
3.22. Example 3.5 (continued) ................................. 101
4.1. A negative cycle (case I) ................................ 112
4.2. A negative cycle (case II) ............................... 112
4.3. Example 4.1 .............................................. 118
4.4. Example 4.1 (continued) .................................. 118
4.5. Example 4.1 (continued) .................................. 118
4.6. Example 4.1 (continued) .................................. 119
4.7. Example 4.1 (continued) .................................. 119
4.8. Example 4.1 (continued) .................................. 120
5.1. The network constructed for TVMCP-NW ..................... 137
5.2. The network for Example 5.1 .............................. 148
6.1. The constructed network for TVQP ......................... 154
6.2. Example 7.1 .............................................. 157
6.3. Example 6.2 .............................................. 160
6.4. Example 6.2 (continued) .................................. 160
8.1. Finding a dynamic f-augmenting path at each iteration
may not generate the maximum generalized flow ............ 180
8.2. A unlimited flow-generating cycle ........................ 181
8.3. Example 8.2 .............................................. 187
8.4. Construct a time-varying network N for a given
digraph G ................................................ 199
|
