Flow location (FlowLoc) problems: dynamic network flows and location models for evacuation planning

In this paper we combine two modeling tools to predict and evaluate evacuation plans: (dynamic) network flows and locational analysis. We present three exact algorithms to solve the single facility version 1-FlowLoc of this problem and compare their running times. After proving the $\mathcal{NP}$ -completeness of the multi facility q-FlowLoc problem, a mixed integer programming formulation and a heuristic for q-FlowLoc are proposed. The paper is concluded by discussing some generalizations of the FlowLoc problem, such as the multi-terminal problem, interdiction problem, the parametric problem and the generalization of the FlowLoc problem to matroids.     

Modeling of building evacuation problems by network flows with side constraints

In this paper we model building evacuations by network flows with side constraints. Side constraints come from variable arc capacities on some arcs which are functions of flows in incident arcs. In this context we study maximum flow, minimum cost, and minimax objectives. For some special structured networks we propose ‘greedy’ algorithms for solving these problems. For more general network structures, solution procedures are recommended which take advantage of the network structures of the problems.     

Maximum-throughput dynamic network flows

This paper presents and solves the maximum throughput dynamic network flow problem, an infinite horizon integer programming problem which involves network flows evolving over time. The model is a finite network in which the flow on each arc not only has an associated upper and lower bound but also an associated transit time. Flow is to be sent through the network in each period so as to satisfy the upper and lower bounds and conservation of flow at each node from some fixed period on. The objective is to maximize the throughput, the net flow circulating in the network in a given period, and this throughput is shown to be the same in each period. We demonstrate that among those flows with maximum throughput there is a flow which repeats every period. Moreover, a duality result shows the maximum throughput equals the minimum capacity of an appropriately defined cut. A special case of the maximum dynamic network flow problem is the problem of minimizing the number of vehicles to meet a fixed periodic schedule. Moreover, the elegantsolution derived by Ford and Fulkerson for the finite horizon maximum dynamic flow problem may be viewed as a special case of the infinite horizon maximum dynamic flow problem and the optimality of solutions which repeat every period.     

A survey of dynamic network flows

Dynamic network flow models describe network-structured, decision-making problems over time. They are of interest because of their numerous applications and intriguing dynamic structure. The dynamic models are specially structured problems that can be solved with known general methods. However, specialized techniques have been developed to exploit the underlying dynamic structure. Here, we present a state-of-the-art survey of the results, applications, algorithms and implementations for dynamic network flows.Presented at the XII International Symposium on Mathematical Programming, Cambridge, Massachusetts, August 1985.Prepared under National Science Foundation Grant ECS-8307549. Reproduction in whole or in part is permitted for any purpose of the United States Government. This document has been approved for public release and sale; its distribution is unlimited.     

On solving continuous-time dynamic network flows

Temporal dynamics is a crucial feature of network flow problems occurring in many practical applications. Important characteristics of real-world networks such as arc capacities, transit times, transit and storage costs, demands and supplies etc. are subject to fluctuations over time. Consequently, also flow on arcs can change over time which leads to so-called dynamic network flows. While time is a continuous entity by nature, discrete-time models are often used for modeling dynamic network flows as the resulting problems are in general much easier to handle computationally. In this paper, we study a general class of dynamic network flow problems in the continuous-time model, where the input functions are assumed to be piecewise linear or piecewise constant. We give two discrete approximations of the problem by dividing the considered time range into intervals where all parameters are constant or linear. We then present two algorithms that compute, or at least converge to optimum solutions. Finally, we give an empirical analysis of the performance of both algorithms.     

Maximum flow problem on dynamic generative network flows with time-varying bounds

This paper considers a new class of network flows, called dynamic generative network flows in which, the flow commodity is dynamically generated at a source node and dynamically consumed at a sink node and the arc-flow bounds are time dependent. Then the maximum dynamic flow problem in such networks for a pre-specified time horizon T is defined and mathematically formulated in both arc flow and path flow presentations. By exploiting the special structure of the problem, an efficient algorithm is developed to solve the general form of the dynamic problem as a minimum cost static flow problem.     

Aggregate-level demand management in evacuation planning

Without successful large-scale regional evacuations, threats such as hurricanes and wild-fires can cause a large loss of life. In this context, automobiles are oftentimes an essential transportation mode for evacuations, but the ensuing traffic typically overwhelms the roadway capacity and causes congestion on a massive scale. Congestion leads to many problems including longer, costlier, and more stressful evacuations, lower compliance rates, and increased risk to the population. Supply-based strategies have traditionally been used in evacuation planning, but they have been proven to be insufficient to reduce congestion to acceptable levels. In this paper, we study the demand-based strategies of aggregate-level staging and routing to structure the evacuation demand, both with and without congestion. We provide a novel modeling framework that offers strategic flexibility and utilizes a lexicographic objective function that represents a hierarchy of relevant evacuation-based goals. We also provide insights into the nature and effect of network bottlenecks. We compare our model with and without congestion in relation to tractability, normative optimality, and robustness under demand uncertainty. We also show the effectiveness of using demand-based strategies as opposed to using the status quo that involves a non-staged or simultaneous evacuation process. Effective solution procedures are developed and tested using hypothetical problem instances as well as using a larger study based on a portion of coastal Virginia, USA.     

Optimal evacuation planning using staging and routing

Evacuation is an important disaster management tool. Evacuating a large region by automobile (the most commonly used mode) is a difficult task, especially as high levels of traffic congestion often form. This paper studies the use of demand-based strategies, specifically, the staging and routing of evacuees. These strategies attempt to manage demand in order to reduce or eliminate congestion. A strategic mixed-integer programming planning model that accounts for evacuation dynamics and congestion is used to study these strategies. The strategies adopted incorporate different evacuee types based on destination requirements and shelter capacity restrictions. The main objective studied is to minimize the network clearance time. We examine the structure of optimal strategies, yielding insights into the use of staging and routing in evacuation management. These insights are then used to develop effective solution procedures. To demonstrate the efficacy of the proposed solution technique, we provide computational experience using a large realistic example based on Virginia Beach.     

Simultaneous design and planning of supply chains with reverse flows: A generic modelling framework

The increase in societal awareness towards environmental issues has accrued the responsibility of goods producers, which at present came to encompass the entire product life cycle. Recently, the efficient design and operation of supply chains with return flows have, in particular, become a major challenge for many companies, given the high number of factors involved and their intricate interactions.     

Numerical simulation of building evacuation in emergency conditions

In the present work, pedestrian behaviour in crowds is assumed to be a coupled phenomena. Therefore, the use of continuousand individual-models in different regions according to its local density is suggested. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Ranking robustness and its application to evacuation planning

We present a new approach to handle uncertain combinatorial optimization problems that uses solution ranking procedures to determine the degree of robustness of a solution. Unlike classic concepts for robust optimization, our approach is not purely based on absolute quantitative performance, but also includes qualitative aspects that are of major importance for the decision maker.We discuss the two variants, solution ranking and objective ranking robustness, in more detail, presenting problem complexities and solution approaches. Using an uncertain shortest path problem as a computational example, the potential of our approach is demonstrated in the context of evacuation planning due to river flooding.     

Exploring express delivery networks in China based on complex network theory

Based on the complex network theory, we explore an express delivery system in China, which consists of two delivery networks, namely, the air delivery network (ADN) and the ground delivery network (GDN). Systematic structural analysis indicates that both delivery networks exhibit small‐world phenomenon, disassortative mixing behavior, and rich‐club phenomenon. However, there are significant differences between ADN and GDN in terms of degree distribution property and community structure. On the basis of the Barabási‐Albert model, we have proposed a network model incorporating the structural features of the two delivery networks to reveal their evolutionary mechanisms. Lastly, the parcel strength and the distance strength are analyzed, which, respectively, reflect the number of parcels and the long‐haul delivery distance handled by a node city. The strengths are highly heterogeneous in both delivery networks and have intense correlations with topological structures. These works are beneficial for express enterprises to construct or extend their express delivery networks, and provide some useful insights on improving parcel delivery service. © 2014 Wiley Periodicals, Inc. Complexity 21: 166–179, 2015     

Multiterminal network flows and applications

The paper discusses the ways to use the condensation technique of Gomory/Hu in the case of non-symmetric networks. Sufficient conditions to get the value of a maximal flow as row resp. column sum of the capacity matrix are derived. Procedures to determine the cut with minimal capacity are developed and applications of the minimal cut technique to problems of optimal sequencing are given.

---

Zusammenfassung Das Papier diskutiert die Möglichkeiten, die Kondensationstechnik von Gomory/Hu auf den Fall unsymmetrischer Netzwerke zu übertragen. Es werden hinreichende Bedingungen dafür abgeleitet, daß der Wert eines maximalen Flusses mit der Zeilenbzw. Spaltensumme der Kapazitätsmatrix übereinstimmt. Es werden Verfahren entwickelt, den Schnitt minimaler Kapazität zu bestimmen. Anwendungen der minimalen Schnitt-Technik auf Probleme der optimalen Reihenfolge werden vorgestellt.

     

Maximal dynamic polymatroid flows and applications

The concept of dynamic polymatroid flows is introduced. It is shown that the time expanded network algorithm which is well known for dynamic network flows works for polymatroid flows as well. As applications we discuss dynamic matroid intersection and dynamic matroid partitionings.     

Robust discrete optimization and network flows

We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0–1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0–1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard -approximable 0–1 discrete optimization problem, remains -approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. The research of the author was partially supported by the Singapore-MIT alliance.The research of the author is supported by a graduate scholarship from the National University of Singapore.Mathematics Subject Classification (2000): 90C10, 90C15     

Guaranteed cost synchronization of a complex dynamical network via dynamic feedback control

In this paper, the problem of guaranteed cost synchronization for a complex network is investigated. In order to achieve the synchronization, two types of guaranteed cost dynamic feedback controller are designed. Based on Lyapunov stability theory, a linear matrix inequality (LMI) convex optimization problem is formulated to find the controller which guarantees the asymptotic stability and minimizes the upper bound of a given quadratic cost function. Finally, a numerical example is given to illustrate the proposed method.     

Two commodity network flows and linear programming

This paper shows that the linear programming formulation of the two-commodity network flow problem leads to a direct derivation of the known results concerning this problem. An algorithm for solving the problem is given which essentially consists of two applications of the Ford—Fulkerson max flow computation. Moreover, the algorithm provides constructive proofs for the results. Some new facts concerning feasible integer flows are also given.