Modeling and Solution Approaches for Non-traditional Network Flow Problems with Complicating Constraints

In this dissertation, we model three network-based optimization problems. Chapter 2 addresses the question of what the operation plan should be for interdependent infrastructure systems in resource-constrained environments so that they collectively operate at the highest level. We develop a network-based operation model of these systems that accounts for interdependencies among them. To solve this large-scale model, a solution approach is proposed that relatively quickly generates high-quality solutions to the problem. Chapter 3 presents a routing model for a single train within a railyard with the objective of minimizing the total length traveled by train. The difference between this problem and the traditional shortest path is that the route must accommodate the length of the train at any time, subject to yard tracks’ configuration. This problem has application in the railway industry where they need to solve the single-train routing problem repeatedly for simulations of train movements in large complex yards. We develop an optimal polynomial-time algorithm that solves an important special case of the problem. Chapter 4 extends the problem defined in Chapter 3 to a two-train routing problem with the objective of minimizing the overall time possible to schedule the routes in a conflict-free manner. We propose a routing problem that indirectly aims to decrease the overall scheduling time for the two trains. We develop a scheduling model that compares the performance of the solution obtained by the proposed routing model with the solutions obtained by solving the problem as two separate single-train yard routing problems. The comparison indicates a better performance obtained by the proposed routing model for specific problems