# Lexicographically Maximum Contraflow Problem with Vertex Capacities

Authors: Phanindra Prasad Bhandari; Shree Ram Khadka
Journal: International Journal of Mathematics and Mathematical Sciences
 (2021)

---

## Abstract

The contraflow approach has been extensively considered in the literature for modeling evacuations and has been claimed, due to its lane-direction-reversal capability, as an efficient idea to speed up the evacuation process. This paper considers the contraflow evacuation model on network with prioritized capacitated vertices that allows evacuees to be held at intermediate spots too, respecting their capacities and priority order. In particular, it studies the maximum flow evacuation planning problem and proposes polynomial and pseudo-polynomial time solution algorithms for static network and dynamic multinetwork, respectively. A real dataset of Kathmandu road network with evacuation spaces is considered to implement the algorithm designed for dynamic multinetwork and to observe its computational performance.


---

## Body

## 1. Introduction

The contraflow approach, which refers to the reversibility of direction of traffic flow in one or more lanes of roadways for fixed time period, re-configures the road network, identifying ideal direction and reallocating available capacity for each arc. The approach, due to its lane-direction-reversal capability, can be taken as a potential remedy to mitigate congestion during emergencies. It significantly reduces the total evacuation time and/or increases the number of evacuees sent from the risk zone to safety. Studies show that reversing one lane of a four-lane dual highway increases the evacuation road capacity by approximately 30%, and by reversing all the inbound lanes, it increases by 67% [1]. The contraflow approach is primarily important for emergency evacuations; nonetheless, its applications are not limited to these. This is commonly used for accommodating directionally imbalanced traffic associated with daily commuter in big cities as well as consequences due to religious gathering, arrangement of concerts or tournaments, etc. However, there is limited implementation of it in real emergency evacuations due to difficulty in using commonly employed methods to duplicate traffic conditions of real contraflow lane during an emergency [1].The first mathematical optimization model for the contraflow problem was proposed by Rebennack et al. [2] that relies on the basis of the network flow model in [3]. They have investigated analytical solutions for the maximum static contraflow (MSCF) problem and maximum dynamic contraflow (MDCF) problem with polynomial time complexities. The solution idea is based on transformation of input network into a new network for which existing network flow algorithms are applicable. The authors in [4] studied the continuous time maximum dynamic contraflow evacuation problem and proposed a polynomial time solution using the notion of natural transformation of flows suggested in [5].Other variants that are closely related to the MDCF problem are the quickest contraflow (QCF) problem and earliest arrival contraflow (EACF) problem. The QCF problem on single-source-single-sink network has been solved polynomially in [2]. The EACF problem for the two-terminal series-parallel (TTSP) network has been studied and a polynomial time solution for this has been proposed in [6]. Maximum as well as earliest version of evacuation contraflow problems in network with not necessarily equal transit time on anti-parallel lanes have been studied in [7]. Network reconstruction-based solution procedures have also been proposed for these problems modeled with discrete as well as continuous time setting. The authors in [8] studied these problems for multinetwork setup and proposed polynomial time solutions for both discrete as well as continuous time models. However, the solution procedures for earliest version of the problems work only for TTSP network. The contraflow approach has been incorporated in the network flow model to study facility location problem in [9], and the notion of abstract flow has been applied to network contraflow problems in [10]. The partial contraflow approach over the abstract network setting has been introduced in [11]. We refer to the survey articles [12, 13] for broader insight into dynamic network flow problems and evacuation planning problems.This paper introduces a new aspect of the evacuation model designed on network with capacitated vertices by imposing the contraflow approach on it. The new model has arc reversal capability and is capable of holding evacuees at temporary shelters at intermediate vertices of given priority. The flow model adopted here is based on weak-conservation constraints given in [14] (cf. [15]). Based on this aspect, the maximum static contraflow problem on ordinary network and maximum dynamic contraflow problem on multinetwork are studied, and solution algorithms for them are proposed. It is crucial, in case of uneven road architecture, for example, to take contraflow models on multinetwork into account for preparing evacuation tasks [8]. Multinetworks capture the situation of road topology with parallel lanes of different transit time and anti-parallel lanes of unequal to and fro transit time. It is considered that the transit time parameter behaves symmetrically during the reversal of arc direction in the case of the dynamic contraflow problem.The evacuation flow model introduced in [14] is revisited and the lexicographically maximum contraflow problem on network with capacitated vertices is introduced in Section 2. The solution procedures to the problems for static and dynamic cases are proposed in Sections 3.1 and 3.2, respectively. A case illustration with a real dataset is made in Section 4. Section 5 concludes the paper.


## 2. Model Description

Consider a directed multigraphG=V,A with vertex set V and arc set A, both to be finite, such that n:=V and m:=A. Represent the source and the sink by s and d, respectively, and assume a terminal set S⊂V with S:=v1,…,vr prioritized from higher to lower priority, i.e., d=v1≻⋯≻vr, to be given. Then, the corresponding two-terminal evacuation network for time horizon T is represented as N=G,la,ua,τa,kv,s,d,T. Here, l:A⟶ℕ0:=ℕ∪0 and u:A⟶ℕ0 represent the lower and upper arc capacity functions which bound the number of flow units on each arc a∈A at each time step from below and from above, respectively. Similarly, the vertex capacity function k:S⟶ℕ0 delimits the total number of flow units, which may be held in each of the vertices v∈S. Moreover, the transit time function τ:A⟶ℕ specifies the time needed by a flow unit to traverse an arc. Treat time parameter in a discrete manner, i.e., T:=0,1,…,T.The non-negative flow variablesfa,t defined by f:A×T⟶ℕ0 that specify the flow over time in the network N are the number of flow units entering arc a at time step t. The number of flow units entering arc a at time step t is assumed to be bounded by the capacity of an arc, i.e., fa,t satisfies the capacity constraints for all a∈A and for all t∈T. That is,(1)0≤fa,t≤ua,∀a∈A,∀t∈T.Moreover,fa,t has to be equal to zero for all t>T−τa and for all a∈A. The excess flow at vertex v∈V at time t∈T, denoted by exfv,t, is defined as(2)0≤exfv,t≔∑a∈δ−v∑ξ=0t−τafa,ξ−∑a∈δ+v∑ξ=0tfa,ξ,where δ−v:=a∈A:a=w,vfor some vertexw∈V and δ+v:=a∈A:a=v,wfor some vertexw∈V denote the set of arcs entering and leaving vertex v∈V, respectively.Further, we need to ensure that the excess flow at each vertexv∈S over time horizon T is to be bounded by the capacity kv, i.e.,(3)exfv,T≤kv,for allv∈S.Consequently, the total flow of evacuees leaving the sources is equal to the total flow of the evacuees held at vertices v∈S over the time horizon T, i.e.,(4)∑a∈δ+s∑ξ=0Tfa,ξ−∑a∈δ−s∑ξ=0Tfa,ξ=∑v∈Sexfv,T.An arca=v,w∈A in which the flow could travel from vertex v to vertex w is replaced by the arc w,v for contraflow purpose. The important feature of the considered dynamic network N is that the capacities and the transit time on anti-parallel arcs could be unequal, and it is allowed to have parallel arcs with different transit time only. Thus, the static network N, we consider here, is not a multinetwork. To this end, the objective of maximum contraflow evacuation planning problem is to lexicographically maximize the vector exfv1,T,…,exfvr,T⊤ such that exfvi,T≤kvi for i=1,…,r, if the direction of arcs on N is allowed to reverse. The network flow problem with this objective is termed as lexicographically maximum dynamic contraflow problem and abbreviated as LexMDCF problem. The maximum contraflow problem with above objective for static network N=G,la,ua,kv,s,d is termed as lexicographically maximum static contraflow problem and is abbreviated as LexMSCF problem.


## 3. Solution Discussion

Rebennack et al. [2] proposed polynomial time analytical solutions to the MSCF problem and the MDCF problem for the first time. They considered the problems in ordinary network that do not have capability of holding flows at intermediate vertices. Their solution idea is based on the reconstruction of input network into a new one, in which the existing network flow algorithms are applicable. This section discusses the solution procedures to LexMSCF problem for ordinary network and LexMDCF problem for multinetwork based on network reconstruction idea.


### 3.1. Lexicographically Maximum Static Contraflow Problem

Consider a static networkN=V,A,la,ua,τa,kv,s,d with terminal set S⊂V as described in Section 2. Moreover, consider that kd=∞, and consider kv to be finite for all v∈S\d. The lexicographically maximum static flow (LexMSF) problem that lexicographically maximizes the amount of flow entering a set of terminals in S with respect to a given prioritization and given vertex capacities has been solved polynomially in [14]. Here, the objective of the LexMSCF problem is to solve the LexMSF problem on N, if direction of arcs on N can be reversed.We modify the solution idea of Rebennack et al. [2] that solves MSCF problem to solve the LexMSCF problem. Their idea is based on modification of input network into a new network by summing the capacities on arcs v,w and w,v such that MSCF problem reduces to MSF problem on it. In particular, the procedure has following steps. At first, given static network N=V,A,ua is transformed into its auxiliary network N˜=V,A˜,ua˜ where the arc set A˜ contains undirected arc v,w, if v,w and/or w,v belong to original arc set A with capacity uv,w∼=uv,w+uw,v. Secondly, a maximum static s−d flow is computed on so-formed undirected network N˜ by using any known algorithm. In our case, to ensure the intermediate holding capability in the solution and to respect the vertex capacities, the lexicographically maximum flow is computed by using LexMSF flow computation idea given in [14] instead of computing ordinary maximum flow. The modified procedure that solves LexMSCF problem is given in Algorithm 1.Algorithm 1: LexMSCF algorithm.
(1)
Given a static networkN=V,A,la,ua,kv,s,d, S:=v1,…,vr⊂V with d=v1≻⋯≻vr, la=0 for all a∈A and integer inputs.(2)
TransformN into network N˜=V,A˜,la˜,ua˜,kv,s,d as in [2] and set la˜=0,∀a˜∈A˜.(3)
Solve LexMSF problem on networkN˜ using algorithm in [14].(4)
Perform flow decomposition into path and cycle flows of maximum flows obtained from step 3 and remove all cycle flows.(5)
Arcw,v∈A is reversed if and only if the flow along arc v,w∈A is greater than uv,w or if there is non-negative flow along arc a∉A.(6)
Obtain LexMSCF solution onN.We state the following lemma that shows equivalence between the optimal flow onN˜ and the optimal contraflow on input network N, which turns out to be useful in optimality proof of algorithms designed for contraflow problems in this paper.Lemma 1 (see [2]).
The maximum static contraflow on a static networkN is equivalent to the maximum static flow on the corresponding transformed network N˜.Theorem 1.
Given a static networkN=V,A,la,ua,kv,s,d, source s and terminal set S=v1,…,vr⊂V with d=v1≻⋯≻vr, and la=0 for all a∈A. Then, Algorithm 1 computes a lexicographically maximum static contraflow on N optimally in strongly polynomial time.Proof.
The LexMSF Algorithm optimally computes a static flow for each terminalsv∈S as sinks on reduced network N˜ (see [14]). Moreover, Lemma 1 shows that these flows are equivalent to the maximum static contraflows on the input network N.
The computational complexity of the algorithm depends on time complexity of the solution procedure on the reduced networkN˜. This is dominated by the time complexity of the solution procedure of LexMSF problem on N˜ since the flow decomposition in each iteration and network transformation can be done only in Omn, see [16], and Om time, respectively. Note that the LexMSF problem can be solved in strongly polynomial time [14].


### 3.2. Lexicographically Maximum Dynamic Contraflow Problem for Multinetwork

Multinetworks capture the evacuation situation with anti-parallel lanes of unequal to and fro transit time as well as parallel lanes of unequal transit time. Maximum dynamic contraflow problems modeled on these class of network without capacitated vertices have been studied in [8]. For given dynamic multinetwork N=V,A,la,ua,τa,ka,s,d,T and terminal set S:=v1,…,vr of capacitated vertices with d=v1≻⋯≻vr, the aim is to solve the LexMDCF problem, if the arc reversibility is permitted only once at time zero. In the following, the solution procedure (Algorithm 2) that solves the MDCF problem for multinetwork is modified to solve LexMDCF problem.Algorithm 2: MDCF algorithm [8].
(1)
Given a multinetworkN=V,A,ua,τa,s,d,T with single source s, single sink d, and integer inputs.(2)
TransformN into undirected multinetwork N˜=V,A˜,ua˜,τa˜,s,d,T where a˜=v,w∈A˜, if v,w,w,v∈A such that τv,w=τw,v, with ua˜=uv,w+uw,v and τa˜=τv,w, and a˜=v,w∈A˜, if v,w∈A and w,v∉A such that τv,w=τw,v, with ua˜=uv,w and τa˜=τv,w.(3)
Label parallel arcsv,w∈N˜ as v,wi such that τv,wi<τv,wi+1, for i=1,2,…,q;q≤m.(4)
Generate a dynamic, temporally repeated flow on networkN˜.(5)
Perform flow decomposition into path and cycle flows of the flow resulting from step 4. Remove the cycle flows.(6)
Arcw,v∈A is reversed, if and only if the flow along arc v,w is greater than uv,w, or if there is a non-negative flow along arc v,w∈A.(7)
Get a maximum dynamic contraflow onN.Solving MDCF problem, the arcw,v∈A is reversed, if the flow along arc v,w exceeds uv,w for τv,w≤τw,v, or τw,v<τv,w. This can be viewed, alternatively, as follows: for v,w,w,v∈A such that τv,w=τw,v, the flow value at arc a˜=v,w∈A˜ greater than the capacity uv,w of the corresponding arc v,w∈A means there is flipping of the direction of arc w,v∈A. Similarly, in the case with unequal transit time, we can see the sense of flipping the direction of arc a=w,v∈A, if there is some positive flow on the corresponding arc a˜=v,w. The minimum cost flow (MCF) algorithm applied to generate a dynamic temporally repeated flow ensures that there is flow along the arc v,w with less or equal transit time in comparison to the transit time of corresponding anti-parallel arc w,v, regardless of whether the arc w,v is saturated. The parallel arcs v,w∈N˜ have been labeled as v,wi such that τv,wi<τv,wi+1, for i=1,2,…,q;q≤m, to avoid obstruction on the multinetwork while applying MCF algorithm.Following theorems (Theorems2 and 3) show that the Algorithm 2 solves maximum dynamic contraflow problem for multinetwork optimally in strongly polynomial time.Theorem 2.
Given a dynamic multinetworkN=V,A,ua,τa,s,d,T with integer inputs. Then, maximum dynamic flow on N˜ is equivalent to a maximum dynamic contraflow on N.Proof.
The auxiliary networkN˜ of the original network N obtained in step 2 is an undirected multinetwork. The maximum dynamic contraflow problem on N can be viewed as a maximum dynamic flow problem on N˜. While solving the latter problem on N˜, the network is to be further transformed by replacing each undirected arc by two oppositely directed arcs with capacities and transit times of both arcs equal to that of original arc. This allows us to send flow on either direction of the arc. However, the flow direction, once chosen, remains fixed throughout the procedure. That is, there is only a flow on one direction of any arc, and never in both directions at the same time as well as at different time periods. However, there could be a flow along arc v,w and w,v such that τv,w≠τw,v for v,w,w,v∈A at the same time or at different time periods. The latter situation does not make the flow on N˜ an infeasible since, in fact, arcs v,w and w,v are physically different arcs for τv,w≠τw,v, due to the labeling of arcs in step 3. Thus, the flow constructed by Algorithm 2 is feasible.
Since every feasible flow of the maximum dynamic flow problem on the transformed networkN˜ is feasible to the maximum dynamic contraflow problem on network N, the maximum dynamic flow on N˜ is not greater than the maximum dynamic contraflow on N. On the other hand, since maximum dynamic flow on network N does not exceed maximum flow for the corresponding time expanded network NT [3], the maximum dynamic contraflow on N is not greater than the maximum static contraflow in time expanded network NT. This static contraflow is equivalent to the optimal static flow in N˜T due to the fact that any maximum static contraflow on network N has equivalent maximum flow in the corresponding transformed network N˜ [2]. Again, since there exists a temporally repeated flow which is maximal over the time horizon T [3], the optimal static flow in N˜T is equivalent to the temporally repeated flow on N˜. Thus, the optimal dynamic contraflow on N is not greater than the optimal dynamic flow on N˜.Theorem 3.
For dynamic multinetworkN=V,A,ua,τa,s,d,T with integer inputs, Algorithm 2 runs in strongly polynomial time.Proof.
Construction of auxiliary network in step 2 and labeling parallel arcs in step 3 require only linear time onm. The running time of Algorithm 2 is dominated by computation of a maximum dynamic flow in step 3. It is computed with the help of temporally repeated flow on N˜. Finding a temporally repeated flow is equivalent to solving a minimum cost flow problem. The minimum mean cycle-canceling algorithm of [17], for instance, requires On2m3logn time for solving this problem. Next effort is to decompose the maximum static flow which requires Omn time [16]. Thus, Algorithm 2 runs in a strongly polynomial time for dynamic multinetwork N.
For given dynamic networkN and terminal set S as described in Section 2, a lexicographically maximum dynamic flow (LexMDF) problem that lexicographically maximizes the amount of flow entering a set of terminals in S with respect to a given prioritization and given vertex capacities has been studied in [14]. The solution procedure to solve this problem is based on the notion of time expanded network introduced in [3]. Since the objective of LexMDCF problem is to respect the vertex capacities on the prioritized terminals, it is not sufficient to compute a maximum dynamic flow by the means of ordinary temporally repeated flows as in Algorithm 2. Instead, to solve the LexMDCF problem, a lexicographically maximum dynamic flow computation technique proposed in [14] can be applied. The solution procedure to solve LexMDCF problem for multinetwork has been summarized in Algorithm 3.Algorithm 3: LexMDCF algorithm for multinetwork.
(1)
Given a dynamic multinetworkN=V,A,la,ua,τa,ka,s,d,T, S=v1,…,vr with d=v1≻⋯≻vr, la=0 for all a∈A and integer inputs.(2)
TransformN into undirected multinetwork N˜=V,A˜,la˜,ua˜,τa˜,kv,s,d,T as in Algorithm 2 and set la˜=0,∀a˜∈A˜.(3)
Label each parallel arcsv,w∈N˜ as v,wi such that τv,wi<τv,wi+1 for i=1,2,…,q; q<m.(4)
Compute LexMDF on networkN˜ using algorithm in [14].(5)
Perform flow decomposition into path and cycle flows of maximum flows obtained from step 4 and remove all cycle flows.(6)
Arcw,v∈A is reversed if and only if the flow along arc v,w∈A is greater than uv,w or if there is non-negative flow along arc a∉A.(7)
Obtain LexMDCF solution for multinetworkN.Theorem 4.
Given a multinetworkN=V,A,la,ua,τa,ka,s,d,T, source s, and terminal set S=v1,…,vr with d=v1≻⋯≻vr, and la=0 for all a∈A. Then, Algorithm 3 computes a lexicographically maximum dynamic contraflow on N in pseudo-polynomial time.Proof.
The LexMDF algorithm of [14] is applied in Algorithm 3 that computes dynamic flows on transformed network N˜ iteratively for each vertex v∈S in priority order optimally. These flows have equivalent maximum dynamic contraflows on input network N for each iteration due to Theorem 2. Also, the application of LexMDF algorithm is dominating step with run time depending upon parameter T. Rest of the steps can be performed in strongly polynomial time. Thus, Algorithm 3 computes a lexicographically maximum dynamic contraflow on multinetwork N in pseudo-polynomial time.


## 3.1. Lexicographically Maximum Static Contraflow Problem

Consider a static networkN=V,A,la,ua,τa,kv,s,d with terminal set S⊂V as described in Section 2. Moreover, consider that kd=∞, and consider kv to be finite for all v∈S\d. The lexicographically maximum static flow (LexMSF) problem that lexicographically maximizes the amount of flow entering a set of terminals in S with respect to a given prioritization and given vertex capacities has been solved polynomially in [14]. Here, the objective of the LexMSCF problem is to solve the LexMSF problem on N, if direction of arcs on N can be reversed.We modify the solution idea of Rebennack et al. [2] that solves MSCF problem to solve the LexMSCF problem. Their idea is based on modification of input network into a new network by summing the capacities on arcs v,w and w,v such that MSCF problem reduces to MSF problem on it. In particular, the procedure has following steps. At first, given static network N=V,A,ua is transformed into its auxiliary network N˜=V,A˜,ua˜ where the arc set A˜ contains undirected arc v,w, if v,w and/or w,v belong to original arc set A with capacity uv,w∼=uv,w+uw,v. Secondly, a maximum static s−d flow is computed on so-formed undirected network N˜ by using any known algorithm. In our case, to ensure the intermediate holding capability in the solution and to respect the vertex capacities, the lexicographically maximum flow is computed by using LexMSF flow computation idea given in [14] instead of computing ordinary maximum flow. The modified procedure that solves LexMSCF problem is given in Algorithm 1.Algorithm 1: LexMSCF algorithm.
(1)
Given a static networkN=V,A,la,ua,kv,s,d, S:=v1,…,vr⊂V with d=v1≻⋯≻vr, la=0 for all a∈A and integer inputs.(2)
TransformN into network N˜=V,A˜,la˜,ua˜,kv,s,d as in [2] and set la˜=0,∀a˜∈A˜.(3)
Solve LexMSF problem on networkN˜ using algorithm in [14].(4)
Perform flow decomposition into path and cycle flows of maximum flows obtained from step 3 and remove all cycle flows.(5)
Arcw,v∈A is reversed if and only if the flow along arc v,w∈A is greater than uv,w or if there is non-negative flow along arc a∉A.(6)
Obtain LexMSCF solution onN.We state the following lemma that shows equivalence between the optimal flow onN˜ and the optimal contraflow on input network N, which turns out to be useful in optimality proof of algorithms designed for contraflow problems in this paper.Lemma 1 (see [2]).
The maximum static contraflow on a static networkN is equivalent to the maximum static flow on the corresponding transformed network N˜.Theorem 1.
Given a static networkN=V,A,la,ua,kv,s,d, source s and terminal set S=v1,…,vr⊂V with d=v1≻⋯≻vr, and la=0 for all a∈A. Then, Algorithm 1 computes a lexicographically maximum static contraflow on N optimally in strongly polynomial time.Proof.
The LexMSF Algorithm optimally computes a static flow for each terminalsv∈S as sinks on reduced network N˜ (see [14]). Moreover, Lemma 1 shows that these flows are equivalent to the maximum static contraflows on the input network N.
The computational complexity of the algorithm depends on time complexity of the solution procedure on the reduced networkN˜. This is dominated by the time complexity of the solution procedure of LexMSF problem on N˜ since the flow decomposition in each iteration and network transformation can be done only in Omn, see [16], and Om time, respectively. Note that the LexMSF problem can be solved in strongly polynomial time [14].


## 3.2. Lexicographically Maximum Dynamic Contraflow Problem for Multinetwork

Multinetworks capture the evacuation situation with anti-parallel lanes of unequal to and fro transit time as well as parallel lanes of unequal transit time. Maximum dynamic contraflow problems modeled on these class of network without capacitated vertices have been studied in [8]. For given dynamic multinetwork N=V,A,la,ua,τa,ka,s,d,T and terminal set S:=v1,…,vr of capacitated vertices with d=v1≻⋯≻vr, the aim is to solve the LexMDCF problem, if the arc reversibility is permitted only once at time zero. In the following, the solution procedure (Algorithm 2) that solves the MDCF problem for multinetwork is modified to solve LexMDCF problem.Algorithm 2: MDCF algorithm [8].
(1)
Given a multinetworkN=V,A,ua,τa,s,d,T with single source s, single sink d, and integer inputs.(2)
TransformN into undirected multinetwork N˜=V,A˜,ua˜,τa˜,s,d,T where a˜=v,w∈A˜, if v,w,w,v∈A such that τv,w=τw,v, with ua˜=uv,w+uw,v and τa˜=τv,w, and a˜=v,w∈A˜, if v,w∈A and w,v∉A such that τv,w=τw,v, with ua˜=uv,w and τa˜=τv,w.(3)
Label parallel arcsv,w∈N˜ as v,wi such that τv,wi<τv,wi+1, for i=1,2,…,q;q≤m.(4)
Generate a dynamic, temporally repeated flow on networkN˜.(5)
Perform flow decomposition into path and cycle flows of the flow resulting from step 4. Remove the cycle flows.(6)
Arcw,v∈A is reversed, if and only if the flow along arc v,w is greater than uv,w, or if there is a non-negative flow along arc v,w∈A.(7)
Get a maximum dynamic contraflow onN.Solving MDCF problem, the arcw,v∈A is reversed, if the flow along arc v,w exceeds uv,w for τv,w≤τw,v, or τw,v<τv,w. This can be viewed, alternatively, as follows: for v,w,w,v∈A such that τv,w=τw,v, the flow value at arc a˜=v,w∈A˜ greater than the capacity uv,w of the corresponding arc v,w∈A means there is flipping of the direction of arc w,v∈A. Similarly, in the case with unequal transit time, we can see the sense of flipping the direction of arc a=w,v∈A, if there is some positive flow on the corresponding arc a˜=v,w. The minimum cost flow (MCF) algorithm applied to generate a dynamic temporally repeated flow ensures that there is flow along the arc v,w with less or equal transit time in comparison to the transit time of corresponding anti-parallel arc w,v, regardless of whether the arc w,v is saturated. The parallel arcs v,w∈N˜ have been labeled as v,wi such that τv,wi<τv,wi+1, for i=1,2,…,q;q≤m, to avoid obstruction on the multinetwork while applying MCF algorithm.Following theorems (Theorems2 and 3) show that the Algorithm 2 solves maximum dynamic contraflow problem for multinetwork optimally in strongly polynomial time.Theorem 2.
Given a dynamic multinetworkN=V,A,ua,τa,s,d,T with integer inputs. Then, maximum dynamic flow on N˜ is equivalent to a maximum dynamic contraflow on N.Proof.
The auxiliary networkN˜ of the original network N obtained in step 2 is an undirected multinetwork. The maximum dynamic contraflow problem on N can be viewed as a maximum dynamic flow problem on N˜. While solving the latter problem on N˜, the network is to be further transformed by replacing each undirected arc by two oppositely directed arcs with capacities and transit times of both arcs equal to that of original arc. This allows us to send flow on either direction of the arc. However, the flow direction, once chosen, remains fixed throughout the procedure. That is, there is only a flow on one direction of any arc, and never in both directions at the same time as well as at different time periods. However, there could be a flow along arc v,w and w,v such that τv,w≠τw,v for v,w,w,v∈A at the same time or at different time periods. The latter situation does not make the flow on N˜ an infeasible since, in fact, arcs v,w and w,v are physically different arcs for τv,w≠τw,v, due to the labeling of arcs in step 3. Thus, the flow constructed by Algorithm 2 is feasible.
Since every feasible flow of the maximum dynamic flow problem on the transformed networkN˜ is feasible to the maximum dynamic contraflow problem on network N, the maximum dynamic flow on N˜ is not greater than the maximum dynamic contraflow on N. On the other hand, since maximum dynamic flow on network N does not exceed maximum flow for the corresponding time expanded network NT [3], the maximum dynamic contraflow on N is not greater than the maximum static contraflow in time expanded network NT. This static contraflow is equivalent to the optimal static flow in N˜T due to the fact that any maximum static contraflow on network N has equivalent maximum flow in the corresponding transformed network N˜ [2]. Again, since there exists a temporally repeated flow which is maximal over the time horizon T [3], the optimal static flow in N˜T is equivalent to the temporally repeated flow on N˜. Thus, the optimal dynamic contraflow on N is not greater than the optimal dynamic flow on N˜.Theorem 3.
For dynamic multinetworkN=V,A,ua,τa,s,d,T with integer inputs, Algorithm 2 runs in strongly polynomial time.Proof.
Construction of auxiliary network in step 2 and labeling parallel arcs in step 3 require only linear time onm. The running time of Algorithm 2 is dominated by computation of a maximum dynamic flow in step 3. It is computed with the help of temporally repeated flow on N˜. Finding a temporally repeated flow is equivalent to solving a minimum cost flow problem. The minimum mean cycle-canceling algorithm of [17], for instance, requires On2m3logn time for solving this problem. Next effort is to decompose the maximum static flow which requires Omn time [16]. Thus, Algorithm 2 runs in a strongly polynomial time for dynamic multinetwork N.
For given dynamic networkN and terminal set S as described in Section 2, a lexicographically maximum dynamic flow (LexMDF) problem that lexicographically maximizes the amount of flow entering a set of terminals in S with respect to a given prioritization and given vertex capacities has been studied in [14]. The solution procedure to solve this problem is based on the notion of time expanded network introduced in [3]. Since the objective of LexMDCF problem is to respect the vertex capacities on the prioritized terminals, it is not sufficient to compute a maximum dynamic flow by the means of ordinary temporally repeated flows as in Algorithm 2. Instead, to solve the LexMDCF problem, a lexicographically maximum dynamic flow computation technique proposed in [14] can be applied. The solution procedure to solve LexMDCF problem for multinetwork has been summarized in Algorithm 3.Algorithm 3: LexMDCF algorithm for multinetwork.
(1)
Given a dynamic multinetworkN=V,A,la,ua,τa,ka,s,d,T, S=v1,…,vr with d=v1≻⋯≻vr, la=0 for all a∈A and integer inputs.(2)
TransformN into undirected multinetwork N˜=V,A˜,la˜,ua˜,τa˜,kv,s,d,T as in Algorithm 2 and set la˜=0,∀a˜∈A˜.(3)
Label each parallel arcsv,w∈N˜ as v,wi such that τv,wi<τv,wi+1 for i=1,2,…,q; q<m.(4)
Compute LexMDF on networkN˜ using algorithm in [14].(5)
Perform flow decomposition into path and cycle flows of maximum flows obtained from step 4 and remove all cycle flows.(6)
Arcw,v∈A is reversed if and only if the flow along arc v,w∈A is greater than uv,w or if there is non-negative flow along arc a∉A.(7)
Obtain LexMDCF solution for multinetworkN.Theorem 4.
Given a multinetworkN=V,A,la,ua,τa,ka,s,d,T, source s, and terminal set S=v1,…,vr with d=v1≻⋯≻vr, and la=0 for all a∈A. Then, Algorithm 3 computes a lexicographically maximum dynamic contraflow on N in pseudo-polynomial time.Proof.
The LexMDF algorithm of [14] is applied in Algorithm 3 that computes dynamic flows on transformed network N˜ iteratively for each vertex v∈S in priority order optimally. These flows have equivalent maximum dynamic contraflows on input network N for each iteration due to Theorem 2. Also, the application of LexMDF algorithm is dominating step with run time depending upon parameter T. Rest of the steps can be performed in strongly polynomial time. Thus, Algorithm 3 computes a lexicographically maximum dynamic contraflow on multinetwork N in pseudo-polynomial time.


## 4. Case Illustration

A case illustration is made by considering Kathmandu road network within and on the Ring Road (see Figure1). Two scenarios: Scenario I with 38 vertices, 118 arcs, and 13 intermediate shelters and Scenario II (including minor road segments) with 52 vertices, 180 arcs, and 14 intermediate shelters, are examined. New Road area, a highly congested business hub with narrow streets, is taken as the source. Evacuation spaces identified in [18] are taken as the sink (Tribhuvan University (TU) area and Bagmati Corridor near Balkhu) and other intermediate shelters. Standard area (population per 45 square meters sphere) has been considered for the holding capacity of each intermediate evacuation space. However, the sink is assumed to have sufficient capacity. Tables 1 and 2 show the name of evacuation spaces together with their corresponding holding capacities and priority order. For this case illustration, shelters (except sink) are prioritized in random selection (however, it can be done with respect to their capacities, distance from the source or available facilities, and so on). Being a discrete time auto-based evacuation planning model, it followed the “two second rule,” considering each minute as a unit of time. It is considered that the average speed of cars is 550 meters per minute that highly matches with the transit time to travel the segment provided by Google Maps data during normal traffic. Considering the time horizon of 60, 90, and 100 minutes and sufficient sink capacity, the results for Scenario I (Table 1) and Scenario II (Table 2) before and after the application of the contraflow approach are demonstrated.Figure 1
Road network for case illustration taken from Google Earth Pro whereS denotes source (New Road) and letters from A to O are sink (Balkhu) and other prioritized intermediate vertices as mentioned in Table 2. Outer boundary traced yellow is Ring Road.Table 1
Maximum flow values (evacuees) at sink (Balkhu) and intermediate vertices for Scenario I.
SNEvacuation spaces (vertices)Vertex capacityPriority orderFlow/contraflow forT=60Flow/contraflow forT=90Flow/contraflow forT=1001Balkhu (A)∞110170/1398017370/2298019770/259802Airport (B)564022880/56403780/56404080/56403Koteshor (C)32703150/3270150/3270150/32704Gaushala (D)22204360/2220360/2220360/22205Satdobato (E)792050/17100/71100/79206Pulchowk (F)27606240/600240/600240/15907Shankha Park (G)2407240/240240/240240/2408Oxygenation Park (H)327080/00/00/09Balkumari (I)474090/00/00/010Teku (J)240010240/540240/540240/54011Naxal (K)90011690/900690/900690/90012Jawalakhel (L)1440120/00/00/013Lagankhel (M)330130/00/00/014Lainchaur (N)213014330/2130330/2130330/2130Table 2
Maximum flow values (evacuees) at sink (Balkhu) and intermediate vertices for Scenario II.
SNEvacuation spaces (vertices)Vertex capacityPriority orderFlow/contraflow forT=60Flow/contraflow forT=90Flow/contraflow forT=1001Balkhu (A)∞113620/2301022620/3741025620/422102Airport (B)564022730/56403630/56403930/56403Koteshor (C)32703120/2190120/3270120/32704Gaushala (D)22204360/2220360/2220360/22205Satdobato (E)792050/00/25200/36606Pulchowk (F)27606150/480150/480150/5407Shankha Park (G)2407240/240240/240240/2408Ring Road (Balaju NG Chowk) (H)32708690/1470690/1470690/14709Oxygenation Park (I)147090/00/00/010Chyasal (J)4740100/00/00/011Teku (K)240011210/420210/420210/42012Naxal (L)90012210/900210/900210/90013Jawalakhel (M)1440130/00/00/014Lagankhel (N)330140/00/00/015Lainchaur (O)213015180/2130180/2130180/2130The results show that the total maximum flow could be increased, while the contraflow approach is applied, by up to approximately 109%, justifying the importance of the approach in the evacuation planning problem. For the real-world problem, it is necessary to restrict the sink also by its actual evacuation space capacity (24090 evacuees [18]). In this case, evacuees that cannot reach sink due to its capacity are distributed among intermediate shelters respecting corresponding capacities, and more than 58 thousand (only nearly 4 thousand less) evacuees in total can be evacuated in 100 minutes for Scenario II, if contraflow is applied. Additional evacuees, about 34 thousand in number for Scenario II with actual sink capacity, can be saved due to consideration of intermediate holding of flows in the evacuation model. Detailed result discussion for this case has been omitted here.The algorithm has been coded into Python with version 3.9.1 and was run on the computer having Windows 10 operating system with 64 GB RAM and 3.60 GHZ Intel Core i9-9900k processor. It took around 1.5, 6, and 9 minutes to run the program while computing lexicographically maximum flows forT=60, T=90, and T=100, respectively, for Scenario I. Similarly, for Scenario II, it took around 4, 16, and 22 minutes for T=60, T=90, and T=100, respectively. These significantly different running times for different values of parameter T and network input size justify the assertion about time complexity (pseudo-polynomial) of Algorithm 3 made in Theorem 4. The finer discretization of time (controlling parameter in algorithm), instead of considering a minute as a unit of time, would minimize the errors associated with transit time of road segments. However, it leads to higher time complexity to run the program.


## 5. Conclusion

Importance and applicability of the idea of contraflow especially in the evacuation planning problem has been increasing. Existing network contraflow models fail to capture the situation where it is possible to send evacuees out from the risk zone to even an intermediate capacitated spot if they cannot reach the destination. This paper considered contraflow evacuation planning problems adopting the weak-conservation constraints that allow holding of flow units at prioritized intermediate vertices of given capacities. In particular, it proposed solution algorithms for lexicographically maximum static contraflow problem and lexicographically maximum (discrete) dynamic contraflow problem for multinetwork.The continuous time dynamic flow model with weak-conservation constraint can also be defined in similar way as given in Section2 by integrating the flow units at each time point t∈0,T instead of adding flow over time for each time step t∈T. Dynamic version of lexicographically contraflow problems studied in this paper can be extended to one with continuous time setting too. These problems can be solved with computational time complexity equal to that of discrete time setting by applying notion of natural transformation of flows suggested in [5].The limitation of the solution algorithm proposed for dynamic version of the problem is that it leads to a pseudo-polynomial time complexity since the size of underlying network strongly depends onT. Searching of polynomial time solution algorithm for this problem as well as studying the quickest and earliest versions of the problem would be future research areas. One could incorporate the idea of intermediate holding of flows in the multicommodity flow model that better reflects the real-world vehicle distribution scenario of most underdeveloped cities.



---

*Source: 6651135-2021-02-13.xml*