On finding paths and flows in multicriteria, stochastic and time-varying networks

This dissertation addresses two classes of network flow problems in networks with multiple, stochastic and time-varying attributes. The first problem class is concerned with providing routing instructions with the ability to make updated decisions as information about travel conditions is revealed for individual travelers in a transportation network. Three exact algorithms are presented for identifying all or a subset of the adaptive Pareto-optimal solutions with respect to the expected value of each criterion from each node to a desired destination for each departure time in the period of interest…

Contents

Chapter 1. Introduction
1.1. Motivation
1.2. Problem Class I
1.3. Problem Class II
1.4. Contributions
Chapter 2. Adaptive Pareto-Optimal Path Strategies
2.1. Introduction
2.2. Literature Review
2.2.1. Single Criterion Shortest Path Problems
2.2.2. Multicriteria Optimal Path Problems
2.3. Pareto-Optimal Hyperpaths in STV Networks
2.4. Network Notation and Problem Definitions
2.5. Solution Approaches
2.5.1. The Adaptive Pareto-Optimal Strategy (APS) Algorithm
2.5.2. The Adaptive Least Expected Disutility Strategy I (ALEDS I) Algorithm
2.5.3. The Adaptive Least Expected Disutility Strategy II (ALEDS II) Algorithm
2.6. Notes on Algorithm Implementation
2.7. Computational Experiments
2.7.1. Experimental Design
2.7.2. Average Run Times of the APS Algorithm
2.7.3. Average Run Times of the ALEDS I and II Algorithms
2.8. Conclusions
Chapter 3. Adjustable Preference Path Strategies
3.1. Introduction
3.2. Network Notation and Problem Definition
3.3. The Adjustable Preference Path Strategy (APPS) Algorithm
3.4. Illustrative Example Problem
3.5. Numerical Experiments
3.5.1. Experimental Design
3.5.2. Results and Discussion
3.6. Conclusions
Chapter 4. The Safest Escape Problem
4.1. Introduction
4.2. Literature Review
4.3. Conceptual Framework
4.3.1. Expectation and Path Flows
4.3.2. Probabilities of Successful Path Traversal
4.4. Safest Escape
4.5. Network Notation and Problem Formulation
4.6. Solution Approach
4.6.1. The PTD residual network
4.6.2. SEscape algorithm
4.6.3. Maximum Probability Path (MPP) algorithm
4.6.4. Proof of the SEscape algorithm
4.7. Illustrative Example
4.8. Numerical Experiments
4.8.1. Experimental Design
4.8.2. Experimental Results
4.9. Conclusions
Chapter 5. Heuristics for MSTV Capacitated Networks
5.1. Introduction
5.2. A Genetic Algorithm for Deterministic, Time -V arying Networks
5.2.1. Network Notation and Problem Definition
5.2.2. Genetic Algorithm
5.2.3. Illustrative Example
5.2.4. Experimental Results
5.2.4.1. Parameter Tuning
5.2.4.2. Algorithm Performance Analysis
5.3. A Noisy Genetic Algorithm for Stochastic, Time -V arying Networks
5.3.1. Sampling Fitness Function
5.3.2. Sampling Design
5.3.3. Constraint Handling
5.3.4. Illustrative Example
5.4. A Noisy Genetic Algorithm for Multicriteria, Stochastic, Time -V aryingNetworks
Chapter 6. Conclusions and Extensions
6.1. Synthesis
6.2. Future Extensions
Appendices
Appendix A Illustrative Example for The APS Algorithm
Appendix B Mathematical Formulation of the SEscape Algorithm
References

Author: Opasanon, Sathaporn -

Source: University of Maryland

Download URL 2: Visit Now