Constructing Optimal Flow Networks: An Exploration Centered on the U.S. Flight Network

Abstract

Flow networks play a critical role in various fields including engineering, transportation, logistics, and communications. Efficient network design is essential for addressing complex demands, constraints, and priorities. This thesis presents a series of techniques and models for optimal flow network design via edge selection. The U.S. domestic passenger flight network serves as a case study for applying, testing, and visualizing the results of the proposed methods.

Four models are explored: spanning tree construction, optimal hub selection, optimal new hub creation, and a generic edge selection model. Spanning trees are shown to minimize the number of edges while satisfying all demand, with fast algorithms available for finding optimal trees based on various factors. Hub selection and new hub creation models are proposed that allow network planners to account for factors such as total passenger-miles traveled, total edge length, and the number of transfers (or a combination thereof)—with an analysis of the conditions under which one model is superior to the other. Finally, a generic edge selection model is presented with a mixed-integer optimization formulation, and is shown to be powerful, versatile, and adaptive to various network settings based on a network planner's preferences, constraints, and circumstances.

The thesis contributes to the fields of operations research, graph theory, and network optimization, and has practical implications for the optimal design of complex networks across a wide range of domains.