Three nonlinear network flow problems

This dissertation is concerned with network flow problems for which some of the conventional assumptions are in violation. These violations in the assumptions disrupt the exploitable structure that exists in traditional cases. As a result, the resulting problems are then not amenable to the efficient solution methods developed for the traditional cases. They still allow convex programming methods. However, the networks considered often represent cities and states that can be large in size, and therefore there is a need to investigate more practically scalable approaches for the considered applications.

In particular, in each chapter, we study a different application, each challenging a different conventional assumption. We then present solution methods that are more scalable compared to the current approaches for the resulting problems. Described methods we develop rely on; characterizing the optimal solution and optimality conditions, analyzing solution sensitivities, and exploiting the remaining network structure.

The first problem is concerned with reliability in minimum cost flow problems. In many applications, especially logistics, travel time variation often has critical implications. As a result, it might be more preferable to use a route with less variation but with a higher mean cost depending on the risk averseness of the decision-maker. One way to model this is by considering a weighted combination of the mean and standard deviation of the flow costs. Even though this choice has modeling benefits, the resulting optimization problem has an objective function that is non-separable by arcs and thus harder to solve than the separable case. We first prove that the solution for this problem coincides with the solution for a particular separable problem. We then leverage this result by using root-finding methods to find that particular separable problem. Essentially, this approach solves the original non-separable problem by solving many easier separable problems. We also discuss how the results could be extended for a more general case of non-separable convex problems. Our experiments show that the proposed methods provide significant advantages over solving the non-separable directly by using an off-the-shelf solver.

We then study how to solve for a system optimal assignment for a particular parking model. Identifying system optimal assignment is crucial as it can be a guide for the transportation planners for implementing policies/strategies that can reduce the congestion in the system. The parking model considered, captures the inherent circling for parking behavior of the users. As a result, it leads to nonlinearities in the flow conservation equations. To solve for a system optimal assignment, we first formulate the optimization problem. By representing decision variables in splitting fractions space, we get linear constraints. However, doing so shifts the complexity to the objective, resulting in a non-convex function. Nevertheless, we propose a descent approach. To find the required derivative information, we provide sensitivity analysis for the cyclic network. We showcase the value of identifying a system optimal assignment on a small toy network, where the planner can adjust the parking prices to derive the user equilibrium towards the system optimal and therefore reducing the total system cost.

In the last chapter, we study a repair sequencing problem for road networks that are impaired due to natural disasters. Our focus here is on long-term recovery disaster relief. We investigate how to identify a (sequential) link repair sequence that minimizes total travel time over the repair horizon, given that at each repair stage road traffic distributes according to the principle of user equilibrium. Unlike the problems in the single machine scheduling literature, the project weights, in this case, are unknown a priori due to the nonlinear congestion effects coming from traffic equilibrium. We first derive an analogue of Bellman's optimality principle, allowing us to solve the problem using methods of dynamic programming. We then develop a bidirectional search heuristic with customized pruning and branching strategies that exploit specific properties of traffic assignment. Our experiments show that our method is scalable and performs well even on networks involving thousands of links.