# Flow Improvement in Evacuation Planning with Budget Constrained Switching Costs

Authors: Ram Chandra Dhungana; Tanka Nath Dhamala
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

Many large-scale natural and human-created disasters have drawn the attention of researchers towards the solutions of evacuation planning problems and their applications. The main focus of these solution strategies is to protect the life, property, and their surroundings during the disasters. With limited resources, it is not an easy task to develop a universally accepted model to handle such issues. Among them, the budget-constrained network flow improvement approach plays significant role to evacuate the maximum number of people within the given time horizon. In this paper, we consider an evacuation planning problem that aims to shift a maximum number of evacuees from a danger area to a safe zone in limited time under the budget constraints for network modification. Different flow improvement strategies with respect to fixed switching cost will be investigated, namely, integral, rational, and either to increase the full capacity of an arc or not at all. A solution technique on static network is extended to the dynamic one. Moreover, we introduce the static and dynamic maximum flow problems with lane reversal strategy and also propose efficient algorithms for their solutions. Here, the contraflow approach reverses the direction of arcs with respect to the lane reversal costs to increase the flow value. As an implementation of an evacuation plan may demand a large cost, the solutions proposed here with budget constrained problems play important role in practice.


---

## Body

## 1. Introduction

People are living under the threats of different natural and human-created disasters, such as hurricanes, floods, wildfires, or chemical spills. Many disasters are uncertain and unavoidable, but their effects can be minimized with efficient evacuation planning. But, the development of efficient models and algorithms for these planning problems is always challenging. To find efficient transportation routes during the evacuation, network flow models have been widely used. An evacuation network is interpreted by using a directed graph where the intersections of roads are represented by nodes, road segments between nodes are represented by arcs, and routes between two nodes are taken as directed paths. The places where evacuees are gathered and start to move at risk are considered as source nodes, and the safe destinations where they are supposed to arrive are sink nodes. Each node has a nonnegative integer capacity which bounds the maximum possible flow amount through it. Every arc has a cost or a transit time assigned to it. A flow in the network is considered as the evacuees or the vehicles carrying evacuees.The network flow problems are to find maximum flow or minimum cost flow in a given network. The maximum dynamic flow problem (MDF) in two-terminal networks is solved polynomially using a static minimum cost flow solution [1]. A flow maximization seeks to send as much flow amount as possible within a time bound. A large number of researchers have studied different flow models for various objectives such as the earliest arrival flow to maximize the flow at every possible time; quickest flow to shift given amount of flow in minimum time; lexicographically maximum flow to maximize the flow in given priority order; and quickest transshipment problem to satisfy given demand and supply in minimum time. These dynamic flow models have widely been used in solving several evacuation planning problems. Static flow solutions are the building blocks for dynamic flow solutions. Usually, the evacuation plans should respect the given time bound that may be continuous or discrete. The authors in [2] show that approximate continuous time solution can be obtained by applying the natural transformation to a discretized time solution. Most of these models, except that of cost minimization problems themselves, consider the travel time on an arc as only the cost on it and do not take care of any additional costs occurred during the evacuation plans. They aim to fulfill the respective objectives on fixed network topology. For details, we refer to [3] and [4] and the references therein.Different types of network modification problems exist in the literature. Generally, the original network is assumed to be not modifiable in the sense that capabilities or costs remain fixed as in the given network. However, this assumption is not valid in many real evacuation scenarios. For example, the capacity of an arc can also be increased up to some limit subject to some capacity incremental cost. For this, a fixed budget can be distributed to increase capacities in the network such that the network topology is modified and an objective, for instance, the flow, with respect to new capacities is maximized. There are three variants of this improvement strategy that deal with rational, integral, and either of the all possible or not at all capacity values in [5]. The first two variants are polynomial time solvable, while the last one is NP-hard even in the cases of bipartite and series-parallel graphs. This third variant called the 0/1 maximum flow improvement strategy is equivalent to the maximum flow-fixed cost problem which is a bicriteria optimization problem where the flow has to be maximized under the budget constraint. A fully polynomial time approximation scheme for series-parallel graphs is presented. The network modification problems that relate to arc-based improvement and node-based upgrading models are also investigated.Contraflow increases the outbound road capacities by reversing the direction of arcs towards the safe destinations. It increases the flow value and decreases the evacuation time by reducing the congestion in an emergency or rush-hour traffic management. The arc reversals are performed on the existing networks with permissible lane reversals without any additional costs. The authors in [6, 7] prove that the contraflow problems for general networks are NP-hard. The former have presented different heuristics for multiterminal network, and the latter have polynomially solved maximum dynamic contraflow (MDCF) and quickest contraflow problems in the case of two-terminal networks, respectively. By introducing the contraflow approach, different evacuation planning problems are efficiently solved in [8, 9]. The earliest arrival transshipment contraflow in multisource networks and with zero transit time in multisink networks has been polynomially solved. The authors in [10] investigate the quickest contraflow problem with constant- and load-dependent transit times. The authors in [11] have developed a class of contraflow algorithms and performed computational experiments. The technique of lane reversals is beneficial for other purposes, for example, crossing eliminations, logistic supports, and use of emergency vehicles and facility locations. The contraflow approach with crossing elimination, facility location-allocation, and partial lane reversal strategies are introduced in [12–14], respectively. The third approach makes use of nonreversed arcs in contraflow for supporting facilities and emergency logistics. Multimodel integrated contraflow for uncertain arrivals of evacuees in an evacuation region with a low mobility population is presented in [15]. Considering the influence of intersections, an improved critical-road model has been investigated to find the optimal contraflow links [16].For provided limited resources, it is not possible to select all arc reversals as demanded by the optimal contraflows. In this paper, we investigate contraflow problems with fixed budget constraint distributed to the arc reversals. The total given budget allows us to reverse only a certain percentage of arcs in a given network. We introduce the maximum dynamic flow improvement problem (MDFIP) and also the maximum contraflow improvement problems in both static and dynamic networks. Then, we propose polynomial time algorithms to solve these problems. To the best of our knowledge, this is the first attempt to incorporate the issues of arc reversal costs on contraflow problems subject to the given total budget constraint. As arc reversals require a lot of costs at emergency period, this approach is more practicable in implementing the contraflow algorithms.The paper is organized as follows. The network flow models are given in Section2. The solutions on static and dynamic flow improvement problems are presented in Sections 3.1 and 3.2, respectively. The contraflow models and their solution procedures with unit switching costs on arcs for the flow improvements are proposed in Section 4. Section 5 concludes the paper.


## 2. Preliminaries

Consider a directed dynamic networkN=V,A,uet,θe,T, with V=V+∪V−∪V0, where V+, V−, and V0 represent sets of sources, sinks, and intermediate nodes, respectively. In particular, V+=s and V−=t, for any two-terminal network. The egress time T is denoted by T=0,1,…,T and Tc=0,1,…,T,T+1 in discrete and continuous time models, respectively. The functions θ:A⟶R≥0 and u:A×T⟶R≥0 are arc transit time and capacity functions, respectively. The capacity function bounds the amount of flow on arcs. Suppose f:A×T⟶R≥0 is a dynamic flow function, where the value fet entering the arc e=v,w at time t also arrives at node w at t+θe. The flow excesses at the node induced by a flow on arcs is denoted by h:V×T⟶R≥0. A directed static network N=V,A,ue is obtained by omitting the time components. For the sake of simplicity, the same functions f and h will be used for static and dynamic flows.


### 2.1. Network Flow Models

#### 2.1.1. Maximum Static Flow Model

The maximum static flow model is to maximize Objective (1) satisfying Constraints (2)–(4):(1)max∑v∈V+hv,(2)∑e∈Av+fe−∑e∈Av−fe=hv,ifv∈V+,0,ifv∈V0,−hv,ifv∈V−,(3)hv≥0,∀v∈V,(4)ue≥fe≥0,∀e∈A,where Av+=v,w∈Aw∈V for v∈V and Av−=u,v∈Au∈V. Outgoing flow from the sources, conservation of flow in intermediate nodes, and entering flow to the sinks are, respectively, shown in Constraint (2). Constraint (4) represents bounds of flows on arcs.


#### 2.1.2. Maximum Dynamic Flow Model

The dynamic network flow model with discrete time setting satisfies Constraints (5)–(8):(5)∑e∈Av+,t≥0fet−∑e∈Av−,t−θe≥0fet−θe=hvt,ifv∈V+,0,ifv∈V0,∀t∈T,−hvt,ifv∈V−,(6)hvt≥0,∀v∈V,∀t∈T,(7)uet≥fet≥0,∀e∈A,∀t∈T,(8)fet=0,∀e∈A,t=T−te+1,T¯.Constraint (8) ensures that the flow does not enter arc e at time t if it will have to leave the arc after the given time horizon. The maximum dynamic flow that can enter the arc e within each integral time step t is bounded by the time varying capacity uet; this is ensured by Constraint (7). Flow conservation conditions are ensured in Constraint (5). Flow value at T is defined in (9) and is to be maximized for the MDF:(9)∑t=0T∑v∈V+hvt.Multiterminal network for single commodity flow can be reduced to the standard two-terminal network by introducing one virtual source node and one virtual sink node. Virtual arcs connect the new source to true sources and true sinks to the new sink. The transit times of these virtual arcs are zero. The capacities of arcs connecting to the virtual source with all other sources are bounded by the capacities of these sources. The capacities of arcs connecting to virtual sink from true sinks are bounded by the capacities of these sinks. Ifθe=0 for all e∈A and T=0, then the formulated problem reduces to the classical maximum flow problem on a static network.


#### 2.1.3. Time-Expanded Flow Model

The dynamic network flow problem inN=V,A,uet,θe,T can be reduced to a static network flow problem in the time-expanded network NT=VT,AT,uT, which is a static representation of the dynamic network. Construction of time-expanded network is as follows:(10)VT≔vt:v∈V,t∈T,AT≔vt,wt+θe:e=v,w∈A,0≤t≤T−θe,with capacity function uetT≔uet,foret∈AT. Let vt,wt+θe∈AT and let fet be a flow in the dynamic network N=V,A,uet,θe,T. The corresponding flow function in the time-expanded network NT=VT,AT,uT is defined by(11)fetT=fvt,wt+θe=fet,∀et∈AT.Relation (11) is a bijection from the set of feasible flows in the dynamic network N=V,A,uet,θe,T to the set of feasible flows in the time-expanded network NT=VT,AT,uT so that dynamic flows fet with time horizon T are equivalent to static flows fetT in the time-expanded network [17].


#### 2.1.4. Minimum Cost Flow Model

Letd:A⟶Z be supply-demand function with supply dv>0 and demand dv<0 for v∈V, and let c:A⟶Z be the cost function. Then, the minimum cost flow formulated as in [1] is(12)min∑e∈Acefe,(13)∑e∈Av+fe−∑e∈Av−fe=dv,∀v∈V,(14)ue≥fe≥0,∀e∈A.The conservation and capacity constraints are given by (13) and (14), respectively. Equation (15) represents the feasibility of supplies and demands. This constraint implies that the total supply is equal to the total demand:(15)∑v∈Vdv=0.The feasibility of minimum cost flow problem can be determined by solving a maximum flow problem [1, 18]. For this, one introduces a supersource node s∗, a supersink node t∗, source arcs s∗,v with capacities dv for v∈V+, and sink arcs v,t∗ with capacities −dv for v∈V−. Recall that ∑v∈V+dv=∑v∈V−dv holds. If the maximum flow saturates all the source arcs, the minimum cost flow problem is feasible; otherwise, it is infeasible.


## 2.1. Network Flow Models

### 2.1.1. Maximum Static Flow Model

The maximum static flow model is to maximize Objective (1) satisfying Constraints (2)–(4):(1)max∑v∈V+hv,(2)∑e∈Av+fe−∑e∈Av−fe=hv,ifv∈V+,0,ifv∈V0,−hv,ifv∈V−,(3)hv≥0,∀v∈V,(4)ue≥fe≥0,∀e∈A,where Av+=v,w∈Aw∈V for v∈V and Av−=u,v∈Au∈V. Outgoing flow from the sources, conservation of flow in intermediate nodes, and entering flow to the sinks are, respectively, shown in Constraint (2). Constraint (4) represents bounds of flows on arcs.


### 2.1.2. Maximum Dynamic Flow Model

The dynamic network flow model with discrete time setting satisfies Constraints (5)–(8):(5)∑e∈Av+,t≥0fet−∑e∈Av−,t−θe≥0fet−θe=hvt,ifv∈V+,0,ifv∈V0,∀t∈T,−hvt,ifv∈V−,(6)hvt≥0,∀v∈V,∀t∈T,(7)uet≥fet≥0,∀e∈A,∀t∈T,(8)fet=0,∀e∈A,t=T−te+1,T¯.Constraint (8) ensures that the flow does not enter arc e at time t if it will have to leave the arc after the given time horizon. The maximum dynamic flow that can enter the arc e within each integral time step t is bounded by the time varying capacity uet; this is ensured by Constraint (7). Flow conservation conditions are ensured in Constraint (5). Flow value at T is defined in (9) and is to be maximized for the MDF:(9)∑t=0T∑v∈V+hvt.Multiterminal network for single commodity flow can be reduced to the standard two-terminal network by introducing one virtual source node and one virtual sink node. Virtual arcs connect the new source to true sources and true sinks to the new sink. The transit times of these virtual arcs are zero. The capacities of arcs connecting to the virtual source with all other sources are bounded by the capacities of these sources. The capacities of arcs connecting to virtual sink from true sinks are bounded by the capacities of these sinks. Ifθe=0 for all e∈A and T=0, then the formulated problem reduces to the classical maximum flow problem on a static network.


### 2.1.3. Time-Expanded Flow Model

The dynamic network flow problem inN=V,A,uet,θe,T can be reduced to a static network flow problem in the time-expanded network NT=VT,AT,uT, which is a static representation of the dynamic network. Construction of time-expanded network is as follows:(10)VT≔vt:v∈V,t∈T,AT≔vt,wt+θe:e=v,w∈A,0≤t≤T−θe,with capacity function uetT≔uet,foret∈AT. Let vt,wt+θe∈AT and let fet be a flow in the dynamic network N=V,A,uet,θe,T. The corresponding flow function in the time-expanded network NT=VT,AT,uT is defined by(11)fetT=fvt,wt+θe=fet,∀et∈AT.Relation (11) is a bijection from the set of feasible flows in the dynamic network N=V,A,uet,θe,T to the set of feasible flows in the time-expanded network NT=VT,AT,uT so that dynamic flows fet with time horizon T are equivalent to static flows fetT in the time-expanded network [17].


### 2.1.4. Minimum Cost Flow Model

Letd:A⟶Z be supply-demand function with supply dv>0 and demand dv<0 for v∈V, and let c:A⟶Z be the cost function. Then, the minimum cost flow formulated as in [1] is(12)min∑e∈Acefe,(13)∑e∈Av+fe−∑e∈Av−fe=dv,∀v∈V,(14)ue≥fe≥0,∀e∈A.The conservation and capacity constraints are given by (13) and (14), respectively. Equation (15) represents the feasibility of supplies and demands. This constraint implies that the total supply is equal to the total demand:(15)∑v∈Vdv=0.The feasibility of minimum cost flow problem can be determined by solving a maximum flow problem [1, 18]. For this, one introduces a supersource node s∗, a supersink node t∗, source arcs s∗,v with capacities dv for v∈V+, and sink arcs v,t∗ with capacities −dv for v∈V−. Recall that ∑v∈V+dv=∑v∈V−dv holds. If the maximum flow saturates all the source arcs, the minimum cost flow problem is feasible; otherwise, it is infeasible.


## 2.1.1. Maximum Static Flow Model

The maximum static flow model is to maximize Objective (1) satisfying Constraints (2)–(4):(1)max∑v∈V+hv,(2)∑e∈Av+fe−∑e∈Av−fe=hv,ifv∈V+,0,ifv∈V0,−hv,ifv∈V−,(3)hv≥0,∀v∈V,(4)ue≥fe≥0,∀e∈A,where Av+=v,w∈Aw∈V for v∈V and Av−=u,v∈Au∈V. Outgoing flow from the sources, conservation of flow in intermediate nodes, and entering flow to the sinks are, respectively, shown in Constraint (2). Constraint (4) represents bounds of flows on arcs.


## 2.1.2. Maximum Dynamic Flow Model

The dynamic network flow model with discrete time setting satisfies Constraints (5)–(8):(5)∑e∈Av+,t≥0fet−∑e∈Av−,t−θe≥0fet−θe=hvt,ifv∈V+,0,ifv∈V0,∀t∈T,−hvt,ifv∈V−,(6)hvt≥0,∀v∈V,∀t∈T,(7)uet≥fet≥0,∀e∈A,∀t∈T,(8)fet=0,∀e∈A,t=T−te+1,T¯.Constraint (8) ensures that the flow does not enter arc e at time t if it will have to leave the arc after the given time horizon. The maximum dynamic flow that can enter the arc e within each integral time step t is bounded by the time varying capacity uet; this is ensured by Constraint (7). Flow conservation conditions are ensured in Constraint (5). Flow value at T is defined in (9) and is to be maximized for the MDF:(9)∑t=0T∑v∈V+hvt.Multiterminal network for single commodity flow can be reduced to the standard two-terminal network by introducing one virtual source node and one virtual sink node. Virtual arcs connect the new source to true sources and true sinks to the new sink. The transit times of these virtual arcs are zero. The capacities of arcs connecting to the virtual source with all other sources are bounded by the capacities of these sources. The capacities of arcs connecting to virtual sink from true sinks are bounded by the capacities of these sinks. Ifθe=0 for all e∈A and T=0, then the formulated problem reduces to the classical maximum flow problem on a static network.


## 2.1.3. Time-Expanded Flow Model

The dynamic network flow problem inN=V,A,uet,θe,T can be reduced to a static network flow problem in the time-expanded network NT=VT,AT,uT, which is a static representation of the dynamic network. Construction of time-expanded network is as follows:(10)VT≔vt:v∈V,t∈T,AT≔vt,wt+θe:e=v,w∈A,0≤t≤T−θe,with capacity function uetT≔uet,foret∈AT. Let vt,wt+θe∈AT and let fet be a flow in the dynamic network N=V,A,uet,θe,T. The corresponding flow function in the time-expanded network NT=VT,AT,uT is defined by(11)fetT=fvt,wt+θe=fet,∀et∈AT.Relation (11) is a bijection from the set of feasible flows in the dynamic network N=V,A,uet,θe,T to the set of feasible flows in the time-expanded network NT=VT,AT,uT so that dynamic flows fet with time horizon T are equivalent to static flows fetT in the time-expanded network [17].


## 2.1.4. Minimum Cost Flow Model

Letd:A⟶Z be supply-demand function with supply dv>0 and demand dv<0 for v∈V, and let c:A⟶Z be the cost function. Then, the minimum cost flow formulated as in [1] is(12)min∑e∈Acefe,(13)∑e∈Av+fe−∑e∈Av−fe=dv,∀v∈V,(14)ue≥fe≥0,∀e∈A.The conservation and capacity constraints are given by (13) and (14), respectively. Equation (15) represents the feasibility of supplies and demands. This constraint implies that the total supply is equal to the total demand:(15)∑v∈Vdv=0.The feasibility of minimum cost flow problem can be determined by solving a maximum flow problem [1, 18]. For this, one introduces a supersource node s∗, a supersink node t∗, source arcs s∗,v with capacities dv for v∈V+, and sink arcs v,t∗ with capacities −dv for v∈V−. Recall that ∑v∈V+dv=∑v∈V−dv holds. If the maximum flow saturates all the source arcs, the minimum cost flow problem is feasible; otherwise, it is infeasible.


## 3. Maximum Flow Improvement Problems

### 3.1. Static Flow Improvements

In the maximum static flow improvement problem (MSFIP), an additional nonnegative numberUe, for each e∈A, is given so that the capacity ue can be increased with some nonnegative cost up to the upper bound Ue≥ue. The improvement capacity function with nonnegative unit cost be is defined as I:A⟶Q≥0. The objective of the problem is to maximize the flow from the sources to sinks by increasing the capacities of arcs within the budget restriction where incremental cost is to be accepted to increase arc capacity. Flow improvement problems (16)–(22) have been formulated as in [5]:(16)∑e∈Av+fe−∑e∈Av−fe=hv,ifv∈V+,0,ifv∈V0,−hv,ifv∈V−,(17)hv≥0,∀v∈V,(18)Ie≥0,∀e∈A,(19)ue+Ie≥fe≥0,∀e∈A,(20)Ue≥ue+Ie≥0,∀e∈A,(21)∑e∈AIebe≤B.Constraint (19) controls the arc flows, Constraint (20) limits capacity increment, and Constraint (21) bounds the total capacity incremental cost B with b as the unit cost. By denoting Fst to be the sum of flow out from the source that enter into the sink, the objective function equals(22)Fst=∑v∈V+hv.Problem 1.
The MSFIP with capacity improvement cost is maximum static flow problems (16)–(22), where capacity of arcs with unit costs can be increased up to specified limit bounded by the improvement cost.
The MSFIP with continuous improvement strategy, in which the improvement functionIe takes any rational values respecting the upper bound, can be solved optimally in polynomial time. The integral MSFIP that takes only integral improvements can be transformed into a budget constraint minimum cost flow problem in polynomial time.
Assume that the unit costbe of increasing the capacity of arc e is a nonnegative number and also assume that the optimal flow improvement corresponding to the arc e is Ie∗=max0,fe∗−ue, where f∗ is the optimal improved maximum flow. Otherwise, the strategy would waste the cost. Such a behavior can be modeled by a flow cost ce defined as(23)cef=0,for0≤f≤ue,be⋅f−ue,forue<f≤Ue,∀e∈A.
By definition,ce is a piecewise-linear convex function. In this case, each e∈A is replaced by two parallel arcs e0 and e1 to make it linear. The capacities u¯e and linear costs c¯e of these arcs are set as(24)u¯e0≔u¯e,u¯e1≔Ue−ue,c¯e0≔0,c¯e1≔be.
This construction is valid from the convexity of cost function. Thus, the improved maximum flow valueFst∗ can be obtained by solving minimum cost flow with cost at most B by the method of binary search in 0,nUmax.Theorem 1.
(see [5]). The integral MSFIP can be solved optimally in polynomial time by OlognUmax minimum cost flow computations in a directed network with 2m arcs, where Umax=maxUe:e∈A is the maximum capacity.Instead of performing a binary search on the interval0,nUmax, the interval can be searched only in multiplicative steps of 1+ϵ, where ϵ>0 is a fixed accuracy parameter. The value Fst′ found by this modified binary search satisfies Fst′≥Fst∗/1+ϵ.Theorem 2.
(see [5]). Let ϵ>0 be fixed. Then, a 1+ϵ-approximation for MSFIP can be obtained in Ologlog1+ϵnUmax minimum cost flow computations in the directed graph with 2m arcs.Each of the minimum cost flow computations have to be carried out in a graph withOgm arcs, where g is the maximum number of breakpoints occurring in the piecewise-linear cost functions. Furthermore, one can solve the problem in strongly polynomial time applying Megiddo’s parametric search [19]. The same search can be applied to solve the rational MSFIP, too.The flow improvement strategy, either to increase the capacity of each arc to its maximum capacity or leave the capacity of arc unchanged, isNP-hard. This 0/1 MSFIP is equivalent to the maximum flow problem with fixed cost on arcs. For given nonnegative capacity ue and cost ce on each e∈A, the latter problem asks to find a subset A∗ of A such that ∑e∈A∗ce≤B and the source-sink flow is maximized. But, the decision variant of this problem is NP-complete. We state the following.Theorem 3.
(see [5]). The maximum flow problem with fixed cost on arcs is NP-hard even on series-parallel and bipartite graphs.The pseudo-polynomial time algorithm for the maximum fixed cost flow problem on series-parallel graphs is presented. They are converted into a fully polynomial time approximation scheme by the scaling technique.Theorem 4.
(see [5]). When the problems are restricted to series-parallel graphs, the maximum flow problem with fixed cost on arcs and 0/1 MSFIP can be solved with fully polynomial time approximation scheme.


### 3.2. Dynamic Flow Improvements

This section extends the MSFIP to maximum dynamic flow improvement problem (MDFIP) considering the time factor. LetIt and bt be capacity improvement and improvement unit cost functions in dynamic network, respectively. The proposed MDFIP can be formulated as follows:(25)max∑t=0T∑v∈V+hvt,(26)subject to∑e∈Av+fet−∑e∈Av−,t−θe≥0fet−θe=hvt,ifv∈V+,0,ifv∈V0,∀t∈T,−hvt,ifv∈V−,(27)hvt≥0,∀v∈V,∀t∈T,(28)Iet≥0,∀e∈A,∀t∈T,(29)fet=0,∀e∈A,t=T−te+1,T¯,(30)uet+Iet≥fet≥0,∀e∈A,∀t∈T,(31)Uet≥uet+Iet≥0,∀e∈A,∀t∈T,(32)∑t=0T∑e∈AIetbet≤B.This is an extension of MDF where Budget Constraint (32) has been imposed to bound the capacity improvement cost, Constraint (31) deals with the maximum possible improvement, and Constraint (30) deals with the feasibility of flow with improved capacity.Letvt,wt+θe∈AT and let Iet be the capacity improvement on arc e∈A; then, the capacity improvement function could be defined as IetT=Ivt,wt+θe=Iet,for allet∈AT. Each dynamic network can be transformed into the corresponding time-expanded network for a given time horizon. The maximum dynamic flow in the given network is equal to the maximum flow in time-expanded network [1].Problem 2.
The MDFIP with capacity improvement cost is the MDF, where capacities of arcs can be increased up to a specified limit accepting the improvement cost.Theorem 5.
The integral and continuous flow improvement problems in dynamic network can be solved optimally in pseudo-polynomial time.Proof.
Let us transform the given integral MDFIP in the dynamic network into the MSFIP in the corresponding static network assumingVT≔vt:v∈V,t∈T, AT≔vt,wt+θe:e=v,w∈A,0≤t≤T−θe, uetT≔uet, IetT≔Ivt,wt+θe=Iet, andbetT≔bet∀et∈AT. Let vt,wt+θe∈AT and let fet be a flow in the dynamic network N=V,A,uet,θe,T; then, the corresponding flow function in NT=VT,AT,uT can be related by(33)fetT≔fvt,wt+θe=fetfor allet∈AT.
Relation (33) is a bijection from the set of feasible flows in the dynamic network N=V,A,uet,θe,T to the set of feasible flows in NT=VT,AT,uT so that dynamic flows fet with time horizon T are equivalent to static flows fetT in NT=VT,AT,uT. Thus, the flow improvement problem in dynamic network N=V,A,uet,θe,T with time horizon T, capacity improvement Iet, and improvement cost bet is equivalent to the flow improvement problem in static network NT=VT,AT,uT with capacity improvement IetT and improvement cost betT. As the integral maximum flow improvement problem in static network can also be solved optimally (cf. Theorem 1), the integral MDFIP can also be solved optimally.
With similar arguments, the continuous MDFIP can be solved optimally in pseudo-polynomial time. □
The dynamic improvement and dynamic improvement cost have been considered in (25)–(32). While constructing time-expanded network in the proof of Theorem 5, they are transformed into static improvement and static improvement cost by applying the transformations IetT≔Ivt,wt+θe=IetandbetT≔bet∀et∈AT, respectively. If one consider improvement and its cost both static in (25)–(32), the time-expanded network copies the arc with the same improved capacity for every arc of the dynamic network. These modifications ensure that each copy of the same arc is improved by the same amount of capacity and the improvement cost of an arc is counted only once for all of its copies.


## 3.1. Static Flow Improvements

In the maximum static flow improvement problem (MSFIP), an additional nonnegative numberUe, for each e∈A, is given so that the capacity ue can be increased with some nonnegative cost up to the upper bound Ue≥ue. The improvement capacity function with nonnegative unit cost be is defined as I:A⟶Q≥0. The objective of the problem is to maximize the flow from the sources to sinks by increasing the capacities of arcs within the budget restriction where incremental cost is to be accepted to increase arc capacity. Flow improvement problems (16)–(22) have been formulated as in [5]:(16)∑e∈Av+fe−∑e∈Av−fe=hv,ifv∈V+,0,ifv∈V0,−hv,ifv∈V−,(17)hv≥0,∀v∈V,(18)Ie≥0,∀e∈A,(19)ue+Ie≥fe≥0,∀e∈A,(20)Ue≥ue+Ie≥0,∀e∈A,(21)∑e∈AIebe≤B.Constraint (19) controls the arc flows, Constraint (20) limits capacity increment, and Constraint (21) bounds the total capacity incremental cost B with b as the unit cost. By denoting Fst to be the sum of flow out from the source that enter into the sink, the objective function equals(22)Fst=∑v∈V+hv.Problem 1.
The MSFIP with capacity improvement cost is maximum static flow problems (16)–(22), where capacity of arcs with unit costs can be increased up to specified limit bounded by the improvement cost.
The MSFIP with continuous improvement strategy, in which the improvement functionIe takes any rational values respecting the upper bound, can be solved optimally in polynomial time. The integral MSFIP that takes only integral improvements can be transformed into a budget constraint minimum cost flow problem in polynomial time.
Assume that the unit costbe of increasing the capacity of arc e is a nonnegative number and also assume that the optimal flow improvement corresponding to the arc e is Ie∗=max0,fe∗−ue, where f∗ is the optimal improved maximum flow. Otherwise, the strategy would waste the cost. Such a behavior can be modeled by a flow cost ce defined as(23)cef=0,for0≤f≤ue,be⋅f−ue,forue<f≤Ue,∀e∈A.
By definition,ce is a piecewise-linear convex function. In this case, each e∈A is replaced by two parallel arcs e0 and e1 to make it linear. The capacities u¯e and linear costs c¯e of these arcs are set as(24)u¯e0≔u¯e,u¯e1≔Ue−ue,c¯e0≔0,c¯e1≔be.
This construction is valid from the convexity of cost function. Thus, the improved maximum flow valueFst∗ can be obtained by solving minimum cost flow with cost at most B by the method of binary search in 0,nUmax.Theorem 1.
(see [5]). The integral MSFIP can be solved optimally in polynomial time by OlognUmax minimum cost flow computations in a directed network with 2m arcs, where Umax=maxUe:e∈A is the maximum capacity.Instead of performing a binary search on the interval0,nUmax, the interval can be searched only in multiplicative steps of 1+ϵ, where ϵ>0 is a fixed accuracy parameter. The value Fst′ found by this modified binary search satisfies Fst′≥Fst∗/1+ϵ.Theorem 2.
(see [5]). Let ϵ>0 be fixed. Then, a 1+ϵ-approximation for MSFIP can be obtained in Ologlog1+ϵnUmax minimum cost flow computations in the directed graph with 2m arcs.Each of the minimum cost flow computations have to be carried out in a graph withOgm arcs, where g is the maximum number of breakpoints occurring in the piecewise-linear cost functions. Furthermore, one can solve the problem in strongly polynomial time applying Megiddo’s parametric search [19]. The same search can be applied to solve the rational MSFIP, too.The flow improvement strategy, either to increase the capacity of each arc to its maximum capacity or leave the capacity of arc unchanged, isNP-hard. This 0/1 MSFIP is equivalent to the maximum flow problem with fixed cost on arcs. For given nonnegative capacity ue and cost ce on each e∈A, the latter problem asks to find a subset A∗ of A such that ∑e∈A∗ce≤B and the source-sink flow is maximized. But, the decision variant of this problem is NP-complete. We state the following.Theorem 3.
(see [5]). The maximum flow problem with fixed cost on arcs is NP-hard even on series-parallel and bipartite graphs.The pseudo-polynomial time algorithm for the maximum fixed cost flow problem on series-parallel graphs is presented. They are converted into a fully polynomial time approximation scheme by the scaling technique.Theorem 4.
(see [5]). When the problems are restricted to series-parallel graphs, the maximum flow problem with fixed cost on arcs and 0/1 MSFIP can be solved with fully polynomial time approximation scheme.


## 3.2. Dynamic Flow Improvements

This section extends the MSFIP to maximum dynamic flow improvement problem (MDFIP) considering the time factor. LetIt and bt be capacity improvement and improvement unit cost functions in dynamic network, respectively. The proposed MDFIP can be formulated as follows:(25)max∑t=0T∑v∈V+hvt,(26)subject to∑e∈Av+fet−∑e∈Av−,t−θe≥0fet−θe=hvt,ifv∈V+,0,ifv∈V0,∀t∈T,−hvt,ifv∈V−,(27)hvt≥0,∀v∈V,∀t∈T,(28)Iet≥0,∀e∈A,∀t∈T,(29)fet=0,∀e∈A,t=T−te+1,T¯,(30)uet+Iet≥fet≥0,∀e∈A,∀t∈T,(31)Uet≥uet+Iet≥0,∀e∈A,∀t∈T,(32)∑t=0T∑e∈AIetbet≤B.This is an extension of MDF where Budget Constraint (32) has been imposed to bound the capacity improvement cost, Constraint (31) deals with the maximum possible improvement, and Constraint (30) deals with the feasibility of flow with improved capacity.Letvt,wt+θe∈AT and let Iet be the capacity improvement on arc e∈A; then, the capacity improvement function could be defined as IetT=Ivt,wt+θe=Iet,for allet∈AT. Each dynamic network can be transformed into the corresponding time-expanded network for a given time horizon. The maximum dynamic flow in the given network is equal to the maximum flow in time-expanded network [1].Problem 2.
The MDFIP with capacity improvement cost is the MDF, where capacities of arcs can be increased up to a specified limit accepting the improvement cost.Theorem 5.
The integral and continuous flow improvement problems in dynamic network can be solved optimally in pseudo-polynomial time.Proof.
Let us transform the given integral MDFIP in the dynamic network into the MSFIP in the corresponding static network assumingVT≔vt:v∈V,t∈T, AT≔vt,wt+θe:e=v,w∈A,0≤t≤T−θe, uetT≔uet, IetT≔Ivt,wt+θe=Iet, andbetT≔bet∀et∈AT. Let vt,wt+θe∈AT and let fet be a flow in the dynamic network N=V,A,uet,θe,T; then, the corresponding flow function in NT=VT,AT,uT can be related by(33)fetT≔fvt,wt+θe=fetfor allet∈AT.
Relation (33) is a bijection from the set of feasible flows in the dynamic network N=V,A,uet,θe,T to the set of feasible flows in NT=VT,AT,uT so that dynamic flows fet with time horizon T are equivalent to static flows fetT in NT=VT,AT,uT. Thus, the flow improvement problem in dynamic network N=V,A,uet,θe,T with time horizon T, capacity improvement Iet, and improvement cost bet is equivalent to the flow improvement problem in static network NT=VT,AT,uT with capacity improvement IetT and improvement cost betT. As the integral maximum flow improvement problem in static network can also be solved optimally (cf. Theorem 1), the integral MDFIP can also be solved optimally.
With similar arguments, the continuous MDFIP can be solved optimally in pseudo-polynomial time. □
The dynamic improvement and dynamic improvement cost have been considered in (25)–(32). While constructing time-expanded network in the proof of Theorem 5, they are transformed into static improvement and static improvement cost by applying the transformations IetT≔Ivt,wt+θe=IetandbetT≔bet∀et∈AT, respectively. If one consider improvement and its cost both static in (25)–(32), the time-expanded network copies the arc with the same improved capacity for every arc of the dynamic network. These modifications ensure that each copy of the same arc is improved by the same amount of capacity and the improvement cost of an arc is counted only once for all of its copies.


## 4. Flow Improvements with Arc Switching Costs

Contraflow approach increases the flow value by reversing the directions of arcs towards the sinks as a flow towards the sources is neither preferred nor expected in emergencies. This concept without any reversal cost is first incorporated in [20] and analytically studied in [7], where the arc is reversed with its full capacity or left as it is. However, a reversal may require some switching costs. Different contraflow models and solution procedures with switching costs are considered throughout this section.Figure1 explains how contraflow works in time invariant network, where there is no arc reversal cost. Given network N=V,A,ue,θe,T, the contraflow uses an auxiliary network N˜=V,A˜,u˜,θ˜,T, where the set of arcs A˜ contains e˜ if e=v,w∈A or er=w,v∈A. The capacity and symmetric transit time functions are considered as u˜e˜≔ue+uer and θ˜e˜≔θefore∈Aθerelse∀e˜∈A˜, respectively. Other parameters of the given network remain the same.Figure 1
Network with capacities and transit times, respectively. (a) Evacuation network. (b) Auxiliary network.
(a)(b)


### 4.1. Maximum Static Flow Problem

The maximum static contraflow problem (MSCFP) introduced in [7] maximizes the source-sink flow value, where directions of arcs have been reversed without considering the reversal costs. In this section, we introduce budget constraint MSCFP and propose its solution procedure for a two-terminal network.The switching cost contraflow (SCCF) finds a feasible flow inN=V,A,ue, where the arc directions can be reversed accepting switching costs whenever flow can be improved. The static SCCF problem has a similar structure as the minimum concave-cost network flow problem [21]. These problems ask to find a feasible flow while minimizing the total cost. The total cost is the sum of concave-costs due to the use of arcs by feasible flow. It can be assumed that the concave-cost per arc consists of a fixed cost, whenever this particular arc is used, and a variable cost depends on the amount of flow. Fixing the variable cost to zero leads to a special problem called minimum cost fixed flow (MCFF) problem. The improvement strategy function I is a 0/1 decision if additional capacity is used or not, independent of how much additional capacity is used. An integral flow improvement strategy is considered throughout this section.Problem 3.
The MSCFP with switching cost is the maximum flow problem in the static network where arcs can be reversed accepting some switching costs and total cost is restricted by a given budget. This problem is denoted by MSCFPWSC (Algorithm1).Algorithm 1:Maximum static contraflow with switching cost (MSCFAWSC).
Input: two-terminal arc reversible network N=V,A,ue with reversal budget B and reversal cost be(1)
Construct an auxiliary network,N˜=V,A˜,u˜e˜ with new capacity u˜e˜=ue→+ue←(2)
Define the cost function byce˜f=0for0≤fe˜≤ue→be←⋅fe˜−ue→forue→<fe˜≤u˜e˜for alle˜∈A˜(3)
Transform the cost and the capacity functions byu¯e0≔ue→u¯e1≔u˜e˜−ue→c¯e0≔0c¯e1≔be←(4)
Find the optimal flowFst∗ in the auxiliary network considering costs defined in Step 3 and the total budget B, by applying binary search in 0,nU˜max, where U˜max=maxu˜e˜:e˜∈A˜(5)
An arce←∈A is reversed with capacity fe˜−ue→ if and only if the flow along e→∈A is greater than ue→ or there is a nonnegative flow along the arc e→∉AOutput: maximum contraflow value in N=V,A,ue using arc reversal budget BTheorem 6.
Algorithm1 solves Problem 3 optimally in polynomial time for integral reversed capacity.Proof.
Step 1 constructs an auxiliary network from the given network which is feasible. Step 2 defines the cost function for the improved capacity which is convex and nonlinear, whereas Step 3 is to linearize the cost function defined in Step 2. Thus, both these steps are feasible. Step 4 finds the optimal flowFst∗ in N˜=V,A˜,u˜e˜ using the binary search method in 0,nU˜max, and Step 5 reverses the direction of arcs according to the direction of the flow obtained in Step 4. So, Step 4 and Step 5 are also feasible. Hence, the algorithm is feasible.
To restrict on budget, this algorithm only reverses the required capacity of the arc so thatIe=max0,fe˜−ue⟶, where fe˜ represents the flow through the arc e˜. Cost for the reversed capacity is defined in Step 2 which is not linear but convex and is linearized in Step 3, as in [5, 22]. Then, MSCFP with switching cost is equivalent to the budget constraint maximum flow improvement problem with integral improvement which is equivalent to the budget constraint minimum cost flow problem. Thus, Problem 3 is equivalent to the budget constraint minimum cost flow problem. Suppose Fst∗ be the optimal integral flow achievable on budget B which can be obtained by the method of binary search in 0,nU˜max [5].
Step 1 constructs an auxiliary network in linear time and is similar for Step 2 and Step 3. Step 5 reverses the arc directions in linear time according to the flow obtained in Step 4 since not both of the arcse⟶ and e← have to be switched at a time. Thus, running time of the algorithm depends on Step 4. Hence, Algorithm 1 solves Problem 3 in OlognU˜max minimum cost flow computations.Algorithm1 reverses the direction of arcs with integral capacity; thus, the improvement is integral. This implies that the optimal flow of the problem is integral. For this, the binary search algorithm can test only for the integral flow values of the interval. Instead of applying binary search in the interval, one can apply Megiddo’s parametric search [19] to extract the solution in Step 4 of Algorithm 1.The maximum valueFst′ satisfying the budget constraint lies in 1,1+ϵ,…,1+ϵk, where k=⌈log1+ϵnU˜max⌉ and ϵ>0 is a fixed accuracy parameter. This modified binary search finds new value such that Fst′≥Fst∗/1+ϵ. If such modification is applied in Step 4 of Algorithm 1, a 1+ϵ approximation for budget constrained maximum contraflow can be obtained in Ologlog1+ϵnU˜max minimum cost flow computations, where ϵ>0 is a fixed accuracy parameter.Example 1.
LetB=20 be the total reversal budget for the evacuation network as shown in Figure 2. Before contraflow configuration, 10 units of flow could be reached in the sink from the source through the paths s−x−t and s−y−t. Likewise, 19 units of flow could be sent through paths s−x−t, s−y−t, and s−y−x−t (cf. Figure 2(b)) applying the contraflow approach for which B=37 is required for the complete arc reversals which is more than the given budget. This means that the upper bound of the budget constraint contraflow is 37. The budget constraint contraflow can be found applying Algorithm 1.
The optimal budget constraint flow in the auxiliary network in Figure1(b) corresponding to Figure 2(a) can be obtained using Step 4. In this network, U˜max=maxu˜e˜e˜∈A˜=max10,9,3,10,9=10. Thus, the flow can be obtained in 0,4×10=0,40 as n≔V. Here, the midpoint of the interval is 20 but it is infeasible so that the flow should be searched in the lower interval 0,19. Again, a middle value of the interval is 10 and its minimum cost is zero as 5 units of flow can be sent through both paths s−x−t and s−y−t without reversing any arcs. The objective of the problem is to maximize the flow under the given budget so that flow should be searched in the upper interval 11,19. The middle value is 15. Its minimum cost is 17 as the reversed arcs are x,s,t,x,andx,y with capacities 4,4,and1, respectively. Here, we reverse the arc x,y only with capacity 1 as the budget should not be wasted. The resulting network flow is shown in Figure 2(c). Next, the possible upper value should be searched in 16,19. Let us check the cost for 17. For this, the minimum cost is 27 which exceeds the given budget, and thus, it is infeasible. Similarly, the minimum cost is checked for 16 units of flow which is 22. Again, this exceeds the budget. Hence, the budget constraint contraflow is 15 which is shown in Figure 2(c) for which 17 units of budget have been used. Still, 3 units of budget remain unused but they are insufficient.Figure 2
Evacuation network, contraflow without budget constraint and contraflow with budget constraint, respectively. (a) Capacity, unit cost. (b, c) Capacity, flow.
(a)(b)(c)Theorem 7.
The fixed switching cost contraflow problem is equivalent to0/1-MSFIP where all data to be positive integral [7].Since the0/1 maximum flow improvement is equivalent to the maximum fixed cost flow problem, this implies that the FSCCF is NP-hard to solve (Theorem 3). The fixed cost for arc reversals makes the problem NP-hard, even in the static case. The static contraflow algorithm is ’blind’ for the arc reversal decisions. Adding a time component to FSCCF makes it practically even more difficult to solve. Based on the above results, the following theorems are proposed.Theorem 8.
The FSCCF problem isNP-hard even in series-parallel graphs.Proof.
The FSCCF problem is equivalent to0/1-MSFIP (Theorem 7). As the maximum flow problem with fixed cost on arcs is equivalent to 0/1-maximum flow improvement [5], then by Theorem 3, it can be claimed that the FSCCF problem is NP-hard even in series-parallel graphs.Theorem 9.
There is a fully polynomial time approximation scheme for the FSCCF problems when the problems are restricted to series-parallel graphs.Proof.
As in proof of Theorem8, the FSCCF problem is equivalent to 0/1-MSFIP and the maximum flow problem with fixed costs on arcs. Since all hardness and approximation results of these problems will be carried over to the FSCCF problem so that a fully polynomial time approximation scheme can be obtained for the FSCCF problems in series-parallel graphs (Theorem 4).As the fixed switching cost contraflow problem is equivalent to the0/1 maximum flow improvement which is equivalent to the minimum cost fixed flow problem, an approximation solution can be found by using the cost-to-time ratio approach [5, 18]. This can be obtained by assuming the capacities ue and unit cost ce/ue.


### 4.2. Maximum Dynamic Flow Problem

The notion of MDF is introduced and solved in [7] by reversing the arcs at time zero with zero cost. In this section, reversal cost is considered to maximize the dynamic contraflow subject to budget constraint which is an extension of MSCFP from static to dynamic networks.Problem 4.
The MDCF problem with switching cost is the MDF where arcs can be reversed accepting switching cost such that the total cost is subject to the budget constraint. It is denoted by MDCFPWSC.Theorem 10.
Algorithm2 solves Problem 4 optimally in pseudo-polynomial time.Proof.
Step 1 is well defined as it transforms the given dynamic network flow problem into the static network flow problem. The feasibility of other steps of the algorithm can be shown as in Theorem6. Thus, the algorithm is feasible.
The dynamic network can be transformed into static network as in Step 1. Step 2 constructs the auxiliary network, and Step 6 finds an optimal flow in auxiliary network with respect to the cost defined in Step 5 and total budgetB. Let fet be the budget constraint contraflow in the dynamic network. Then, the corresponding budget constraint flow function in the network N˜T=VT,A˜T,u˜T can be related by the following equation:(34)fe˜tT=fvt,wt+θe˜=fet,∀e˜t∈A˜T.
It is a bijection from the set of feasible budget constraint contraflows in the dynamic networkN=V,A,uet,θe,T to the set of feasible budget constraint flows in N˜T=VT,A˜T,u˜T so that the contraflows fet with time horizon T are equivalent to the flows fe˜tT in the time-expanded network. Remaining proof of the theorem can be shown as in Theorem 6. Suppose Fdy∗ be the optimal contraflow achievable on budget B. Hence, the optimal contraflow can be obtained in OlogTnU˜max minimum cost flow computations.Algorithm 2: Maximum dynamic contraflow with switching cost (MDCFAWSC).
Input: two-terminal arc reversible network N=V,A,uet,θe,T with reversal budget B, reversal cost bet, and symmetric arc capacity(1)
Transform the given dynamic network into the time-expanded network byVT≔vt:v∈V,t∈TAT≔vt,wt+θee=v,w∈A,0≤t≤T−θeuetT≔uet,foret∈ATbetT≔bet,foret∈ATcapacities and costs of holdover arcs are infinity and zero, respectively(2)
Construct an auxiliaryN˜T=VT,A˜T,u˜T as e˜t∈A˜ife→t=vt,wt+θe∈AT or e←t=wt−θe,vt∈AT with new capacity u˜e˜tT=ue→tT+ue←tTfor alle˜t∈A˜T(3)
Define the cost function byce˜tTfe˜tT=0for0≤fe˜tT≤ue→tTbe→tT⋅fe˜tT−ue→tTforue→tT<fe˜tT≤u˜e˜tTfor alle˜t∈A˜T(4)
Transform the cost and the capacity functions byu¯e0T≔ue→tTu¯e1T≔u˜e˜tT−ue→tTc¯e0T≔0c¯e1T≔be←tT(5)
Find the optimal flow in the auxiliary network considering budgetB and the cost defined in Step 4 using binary search in 0,nTU˜max, where U˜max=maxu˜e˜tT:e˜t∈A˜T(6)
An arce←t∈AT is reversed with capacity f˜e˜tT−ue→tT if and only if the flow along e→t∈AT is greater than ue→tT or there is a nonnegative flow along the arc e→t∉AT(7)
Reconstruct the dynamic network flow from the static network flow according to the flow obtained in Step 5 and arc reversal in Step 6Output: Maximum dynamic contraflow in N=V,A,uet,θe,T with respect to budget B


## 4.1. Maximum Static Flow Problem

The maximum static contraflow problem (MSCFP) introduced in [7] maximizes the source-sink flow value, where directions of arcs have been reversed without considering the reversal costs. In this section, we introduce budget constraint MSCFP and propose its solution procedure for a two-terminal network.The switching cost contraflow (SCCF) finds a feasible flow inN=V,A,ue, where the arc directions can be reversed accepting switching costs whenever flow can be improved. The static SCCF problem has a similar structure as the minimum concave-cost network flow problem [21]. These problems ask to find a feasible flow while minimizing the total cost. The total cost is the sum of concave-costs due to the use of arcs by feasible flow. It can be assumed that the concave-cost per arc consists of a fixed cost, whenever this particular arc is used, and a variable cost depends on the amount of flow. Fixing the variable cost to zero leads to a special problem called minimum cost fixed flow (MCFF) problem. The improvement strategy function I is a 0/1 decision if additional capacity is used or not, independent of how much additional capacity is used. An integral flow improvement strategy is considered throughout this section.Problem 3.
The MSCFP with switching cost is the maximum flow problem in the static network where arcs can be reversed accepting some switching costs and total cost is restricted by a given budget. This problem is denoted by MSCFPWSC (Algorithm1).Algorithm 1:Maximum static contraflow with switching cost (MSCFAWSC).
Input: two-terminal arc reversible network N=V,A,ue with reversal budget B and reversal cost be(1)
Construct an auxiliary network,N˜=V,A˜,u˜e˜ with new capacity u˜e˜=ue→+ue←(2)
Define the cost function byce˜f=0for0≤fe˜≤ue→be←⋅fe˜−ue→forue→<fe˜≤u˜e˜for alle˜∈A˜(3)
Transform the cost and the capacity functions byu¯e0≔ue→u¯e1≔u˜e˜−ue→c¯e0≔0c¯e1≔be←(4)
Find the optimal flowFst∗ in the auxiliary network considering costs defined in Step 3 and the total budget B, by applying binary search in 0,nU˜max, where U˜max=maxu˜e˜:e˜∈A˜(5)
An arce←∈A is reversed with capacity fe˜−ue→ if and only if the flow along e→∈A is greater than ue→ or there is a nonnegative flow along the arc e→∉AOutput: maximum contraflow value in N=V,A,ue using arc reversal budget BTheorem 6.
Algorithm1 solves Problem 3 optimally in polynomial time for integral reversed capacity.Proof.
Step 1 constructs an auxiliary network from the given network which is feasible. Step 2 defines the cost function for the improved capacity which is convex and nonlinear, whereas Step 3 is to linearize the cost function defined in Step 2. Thus, both these steps are feasible. Step 4 finds the optimal flowFst∗ in N˜=V,A˜,u˜e˜ using the binary search method in 0,nU˜max, and Step 5 reverses the direction of arcs according to the direction of the flow obtained in Step 4. So, Step 4 and Step 5 are also feasible. Hence, the algorithm is feasible.
To restrict on budget, this algorithm only reverses the required capacity of the arc so thatIe=max0,fe˜−ue⟶, where fe˜ represents the flow through the arc e˜. Cost for the reversed capacity is defined in Step 2 which is not linear but convex and is linearized in Step 3, as in [5, 22]. Then, MSCFP with switching cost is equivalent to the budget constraint maximum flow improvement problem with integral improvement which is equivalent to the budget constraint minimum cost flow problem. Thus, Problem 3 is equivalent to the budget constraint minimum cost flow problem. Suppose Fst∗ be the optimal integral flow achievable on budget B which can be obtained by the method of binary search in 0,nU˜max [5].
Step 1 constructs an auxiliary network in linear time and is similar for Step 2 and Step 3. Step 5 reverses the arc directions in linear time according to the flow obtained in Step 4 since not both of the arcse⟶ and e← have to be switched at a time. Thus, running time of the algorithm depends on Step 4. Hence, Algorithm 1 solves Problem 3 in OlognU˜max minimum cost flow computations.Algorithm1 reverses the direction of arcs with integral capacity; thus, the improvement is integral. This implies that the optimal flow of the problem is integral. For this, the binary search algorithm can test only for the integral flow values of the interval. Instead of applying binary search in the interval, one can apply Megiddo’s parametric search [19] to extract the solution in Step 4 of Algorithm 1.The maximum valueFst′ satisfying the budget constraint lies in 1,1+ϵ,…,1+ϵk, where k=⌈log1+ϵnU˜max⌉ and ϵ>0 is a fixed accuracy parameter. This modified binary search finds new value such that Fst′≥Fst∗/1+ϵ. If such modification is applied in Step 4 of Algorithm 1, a 1+ϵ approximation for budget constrained maximum contraflow can be obtained in Ologlog1+ϵnU˜max minimum cost flow computations, where ϵ>0 is a fixed accuracy parameter.Example 1.
LetB=20 be the total reversal budget for the evacuation network as shown in Figure 2. Before contraflow configuration, 10 units of flow could be reached in the sink from the source through the paths s−x−t and s−y−t. Likewise, 19 units of flow could be sent through paths s−x−t, s−y−t, and s−y−x−t (cf. Figure 2(b)) applying the contraflow approach for which B=37 is required for the complete arc reversals which is more than the given budget. This means that the upper bound of the budget constraint contraflow is 37. The budget constraint contraflow can be found applying Algorithm 1.
The optimal budget constraint flow in the auxiliary network in Figure1(b) corresponding to Figure 2(a) can be obtained using Step 4. In this network, U˜max=maxu˜e˜e˜∈A˜=max10,9,3,10,9=10. Thus, the flow can be obtained in 0,4×10=0,40 as n≔V. Here, the midpoint of the interval is 20 but it is infeasible so that the flow should be searched in the lower interval 0,19. Again, a middle value of the interval is 10 and its minimum cost is zero as 5 units of flow can be sent through both paths s−x−t and s−y−t without reversing any arcs. The objective of the problem is to maximize the flow under the given budget so that flow should be searched in the upper interval 11,19. The middle value is 15. Its minimum cost is 17 as the reversed arcs are x,s,t,x,andx,y with capacities 4,4,and1, respectively. Here, we reverse the arc x,y only with capacity 1 as the budget should not be wasted. The resulting network flow is shown in Figure 2(c). Next, the possible upper value should be searched in 16,19. Let us check the cost for 17. For this, the minimum cost is 27 which exceeds the given budget, and thus, it is infeasible. Similarly, the minimum cost is checked for 16 units of flow which is 22. Again, this exceeds the budget. Hence, the budget constraint contraflow is 15 which is shown in Figure 2(c) for which 17 units of budget have been used. Still, 3 units of budget remain unused but they are insufficient.Figure 2
Evacuation network, contraflow without budget constraint and contraflow with budget constraint, respectively. (a) Capacity, unit cost. (b, c) Capacity, flow.
(a)(b)(c)Theorem 7.
The fixed switching cost contraflow problem is equivalent to0/1-MSFIP where all data to be positive integral [7].Since the0/1 maximum flow improvement is equivalent to the maximum fixed cost flow problem, this implies that the FSCCF is NP-hard to solve (Theorem 3). The fixed cost for arc reversals makes the problem NP-hard, even in the static case. The static contraflow algorithm is ’blind’ for the arc reversal decisions. Adding a time component to FSCCF makes it practically even more difficult to solve. Based on the above results, the following theorems are proposed.Theorem 8.
The FSCCF problem isNP-hard even in series-parallel graphs.Proof.
The FSCCF problem is equivalent to0/1-MSFIP (Theorem 7). As the maximum flow problem with fixed cost on arcs is equivalent to 0/1-maximum flow improvement [5], then by Theorem 3, it can be claimed that the FSCCF problem is NP-hard even in series-parallel graphs.Theorem 9.
There is a fully polynomial time approximation scheme for the FSCCF problems when the problems are restricted to series-parallel graphs.Proof.
As in proof of Theorem8, the FSCCF problem is equivalent to 0/1-MSFIP and the maximum flow problem with fixed costs on arcs. Since all hardness and approximation results of these problems will be carried over to the FSCCF problem so that a fully polynomial time approximation scheme can be obtained for the FSCCF problems in series-parallel graphs (Theorem 4).As the fixed switching cost contraflow problem is equivalent to the0/1 maximum flow improvement which is equivalent to the minimum cost fixed flow problem, an approximation solution can be found by using the cost-to-time ratio approach [5, 18]. This can be obtained by assuming the capacities ue and unit cost ce/ue.


## 4.2. Maximum Dynamic Flow Problem

The notion of MDF is introduced and solved in [7] by reversing the arcs at time zero with zero cost. In this section, reversal cost is considered to maximize the dynamic contraflow subject to budget constraint which is an extension of MSCFP from static to dynamic networks.Problem 4.
The MDCF problem with switching cost is the MDF where arcs can be reversed accepting switching cost such that the total cost is subject to the budget constraint. It is denoted by MDCFPWSC.Theorem 10.
Algorithm2 solves Problem 4 optimally in pseudo-polynomial time.Proof.
Step 1 is well defined as it transforms the given dynamic network flow problem into the static network flow problem. The feasibility of other steps of the algorithm can be shown as in Theorem6. Thus, the algorithm is feasible.
The dynamic network can be transformed into static network as in Step 1. Step 2 constructs the auxiliary network, and Step 6 finds an optimal flow in auxiliary network with respect to the cost defined in Step 5 and total budgetB. Let fet be the budget constraint contraflow in the dynamic network. Then, the corresponding budget constraint flow function in the network N˜T=VT,A˜T,u˜T can be related by the following equation:(34)fe˜tT=fvt,wt+θe˜=fet,∀e˜t∈A˜T.
It is a bijection from the set of feasible budget constraint contraflows in the dynamic networkN=V,A,uet,θe,T to the set of feasible budget constraint flows in N˜T=VT,A˜T,u˜T so that the contraflows fet with time horizon T are equivalent to the flows fe˜tT in the time-expanded network. Remaining proof of the theorem can be shown as in Theorem 6. Suppose Fdy∗ be the optimal contraflow achievable on budget B. Hence, the optimal contraflow can be obtained in OlogTnU˜max minimum cost flow computations.Algorithm 2: Maximum dynamic contraflow with switching cost (MDCFAWSC).
Input: two-terminal arc reversible network N=V,A,uet,θe,T with reversal budget B, reversal cost bet, and symmetric arc capacity(1)
Transform the given dynamic network into the time-expanded network byVT≔vt:v∈V,t∈TAT≔vt,wt+θee=v,w∈A,0≤t≤T−θeuetT≔uet,foret∈ATbetT≔bet,foret∈ATcapacities and costs of holdover arcs are infinity and zero, respectively(2)
Construct an auxiliaryN˜T=VT,A˜T,u˜T as e˜t∈A˜ife→t=vt,wt+θe∈AT or e←t=wt−θe,vt∈AT with new capacity u˜e˜tT=ue→tT+ue←tTfor alle˜t∈A˜T(3)
Define the cost function byce˜tTfe˜tT=0for0≤fe˜tT≤ue→tTbe→tT⋅fe˜tT−ue→tTforue→tT<fe˜tT≤u˜e˜tTfor alle˜t∈A˜T(4)
Transform the cost and the capacity functions byu¯e0T≔ue→tTu¯e1T≔u˜e˜tT−ue→tTc¯e0T≔0c¯e1T≔be←tT(5)
Find the optimal flow in the auxiliary network considering budgetB and the cost defined in Step 4 using binary search in 0,nTU˜max, where U˜max=maxu˜e˜tT:e˜t∈A˜T(6)
An arce←t∈AT is reversed with capacity f˜e˜tT−ue→tT if and only if the flow along e→t∈AT is greater than ue→tT or there is a nonnegative flow along the arc e→t∉AT(7)
Reconstruct the dynamic network flow from the static network flow according to the flow obtained in Step 5 and arc reversal in Step 6Output: Maximum dynamic contraflow in N=V,A,uet,θe,T with respect to budget B


## 5. Conclusions

To find the minimum cost, a maximum flow and the quickest time in static or dynamic networks are still emerging fields of research in the literature. Moreover, the best reconfiguration of an evacuation network is being more interesting both from theoretical as well as application points of view. However, in most of the cited publications, the arc reversal costs are considered to be zero, given the highest priority for evacuees rather than taking account of a fixed budget in emergency periods. Many efficient algorithms are presented so far.In this paper, we look at the above problems considering the fixed budgetary costs in addition. Our focus is given on the flow improvement problems with switching costs constrained by arc reversal costs on different static and dynamic network flow models. Different variants of flow improvement problems have been studied, and their complexities are given. Here, the contraflow reconfiguration with arc switching cost has been introduced for the first time. Based on this approach, a polynomial time algorithm and a pseudo-polynomial time algorithm are proposed for maximum static and maximum dynamic contraflow improvement problems, respectively. The arc capacities in these dynamic flow models are subject to the time-dependent capacity constraints with time invariant transit times. Therefore, these solutions are equally applicable if both these parameters are taken to be time invariant. If both parameters are taken to be time- or flow-dependent, the hardness increases, and it is our further interest. The findings of these investigations are of both theoretical and practical interest.



---

*Source: 1605806-2020-06-01.xml*