DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# 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

# Report Date:

## 2012-09-13

# Pagination or Media Count:

##
220.0

# 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.

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#