# Network Reconfiguration with Orientation-Dependent Transit Times

Authors: Hari Nandan Nath; Urmila Pyakurel; Tanka Nath Dhamala
Journal: International Journal of Mathematics and Mathematical Sciences
 (2021)

---

## Abstract

Motivated by applications in evacuation planning, we consider a problem of optimizing flow with arc reversals in which the transit time depends on the orientation of the arc. In the considered problems, the transit time on an arc may change when it is reversed, contrary to the problems considered in the existing literature. Extending the existing idea of auxiliary network construction to allow asymmetric transit time on arcs, we present strongly polynomial time algorithms for solving single-source-single-sink maximum dynamic contraflow problem and quickest contraflow problem. The results are substantiated by a computational experiment in a Kathmandu road network. An algorithm to solve the corresponding earliest arrival contraflow problem with a pseudo-polynomial-time complexity is also presented. The partial contraflow approach for the corresponding problems has also been discussed.


---

## Body

## 1. Introduction

The transportation network is represented as a dynamic network in which road segments represent the arcs and intersection between them are the nodes. The unsafe locations of network are the sources and the locations at safe regions are the sinks. Each node and arc of the network are bounded by finite capacities. Each arc has a transit time or a cost function that determines the amount of time or cost needed to travel it. The network may contain arcs in both directions with different capacities and asymmetric transit times or costs. The computational complexities for the transportation planning are heavily dependent upon the number of sources, sinks, parameters on the arcs, and nodes, like constant, time-dependent, or flow-dependent capacities or transit times as well as additional constraints. The time we consider mostly is discrete, which approximates the computationally heavy continuous models at the cost of solution approximations. Also, the constant time is probably approximated by free flow speeds or certain queuing rules and constant capacity settings that reduce the problem to be linear, at least more tractable, in contrast to the more general and realistic flow-dependent traffic flow scenarios. For extensive explanation on diversified theories and applications, we recommend Dhamala et al.[1] and Kotsireas et al. [2] and the citations therein.The transportation network, during or after disastrous situations, becomes more congested due to large number of people and vehicles towards the safer areas on the streets. Moreover, the movement towards risk areas from safer places is discouraged because of which the corresponding road lanes are almost empty. The empty lanes management plays vital role to reduce the traffic congestion. The optimal lane reversal strategy makes the traffic systematic and smooth by removing the traffic jams caused in different large-scale natural and man-made disasters, busy office hours, special events, and street demonstrations. The contraflow reconfiguration, by means of various operations research models, heuristics, optimization, and simulation techniques, reverses the usual direction of empty lanes towards the sinks satisfying the given constraints that increase the flow value and decrease the average evacuation time [3, 4].Although the capacity of lanes is assumed to be constant, the transit times may vary. If we consider the inflow-dependent or load-dependent transit times, the empty lanes may have likely zero time contrary to the congested segments where the transit times increase with the flow density. In reality, the transit time of incoming lanes towards the sources may not be equal to the outgoing lanes. It may be the cases depending on the network topology as well. In such cases, the free flow transit time has been considered for the reversed lanes [4]. Recently, the authors in [5] have considered the asymmetric transit times on the lanes but those lanes are individual and reversal decisions are made with their own transit times, that is, symmetric transit times such as in [3, 6, 7].In this paper, we consider the asymmetric transit times of reversed lanes in general form and show their impact on optimal lane reversals; that is, our transit time is dependent on the orientation of the lanes which applies asymmetric times. The capacities of both reversals are the same by adding both capacities.Consider a network in Figure1(a). The arc labels represent the capacity of the arc and travel time on the direction of the arc. For example, the capacity of s,a is 4 and its travel time is 1. That means a flow of 4 units per unit time can be sent from s to a and takes 1 unit of time to reach from s to a. For a time horizon of 6 units, a maximum of 8 units of flow (1 along s–a–d twice, 1 along s–b–d thrice, and 1 along s–a–b–d thrice) can be sent from s to d without allowing arc reversals.Figure 1
(a) Network with arc labels capacity and transit time; (b)b,a reversed with the same transit time; (c)b,a reversed with orientation-dependent transit time; (d)a,b reversed with orientation-dependent transit time.
(a)(b)(c)(d)Ifb,a is reversed and the transit time is kept intact (Figure 1(b)), the maximum of 10 units of flow (1 along s–a–d twice, 1 along s–b–d thrice, 1 along s–a–b–d (that contains original a,b) thrice, and 2 along s–a–b–d (that contains b,a reversed) once) can be sent.If the transit time depends on the orientation, whenb,a is reversed, its transit time becomes that of original a,b (Figure 1(c)). In this case, there is a maximum of 14 units of flow (1 along s–a–d twice, 1 along s–b–d thrice, and 3 along s–a–b–d thrice). In this case, we can add the capacities of a,b,b,a and replace the two arcs by a single arc a,b. If a,b is reversed, however, the maximum flow value reduces to 5 (Figure 1(d)).Kim et al. [8] firstly model the contraflow problem as an integer programming problem, thereby proving its NP-hardness. As finding exact mathematical solutions for general contraflow techniques is costly, they present two greedy and bottleneck heuristics for possible numerical approximate solutions to the quickest contraflow problem. With computational experiments, it has been shown that at least 40% evacuation time can be reduced by reverting at most 30% arcs. Rebennack et al. [3] solve the two-terminal maximum and quickest contraflow problems optimally in strongly polynomial times. Pyakurel and Dhamala [6] solve the earliest arrival contraflow problem on a two-terminal network in pseudo-polynomial-time. They solve it in strongly polynomial time if the network is series-parallel. The continuous time solution is given in [7] and the solutions with similar objectives are given in [9, 10]. They show that if the minimum cut arcs have symmetric capacities, then the flow is double with the contraflow. Pyakurel et al. [11] give the first temporally repeated flow algorithm to solve the quickest contraflow problem, within a complexity of solving a min-cost flow problem. The costs for arc reversals as switching costs are studied in [12]. The contraflow models with intermediate storage are introduced in [13].In this paper, we introduce the maximum dynamic contraflow, earliest arrival, and quickest contraflow problems on asymmetric transit time network and present efficient algorithms to solve these problems in two-terminal networks. Modifying the network transformation suggested by Rebennack et al. [3] in case of symmetric travel time cases, we show that the approach works equally well in the asymmetric travel time settings. The results are extended with partial lane reversals as well. We analyze our solutions in both discrete and continuous time settings. The novelty of this work is to optimize network topology with unequal transit times on reversal arcs to improve congestion by increasing the flow value and decreasing the evacuation time.We organize the paper as follows.Section 2 presents mathematical formulations and models of the problems allowing asymmetric transit times on arcs. We investigate the maximum dynamic, earliest arrival, and quickest flow problems in Section 3. These results are extended with partial lane reversals in Section 4. In Section 5, some computational results, taking a part of Kathmandu road network as an example network, are presented. The paper is concluded in Section 6.


## 2. Basic Concepts

A networkN is a directed graph consisting of a finite set of nodes V and a finite set of arcs A with V=n,A=m. An arc e∈A is associated with a unique pair of nodes i,j: one of them is called the head of e and the other the tail. If e has head i and tail j, then it is called directed from i to j. We consider something known as flow that moves from a set of nodes S⊂V, called sources to D⊂V (S≠D). The amount of flow is limited by a capacity function u:A⟶ℝ≥0. A travel time τ:A⟶ℝ≥0 is associated with the flow. We denote such a network by N=V,A,u,τ,S,D. If S=s and D=d, we denote the network by N=V,A,u,τ,s,d. We define the set of arcs incoming to node i as(1)Ai−=e∈A:iis the head ofe,and the set of arcs going out of it as(2)Ai+=e∈A:iis the tail ofe.


### 2.1. Static Flow

A static flow is a functionx:A⟶ℝ≥0 which satisfies the following conditions:(3)∑e∈Ai+xe−∑e∈Ai−xe=0∀i∈V\S,D,(4)xe≤ue∀e∈A.The value of the static flowx is(5)vx=∑d∈D∑e∈Ad−xe.A static flow x is called a circulation if (3) is satisfied by all i∈V. A flow x that maximizes vx is called a maximum static flow.


#### 2.1.1. Flow Decomposition

LetP denote the set of all simple paths from S to D, and let C denote the set of all simple cycles in N. Then every static flow x has a flow decomposition xPP∈P∪C such that xP≥0∀P∈P∪C and(6)∑P∈P∪CxP:e∈PxP=xe.


#### 2.1.2. Minimum Cost Flow

Given two functionsb:V⟶ℝ, called supply, and c:A⟶ℝ, called cost with ∑i∈Vbi=0, a flow x, satisfying (4) and(7)∑e∈Ai+xe−∑e∈Ai−xe=bi∀i∈V,is called a minimum cost flow if it minimizes ∑e∈Acexe. In various applications, the travel time τ is considered as cost.


#### 2.1.3. Residual Network

A very important notion for various network flow calculations is a residual network. Given a static flowx, the residual network Nx has the same vertex set V. The arc set Ax consists of arcs constructed in the following way: For each e∈A directed from i to j, if xe<ue, there is an arc in Ax directed from i to j with residual capacity ue−xe and cost ce. If xe>0, we have an arc in Ax directed from j to i with residual capacity xe and cost −ce.For more details, we refer the reader to Ahuja et al. [14].


### 2.2. Dynamic Flow

A dynamic flowΦ with time horizon T consists of Lebesgue-integrable functions Φe:0,T⟶ℝ≥0 for each arc e∈A such that Φeθ=0 for θ≥T−τe. Here, Φeθ can be realized as the rate of flow entering e at time θ. The flow entering the tail i of the arc e=i,j at time θ reaches the head j of e at time θ+τe. For each i∈V, we define the excess of node i induced by Φ at time θ as(8)excΦi,θ=∑e∈Ai−∫0θ−τeΦeσdσ−∑e∈Ai+∫0θΦeσdσ, which is the net amount of flow that is stored at node i up to time θ. In what follows, we assume S=s,D=d for simplicity. A feasible dynamic flow Φ satisfies(9)excΦi,θ≥0∀θ∈0,T,∀i∈V\s,(10)excΦi,T=0,∀i∈V\s,d,(11)0≤Φeθ≤ue,∀e∈A,θ∈0,T.The value of the dynamic flowΦ at time θ is(12)vθΦ=excΦd,θ,and the total value of the dynamic flow Φ is(13)vΦ=vTΦ=excΦd,T.For more details, refer to Skutella [15].Given a time horizonT, the dynamic flow Φ that maximizes vTΦ is called the maximum dynamic flow. Given a flow value Q, the dynamic flow with minimum time horizon T∗ such that vT∗Φ=Q is called the quickest flow, and the dynamic flow Φ which maximizes vθΦ for all θ∈0,T is called the earliest arrival flow.


#### 2.2.1. Temporally Repeated Flow

Given a static flowx and a time horizon T, a flow decomposition on x gives a set of paths P with flow xP for each P∈P. Flow is sent along P at a constant rate xP from time 0 to maxT−τP,0, where τP=∑e∈Pτe is the travel time on path P, to define a dynamic flow known as the temporally repeated flow. To give an explicit expression for the dynamic flow, we define the following for e in a path P directed from i to j:Psi= the portion of the path P from s to i,Pjd= the portion of the path P from j to d,(14)Peθ=P∈P:e∈P,τPsi≤θ,τPjd<T−θ.Now, the dynamic flowΦ is defined by(15)Φeθ=∑P∈PeθxP∀e∈A,θ∈0,T.


#### 2.2.2. Discrete Dynamic Flow

Discretizing the time intervals0,T into the time steps 0,1,…,T−1, each corresponding to 0,1,1,2,⋯T−1,T, we can replace the integral sign in (9) by a summation sign (removing dσ); the corresponding flow is known as discrete dynamic flow. Using the concept of natural transformations, Fleischer and Tardos [16] show the equivalence between the two problems so that the solution procedures of a problem in continuous time version can be carried to the solution procedure of the corresponding problem in the discrete version, and vice versa.


## 2.1. Static Flow

A static flow is a functionx:A⟶ℝ≥0 which satisfies the following conditions:(3)∑e∈Ai+xe−∑e∈Ai−xe=0∀i∈V\S,D,(4)xe≤ue∀e∈A.The value of the static flowx is(5)vx=∑d∈D∑e∈Ad−xe.A static flow x is called a circulation if (3) is satisfied by all i∈V. A flow x that maximizes vx is called a maximum static flow.


### 2.1.1. Flow Decomposition

LetP denote the set of all simple paths from S to D, and let C denote the set of all simple cycles in N. Then every static flow x has a flow decomposition xPP∈P∪C such that xP≥0∀P∈P∪C and(6)∑P∈P∪CxP:e∈PxP=xe.


### 2.1.2. Minimum Cost Flow

Given two functionsb:V⟶ℝ, called supply, and c:A⟶ℝ, called cost with ∑i∈Vbi=0, a flow x, satisfying (4) and(7)∑e∈Ai+xe−∑e∈Ai−xe=bi∀i∈V,is called a minimum cost flow if it minimizes ∑e∈Acexe. In various applications, the travel time τ is considered as cost.


### 2.1.3. Residual Network

A very important notion for various network flow calculations is a residual network. Given a static flowx, the residual network Nx has the same vertex set V. The arc set Ax consists of arcs constructed in the following way: For each e∈A directed from i to j, if xe<ue, there is an arc in Ax directed from i to j with residual capacity ue−xe and cost ce. If xe>0, we have an arc in Ax directed from j to i with residual capacity xe and cost −ce.For more details, we refer the reader to Ahuja et al. [14].


## 2.1.1. Flow Decomposition

LetP denote the set of all simple paths from S to D, and let C denote the set of all simple cycles in N. Then every static flow x has a flow decomposition xPP∈P∪C such that xP≥0∀P∈P∪C and(6)∑P∈P∪CxP:e∈PxP=xe.


## 2.1.2. Minimum Cost Flow

Given two functionsb:V⟶ℝ, called supply, and c:A⟶ℝ, called cost with ∑i∈Vbi=0, a flow x, satisfying (4) and(7)∑e∈Ai+xe−∑e∈Ai−xe=bi∀i∈V,is called a minimum cost flow if it minimizes ∑e∈Acexe. In various applications, the travel time τ is considered as cost.


## 2.1.3. Residual Network

A very important notion for various network flow calculations is a residual network. Given a static flowx, the residual network Nx has the same vertex set V. The arc set Ax consists of arcs constructed in the following way: For each e∈A directed from i to j, if xe<ue, there is an arc in Ax directed from i to j with residual capacity ue−xe and cost ce. If xe>0, we have an arc in Ax directed from j to i with residual capacity xe and cost −ce.For more details, we refer the reader to Ahuja et al. [14].


## 2.2. Dynamic Flow

A dynamic flowΦ with time horizon T consists of Lebesgue-integrable functions Φe:0,T⟶ℝ≥0 for each arc e∈A such that Φeθ=0 for θ≥T−τe. Here, Φeθ can be realized as the rate of flow entering e at time θ. The flow entering the tail i of the arc e=i,j at time θ reaches the head j of e at time θ+τe. For each i∈V, we define the excess of node i induced by Φ at time θ as(8)excΦi,θ=∑e∈Ai−∫0θ−τeΦeσdσ−∑e∈Ai+∫0θΦeσdσ, which is the net amount of flow that is stored at node i up to time θ. In what follows, we assume S=s,D=d for simplicity. A feasible dynamic flow Φ satisfies(9)excΦi,θ≥0∀θ∈0,T,∀i∈V\s,(10)excΦi,T=0,∀i∈V\s,d,(11)0≤Φeθ≤ue,∀e∈A,θ∈0,T.The value of the dynamic flowΦ at time θ is(12)vθΦ=excΦd,θ,and the total value of the dynamic flow Φ is(13)vΦ=vTΦ=excΦd,T.For more details, refer to Skutella [15].Given a time horizonT, the dynamic flow Φ that maximizes vTΦ is called the maximum dynamic flow. Given a flow value Q, the dynamic flow with minimum time horizon T∗ such that vT∗Φ=Q is called the quickest flow, and the dynamic flow Φ which maximizes vθΦ for all θ∈0,T is called the earliest arrival flow.


### 2.2.1. Temporally Repeated Flow

Given a static flowx and a time horizon T, a flow decomposition on x gives a set of paths P with flow xP for each P∈P. Flow is sent along P at a constant rate xP from time 0 to maxT−τP,0, where τP=∑e∈Pτe is the travel time on path P, to define a dynamic flow known as the temporally repeated flow. To give an explicit expression for the dynamic flow, we define the following for e in a path P directed from i to j:Psi= the portion of the path P from s to i,Pjd= the portion of the path P from j to d,(14)Peθ=P∈P:e∈P,τPsi≤θ,τPjd<T−θ.Now, the dynamic flowΦ is defined by(15)Φeθ=∑P∈PeθxP∀e∈A,θ∈0,T.


### 2.2.2. Discrete Dynamic Flow

Discretizing the time intervals0,T into the time steps 0,1,…,T−1, each corresponding to 0,1,1,2,⋯T−1,T, we can replace the integral sign in (9) by a summation sign (removing dσ); the corresponding flow is known as discrete dynamic flow. Using the concept of natural transformations, Fleischer and Tardos [16] show the equivalence between the two problems so that the solution procedures of a problem in continuous time version can be carried to the solution procedure of the corresponding problem in the discrete version, and vice versa.


## 2.2.1. Temporally Repeated Flow

Given a static flowx and a time horizon T, a flow decomposition on x gives a set of paths P with flow xP for each P∈P. Flow is sent along P at a constant rate xP from time 0 to maxT−τP,0, where τP=∑e∈Pτe is the travel time on path P, to define a dynamic flow known as the temporally repeated flow. To give an explicit expression for the dynamic flow, we define the following for e in a path P directed from i to j:Psi= the portion of the path P from s to i,Pjd= the portion of the path P from j to d,(14)Peθ=P∈P:e∈P,τPsi≤θ,τPjd<T−θ.Now, the dynamic flowΦ is defined by(15)Φeθ=∑P∈PeθxP∀e∈A,θ∈0,T.


## 2.2.2. Discrete Dynamic Flow

Discretizing the time intervals0,T into the time steps 0,1,…,T−1, each corresponding to 0,1,1,2,⋯T−1,T, we can replace the integral sign in (9) by a summation sign (removing dσ); the corresponding flow is known as discrete dynamic flow. Using the concept of natural transformations, Fleischer and Tardos [16] show the equivalence between the two problems so that the solution procedures of a problem in continuous time version can be carried to the solution procedure of the corresponding problem in the discrete version, and vice versa.


## 3. Dynamic Contraflow Solutions

We consider the networkN with set of nodes V, set of arcs A, capacity u:A⟶ℝ≥0, and travel time functions τ,τ←:A⟶ℝ≥0. For each e∈A, with the tail node i and head node j, τe or τe denotes the arc transit time from i to j and τ←e or τ←e denotes arc transit time from j to i. Without loss of generality, we make the following conventions:(1)
There exist at most two arcs (with opposite orientations) between any two nodesi and j. We denote the arc ewith the tail i and the head j by i,j.(2)
Wheneveri,j∈A, there is j,i∈A. This can be done, for our purpose, by assigning uji=0 if such an arc does not exist.(3)
Definingτj,i=τ←i,j, we assume the existence of only one travel time function τ.Remark 1.
In case the above-mentioned conventions are not satisfied, we can use suitable network transformations to meet the requirements. For example, ifτi,j≠τ←i,j, we can transform the network N0 in Figure 2(a) to the network N shown in Figure 2(b). Given the capacities ui,j=uij,uj,i=uji and transit times τi,j=α1,τ←i,j=α2,τj,i=β1,τ←j,i=β2, we replace arc i,j in N0 by two arcs i,j,j,i with capacities and transit times uij,α1 and 0,α2, respectively. The arc j,i in N0 is replaced by i,k,k,j,j,k,k,i adding a node k to the network to avoid parallel arcs. The capacities and travel times of j,k,k,i are taken as uji,0 and uji,β1, respectively, and those of i,k,k,j are taken as 0,β2, and 0,0, respectively.Figure 2
Network transformation for the casesτj,i≠τ←i,j. (a) Network N0. (b) Network N.
(a)(b)Definition 1.
(Auxiliary network). For eachN=V,A,u,τ,s,d, we define the auxiliary network as N′=V′,A′,u′,τ′,s,d, in which(1)
V′=V,A′=A(2)
∀i,j∈A,u′i,j=ui,j+uj,i(3)
∀i,j∈A′,τ′i,j=τi,jExample 1.
Consider a networkN as depicted in Figure 3(a). The arc labels represent the capacity and the transit time. The auxiliary network N′ of N is constructed in Figure 3(b). The capacity of each arc is the sum of its capacity and the opposite arc and the transit time is the same as that of the corresponding arc in N.Figure 3
(a) Evacuation networkN. (b) Auxiliary network N′.
(a)(b)


### 3.1. Maximum Dynamic Contraflow

Problem 1.
(maximum dynamic contraflow problem with orientation-dependent transit times). Given a networkN=V,A,u,τ,s,d with transit time τ depending on the orientation and a time horizon T, find the maximum dynamic flow allowing the arc reversals at time 0.According to Ford and Fulkerson [17], the problem of finding the static flow corresponding to the temporally repeated maximum dynamic flow can be formulated as(16)min−Tv+∑i,j∈Aτi,jxi,j,∑e∈Ai+xi,j−∑i,j∈Ai−xi,j=v,i=s−v,i=d0,i∈V\s,d,0≤xi,j≤ui,j∀i,j∈A.Problem1 is to find the maximum dynamic flow so that an arc i,j can take also the capacity of j,i and vice versa. So, xi,j+xj,i must not exceed ui,j+uj,i. However, the removal of cycle flows does not change the value of the static flow v and does not improve −Tv+∑i,j∈Aτi,jxi,j; we can impose the condition that either xi,j=0 or xj,i=0. So, the problem to find the static flow corresponding temporally repeated maximum dynamic flow can be stated as(17)min−Tv+∑i,j∈Aτi,jxi,j,(18)∑e∈Ai+xi,j−∑i,j∈Ai−xi,j=v,i=s,−v,i=d,0,i∈V\s,d,(19)0≤xi,j≤ui,j+uj,i∀i,j∈A,(20)xi,j⋅xj,i=0.See also [17] for the similar formulation of maximizing the static flow in undirected and mixed networks. The problem in (17)–(19) is a linear programming problem and (20) can be satisfied by the removal of cycle flows in the solution. Since a linear programming problem is polynomial solvable and using flow decomposition, removal of cycle flows also can be done in polynomial time (see [14]); we can find the static flow corresponding to the temporally repeated maximum dynamic flow allowing arc reversals in a polynomial time. If the static flow in an arc exceeds its capacity, the opposite arc has to be reversed at time zero.In Algorithm1, we present a procudure to solve Problem 1.Algorithm 1: Maximum dynamic contraflow with orientation-dependent transit times.
Input: A network N=V,A,u,τ,s,d with orientation dependent transit time τ, and a time horizon TOutput: Maximum dynamic flow with arc reversals(1)
Construct the auxiliary networkN′=V′,A′,u′,τ′,s,d according to Definition 1.(2)
Find a static flowx corresponding to the temporally repeated dynamic flow in N′.(3)
Decomposex into chain-flows and cycle-flows. Remove the cycle-flows and update x.(4)
Reversej,i∈A if and only if xi,j>ui,j. Dynamic flow in reconfigured N= a temporally repeated flow corresponding to x with the time horizon T.Theorem 1.
Algorithm1 solves the maximum dynamic contraflow problem with orientation-dependent transit times correctly.Proof.
It is easy to see that steps 1–3 are well defined. Step 4 may be ill defined if for somei,j∈A′,xi,j,xj,i>0. But because the removal of cycle flows in Step 3 ensures either xi,j or xj,i to be zero, Step 4 is also well defined. Moreover, xi,j≤u′i,j=ui,j+uj,i. This shows that x is feasible in N after necessary arc reversals.
Since the cycle flows do not contribute to the value of the flow,x is optimal in N′ even after removing the cycle flows in Step 3. Let vx be the value of such a dynamic flow. We claim that x is optimal in N (after arc reversals). If not so, there exists an instance of arc reversals, Ny, of N in which we can find a static flow y, temporal repetition of which results in a dynamic flow with flow value more than vx. In Ny, we can replace i,j and j,i by a single arc i,j with transit time τi,j and capacity ui,j+uj,i if i,j has been reversed. Let P be the set of paths corresponding to the path decomposition of y. Corresponding to each path P: s–i1–i2–⋯–ik–d in P, we have a path P′: s–i1–i2–⋯–ik–d in N′. Each arc in P′ has the same transit time and the capacity not less than that of the corresponding arc in P. Let the collection of such paths P′ be P′. Defining a flow y′i,j=yi,j for each i,j∈P′, we can find a dynamic flow in N′ with a flow value more than vx. This contradicts the optimality of x in N′ also.
Hence, Algorithm1 computes the maximum dynamic flow in N reversing appropriate arcs.Theorem 2.
Algorithm1 runs in OMDF+nm time where n=V,m=A and MDF is the running time of a temporally repeated maximum dynamic flow computation.Proof.
The construction of the auxiliary network in Step 1 requiresOm time. The flow decomposition in Step 3 can be done in Omn time (Ahuja et al.) [14]. Step 4 can be performed in Om time. Thus, if MDF is the running time of Step 2, the algorithm runs in OMDF+nm time. However, in general, this complexity could be considered as the complexity of MDF solution. □Theorem 3.
The maximum dynamic contraflow problem with orientation-dependent transit times can be solved in a strongly polynomial time.Proof.
From Theorem2, the running time of Algorithm 1 is OMDF+nm, where MDF is the running time of a maximum dynamic flow calculation. In N=V,A,u,τ,s,d, and consequently in the auxiliary network N′, we can find the static flow x corresponding to the maximum dynamic flow as follows [16]:(1)
Add an arcd,s with ud,s=∞ and τ′d,s=−T to the auxiliary network N′ to obtain a network N″.(2)
Calculate the minimum cost circulationx′ in N″.(3)
x= the restriction of x′ to N′.
Using the enhanced capacity scaling algorithm mentioned by Orlin [18], the minimum cost circulation in N″ can be calculated in Omlognm+nlogn time. This proves the assertion. □


### 3.2. Quickest Contraflow

Problem 2.
(Quickest contraflow problem with orientation-dependent transit times). Given a networkN=V,A,u,τ,s,d with transit time τ depending on the orientation and a supply Q at s, find the dynamic flow with minimum time horizon allowing the arc reversals at time 0.We construct Algorithm2 to solve Problem 2.Algorithm 2: Quickest contraflow with orientation-dependent transit times.
Input: A network N=V,A,u,τ,s,d with orientation dependent transit time τ, and a supply Q at sOutput: Quickest flow with the arc reversals(1)
Construct the auxiliary networkN′=V′,A′,u′,τ′,s,d according to Definition 1.(2)
Find a static flowx corresponding to the temporally repeated quickest flow in N′, and the quickest time T∗.(3)
Decomposex into chain-flows and cycle-flows. Remove the cycle-flows and update x.(4)
Reversej,i∈A if and only if xi,j>ui,j. Quickest flow in reconfigured N= a temporally repeated flow corresponding to x with the time horizon T∗.LetvT be the value of the maximum dynamic flow with time horizon T. One of the strategies to find the quickest flow with a supply Q at s is to search for the minimum time horizon T∗ such that Q≤vT∗. Various search strategies are described in Burkard et al.’s work [19]. This requires solving the maximum dynamic flow problem repeatedly. Using this technique in Step 2, the feasibility and optimality arguments given in Theorem 1 are valid in Algorithm 2 as well. Hence, we have the following result.Theorem 4.
Algorithm2 solves the quickest contraflow problem with orientation-dependent transit times correctly.Analogous to the case of solving the maximum dynamic contraflow problem, ifQF is the complexity of solving the quickest flow problem in N, we have the following.Theorem 5.
Algorithm2 runs in OQF+nm time, where QF is the running time of a temporally repeated quickest flow problem.Since there exist strongly polynomial algorithms for solving the quickest flow problem, we have the following.Theorem 6.
The quickest contraflow problem with orientation-dependent transit times can be solved in a strongly polynomial time.Proof.
Consider a networkN=V,A,u,τ,s,d with a supply Q at the source s. We show that the complexity of Algorithm 2 is strongly polynomial to reach the conclusion. Using the cancel-and-tighten algorithm described in the work of Saho and Shigeno [20], to solve the quickest flow problem Step 2 takes Onm2log2n time. Using the fact in Theorem 5, the complexity of Algorithm 2 is Onm2log2n. This proves the assertion. □


### 3.3. Earliest Arrival Contraflow

Consider a networkN=V,A,u,τ,s,d with orientation-dependent transit time τ. With a given time horizon T, the earliest arrival flow problem seeks to find the flow that is maximum with each time horizon θ∈0,T. Carrying over the idea of solving the maximum dynamic contraflow problem, we try to solve the earliest arrival flow problem on the auxiliary network N′. This can be carried out by implementing the successive shortest path algorithm in the residual network of N′ ([21, 22]). The idea is to send the flow successively through shortest paths amounting the residual capacity of the path. Such a path, being in the residual network, may contain negative (cost) time arcs also. Sending flow through negative cost arcs sends the flow back in time. This may result in the arc used by the flow in some time interval, not used in the other time interval, and used again in some further time interval. So, an arc reversed to optimize the flow at one time does not remain reversed throughout the given whole-time interval. In other words, an arc may have to be flipped back and forth unlike in the cases of maximum dynamic contraflow and quickest contraflow, where an arc reversed at the beginning (time zero) remains reversed throughout.Problem 3.
Given a networkN=V,A,u,τ,s,d with orientation-dependent transit time τ and a time horizon T, find a dynamic flow which is maximum at every time horizon θ such that 0≤θ≤T allowing arc reversals at time θ.We propose Algorithm3, which sends the flow along the successive shortest paths in the residual network of the auxiliary network.Algorithm 3: Earliest arrival contraflow with orientation-dependent transit times.
Input: A network N=V,A,u,τ,s,d with orientation dependent transit time τ, and a time horizon TOutput: Earliest arrival flow with the arc reversals(1)
Construct the auxiliary networkN′=V′,A′,u′,τ′,s,d according to Definition 1.(2)
Find the earliest arrival flowf in N′.(3)
Reversej,i∈A if fijθ>ui,j at time θ∈0,T. f is the earliest arrival flow with arc reversals in N.The earliest arrival flow in Step 2 can be found by sending the flow equal to the residual capacity along the shortest paths in the residual network ofN′. The generalized temporally repeated flow can be found in [15]. Such an algorithm runs in a pseudo-polynomial-time.Theorem 7.
Algorithm3 solves the earliest arrival contraflow problem with orientation-dependent transit times in a pseudo-polynomial-time.However, in a series-parallel network with a single source and single sink, the maximum dynamic flow has the earliest arrival property (Ruzika et al.) [23]. So, in case of a series-parallel network N, Algorithm 1 solves Problem 3. Moreover, the maximum dynamic flow in the auxiliary network of a series parallel network with time horizon T can be solved in Omn+mlogm time by sending the flow iteratively through the s–d paths with the minimum time and removing the saturated arcs, considering only the paths with time not exceeding T. So, we have the following.Theorem 8.
IfN=V,A,u,τ,s,d is a series-parallel network, then the earliest arrival contraflow problem with orientation-dependent transit times can be solved in Omn+mlogm time.


## 3.1. Maximum Dynamic Contraflow

Problem 1.
(maximum dynamic contraflow problem with orientation-dependent transit times). Given a networkN=V,A,u,τ,s,d with transit time τ depending on the orientation and a time horizon T, find the maximum dynamic flow allowing the arc reversals at time 0.According to Ford and Fulkerson [17], the problem of finding the static flow corresponding to the temporally repeated maximum dynamic flow can be formulated as(16)min−Tv+∑i,j∈Aτi,jxi,j,∑e∈Ai+xi,j−∑i,j∈Ai−xi,j=v,i=s−v,i=d0,i∈V\s,d,0≤xi,j≤ui,j∀i,j∈A.Problem1 is to find the maximum dynamic flow so that an arc i,j can take also the capacity of j,i and vice versa. So, xi,j+xj,i must not exceed ui,j+uj,i. However, the removal of cycle flows does not change the value of the static flow v and does not improve −Tv+∑i,j∈Aτi,jxi,j; we can impose the condition that either xi,j=0 or xj,i=0. So, the problem to find the static flow corresponding temporally repeated maximum dynamic flow can be stated as(17)min−Tv+∑i,j∈Aτi,jxi,j,(18)∑e∈Ai+xi,j−∑i,j∈Ai−xi,j=v,i=s,−v,i=d,0,i∈V\s,d,(19)0≤xi,j≤ui,j+uj,i∀i,j∈A,(20)xi,j⋅xj,i=0.See also [17] for the similar formulation of maximizing the static flow in undirected and mixed networks. The problem in (17)–(19) is a linear programming problem and (20) can be satisfied by the removal of cycle flows in the solution. Since a linear programming problem is polynomial solvable and using flow decomposition, removal of cycle flows also can be done in polynomial time (see [14]); we can find the static flow corresponding to the temporally repeated maximum dynamic flow allowing arc reversals in a polynomial time. If the static flow in an arc exceeds its capacity, the opposite arc has to be reversed at time zero.In Algorithm1, we present a procudure to solve Problem 1.Algorithm 1: Maximum dynamic contraflow with orientation-dependent transit times.
Input: A network N=V,A,u,τ,s,d with orientation dependent transit time τ, and a time horizon TOutput: Maximum dynamic flow with arc reversals(1)
Construct the auxiliary networkN′=V′,A′,u′,τ′,s,d according to Definition 1.(2)
Find a static flowx corresponding to the temporally repeated dynamic flow in N′.(3)
Decomposex into chain-flows and cycle-flows. Remove the cycle-flows and update x.(4)
Reversej,i∈A if and only if xi,j>ui,j. Dynamic flow in reconfigured N= a temporally repeated flow corresponding to x with the time horizon T.Theorem 1.
Algorithm1 solves the maximum dynamic contraflow problem with orientation-dependent transit times correctly.Proof.
It is easy to see that steps 1–3 are well defined. Step 4 may be ill defined if for somei,j∈A′,xi,j,xj,i>0. But because the removal of cycle flows in Step 3 ensures either xi,j or xj,i to be zero, Step 4 is also well defined. Moreover, xi,j≤u′i,j=ui,j+uj,i. This shows that x is feasible in N after necessary arc reversals.
Since the cycle flows do not contribute to the value of the flow,x is optimal in N′ even after removing the cycle flows in Step 3. Let vx be the value of such a dynamic flow. We claim that x is optimal in N (after arc reversals). If not so, there exists an instance of arc reversals, Ny, of N in which we can find a static flow y, temporal repetition of which results in a dynamic flow with flow value more than vx. In Ny, we can replace i,j and j,i by a single arc i,j with transit time τi,j and capacity ui,j+uj,i if i,j has been reversed. Let P be the set of paths corresponding to the path decomposition of y. Corresponding to each path P: s–i1–i2–⋯–ik–d in P, we have a path P′: s–i1–i2–⋯–ik–d in N′. Each arc in P′ has the same transit time and the capacity not less than that of the corresponding arc in P. Let the collection of such paths P′ be P′. Defining a flow y′i,j=yi,j for each i,j∈P′, we can find a dynamic flow in N′ with a flow value more than vx. This contradicts the optimality of x in N′ also.
Hence, Algorithm1 computes the maximum dynamic flow in N reversing appropriate arcs.Theorem 2.
Algorithm1 runs in OMDF+nm time where n=V,m=A and MDF is the running time of a temporally repeated maximum dynamic flow computation.Proof.
The construction of the auxiliary network in Step 1 requiresOm time. The flow decomposition in Step 3 can be done in Omn time (Ahuja et al.) [14]. Step 4 can be performed in Om time. Thus, if MDF is the running time of Step 2, the algorithm runs in OMDF+nm time. However, in general, this complexity could be considered as the complexity of MDF solution. □Theorem 3.
The maximum dynamic contraflow problem with orientation-dependent transit times can be solved in a strongly polynomial time.Proof.
From Theorem2, the running time of Algorithm 1 is OMDF+nm, where MDF is the running time of a maximum dynamic flow calculation. In N=V,A,u,τ,s,d, and consequently in the auxiliary network N′, we can find the static flow x corresponding to the maximum dynamic flow as follows [16]:(1)
Add an arcd,s with ud,s=∞ and τ′d,s=−T to the auxiliary network N′ to obtain a network N″.(2)
Calculate the minimum cost circulationx′ in N″.(3)
x= the restriction of x′ to N′.
Using the enhanced capacity scaling algorithm mentioned by Orlin [18], the minimum cost circulation in N″ can be calculated in Omlognm+nlogn time. This proves the assertion. □


## 3.2. Quickest Contraflow

Problem 2.
(Quickest contraflow problem with orientation-dependent transit times). Given a networkN=V,A,u,τ,s,d with transit time τ depending on the orientation and a supply Q at s, find the dynamic flow with minimum time horizon allowing the arc reversals at time 0.We construct Algorithm2 to solve Problem 2.Algorithm 2: Quickest contraflow with orientation-dependent transit times.
Input: A network N=V,A,u,τ,s,d with orientation dependent transit time τ, and a supply Q at sOutput: Quickest flow with the arc reversals(1)
Construct the auxiliary networkN′=V′,A′,u′,τ′,s,d according to Definition 1.(2)
Find a static flowx corresponding to the temporally repeated quickest flow in N′, and the quickest time T∗.(3)
Decomposex into chain-flows and cycle-flows. Remove the cycle-flows and update x.(4)
Reversej,i∈A if and only if xi,j>ui,j. Quickest flow in reconfigured N= a temporally repeated flow corresponding to x with the time horizon T∗.LetvT be the value of the maximum dynamic flow with time horizon T. One of the strategies to find the quickest flow with a supply Q at s is to search for the minimum time horizon T∗ such that Q≤vT∗. Various search strategies are described in Burkard et al.’s work [19]. This requires solving the maximum dynamic flow problem repeatedly. Using this technique in Step 2, the feasibility and optimality arguments given in Theorem 1 are valid in Algorithm 2 as well. Hence, we have the following result.Theorem 4.
Algorithm2 solves the quickest contraflow problem with orientation-dependent transit times correctly.Analogous to the case of solving the maximum dynamic contraflow problem, ifQF is the complexity of solving the quickest flow problem in N, we have the following.Theorem 5.
Algorithm2 runs in OQF+nm time, where QF is the running time of a temporally repeated quickest flow problem.Since there exist strongly polynomial algorithms for solving the quickest flow problem, we have the following.Theorem 6.
The quickest contraflow problem with orientation-dependent transit times can be solved in a strongly polynomial time.Proof.
Consider a networkN=V,A,u,τ,s,d with a supply Q at the source s. We show that the complexity of Algorithm 2 is strongly polynomial to reach the conclusion. Using the cancel-and-tighten algorithm described in the work of Saho and Shigeno [20], to solve the quickest flow problem Step 2 takes Onm2log2n time. Using the fact in Theorem 5, the complexity of Algorithm 2 is Onm2log2n. This proves the assertion. □


## 3.3. Earliest Arrival Contraflow

Consider a networkN=V,A,u,τ,s,d with orientation-dependent transit time τ. With a given time horizon T, the earliest arrival flow problem seeks to find the flow that is maximum with each time horizon θ∈0,T. Carrying over the idea of solving the maximum dynamic contraflow problem, we try to solve the earliest arrival flow problem on the auxiliary network N′. This can be carried out by implementing the successive shortest path algorithm in the residual network of N′ ([21, 22]). The idea is to send the flow successively through shortest paths amounting the residual capacity of the path. Such a path, being in the residual network, may contain negative (cost) time arcs also. Sending flow through negative cost arcs sends the flow back in time. This may result in the arc used by the flow in some time interval, not used in the other time interval, and used again in some further time interval. So, an arc reversed to optimize the flow at one time does not remain reversed throughout the given whole-time interval. In other words, an arc may have to be flipped back and forth unlike in the cases of maximum dynamic contraflow and quickest contraflow, where an arc reversed at the beginning (time zero) remains reversed throughout.Problem 3.
Given a networkN=V,A,u,τ,s,d with orientation-dependent transit time τ and a time horizon T, find a dynamic flow which is maximum at every time horizon θ such that 0≤θ≤T allowing arc reversals at time θ.We propose Algorithm3, which sends the flow along the successive shortest paths in the residual network of the auxiliary network.Algorithm 3: Earliest arrival contraflow with orientation-dependent transit times.
Input: A network N=V,A,u,τ,s,d with orientation dependent transit time τ, and a time horizon TOutput: Earliest arrival flow with the arc reversals(1)
Construct the auxiliary networkN′=V′,A′,u′,τ′,s,d according to Definition 1.(2)
Find the earliest arrival flowf in N′.(3)
Reversej,i∈A if fijθ>ui,j at time θ∈0,T. f is the earliest arrival flow with arc reversals in N.The earliest arrival flow in Step 2 can be found by sending the flow equal to the residual capacity along the shortest paths in the residual network ofN′. The generalized temporally repeated flow can be found in [15]. Such an algorithm runs in a pseudo-polynomial-time.Theorem 7.
Algorithm3 solves the earliest arrival contraflow problem with orientation-dependent transit times in a pseudo-polynomial-time.However, in a series-parallel network with a single source and single sink, the maximum dynamic flow has the earliest arrival property (Ruzika et al.) [23]. So, in case of a series-parallel network N, Algorithm 1 solves Problem 3. Moreover, the maximum dynamic flow in the auxiliary network of a series parallel network with time horizon T can be solved in Omn+mlogm time by sending the flow iteratively through the s–d paths with the minimum time and removing the saturated arcs, considering only the paths with time not exceeding T. So, we have the following.Theorem 8.
IfN=V,A,u,τ,s,d is a series-parallel network, then the earliest arrival contraflow problem with orientation-dependent transit times can be solved in Omn+mlogm time.


## 4. Partial Contraflow Algorithm

The approach described inSection 3 either reverses an arc or does not reverse it. In various applications, for example, evacuation planning, an arc refers to a collection of lanes in a particular direction; it is beneficial if we reverse the lanes required by the flow. The unused lanes may be used for other facilities [24]. Realizing the need of arc reversals up to the required capacity only, the authors in [4] introduce the concept of partial arc reversals. We extend the procedure in case of orientation-dependent transit times on arcs.Algorithm4 describes the generic procedure to solve the corresponding problems described in Section 3. The algorithm not only reverses the arcs up to the necessary capacity but also lists the unused capacities of the arcs of the network considered.Algorithm 4: Generic partial contraflow algorithm.
Input: Network N=V,A,u,τ,s,d with orientation dependent transit timesOutput: Partial contraflow reconfiguration of N with unused capacities r.(1)
Find a cycle-free flowx in the auxiliary network N′=V′,A′,u′,τ′,s,t.(2)
Reversej,i∈A proportional to the capacity xi,j−ui,j if xi,j>ui,j.(3)
For eachi,j∈E, if i,j is reversed, then rij=uij′−xji and rji=0. If neither i,j nor j,i is reversed, ri,j=ui,j−xi,j.The correctness of Algorithm4 can easily be realized from the correctness of the corresponding algorithm with full arc reversal and the following fact. For the arcs i,j,j,i between nodes i and j, it is evident that either only one of them is reversed or both of them are not reversed. If i,j is reversed, it clearly indicates that xj,i>uj,i; there is no capacity of j,i unused; that is, rj,i=0, and(21)ri,j=ui,j−xj,i−uj,i=ui,j+uj,i−xj,i=u′i,j−xj,i.If both arcs are not reversed, thenxij≤ui,j meaning ri,j=ui,j−xi,j.The flowx in Step 1 of Algorithm 4 has to be considered as the corresponding static flow in case of the maximum dynamic contraflow (Section 3.1) and quickest flow (Section 3.2) and the dynamic flow in case of the earliest arrival flow (Section 3.3). Step 2 has to be implemented at time zero and at time θ accordingly.As the extra procedure of listing the unused capacities in Step 3 takes onlyOm time, the overall complexities of the algorithms in case of partial contraflow are the same as those of the contraflow. Thus, we have the following.Theorem 9.
The worst-case complexity of a partial contraflow problem with orientation-dependent transit times is the same as that of the corresponding contraflow problem.


## 5. Computational Experiment

For testing the computational performance of the maximum dynamic contraflow algorithm (Algorithm1) and the quickest contraflow algorithm (Algorithm 2), we consider Kathmandu road network inside Ring Road with major road segments as an example network (Figure 4). We consider a problem of evacuating people in Dasharath Stadium and surrounding area to outside of the Ring Road in case of auto-based-emergency evacuation.Figure 4
(a) Kathmandu road network. (b) Maximum flow direction with arc reversalsT=1 hour.
(a)(b)The constructed directed network consists of 69 nodes and 232 arcs (see Table1). The direction of arcs is taken as the direction of the usual flow of the traffic in the corresponding segments. The capacities of the road segments are taken from 2 to 4 units of flow per second according to the number of lanes. The travel time (in seconds) in one of the arcs between any two nodes is considered according to the length and that in the opposite arc is chosen differing from it by 0 to 30 seconds (chosen randomly). The considered data are taken only for the purpose of testing the algorithms. The accuracy of capacity and travel time demands complex technical examinations.Table 1
Network data for computations (Section5).
ijuijujiτijτjiijuijujiτijτjiijuijujiτijτji0493385700140707001604363601922414112401816114221818232247472124021213422322531122212145221025456223550562218015059226570672290110782285957332245558922302583022253083222243091022354510112234341027223035103022646411122230351213402025122722404013144026261415404042142522556015164024271524225050162204525216232241411920225050192222454020212210010520482213014521472250502148221531532223223640224544145145232422343024252242382526223025254203362826272218162728223232282922343028412217152930221816294022242430312224283132222522323322222033342220253435223230343722888035372224283637223540383922657539402247473943223235404122303441422230344143223737424422120135444522135135454622135135484922126126495022383850512238385064222020515222807551632213012551642245455253225045526122403553542218185361222522545522686854582270705556223634555722767055582282755758228075585922454059602260656062223434626322686864101221801601019992200639992260606299922108100609992211711059104224747104999220059999224545579992221215699922171171699922108108359992215315336110229010011099922003699922706538112225040112999220038999224136439992210090449992214513546999445050219992219020047118221981981189992200479992280806499922135135Source node: 0; sink node: 999.We calculate the maximum dynamic flow with and without contraflow taking time horizons from as low as 5 minutes to as high as 1 hour. At each time horizon considered, we find that the value of the flow after allowing arc reversals is almost the double of that without arc reversals (Figure5(a)). At T = 5 minutes, it is 44 without arc reversals and 88 with arc reversals. At T=60 minutes, the corresponding values are 29,312 and 58,502.Figure 5
Flow value and time comparisons.
(a)(b)Given a flow value at the source, the calculation of quickest flow shows that the decrease in the quickest time increases with the increase in the flow value. With the flow value as low as 500, the quickest time decreases only by 7%, which is 47% for the flow value 50,000.With growing time horizon and growing flow value, as well as the number of arcs, the flow occupies more and more arcs and, consequently, the number of arcs reversed increases. However, it remains fixed after some value of time or the flow value (Figure6(a) for maximum dynamic flows calculations and Figure 6(b) for quickest flows).Figure 6
Number of arcs reversed.
(a)(b)Among the considered instances, the running time of a maximum contraflow calculation is at most 0.013 seconds, and that of a quickest contraflow calculation is at most 0.067 seconds. The coding is done in Python programming language and run in MacOS 11.1 with 1.8 GHz Dual-Core Intel Core i5 processor, and 8 GB RAM.


## 6. Conclusion

In this work, we introduce the contraflow problem in which the transit time on an arc depends on the direction of the arc; that is, the transit time on an arc may change after its reversal. This extends the notion, in the existing literature, that the transit time on arcs remains the same before and after the arc reversal to the cases where the time on arcs depends on its orientation. Presenting a method of constructing an auxiliary network, strongly polynomial time algorithms for maximum dynamic contraflow problem and quickest contraflow problem with orientation-dependent transit times are presented for a single-source-single-sink network. In the similar settings, for the earliest arrival contraflow problem, a pseudo-polynomial-time algorithm is also presented. The computational performance of the algorithms for maximum dynamic contraflow and quickest contraflow taking a Kathmandu road network is also tested.The presented approach is useful, particularly, in transportation planning, where the transit time depends on the direction of the traffic flow because of various reasons, for example, topography of the road. When the direction of the traffic flow in a road segment is reversed, if the capacity permits, it is beneficial to reverse only the necessary lanes. To address such an issue, we present corresponding algorithms in the partial contraflow setting as well. Analyzing impressive results from this research, its further extensions to flow-dependent scenarios would be interesting problems.



---

*Source: 6613622-2021-03-11.xml*