# Dynamic Multicommodity Contraflow Problem with Asymmetric Transit Times

Authors: Shiva Prakash Gupta; Urmila Pyakurel; Tanka Nath Dhamala
Journal: Journal of Applied Mathematics
 (2022)

---

## Abstract

A maximum dynamic multicommodity flow problem concerns with the transportation of several different commodities through the specific source-sink path of an underlying capacity network with the objective of maximizing the sum of commodity flows within a given time horizon. Motivated by the uneven road condition of transportation network topology, we introduce the dynamic multicommodity contraflow problem with asymmetric transit times on arcs that increase the outbound lane capacities by reverting the orientation of lanes towards the demand nodes. Moreover, a pseudo-polynomial time algorithm by using a time-expanded graph and an FPTAS by using aΔ-condensed time-expanded network are presented.


---

## Body

## 1. Introduction

Linear multicommodity flow problems are represented by linear programs which can be characterized by a set of commodities and an underlying network. A commodity may be a good data that has got to be shipped (transferred) from one or more source nodes to at least one or more destination nodes within the network. In this study, we consider the multicommodity flow problems that concern with the routing of various commodities through a network to the unique source-sink pairs. In day-to-day life, these commodities might be telephone calls or messages in a telecommunications network or packages (goods) in a distribution network. The commodities are not interchangeable due to their unique characteristics. That is, demand for one commodity cannot be satisfied by another. For more details, we refer to [1–6].The transportation network is considered a network in which the supply points (origins), the demand points (destinations), and the intersection of road segments constitute the nodes. The arcs are line segments connecting two nodes. Each arc has a positive rational capacity that limits the flow amount (i.e., transported commodities) and the travel time.If we do not distinguish the flow in the multicommodity flow problem, then it becomes a single-commodity flow problem. To model a variety of real-world problems, classical network flows are useful, but they fail to incorporate a crucial element of many routing problems, i.e., time component. Ford and Fulkerson [7] incorporated this component and introduced a dynamic flow problem.The pressure of highly competitive market places influences corporate operations, and as a result, a company attempts to identify the best way to generate and transmit goods to consumers. Business decision-makers choose how and when items should be supplied to meet quality and quantity requirements cost-effectively to maximize profit. Transportation models provide a powerful framework to guide decision-makers in the context. Transportation plays an important part in the supply chain, and its value will not be lessened regardless of how big or small a company is [4]. Communication networks have become totally entwined with our modern society as a result of technological advancements. The application of communication networks ranges from everyday devices to complex equipment in aircraft, computer systems, and telecommunication as well as the Internet [8]. The multicommodity network flow may be used to create almost any communication network, including wireless and fiber optic networks. Authors in [9] employed the multicommodity flow formulation as an extension of the Steiner tree problem. Padmanabh and Roy [10] used a multicommodity flow method to construct a wireless sensor network routing protocol. A wireless sensor network is defined as a network of nodes having communication devices. To overcome the problem, they presented a golden ratio-based search method.The multicommodity flow problem is more complex than their single-commodity part. A static multicommodity flow problem is solved in polynomial time by using ellipsoid or interior-point methods. However, Hall et al. [11] have shown that the dynamic multicommodity flow problem is NP-hard even for series-parallel graphs or have only two commodities. Kappmeier [12] provided a solution to the maximum dynamic multicommodity flow problem using a time-expanded network within pseudo-polynomial time complexity.Contraflow implies flipping of arc orientations to amplify the flow and reduce the travel time by increasing its capacity. Furthermore, increased traffic on roadways causes a slew of mobility issues because of congestion. As a result, contraflow plays a significant role in transportation sector planning, rush hour traffic management, and emergency evacuation planning.Analytical solutions for two-terminal single-commodity maximum and quickest contraflow problems withτe=τer were obtained by Rebennack et al. [13] in strongly polynomial time. The lane reversals are made at time zero and kept fixed afterward. For more details on contraflow problems, we refer to [14] and references therein. Flow with intermediate storage was investigated by Pyakurel and Dempe in [15, 16]. Authors in [17–19] extended a partial contraflow approach in multicommodity flow problems and provided the solution.Due to the uneven road network, transit time fromv to w of an arc v,w is different from w to v which means that it is asymmetrical, i.e., τe≠τer as shown in Figure 1(a). To deal with this, we have the following assumptions.
(i)
The capacities of auxiliary arcs is the sum of capacities of arcse and er, i.e., ua=ue+uer(ii)
The transit time of auxiliary arcτa is taken as transit time of nonreversed arcs as shown in Figures 1(b) and 1(c)(iii)
In the case of a single direction for eache∈A, there exist er∈A and τa=τe=τer for contraflow configurationFigure 1
(a) represents a two-way road network, (b) represents the network, if arcer is reversed in the direction of arc e, and (c) represents the network, if arc e is reversed in the direction of arc er.
(a)(b)(c)By modifying the algorithm of [13], Nath et al. [20] solved the dynamic contraflow problems such that the reversals use asymmetric transit times that should be taken by unreserved ones. Recently, Gupta et al. [21] extended the approach of Nath et al. [20] in case of lexicographic flow and earliest arrival transshipment problems and presented algorithms to solve them. The same authors in [22] also introduced this approach in the case of a lossy network with τe≠τer on arcs and provided the algorithms to solve the problem in the discrete- and continuous-time setting for single-commmodity. The extension of this problem in multicommodity was investigated in [23].


### 1.1. Contribution of the Paper

We introduce the contraflow approach withτe≠τer in a multicommodity flow problem and present an algorithm to solve the maximum dynamic multicommodity contraflow (DMCCF) problem on the time-expanded graph in pseudo-polynomial time. We also present a fully polynomial time approximation scheme (FPTAS) to solve the same problem by using a Δ-condensed time-expanded network. This technique reduces the congestion in rush hour traffic that minimizes the delivery time of commodities (goods) from factory outlets to the retailer and minimizes the transportation cost by maximizing the commodities. We only reverse the necessary arc capacities and save the unused arc capacities that can be used in case of emergency for logistic support by putting the facility on the saved arcs (cf. Figure 2). It can also be used to park the vehicle for a certain time to reduce congestion. To the best of our knowledge, these contributions are new.Figure 2
(a) Given network and (b) auxiliary network of (a).
(a)
(Capacity, transit time)(b)
(Capacity, transit time)The paper is organized as follows. In Section2, we provide some basic notations and models used in the article. The maximum DMCCF problem with asymmetric transit times on arcs is introduced in Section 3. We present a pseudo-polynomial time algorithm and an FPTAS to solve this problem in the same section. The paper is concluded in Section 4.


## 1.1. Contribution of the Paper

We introduce the contraflow approach withτe≠τer in a multicommodity flow problem and present an algorithm to solve the maximum dynamic multicommodity contraflow (DMCCF) problem on the time-expanded graph in pseudo-polynomial time. We also present a fully polynomial time approximation scheme (FPTAS) to solve the same problem by using a Δ-condensed time-expanded network. This technique reduces the congestion in rush hour traffic that minimizes the delivery time of commodities (goods) from factory outlets to the retailer and minimizes the transportation cost by maximizing the commodities. We only reverse the necessary arc capacities and save the unused arc capacities that can be used in case of emergency for logistic support by putting the facility on the saved arcs (cf. Figure 2). It can also be used to park the vehicle for a certain time to reduce congestion. To the best of our knowledge, these contributions are new.Figure 2
(a) Given network and (b) auxiliary network of (a).
(a)
(Capacity, transit time)(b)
(Capacity, transit time)The paper is organized as follows. In Section2, we provide some basic notations and models used in the article. The maximum DMCCF problem with asymmetric transit times on arcs is introduced in Section 3. We present a pseudo-polynomial time algorithm and an FPTAS to solve this problem in the same section. The paper is concluded in Section 4.


## 2. Preliminaries

In this section, we give some basic notations and definitions, with the flow models used in this paper to make it self-contained.The Flow Models. Let us consider the network topologyN=V,A,K,u,τ,di,S+,S−,T, where V denotes the set of nodes, A is the set of arcs, and K=1,2,⋯,k is the set of commodities with V=n and A=m. Each commodity i∈K is routed through a unique source-sink pair si,ti. The sets S+ and S−⊂V denote the source and sink sets of all commodities, respectively. On each arc e=v,w, the capacity function u:A⟶ℝ≥0 restricts the flow of commodities, and a nonnegative transit time function τ:A⟶ℝ≥0 measures the time to transship the flow from the entry point v to the exit point w of arc e=v,w. The number di denotes the demand and supply of commodity in each commodity i. A static network is a network besides the temporal dimension denoted by N=V,A,K,u,di,S+,S−.


### 2.1. Dynamic Multicommodity Flow

A discrete dynamic multicommodity flowΦ on the given network N with constant transit time on arcs is a sum of flows defined by the function Φi:Aa×T⟶ℝ+ for given time T satisfying the following constraints:
(1)∑e∈Bv∑δ=0T−τeΦeiδ−∑e∈Av∑δ=0TΦeiδ=0,v∉S+,S−,(2)∑e∈Bv∑δ=0θ−τeΦeiδ−∑e∈Av∑δ=0θΦeiδ≥0,∀θ∈T,v≠S+,(3)0≤∑i=1kΦeiθ≤ue+uer,∀e∈A,θ∈T.The maximum DMCCF problem is to find a DMCCF of maximum value∑Φi in
(4)max∑i∈KΦi=max∑e∈Bd∑δ=0T−τeΦeiδ.The time periodT is denoted by T=0,1,⋯,T in discrete-time settings and T=0,T in continuous-time settings. The sets Av=v,w∣w∈V and Bv=w,v∣w∈V denote outgoing arcs from node v and incoming arcs to node v, respectively, such that AS−=BS+=∅, except in the lane reversal network. The constraints in (1) are flow conservation constraints at intermediate nodes for time horizon T, whereas the constraints in (2) represent nonconservation of flow at intermediate time points. The constraints in (3) are capacity constraints bounded by capacities of the auxiliary network. Also, the maximum static flow problem has an analogous formulation by dropping out the time parameters in constraints (1)–(3) and the objective function (4), respectively.


### 2.2.Δ-Condensed Time-Expanded Graph

For the networkN=V,A,K,u,τ,di,S+,S−,T, authors in [24] introduced the Δ-condensed time-expanded network NTΔ=VTΔ,ATΔ=AMΔ∪AHΔ∪A+Δ∪A−Δ,K,u′,τ′,di,S+′,S−′,T, where all transit times on arcs are multiple of Δ>0 such that T/Δ is bounded by a polynomial in the input size. The number di,v denotes the supplies and demands for each vertex v∈V and each commodity i∈K. The nodes and arcs in the Δ-condensed time-expanded network are defined as
(5)VTΔ=vθ:v∈V,θ=0,1,2,⋯,TΔ∪si′,ti′:i∈K∪s∗,t∗,AMΔ=vθ,wθ+τe:e=v,w∈A,θ=0,1,⋯,T−τeΔ,AHΔ=vθ,vθ+1:e=v,w∈A,θ=0,1,⋯,TΔ−1,A+Δ=∪s∗,si′:i∈K∪si′,sθ:i∈K,si′∈S+′,θ∈0,1,2,⋯,TΔ,A−Δ=∪ti′,t∗:i∈K∪tθ,ti′:i∈K,ti′∈S−′,θ∈0,1,2,⋯,TΔ,where S′+=si′∪s∗ and S′−=ti′∪t∗ for all i∈K. The sets si′ and ti′ are superterminals for each commodity, and s∗,t∗ represents superterminals for the Δ-condensed time-expanded network. The capacities are defined as
(6)u′e′=ue,ifarce′∈AMΔ∪AHΔwithe′=eθ,∞,else,if node balances are not given. The capacities are defined by
(7)u′e′=ue,ifarce′∈AMΔ∪AHΔwithe′=eθ,di,s,e′=s∗,si′,−di,t,e′=ti′,t∗,∞,else,if node balances are given as in [12].In timeT=αΔ for discrete-time or T=αΔ,α+1Δ for continuous-time, the copies of VTΔ correspond to flow through V, where α=0,1,2,⋯,T/Δ. For every arc corresponding to a discrete-time setting with multiple of Δ, capacities are rescaled by Δue. If transit times on arcs are not multiple of Δ, then they are rounded up to multiple of Δ by τ′e=τe/ΔΔ and 0≤τ′e−τe<Δ for all arcs e∈A. A Δ-condensed time-expanded network reduces to the classical time-expanded network, if Δ=1.Example 1.
Given a multicommodity networkN with asymmetric transit times on arcs, where s1,s2 are the source nodes and t1,t2 are the sink nodes as shown in Figure 2(a), the arcs between nodes v and w denoted by v,w and w,v represent two-way road segments. The first and second numbers on the arcs represent capacity and transit time (cost) associated with the arcs. By adding two-way capacities of the arcs e and er, an auxiliary network is formed with capacities ua and transit time of nonreversed as τa shown in Figure 2(b).


## 2.1. Dynamic Multicommodity Flow

A discrete dynamic multicommodity flowΦ on the given network N with constant transit time on arcs is a sum of flows defined by the function Φi:Aa×T⟶ℝ+ for given time T satisfying the following constraints:
(1)∑e∈Bv∑δ=0T−τeΦeiδ−∑e∈Av∑δ=0TΦeiδ=0,v∉S+,S−,(2)∑e∈Bv∑δ=0θ−τeΦeiδ−∑e∈Av∑δ=0θΦeiδ≥0,∀θ∈T,v≠S+,(3)0≤∑i=1kΦeiθ≤ue+uer,∀e∈A,θ∈T.The maximum DMCCF problem is to find a DMCCF of maximum value∑Φi in
(4)max∑i∈KΦi=max∑e∈Bd∑δ=0T−τeΦeiδ.The time periodT is denoted by T=0,1,⋯,T in discrete-time settings and T=0,T in continuous-time settings. The sets Av=v,w∣w∈V and Bv=w,v∣w∈V denote outgoing arcs from node v and incoming arcs to node v, respectively, such that AS−=BS+=∅, except in the lane reversal network. The constraints in (1) are flow conservation constraints at intermediate nodes for time horizon T, whereas the constraints in (2) represent nonconservation of flow at intermediate time points. The constraints in (3) are capacity constraints bounded by capacities of the auxiliary network. Also, the maximum static flow problem has an analogous formulation by dropping out the time parameters in constraints (1)–(3) and the objective function (4), respectively.


## 2.2.Δ-Condensed Time-Expanded Graph

For the networkN=V,A,K,u,τ,di,S+,S−,T, authors in [24] introduced the Δ-condensed time-expanded network NTΔ=VTΔ,ATΔ=AMΔ∪AHΔ∪A+Δ∪A−Δ,K,u′,τ′,di,S+′,S−′,T, where all transit times on arcs are multiple of Δ>0 such that T/Δ is bounded by a polynomial in the input size. The number di,v denotes the supplies and demands for each vertex v∈V and each commodity i∈K. The nodes and arcs in the Δ-condensed time-expanded network are defined as
(5)VTΔ=vθ:v∈V,θ=0,1,2,⋯,TΔ∪si′,ti′:i∈K∪s∗,t∗,AMΔ=vθ,wθ+τe:e=v,w∈A,θ=0,1,⋯,T−τeΔ,AHΔ=vθ,vθ+1:e=v,w∈A,θ=0,1,⋯,TΔ−1,A+Δ=∪s∗,si′:i∈K∪si′,sθ:i∈K,si′∈S+′,θ∈0,1,2,⋯,TΔ,A−Δ=∪ti′,t∗:i∈K∪tθ,ti′:i∈K,ti′∈S−′,θ∈0,1,2,⋯,TΔ,where S′+=si′∪s∗ and S′−=ti′∪t∗ for all i∈K. The sets si′ and ti′ are superterminals for each commodity, and s∗,t∗ represents superterminals for the Δ-condensed time-expanded network. The capacities are defined as
(6)u′e′=ue,ifarce′∈AMΔ∪AHΔwithe′=eθ,∞,else,if node balances are not given. The capacities are defined by
(7)u′e′=ue,ifarce′∈AMΔ∪AHΔwithe′=eθ,di,s,e′=s∗,si′,−di,t,e′=ti′,t∗,∞,else,if node balances are given as in [12].In timeT=αΔ for discrete-time or T=αΔ,α+1Δ for continuous-time, the copies of VTΔ correspond to flow through V, where α=0,1,2,⋯,T/Δ. For every arc corresponding to a discrete-time setting with multiple of Δ, capacities are rescaled by Δue. If transit times on arcs are not multiple of Δ, then they are rounded up to multiple of Δ by τ′e=τe/ΔΔ and 0≤τ′e−τe<Δ for all arcs e∈A. A Δ-condensed time-expanded network reduces to the classical time-expanded network, if Δ=1.Example 1.
Given a multicommodity networkN with asymmetric transit times on arcs, where s1,s2 are the source nodes and t1,t2 are the sink nodes as shown in Figure 2(a), the arcs between nodes v and w denoted by v,w and w,v represent two-way road segments. The first and second numbers on the arcs represent capacity and transit time (cost) associated with the arcs. By adding two-way capacities of the arcs e and er, an auxiliary network is formed with capacities ua and transit time of nonreversed as τa shown in Figure 2(b).


## 3. Dynamic Multicommodity Contraflow

In this section, we introduce the maximum DMCCF by reverting the necessary arc capacities. Hall et al. [11] proved that the dynamic multicommodity flow problem is NP-hard.


### 3.1. Pseudo-Polynomial Solution of Maximum DMCCF

Time expansion is an important tool to solve dynamic flow problems introduced by Ford and Fulkerson [7] for a single-commodity flow problem. Further, it can be extended to the case of the multicommodity flow problem. Kappmeier [12] and Lozovanu and Fonoberova [25] have shown the equivalency between static multicommodity flow on the time-expanded network and dynamic multicommodity flow on the original network as given below.Lemma 1.
LetN=V,A,K,u,τ,di,S+,S−,T be a dynamic network. For any time horizon T, in a feasible static S′+−S′− multicommodity flow f in the time-expanded network NT, there exists a feasible dynamic multicommodity flow Φ with the sources S+ and sinks S− in network N that sends the equal amount of flow within the same time horizon T, i.e., fT=Φ and vice versa.Maximum dynamic contraflow problems for a single commodity with unequal transit times on antiparallel arcs are solved by Nath et al. [20]. Based on this, we introduce the contraflow approach on the dynamic multicommodity flow problem with asymmetric transit times on antiparallel arcs and present Problem 2.Problem 2.
Consider a networkN=V,A,K,u,τ,di,S+,S−,T with asymmetric transit times on arcs. The maximum DMCCF problem sends the maximum flow in the unique pair of source and sink nodes si,ti for each commodity i=1,2,⋯,k and for a given time by saving the unused arc capacity.To find the solution of the maximum dynamic multicommodity contraflow problem with asymmetric transit times on arcs (Problem2), we design Algorithm 1.Algorithm 1:Algorithm for maximum DMCCF.
Input: Given dynamic multicommodity flow network N=V,A,K,u,τ,di,S+,S−,T1. A given dynamic network is transformed into time-expanded network byNT=VT,AT=AM∪AH∪A+∪A−,K,u,τ,di,S+′,S−′,T2. An auxiliary networkNTa=VT,ATa,K,ua,τa,di,S+′,S−′,T is constructed withu′a=ue+uerτ′a=τeifarcerisreversedindirectionofeτerifarceisreversedindirectionofer.3. Compute the MSMCFf on the auxiliary network NTa.4. Decomposef along the si−ti,∀i∈K paths and cycles and remove cycle flows and update f.5. Reverseerθ∈AT up to the capacity faθ−ue iff faθ>ue, ue replaced by 0 whenever eθ∉AT where fe=∑i=1kfei and ue=∑i=1kuei.6. For eacheθ∈AT, if erθ is reversed, scerθ=ua−feθ and sceθ=0. If neither e nor er is reversed, sceθ=ue−feθ>0, where sceθ is the saved capacity of e.Output: The Maximum DMCCFTheorem 3.
Algorithm1 solves the maximum DMCCF problem with asymmetric transit times on arcs in pseudo-polynomial time.Proof.
The proof of feasibility is obvious as it transforms the given dynamic network flow problem into the static network flow problem on the time-expanded auxiliary network. A feasible solution of maximum dynamic multicommodity flow onNTa is also feasible to the maximum DMCCF solution on network N. As described above, the dynamic multicommodity flow problem on network N reduces to a static multicommodity flow problem on NTa. By reducing the multicommodity to a single-commmodity and decomposing the flow into si−ti paths, dynamic multicommodity flow solution can be obtained optimally on the auxiliary network NTa. An optimal solution on NTa is equivalent to a feasible solution on N. The unused capacities of the arcs are saved by partial lane reversals in Step 5.
In the time-expanded graph, there areT copies of the given network. Since the time-expanded graph has T+1n nodes and OTm+2=OTm edges, therefore applying the algorithm on the time-expanded graph has a time complexity of OT2mn. As running time depends polynomially on OT2mn; hence, it is pseudo-polynomial.Example 2.
We compute maximum dynamic multicommodity flow on the auxiliary network obtained by adding two-way capacities of Figure2(a) within time horizon T=8. The repetition of path flows of each commodity is shown in a time-expanded network. We get static flow f on the time-expanded network which corresponds to multicommodity flow over time Φ on the auxiliary network. Since only essential arc capacities are reverted, certain capacities are preserved (cf. Figure 3).Figure 3
A network with the flow and saved capacities on arcs.The maximum dynamic multicommodity contraflow computation is shown in Figure4.Figure 4
Time-expanded network of Figure2(b).The comparison of maximum dynamic multicommodity flow before and after lane reversals is shown in Table1 and Figure 5.Table 1
Maximum dynamic multicommodity flow before and after lane reversals.
Time-expanded graphPathTimeFlow before LRTotal flowFlow after LRTotal flows1−v−x−w−t161326s1−v−x−y−w−t171212s2−v−y−w−t272448Total916LR = lane reversals.Figure 5
Comparison of flow before and after lane reversals.The percentage increment after lane reversals is 77.77.


### 3.2. Approximate Solution of Maximum DMCCF

A well-known technique to solve dynamic flow problems is a time-expanded network, but it has the drawback of a large blowup of its size. By reducing the size of the time-expanded network, an efficient algorithm is presented. This reduction technique is known as condensation in the setting of a time-expanded network, and the network is known as theΔ-condensed time-expanded network. If we take Δ=1, then the Δ-condensed time-expanded network reduces to the classical time-expanded network. To solve Problem 2 in fully polynomial time, we present Algorithm 2.Algorithm 2: An FPTAS algorithm for maximum DMCCF with asymmetric transit times on arcs.
Input: Given dynamic multicommodity flow network N=V,A,K,u,τ,di,S+,S−,T1. The auxiliary networkNa is transformed to Δ-condensed auxiliary network NTΔa=VTΔ,ATΔa,K,ua′,τa′,di,S+′,S−′,T withu′a=Δue+uerτ′a=τe/ΔΔifarcerreversedinthedirectionofeτer/ΔΔifarcereversedinthedirectionofer.2. Compute the MSMCFf on the auxiliary network NTΔa.3. Decomposef along the si−ti,∀i∈K paths and cycles, remove cycle flows and update f.4. Reverseerθ∈ATΔ up to the capacity fe′θ−u′e iff fe′θ>u′e, ue replaced by 0 whenever eθ∉ATΔ where f′e=∑i=1kf′ei and u′e=∑i=1ku′ei.5. For eacheθ∈ATΔ, if erθ is reversed, scerθ=ua−feθ and sceθ=0. If neither e nor er is reversed, sceθ=ue−feθ>0, where sceθ is the saved capacity of e.Output: The maximum DMCCFTheorem 4.
Algorithm2 provides an approximate solution to the maximum DMCCF problem with asymmetric transit times on arcs.Proof.
The proof of feasibility is similar to Theorem3.
Next, we prove the optimality. Feasibility implies that an approximate optimal solution of maximum DMCCF on networkN is also a feasible approximate solution to the maximum dynamic multicommodity flow on NTΔa. The dynamic multicommodity flow problem on network N reduces to a static multicommodity flow problem on NTΔa. By reducing the multicommodity to a single-commmodity and decomposing it into the si−ti path, an approximate dynamic multicommodity flow solution can be obtained optimally on the auxiliary network NTΔa. An approximate optimal solution on NTΔa is a feasible solution on N. The unused capacities of the arcs by partial contraflow are saved in Step 5. Thus, an approximate maximum DMCCF solution on each arc of the given network N can be computed optimally.Corollary 5.
An FPTAS to the maximum DMCCF problem can be computed in fully polynomial time complexity.Proof.
The complexity of Algorithm2 is dominated by Steps 2 and 3. The Δ-condensed auxiliary network contains n2/ε2 nodes and mn/ε2 arcs. Since Steps 2 and 3 are solved in polynomial time and the remaining steps can be solved in linear time, it is polynomial in input size as well as 1/ε. Thus, the solution can be computed in fully polynomial time.Example 3.
By scaling the capacities and transit times on arcs given in Figure2(b), Δ-condensed networks are formed. The approximate solution of Problem 2 can be calculated by using the Δ-condensed time-expanded network as shown in Figure 6 by taking Δ=2.Figure 6
Δ-condensed time-expanded network of Figure 2(b) after scaling capacity and transit time.The comparison of MDMCF before and after lane reversals is shown in Table2.Table 2
Maximum dynamic multicommodity flow before and after lane reversals.
Δ-condensed time-expanded graphPathTimeFlow before LRTotal flowFlow after LRTotal flows1−v−x−w−t182244s1−v−y−w−t182222s2−v−y−w−t284448Total814LR = lane reversals.The percentage increment in flow value after lane reversal is 75.


## 3.1. Pseudo-Polynomial Solution of Maximum DMCCF

Time expansion is an important tool to solve dynamic flow problems introduced by Ford and Fulkerson [7] for a single-commodity flow problem. Further, it can be extended to the case of the multicommodity flow problem. Kappmeier [12] and Lozovanu and Fonoberova [25] have shown the equivalency between static multicommodity flow on the time-expanded network and dynamic multicommodity flow on the original network as given below.Lemma 1.
LetN=V,A,K,u,τ,di,S+,S−,T be a dynamic network. For any time horizon T, in a feasible static S′+−S′− multicommodity flow f in the time-expanded network NT, there exists a feasible dynamic multicommodity flow Φ with the sources S+ and sinks S− in network N that sends the equal amount of flow within the same time horizon T, i.e., fT=Φ and vice versa.Maximum dynamic contraflow problems for a single commodity with unequal transit times on antiparallel arcs are solved by Nath et al. [20]. Based on this, we introduce the contraflow approach on the dynamic multicommodity flow problem with asymmetric transit times on antiparallel arcs and present Problem 2.Problem 2.
Consider a networkN=V,A,K,u,τ,di,S+,S−,T with asymmetric transit times on arcs. The maximum DMCCF problem sends the maximum flow in the unique pair of source and sink nodes si,ti for each commodity i=1,2,⋯,k and for a given time by saving the unused arc capacity.To find the solution of the maximum dynamic multicommodity contraflow problem with asymmetric transit times on arcs (Problem2), we design Algorithm 1.Algorithm 1:Algorithm for maximum DMCCF.
Input: Given dynamic multicommodity flow network N=V,A,K,u,τ,di,S+,S−,T1. A given dynamic network is transformed into time-expanded network byNT=VT,AT=AM∪AH∪A+∪A−,K,u,τ,di,S+′,S−′,T2. An auxiliary networkNTa=VT,ATa,K,ua,τa,di,S+′,S−′,T is constructed withu′a=ue+uerτ′a=τeifarcerisreversedindirectionofeτerifarceisreversedindirectionofer.3. Compute the MSMCFf on the auxiliary network NTa.4. Decomposef along the si−ti,∀i∈K paths and cycles and remove cycle flows and update f.5. Reverseerθ∈AT up to the capacity faθ−ue iff faθ>ue, ue replaced by 0 whenever eθ∉AT where fe=∑i=1kfei and ue=∑i=1kuei.6. For eacheθ∈AT, if erθ is reversed, scerθ=ua−feθ and sceθ=0. If neither e nor er is reversed, sceθ=ue−feθ>0, where sceθ is the saved capacity of e.Output: The Maximum DMCCFTheorem 3.
Algorithm1 solves the maximum DMCCF problem with asymmetric transit times on arcs in pseudo-polynomial time.Proof.
The proof of feasibility is obvious as it transforms the given dynamic network flow problem into the static network flow problem on the time-expanded auxiliary network. A feasible solution of maximum dynamic multicommodity flow onNTa is also feasible to the maximum DMCCF solution on network N. As described above, the dynamic multicommodity flow problem on network N reduces to a static multicommodity flow problem on NTa. By reducing the multicommodity to a single-commmodity and decomposing the flow into si−ti paths, dynamic multicommodity flow solution can be obtained optimally on the auxiliary network NTa. An optimal solution on NTa is equivalent to a feasible solution on N. The unused capacities of the arcs are saved by partial lane reversals in Step 5.
In the time-expanded graph, there areT copies of the given network. Since the time-expanded graph has T+1n nodes and OTm+2=OTm edges, therefore applying the algorithm on the time-expanded graph has a time complexity of OT2mn. As running time depends polynomially on OT2mn; hence, it is pseudo-polynomial.Example 2.
We compute maximum dynamic multicommodity flow on the auxiliary network obtained by adding two-way capacities of Figure2(a) within time horizon T=8. The repetition of path flows of each commodity is shown in a time-expanded network. We get static flow f on the time-expanded network which corresponds to multicommodity flow over time Φ on the auxiliary network. Since only essential arc capacities are reverted, certain capacities are preserved (cf. Figure 3).Figure 3
A network with the flow and saved capacities on arcs.The maximum dynamic multicommodity contraflow computation is shown in Figure4.Figure 4
Time-expanded network of Figure2(b).The comparison of maximum dynamic multicommodity flow before and after lane reversals is shown in Table1 and Figure 5.Table 1
Maximum dynamic multicommodity flow before and after lane reversals.
Time-expanded graphPathTimeFlow before LRTotal flowFlow after LRTotal flows1−v−x−w−t161326s1−v−x−y−w−t171212s2−v−y−w−t272448Total916LR = lane reversals.Figure 5
Comparison of flow before and after lane reversals.The percentage increment after lane reversals is 77.77.


## 3.2. Approximate Solution of Maximum DMCCF

A well-known technique to solve dynamic flow problems is a time-expanded network, but it has the drawback of a large blowup of its size. By reducing the size of the time-expanded network, an efficient algorithm is presented. This reduction technique is known as condensation in the setting of a time-expanded network, and the network is known as theΔ-condensed time-expanded network. If we take Δ=1, then the Δ-condensed time-expanded network reduces to the classical time-expanded network. To solve Problem 2 in fully polynomial time, we present Algorithm 2.Algorithm 2: An FPTAS algorithm for maximum DMCCF with asymmetric transit times on arcs.
Input: Given dynamic multicommodity flow network N=V,A,K,u,τ,di,S+,S−,T1. The auxiliary networkNa is transformed to Δ-condensed auxiliary network NTΔa=VTΔ,ATΔa,K,ua′,τa′,di,S+′,S−′,T withu′a=Δue+uerτ′a=τe/ΔΔifarcerreversedinthedirectionofeτer/ΔΔifarcereversedinthedirectionofer.2. Compute the MSMCFf on the auxiliary network NTΔa.3. Decomposef along the si−ti,∀i∈K paths and cycles, remove cycle flows and update f.4. Reverseerθ∈ATΔ up to the capacity fe′θ−u′e iff fe′θ>u′e, ue replaced by 0 whenever eθ∉ATΔ where f′e=∑i=1kf′ei and u′e=∑i=1ku′ei.5. For eacheθ∈ATΔ, if erθ is reversed, scerθ=ua−feθ and sceθ=0. If neither e nor er is reversed, sceθ=ue−feθ>0, where sceθ is the saved capacity of e.Output: The maximum DMCCFTheorem 4.
Algorithm2 provides an approximate solution to the maximum DMCCF problem with asymmetric transit times on arcs.Proof.
The proof of feasibility is similar to Theorem3.
Next, we prove the optimality. Feasibility implies that an approximate optimal solution of maximum DMCCF on networkN is also a feasible approximate solution to the maximum dynamic multicommodity flow on NTΔa. The dynamic multicommodity flow problem on network N reduces to a static multicommodity flow problem on NTΔa. By reducing the multicommodity to a single-commmodity and decomposing it into the si−ti path, an approximate dynamic multicommodity flow solution can be obtained optimally on the auxiliary network NTΔa. An approximate optimal solution on NTΔa is a feasible solution on N. The unused capacities of the arcs by partial contraflow are saved in Step 5. Thus, an approximate maximum DMCCF solution on each arc of the given network N can be computed optimally.Corollary 5.
An FPTAS to the maximum DMCCF problem can be computed in fully polynomial time complexity.Proof.
The complexity of Algorithm2 is dominated by Steps 2 and 3. The Δ-condensed auxiliary network contains n2/ε2 nodes and mn/ε2 arcs. Since Steps 2 and 3 are solved in polynomial time and the remaining steps can be solved in linear time, it is polynomial in input size as well as 1/ε. Thus, the solution can be computed in fully polynomial time.Example 3.
By scaling the capacities and transit times on arcs given in Figure2(b), Δ-condensed networks are formed. The approximate solution of Problem 2 can be calculated by using the Δ-condensed time-expanded network as shown in Figure 6 by taking Δ=2.Figure 6
Δ-condensed time-expanded network of Figure 2(b) after scaling capacity and transit time.The comparison of MDMCF before and after lane reversals is shown in Table2.Table 2
Maximum dynamic multicommodity flow before and after lane reversals.
Δ-condensed time-expanded graphPathTimeFlow before LRTotal flowFlow after LRTotal flows1−v−x−w−t182244s1−v−y−w−t182222s2−v−y−w−t284448Total814LR = lane reversals.The percentage increment in flow value after lane reversal is 75.


## 4. Conclusions

The maximum multicommodity flow over time problem is the transshipment of several kinds of commodities (goods) in underlying network topology, respecting capacity constraints on the arcs with the objective of maximizing the sum of flow of all commodities in the specified period. It is computationally hard. A time expansion is a technique to solve dynamic flow problems, but it has pseudo-polynomial time complexity. By reducing the size of the network, by a factor ofΔ, a Δ-condensed time-expanded network is introduced without changing flow values too much; an efficient approximation scheme is developed.By flipping the orientation of lanes and taking the transit time of the nonflipped arc, the capacity of the lanes will be increased that amplifies the flow value and reduces the time horizon that reflects the situation of contraflow of uneven road topology in the real sense. The maximum dynamic multicommodity partial contraflow problem with symmetric transit times on arcs was solved in pseudo-polynomial time. An FPTAS was also developed.In this paper, we introduced a dynamic multicommodity partial contraflow problem with asymmetric transit times on arcs. To solve it, we presented two algorithms. The first algorithm solved the problem in pseudo-polynomial time, and the second one provided an approximate solution in fully polynomial time complexity. Theorem3 proved the feasibility and optimality of Algorithm 1. It has also calculated the time complexity of the algorithm. So, the correctness of Algorithm 1 is proven. By taking an instance, we have shown that the flow value is increased by 77.7% after contraflow (cf. Table 1 and Figure 5). Algorithm 2 provides an approximate solution of the same problem by taking larger time steps instead of single time steps, and its correctness is proven in Theorem 4. It has been shown that the flow value is increased by 75% after contraflow (cf. Table 2). Although the flow increment in the second case is less than the first one, the second one is better because it solves the problem in polynomial time. The major objective of this work is to provide theoretical results that are most applicable to reducing traffic congestion. Implementation of these results will be an agenda of future work. By analyzing impressive results from this study, it would be interesting to extend it further to the earliest arrival multicommodity flow problems.



---

*Source: 3697141-2022-02-22.xml*