Accession Number : ADA564645

Title :   The Average Network Flow Problem: Shortest Path and Minimum Cost Flow Formulations, Algorithms, Heuristics, and Complexity

Descriptive Note : Doctorial thesis

Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH GRADUATE SCHOOL OF ENGINEERING AND MANAGEMENT

Personal Author(s) : Jordan, Jeremy D

Report Date : 13 Sep 2012

Pagination or Media Count : 220

Abstract : Integrating value focused thinking with the shortest path problem results in a unique formulation called the multiobjective average shortest path problem. We prove this is NP-complete for general graphs. For directed acyclic graphs, an efficient algorithm and even faster heuristic are proposed. While the worst case error of the heuristic is proven unbounded, its average performance on random graphs is within 3% of the optimal solution. Additionally, a special case of the more general biobjective average shortest path problem is given, allowing tradeoffs between decreases in arc set cardinality and increases in multiobjective value; the algorithm to solve the average shortest path problem provides all the information needed to solve this more difficult biobjective problem. These concepts are then extended to the minimum cost flow problem creating a new formulation we name the multiobjective average minimum cost flow. This problem is proven NP-complete as well. For directed acyclic graphs, two efficient heuristics are developed, and although we prove the error of any successive average shortest path heuristic is in theory unbounded, they both perform very well on random graphs. Furthermore, we define a general biobjective average minimum cost flow problem. The information from the heuristics can be used to estimate the efficient frontier in a special case of this problem trading off total flow and multiobjective value. Finally, several variants of these two problems are discussed. Proofs are conjectured showing the conditions under which the problems are solvable in polynomial time and when they remain NP-complete.

Descriptors :   *ALGORITHMS , *HEURISTIC METHODS , *NETWORK FLOWS , DECISION THEORY , FORMULATIONS

Subject Categories : Numerical Mathematics
Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE