# Maximum Multicommodity Flow with Intermediate Storage

Authors: Durga Prasad Khanal; Urmila Pyakurel; Tanka Nath Dhamala
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The multicommodity flow problem deals with the transshipment of more than one commodity from respective sources to corresponding sinks without violating the capacity constraints. Due to the capacity constraints, flows out from the sources may not reach their sinks, and so, the storage of excess flows at intermediate nodes plays an important role in the maximization of flow values. In this paper, we introduce the maximum static as well as maximum dynamic multicommodity flow problems with intermediate storage. We present polynomial and pseudopolynomial time algorithms for the former and latter problems, respectively. We also present the solution procedures to these problems in contraflow network having symmetric as well as asymmetric arc transit times. We transform the solutions in continuous-time settings by using natural transformation.


---

## Body

## 1. Introduction

Network is a topological structure with links (arcs), with its crossings (nodes) being its components. The transportation network is one of the relevant examples of a network topology, in which road segments are considered as the arcs and their crossings as nodes. Any kinds of entities moving on the road are considered as flows, and their initial and final destinations are considered as the source and sink, respectively. Each arc has nonnegative capacity, which limits the flow on arc. Dynamic network has one more attribute on arc, i.e., transit time, which represents the time to send the flow from one node to another one. Ford and Fulkerson are the pioneers of the network flow over time (so-called dynamic flow) problems [1, 2].The transshipment of several different commodities from respective sources to corresponding sinks through a network without violating the capacity constraints on the arcs is known as multicommodity flow problem. Vehicle routine in transportation, production planning, supply chains for essential goods, and massage routing in telecommunication are some examples of multicommodity flow problem. On the basis of temporal dimension, multicommodity flow problem can be classified as static multicommodity flow problem and dynamic multicommodity flow problem [3–6]. If we maximize the supply-demand in a fixed time horizon, then the problem becomes a maximum dynamic multicommodity flow problem. The static multicommodity flow problem is polynomial time solvable by using the ellipsoid or interior point method, whereas dynamic multicommodity flow problem is NP-hard [7]. By using time expanded network, Kappmeier [8] provided the solution of maximum dynamic multicommodity flow problem and multisource single sink multicommodity earliest arrival transshipment problem in pseudopolynomial time complexity. Priority-based multicommodity flow problem and polynomial time solution strategy are presented in [9].Maximum flow problem with intermediate storage is extremely relevant in large scale disaster management. In evacuation models, one wishes to shift maximum evacuees from danger zones (sources) to safety places (sinks) as quickly and efficiently as possible. Thus, at the time of evacuation, if the number of evacuees out from sources is greater than the minimum cut capacity, then the excess evacuees can be placed at intermediate shelters that are comparatively safer than the danger zone. The various applications of the network flow with intermediate storage are evacuation planning, demand-supply chain of goods, water supply system, etc. Pyakurel and Dempe [10] introduced the concept of maximum static and maximum dynamic flow problems with intermediate storage and presented polynomial time algorithms to solve them. They also presented polynomial time algorithm for dynamic contraflow problem with intermediate storage. In case of multisource multisink network, Pyakurel et al. [11] solved the prioritized maximum flow problem with intermediate storage and presented polynomial time algorithm to solve the problem, where priority is given to the farthest element from the source. Recently, Pyakurel and Dempe [12] presented efficient algorithms for universal maximum dynamic flow problem with intermediate storage in general as well as two-terminal series parallel networks.In two-way network, contraflow (lane reversal) is one of the best techniques to increase the outbound capacities of arcs and minimize the overall time horizon, in which arcs are reversed towards the destination [13]. Rebennack et al. [14] provided the models and polynomial time algorithms for maximum and quickest flow problems in a two-terminal network by reverting the arcs at time zero and keeping them fixed afterward by using analytical approach for discrete-time settings. In continuous-time settings, Pyakurel and Dhamala [15] introduced the dynamic contraflow model. By using the natural transformation of Fleischer and Tardos [16], they have presented efficient algorithms to solve the maximum, quickest, and earliest arrival flow problems with lane reversals.Pyakurel et al. [17] introduced the concept of partial lane reversals, in which only necessary arc capacities are reversed to increase the flow value, and unused arc capacities are saved for other emergency proposes like logistic supports and facility locations. Dhamala et al. [18] presented approximation algorithms for quickest multicommodity flow over time problem with partial lane reversals using length bound flow and condensed time expanded network in discrete-time settings. Continuous-time solutions of these problems are found in [19]. Similarly, Pyakurel et al. [20] presented polynomial time algorithm for maximum static and pseudopolynomial algorithm for maximum dynamic multicommodity flow problems with partial lane reversals.In this paper, we aim to find the solution of discrete-time maximum multicommodity flow problem with intermediate storage by integrating the concept of multicommodity flow problem and the maximum flow problem with intermediate storage. We present polynomial time algorithm for static multicommodity flow problem and pseudopolynomial time algorithm for dynamic multicommodity flow problem by allowing the storage of excess flow at intermediate nodes. We extend the results for contraflow configuration with symmetric as well as asymmetric transit times and also in continuous-time settings.Our models are designed with the following limitations: at each intermediate node, inflow must be greater or equal to the outflow. At each arc, flow must not exceed the capacity. The storage capacity of intermediate nodes must be at least the sum of incoming arc capacities. Every commodity must transship from respective sources to their corresponding sinks. Objects within a commodity group are homogeneous and between the commodity groups are heterogeneous.We organize the paper as follows. Section2 provides the basic terminologies used in the paper and the mathematical formulation of flow models. In Section 3, we present a polynomial time algorithm to solve the maximum static multicommodity flow problem with intermediate storage, and in Section 4, we solve the maximum dynamic multicommodity flow problem with intermediate storage in pseudopolynomial time complexity. For two-way multicommodity network, we present a solution procedure of these problems in Section 5 within the same time complexity. Similarly, in Section 6, we extend the results of dynamic flow problems in continuous-time settings by using natural transformation. The paper is concluded in Section 7.


## 2. Basic Terminologies and Mathematical Models

Consider a dynamic networkN=V,A,K,u,b,τ,di,S,D,T, where V and A⊆V×V represent the sets of nodes and arcs with V=n and A=m, respectively. Let si∈S⊂V and ti∈D⊂V be the source and sink nodes with respect to commodity i∈K=1,2,…,k and I=V∖S,D the set of intermediate nodes. Here, di represents the amount of supply from the source node si for each commodity i∈K that is to be sent to the corresponding sink ti and the intermediate nodes I. Each arc a=v,w∈A with heada=w and taila=v is equipped with a capacity function u:A⟶ℛ+ that restricts the flow of commodity and a nonnegative transit time function τ:A⟶ℛ+ that measures the time to transship the flow from node v to node w. Similarly, b:V⟶ℛ+ represents the storage capacity function of nodes that is used to hold the flow at sources and sinks, together with the storage of excess flow leaving from the source si but not reaching the sink ti at intermediate nodes. Capacity of arcs (roads) and the storage capacity of nodes (shelters) are the controlling parameters of our model, which control the flow at arcs and nodes, respectively. Let δoutv and δinv be the set of outgoing arcs from node v and incoming arcs to node v, respectively. The time period T given in advance is denoted by T=0,1,…,T in discrete-time settings and T=0,T+1 in continuous-time settings. In static flow, the transit time is considered as the cost, and time parameter T is absent.Throughout the paper, we consider that the storage capacity of sources and sinks is sufficiently large, i.e.,bsi=bti≤∞ and that of intermediate nodes is finite. If the sum of incoming arc capacities of an intermediate node v∈I is more than the sum of outgoing arc capacities, then the excess flow is used to store at v. Moreover, for the uniqueness of the solution, the storage capacity of v∈I should be bv≥∑a∈δinvua.


### 2.1. Static Multicommodity Flow Model

The static multicommodity flow functiong on the given network N=V,A,K,c,u,b,di,S,D is the sum of nonnegative arc flow functions gai:A⟶ℛ+ and the excess flow functions gvi:I⟶ℛ+, for each i∈K, satisfying conditions (1)–(5). The linear programming formulation of static multicommodity flow with intermediate storage is as follows:(1)maxdi=∑a∈δoutsigai=∑a∈δintigai+∑v∈I:bv≥0gvi,such that(2)∑a∈δinvgai−∑a∈δoutvgai≥0,∀v∈I,i∈K,(3)0≤ga=∑i∈Kgai≤ua,∀a∈A,(4)0≤gv=∑i∈Kgvi≤bv,∀v∈I,(5)∑a∈δinvua≤bv,∀v∈I.Objective function in equation (1) is to maximize the total flow out from each source, for all i∈K, which is equal to the sum of inflow at the sink and the excess flow at intermediate nodes. Equation (2) represents the nonconservation of flow at intermediate nodes. The constraint in (3) represents the bundle constraint on each arc that is bounded by its capacity, and the constraints in (4) represent the excess flow at each intermediate node, which is bounded by the storage capacity. Similarly, the constraint in (5) represents that the storage capacity of intermediate node v∈I is at least the sum of incoming arc capacities to v. The cost of static flow g associated with arc a and commodity i with cost coefficient cai is defined as(6)cg=∑i∈K∑a∈Acaigai.


### 2.2. Dynamic Multicommodity Flow Model

For a given dynamic networkN with constant transit time τ on each arc a, the multicommodity flow over time function ψ is the sum of nonnegative arc flow functions ψi:A×T⟶ℛ+ and the storage flow functions ψvi:I×T⟶ℛ+ for each i∈K, satisfying constraints (7)–(11). The linear programming formulation of dynamic multicommodity flow with intermediate storage is as follows:(7)maxdi=∑a∈δoutsi∑θ=0Tψaiθ=∑a∈δinti∑θ=τaTψaiθ−τa+∑v∈I:bv≥0ψviT,such that(8)∑a∈δinv∑β=τaθψaiβ−τa−∑a∈δoutv∑β=0θψaiβ≥0,∀v∈I,i∈K,θ∈T,(9)0≤ψaθ=∑i∈Kψaiθ≤ua,∀a∈A,θ∈T,(10)0≤ψvθ=∑i∈Kψviθ≤bv,∀v∈I,θ∈T,(11)∑a∈δinvua≤bv≤T∑a∈δinvua,∀v∈I.Equation (7) is an objective function that maximizes the total flow out from the source in time horizon T, for each i∈K, which is equal to the sum of inflow at sink and the excess flow at intermediate nodes. Equation (8) represents the nonconservation of flow at intermediate nodes for each time step θ. In any instance of time θ, the bundle constraint in (9) is bounded by arc capacity, and the constraint in (10) represents that the excess flow at each intermediate node is bounded by the storage capacity. Similarly, the constraint in (11) represents the lower and upper bounds of the storage capacity of intermediate node v∈I. The cost of discrete dynamic flow ψ associated with arc a and commodity i with cost coefficient cai is defined as(12)cψ=∑i∈K∑a∈Acai∑θ=0Tψaiθ.


## 2.1. Static Multicommodity Flow Model

The static multicommodity flow functiong on the given network N=V,A,K,c,u,b,di,S,D is the sum of nonnegative arc flow functions gai:A⟶ℛ+ and the excess flow functions gvi:I⟶ℛ+, for each i∈K, satisfying conditions (1)–(5). The linear programming formulation of static multicommodity flow with intermediate storage is as follows:(1)maxdi=∑a∈δoutsigai=∑a∈δintigai+∑v∈I:bv≥0gvi,such that(2)∑a∈δinvgai−∑a∈δoutvgai≥0,∀v∈I,i∈K,(3)0≤ga=∑i∈Kgai≤ua,∀a∈A,(4)0≤gv=∑i∈Kgvi≤bv,∀v∈I,(5)∑a∈δinvua≤bv,∀v∈I.Objective function in equation (1) is to maximize the total flow out from each source, for all i∈K, which is equal to the sum of inflow at the sink and the excess flow at intermediate nodes. Equation (2) represents the nonconservation of flow at intermediate nodes. The constraint in (3) represents the bundle constraint on each arc that is bounded by its capacity, and the constraints in (4) represent the excess flow at each intermediate node, which is bounded by the storage capacity. Similarly, the constraint in (5) represents that the storage capacity of intermediate node v∈I is at least the sum of incoming arc capacities to v. The cost of static flow g associated with arc a and commodity i with cost coefficient cai is defined as(6)cg=∑i∈K∑a∈Acaigai.


## 2.2. Dynamic Multicommodity Flow Model

For a given dynamic networkN with constant transit time τ on each arc a, the multicommodity flow over time function ψ is the sum of nonnegative arc flow functions ψi:A×T⟶ℛ+ and the storage flow functions ψvi:I×T⟶ℛ+ for each i∈K, satisfying constraints (7)–(11). The linear programming formulation of dynamic multicommodity flow with intermediate storage is as follows:(7)maxdi=∑a∈δoutsi∑θ=0Tψaiθ=∑a∈δinti∑θ=τaTψaiθ−τa+∑v∈I:bv≥0ψviT,such that(8)∑a∈δinv∑β=τaθψaiβ−τa−∑a∈δoutv∑β=0θψaiβ≥0,∀v∈I,i∈K,θ∈T,(9)0≤ψaθ=∑i∈Kψaiθ≤ua,∀a∈A,θ∈T,(10)0≤ψvθ=∑i∈Kψviθ≤bv,∀v∈I,θ∈T,(11)∑a∈δinvua≤bv≤T∑a∈δinvua,∀v∈I.Equation (7) is an objective function that maximizes the total flow out from the source in time horizon T, for each i∈K, which is equal to the sum of inflow at sink and the excess flow at intermediate nodes. Equation (8) represents the nonconservation of flow at intermediate nodes for each time step θ. In any instance of time θ, the bundle constraint in (9) is bounded by arc capacity, and the constraint in (10) represents that the excess flow at each intermediate node is bounded by the storage capacity. Similarly, the constraint in (11) represents the lower and upper bounds of the storage capacity of intermediate node v∈I. The cost of discrete dynamic flow ψ associated with arc a and commodity i with cost coefficient cai is defined as(12)cψ=∑i∈K∑a∈Acai∑θ=0Tψaiθ.


## 3. Maximum Static Multicommodity Flow

In this section, we introduce the maximum static multicommodity flow problem with intermediate storage and present a polynomial time algorithm to solve it.Problem 1.
For a given static networkN=V,A,K,c,u,b,di,S,D, the maximum static multicommodity flow problem with intermediate storage finds the maximization of flow leaving from each source si, for all i∈K, which is to be sent to the corresponding sink ti via si−ti paths by allowing the storage of maximum excess flow at intermediate nodes with storage capacity bv≥∑a∈δinvua.As the solution strategy, we first reduce the multicommodity flow problem intok independent single commodity flow problems by reallocating the capacity of bundle arcs using the resource directive decomposition method. It reallocates the capacity of bundle arc for each commodity in such a way that the objective is optimal. The decomposition algorithm to minimal-cost multicommodity flow problem can be used for minimum cost flow problem, which was the motivation for the development of the original Dantzig–Wolfe decomposition method [21] (see Bazaraa et al. [22]). For each i∈K, we used to store the maximum flow at sink ti and the excess flow at intermediate nodes v∈I with priority order. As in Pyakurel and Dempe [10], we have a single sink for each commodity i∈K, which is considered as the most appropriate place to store the flow. So, the first priority is given to the sink to transship as much flow as possible. To store the excess flow at intermediate nodes, we set the priority order as follows: for each v∈I with storage capacity bv≥∑a∈δinvua, calculate the shortest distance dsi,v, for each i, by using algorithm of Dijkstra [23]. We consider the path with the minimum cost as the shortest path, and the priority is given to the farthest node among the nodes with shortest distance. That is, ∀v1,v2∈I if dsi,v1>dsi,v2, then v1 is higher in priority than v2 and it is denoted by v1≻v2. It is to be noted that the nodes lying in the bundle arcs may have different priority ordering with respect to the commodity.For each prioritized nodev∈I, we create dummy port vi′ (since the node v∈I lying in the bundle arc contains the flow of more than one commodity, so dummy ports are represented commodity-wise, i.e., vi′) with cost cv,vi′=dv,vi′=0 and capacity uv,vi′=bv=bvi′, where uv,vi′ and cv,vi′ are the arc capacity and cost of dummy arc v,vi′, respectively. Every dummy port vi′ with respect to commodity i has the same priority order as v has. Associated with each commodity i, the collection of dummy ports vi′ together with the sink ti forms a modified network Ni′=Vi′,Ai′,c,u,b,di,si,Di′ with single source si and multiple sink Di′=ti∪vi′. For an instance, if ti≻vi,1≻…≻vi,r is priority order of nodes with respect to commodity i, then Di′=ti=vi,0′,vi,1′,…,vi,r′.Now, we present a polynomial time algorithm to solve Problem1 by using the algorithm of Pyakurel and Dempe [10] for single source multisink network Ni′, ∀i∈K.Theorem 1.
Algorithm1 solves the maximum static multicommodity flow problem with intermediate storage optimally.Algorithm 1: Maximum static multicommodity flow algorithm with intermediate storage (MSMCFAIS).
Input: given static network N=V,A,K,c,u,b,di,S,D.Output: maximum static multicommodity flow with intermediate storage in N.(1)
Reconfigure the multicommodity flow problem intok independent single commodity flow problems by reallocating the capacity of bundle arcs using the resource directive decomposition.(2)
For eachv∈I with bv≥∑a∈δinvua, compute commodity-wise shortest distance dsi,v by using Dijkstra’s algorithm.(3)
Fix the priority order asti≻vi,1≻…≻vi,r with respect to commodity i with first priority to the sink ti and priority for intermediate elements as dsi,vi,m>dsi,vi,m+1⇒vi,m≻vi,m+1, for m=1,…,r−1.(4)
For eachi∈K, construct the modified network Ni′=Vi′,Ai′,c,u,b,di,si,Di′ with single source si and multiple sinks with dummy ports Di′=ti=vi,0′,vi,1′,…,vi,r′.(5)
Fori=1,…,k:Compute the lexicographic maximum static flow inNi′ with priority order of Step 3 according to [10].(6)
Transform the solution to the original networkN by removing the dummy ports and the dummy arcs.Proof.
Before proving the optimality, we first prove the feasibility of the algorithm. Step 1 is the use of decomposition algorithm to reduce the multicommodity flow problem to single commodity flow problem, and Step 2 calculates the shortest distances by using Dijkstra’s algorithm, so both steps are feasible. Steps 3, 4, and 6 are prioritization of nodes, modification of network, and transformation of solution, which can be solved in linear time, and so they are feasible. Similarly, according to Pyakurel and Dempe [10], Step 5 provides feasible flow with intermediate storage for each commodity i∈K. Thus, the solution obtained from Algorithm 1 is feasible.
The optimality of algorithm is assured by Step 5. For each commodityi∈K, lexicographic maximum static flow in prioritized sink Di′ is obtained optimally as the single commodity flow problem solved by Pyakurel and Dempe [10]. So, the sum of optimal single commodity flows ∑idi is optimal multicommodity flow with intermediate storage.Theorem 2.
Maximum static multicommodity flow problem with intermediate storage can be solved in polynomial time complexity by using Algorithm1.Proof.
The decomposition algorithm in Step 1 is obtained in polynomial time complexity, and the shortest distance can be obtained inOn2 time by using Dijkstra’s algorithm. The prioritization of nodes and creating dummy ports can be obtained in linear time. For each single commodity i, Step 5 can be solved in polynomial time complexity of Oδmn for 0<δ<n, [10]. Therefore, Algorithm 1 solves the maximum static multicommodity flow problem with intermediate storage in polynomial time with complexity On2+Okδmn, where K=k.Example 1.
Consider a two-commodity network with capacity and cost on each arc as shown in Figure1(a), where the numbers aside the nodes represent the node capacities. Using Dijkstra’s algorithm, we find the shortest distance of each intermediate node and fix the priority order with farther-in-distance-higher-in-priority. So, the priority orders are t1≻y≻x and t2≻x≻y for commodity 1 and commodity 2, respectively. After priority ordering, we denote D1′=t1,y1′,x1′ and D2′=t2,x2′,y2′ as the set of prioritized dummy ports for commodity 1 and commodity 2, respectively, which is presented in Figure 1(b).
While decomposing the flow on the bundle arcx,y, flows of 3 and 2 units are assigned for commodity 1 and commodity 2, respectively. By using Algorithm 1, the maximum amount of flow leaving the source s1 is 4 units out of which 2 units of flow are reached at sink t1 and the intermediate nodes y and x hold 1 unit each. Similarly, 7 units of flow are transmitted from the source s2, out of which 6 units of flow are reached at the sink t2 and the intermediate nodes x and y hold 1 and 0 units, respectively. At last, the solution is transformed to the original network by removing the dummy ports and dummy arcs and sending back the flow to its respective nodes. The amount of flow stored at sinks and the intermediate nodes is gt1=2,gt2=6,gx=2, and gy=1. If the intermediate storage is not permitted, then the flow of gt1=2 and gt2=6 units can only be transshipped.Figure 1
(a) A two-commodity network with capacity and cost on the arcs and storage capacity on the nodes. (b) The modified network of (a) with prioritized dummy ports.
(a)(b)


## 4. Maximum Dynamic Multicommodity Flow

This section deals with the maximum dynamic multicommodity flow problem, where storage of the excess flow at intermediate nodes is allowed. We present a pseudopolynomial time algorithm based on the time expanded network of Kappmeier [8] to solve the problem.Problem 2.
For a given dynamic networkN=V,A,K,u,b,τ,di,S,D,T, the maximum dynamic multicommodity flow problem with intermediate storage is to maximize the flow leaving each source si, for all i∈K, which is to be sent to the corresponding sink ti via si−ti paths by allowing the storage of maximum excess flow at the intermediate nodes with storage capacity ∑a∈δinvua≤bv≤T∑a∈δinvua within time horizon T.As inSection 3, we first reduce the multicommodity flow problem into k independent subproblems and fix the priority order of intermediate nodes. Static solution is obtained in the modified single source and multisink network Ni′=Vi′,Ai′,u,b,τ,di,si,Di′,T for all i∈K, by using Algorithm 1. To obtain the dynamic solution, we use the static multicommodity flow on time expanded network as in Kappmeier [8].For this, we construct a temporary sinkt¯i with infinite capacity and join each dummy port vi′∈Di′ with uvi′,t¯i=gvi′iθ and τvi′,t¯i=0, where gvi′iθ is the static flow of commodity i at vi′ at time θ. The choice of uvi′,t¯i=gvi′iθ is taken to assure that the flow while sending back from the dummy ports must be on respective nodes. Now, for each i∈K, the new network N˜i′ is obtained by adding temporary sink and arcs in Ni′ so that it becomes a single source single sink network with prioritized intermediate nodes. Let NT=VT,AT=AM∪AH∪As∪At,K,u,b,τ,di,S^,D^,T be the time expanded network of new network N˜′=∪iN˜i′, where N˜i′ is obtained by including temporary sinks, supersource, and supersink in Ni′. The components in time expanded network NT are defined as follows:(13)VT=vθ:v∈V,θ∈T∪vi,θ′∪t¯i,θ:i∈K,θ∈T∪si∗,t¯i∗:i∈K∪s˜,t˜,AM=vθ,wθ+τa:a=v,w∈A,θ∈T∪vθ,vi,θ′∪vi,θ′,t¯i,θ:v∈I,θ∈T,AH=vθ,vθ+1:v∈V,θ∈T∪vi,θ′,vi,θ+1′∪t¯i,θ,t¯i,θ+1:i∈K,θ∈T,As=s˜,si∗:i∈K∪si∗,si,θ:i∈K,θ∈T,At=t˜,t¯i∗:i∈K∪t¯i∗,t¯i,θ:i∈K,θ∈T,S^=s˜,si∗,si,θ:i∈K,θ∈T,D^=t˜,ti∗,t¯i,θ:i∈K,θ∈T.Kappmeier [8] has shown that the static multicommodity flow on the time expanded network is equivalent to the dynamic multicommodity flow on the original network.Theorem 3.
(see [8]). For a given dynamic network N=V,A,K,u,b,τ,di,S,D,T with time horizon T, a feasible static S^−D^ multicommodity flow gT in the time expanded network NT yields the feasible dynamic multicommodity flow ψ in N such that gT=ψ.We now present an algorithm to solve problem2 by using time expanded network.Theorem 4.
Algorithm2 provides an optimal solution to the maximum dynamic multicommodity flow problem with intermediate storage in pseudopolynomial time complexity.Algorithm 2: Maximum dynamic multicommodity flow algorithm with intermediate storage (MDMCFAIS).
Input: given dynamic network N=V,A,K,u,b,τ,di,S,D,T.Output: maximum dynamic multicommodity flow with intermediate storage in N.(1)
Reconfigure the multicommodity flow problem intok independent single commodity flow problems by reallocating the capacity of bundle arcs by using the resource directive decomposition and considering the transit times as cost.(2)
Construct a modified new networkN˜′ by including temporary sinks, supersource, and supersink in Ni′.(3)
Using new networkN˜′, construct the time expanded network NT=VT,AT=AM∪AH∪As∪At,K,u,b,τ,di,S^,D^,T.(4)
Calculate the maximum static multicommodity flow with intermediate storage on the time expanded networkNT by using Algorithm 1.(5)
Transform the solution to the original networkN by removing the dummy ports, temporary sinks, supersource, supersink, and dummy arcs.Proof.
At first, we prove the feasibility of Algorithm2. As Step 1 is a reconfiguration of given network by using decomposition algorithm, and Step 2 is its modification including dummy ports and temporary sinks, so these steps provide the feasible solution. Due to Theorem 3, construction of time expanded network in Step 3 is feasible, and the feasibility of Step 4 is obtained by Algorithm 1. The transformation of solution in original network is also feasible. The optimality of algorithm is assured by the optimality of Step 4, which is as similar to [8].
Next, we prove the computational time of Algorithm2, which is dominated by the complexity of Step 4. Here, the computational time complexity of Step 4 is OT×MSMCFAIS, where OMSMCFAIS is the complexity of maximum static multicommodity flow algorithm with intermediate storage. From Theorem 2, OMSMCFAIS=On2+Okδmn for 0<δ<n. With Step 4 being polynomial in input size of the network, but not bounded in T, Algorithm 2 solves the maximum dynamic multicommodity flow problem with intermediate storage in pseudopolynomial time.Example 2.
Consider a two-commodity network from Figure1 by considering the cost on each arc as the transit time with time horizon T=5. The prioritization of intermediate nodes and creating dummy ports are similar to Example 1. For each commodity i=1,2, the problem is reduced to single source and multisink single commodity flow problem due to dummy ports (see Figure 1(b)). By adding temporary sink t¯i, it reduces to commodity-wise single source single sink (i.e., si−t¯i) problem, which is shown in Figure 2. We calculate the maximum static multicommodity flow with intermediate storage using Algorithm 1 and then repeat the procedure with intermediate storage in time expanded network as similar to Kappmeier [8]. Here, the maximum static flow is calculated from minimum cost flow by considering the transit time as cost. Figure 3 represents the time expanded network of Figure 2 with time horizon T=5. At last, we obtain the maximum dynamic flow with intermediate storage by removing the dummy arcs and replacing the flow of dummy ports to their respective nodes.
For commodity 1, total amount of flow leaving the sources1 within the time horizon T=5 along the path s1−x−y−t1 is 20 units, out of which 4, 8, and 8 units are transshipped with priority order at t1, y and x, respectively. For commodity 2, flows are sent through two paths s2−x−y−t2 and s2−y−t2 with priority order t2≻x≻y. It is to be noted that while sending flow from the path s2−x−y−t2, flow leaving s2 at θ=0 sends 2 units of flow at t2 by storing 1 unit at x. After next iteration onward, flow cannot reach the sink, and so it is to be stored at x but not at y because x is higher in priority than y. Similarly, path s2−y−t2 first sends 4 units of flow thrice at t2 and then holds the flow at y for next two times. Total amount of flow leaving the source s2 through two paths within T=5 is 32 units, out of which 14, 10, and 8 units are transshipped at t2, x and y, respectively. The detailed information of the flow leaving from sources at different time steps θ, which are to be stored at sinks and the intermediate nodes, is presented in Table 1.
Here, the amount of flow reaching the sinks is the maximum multicommodity flow without intermediate storage. So, if intermediate storage is prohibited, then only 4 units of flow of commodity 1 and 14 units of flow of commodity 2 can be reached at their respective sinks within the timeT=5.Figure 2
Modified new networkN˜′ with dummy ports and temporary sinks.Figure 3
Time expanded multicommodity network flow with intermediate storage, where black and red colors are for commodity 1 and commodity 2, respectively. Dotted arcs represent the dummy arcs.Table 1
Multicommodity flow with intermediate storage in each timeθ.
Commodity 1Commodity 2Path:s1−x−y−t1Path:s2−x−y−t2Start time ats1Flow atReaching time at last nodeStart time ats2Flow atReaching time at last nodexyt1xyt2θ = 0112θ = 4 at t1θ = 0102θ = 5 at t2θ = 1112θ = 5 at t1θ = 13××θ = 3 at xθ = 213×θ = 4 at yθ = 23××θ = 4 at xθ = 313×θ = 5 at yθ = 33××θ = 5 at xθ = 44××θ = 5 at xPath:s2−y−t2θ = 0×04θ = 3 at t2θ = 1×04θ = 4 at t2θ = 2×04θ = 5 at t2θ = 3×4×θ = 4 at yθ = 4×4×θ = 5 at yTotal884Totald1 = 20Total10814Totald2 = 32


## 5. Multicommodity Contraflow Problems

In this section, we investigate the multicommodity flow problem with contraflow configuration, where the storage of excess flow at intermediate nodes is allowed. In a two-way network, contraflow means the reversal of oppositely directed arcs towards the destination node to improve the flow and reduce the overall time horizon. We discuss two different aspects of transit times (or cost for static), symmetric and asymmetric, between the pair of nodes with oppositely directed arcs.


### 5.1. Contraflow with Symmetric Transit Times

LetN=V,A,K,u,b,τ,di,S,D,T be a dynamic multicommodity network having symmetric transit times on antiparallel arcs, i.e., τa=τa←, where a←=w,v is oppositely directed arc of a=v,w. To solve the problem in contraflow network, we transform the given network to an auxiliary network as follows.For a given two-way multicommodity networkN with symmetric transit times, the corresponding auxiliary network is denoted by N¯ with network topology N¯=V,A¯,K,u¯,b,τ¯,di,S,D,T, containing undirected edges A¯=v,w:v,worw,v∈A. The capacity of an arc in an auxiliary network is the sum of capacities of arcs a and a← such that u¯a=ua+ua←, where ua=0 if a∉A. The transit time of an arc in an auxiliary network is(14)τ¯a=τa,ifa∈A,τa←,otherwise.All other parameters are the same as inN. Contrary to the general network, incoming arcs to the sources si and outgoing arcs from the sinks ti may be present in the contraflow network for all i∈K.We now present the maximum dynamic contraflow problem with intermediate storage herein.Problem 3.
For a given dynamic networkN=V,A,K,u,b,τ,di,S,D,T, the maximum dynamic multicommodity contraflow problem with intermediate storage is to find the maximum flow leaving from each source si,∀i∈K, which is to be sent to their respective sinks ti via si−ti paths by allowing the storage of maximum excess flow at intermediate nodes v∈I with storage capacity ∑a∈δinvua≤bv≤T∑a∈δinvua,∀a∈A¯ within the given time horizon T by reverting the direction of arcs at time zero.To solve the problem, we present an algorithm based on the time expanded network of an auxiliary networkN¯ as follows.We first transform the given two-way network into an auxiliary networkN¯. As in Section 3, we decompose the multicommodity flow problem to k single commodity flow problems and then fix the priority order of each intermediate node. On each cycle free path of auxiliary network N¯, we solve the maximum dynamic multicommodity flow problem, for each i∈K, as described in Section 4.Here, Steps 1, 3, and 4 of Algorithm3 can be computed in OE time. In Step 2, we can find a pseudopolynomial time solution for dynamic multicommodity contraflow problem with intermediate storage in N¯ (as in Theorem 4). So, the maximum dynamic multicommodity contraflow problem with intermediate storage can be solved in pseudopolynomial time by using Algorithm 3.Algorithm 3: Maximum dynamic multicommodity contraflow algorithm with intermediate storage.
Input: given two-way dynamic multicommodity network N.Output: maximum dynamic multicommodity contraflow with intermediate storage.(1)
Construct an auxiliary networkN¯ of N.(2)
Compute the maximum dynamic multicommodity flow with intermediate storage inN¯ by using Algorithm 2.(3)
Decompose the flow alongsi−ti paths and cycles, and remove the flows in cycles ∀i∈K.(4)
An arca← is reversed if and only if the flow along arc a is greater than its capacity, or if there is a nonnegative flow along arc a∉A.Theorem 5.
Algorithm3 solves the maximum dynamic multicommodity contraflow problem with intermediate storage in pseudopolynomial time complexity.Remark 1.
If we consider the cost instead of transit time and apply Algorithm1 in Step 2 of Algorithm 3, then the solution of maximum static multicommodity contraflow problem with intermediate storage can be obtained in polynomial time complexity.


### 5.2. Contraflow with Orientation-Dependent Transit Times

If the transit times on antiparallel arcs of a two-way network are not identical, then it is known as the network with asymmetric transit times. For a network with asymmetric transit times, if the transit times of arcs in an auxiliary network are taken as the orientation of the arcs, then it is known as orientation-dependent transit time. Nath et al. [24] considered the orientation-dependent asymmetric transit times of reversed lanes in general form and presented strongly polynomial time algorithms to solve the single source single sink maximum dynamic and quickest contraflow problems. Here, we discuss about the multicommodity contraflow problem with intermediate storage by taking orientation-dependent transit times.LetN=V,A,K,u,b,τ,di,S,D,T be a two-way dynamic network with asymmetric nonzero transit times τ on arcs, so that τa≠τa←. We construct an auxiliary network N¯=V,A¯,K,u¯,b,τ¯,di,S,D,T, where A¯ is obtained by reverting the direction of arcs a← at time zero. The arc capacity u¯ and transit time τ¯a can be obtained as follows:(15)u¯a=ua+ua←,where ua=0 if a∉A and(16)τ¯a=τaif the orientation of arc is along a,τa←if the orientation of arc is alonga←.By using Algorithm3, the optimal solution for maximum static and maximum dynamic multicommodity contraflow problems with intermediate storage can be obtained for a given network with asymmetric transit times, where transit time is considered as a cost in static problem.If, on the other hand, the transit time attributes on the evacuation network are antisymmetric, but one wishes to adopt contraflow approach with the same transit time on the reversed arcs as it was before its reversal, Algorithm3 obviously works well as that can be interpreted as symmetric transit time solution. It can be applied if two nodes in a network have parallel connections with different transit times.


## 5.1. Contraflow with Symmetric Transit Times

LetN=V,A,K,u,b,τ,di,S,D,T be a dynamic multicommodity network having symmetric transit times on antiparallel arcs, i.e., τa=τa←, where a←=w,v is oppositely directed arc of a=v,w. To solve the problem in contraflow network, we transform the given network to an auxiliary network as follows.For a given two-way multicommodity networkN with symmetric transit times, the corresponding auxiliary network is denoted by N¯ with network topology N¯=V,A¯,K,u¯,b,τ¯,di,S,D,T, containing undirected edges A¯=v,w:v,worw,v∈A. The capacity of an arc in an auxiliary network is the sum of capacities of arcs a and a← such that u¯a=ua+ua←, where ua=0 if a∉A. The transit time of an arc in an auxiliary network is(14)τ¯a=τa,ifa∈A,τa←,otherwise.All other parameters are the same as inN. Contrary to the general network, incoming arcs to the sources si and outgoing arcs from the sinks ti may be present in the contraflow network for all i∈K.We now present the maximum dynamic contraflow problem with intermediate storage herein.Problem 3.
For a given dynamic networkN=V,A,K,u,b,τ,di,S,D,T, the maximum dynamic multicommodity contraflow problem with intermediate storage is to find the maximum flow leaving from each source si,∀i∈K, which is to be sent to their respective sinks ti via si−ti paths by allowing the storage of maximum excess flow at intermediate nodes v∈I with storage capacity ∑a∈δinvua≤bv≤T∑a∈δinvua,∀a∈A¯ within the given time horizon T by reverting the direction of arcs at time zero.To solve the problem, we present an algorithm based on the time expanded network of an auxiliary networkN¯ as follows.We first transform the given two-way network into an auxiliary networkN¯. As in Section 3, we decompose the multicommodity flow problem to k single commodity flow problems and then fix the priority order of each intermediate node. On each cycle free path of auxiliary network N¯, we solve the maximum dynamic multicommodity flow problem, for each i∈K, as described in Section 4.Here, Steps 1, 3, and 4 of Algorithm3 can be computed in OE time. In Step 2, we can find a pseudopolynomial time solution for dynamic multicommodity contraflow problem with intermediate storage in N¯ (as in Theorem 4). So, the maximum dynamic multicommodity contraflow problem with intermediate storage can be solved in pseudopolynomial time by using Algorithm 3.Algorithm 3: Maximum dynamic multicommodity contraflow algorithm with intermediate storage.
Input: given two-way dynamic multicommodity network N.Output: maximum dynamic multicommodity contraflow with intermediate storage.(1)
Construct an auxiliary networkN¯ of N.(2)
Compute the maximum dynamic multicommodity flow with intermediate storage inN¯ by using Algorithm 2.(3)
Decompose the flow alongsi−ti paths and cycles, and remove the flows in cycles ∀i∈K.(4)
An arca← is reversed if and only if the flow along arc a is greater than its capacity, or if there is a nonnegative flow along arc a∉A.Theorem 5.
Algorithm3 solves the maximum dynamic multicommodity contraflow problem with intermediate storage in pseudopolynomial time complexity.Remark 1.
If we consider the cost instead of transit time and apply Algorithm1 in Step 2 of Algorithm 3, then the solution of maximum static multicommodity contraflow problem with intermediate storage can be obtained in polynomial time complexity.


## 5.2. Contraflow with Orientation-Dependent Transit Times

If the transit times on antiparallel arcs of a two-way network are not identical, then it is known as the network with asymmetric transit times. For a network with asymmetric transit times, if the transit times of arcs in an auxiliary network are taken as the orientation of the arcs, then it is known as orientation-dependent transit time. Nath et al. [24] considered the orientation-dependent asymmetric transit times of reversed lanes in general form and presented strongly polynomial time algorithms to solve the single source single sink maximum dynamic and quickest contraflow problems. Here, we discuss about the multicommodity contraflow problem with intermediate storage by taking orientation-dependent transit times.LetN=V,A,K,u,b,τ,di,S,D,T be a two-way dynamic network with asymmetric nonzero transit times τ on arcs, so that τa≠τa←. We construct an auxiliary network N¯=V,A¯,K,u¯,b,τ¯,di,S,D,T, where A¯ is obtained by reverting the direction of arcs a← at time zero. The arc capacity u¯ and transit time τ¯a can be obtained as follows:(15)u¯a=ua+ua←,where ua=0 if a∉A and(16)τ¯a=τaif the orientation of arc is along a,τa←if the orientation of arc is alonga←.By using Algorithm3, the optimal solution for maximum static and maximum dynamic multicommodity contraflow problems with intermediate storage can be obtained for a given network with asymmetric transit times, where transit time is considered as a cost in static problem.If, on the other hand, the transit time attributes on the evacuation network are antisymmetric, but one wishes to adopt contraflow approach with the same transit time on the reversed arcs as it was before its reversal, Algorithm3 obviously works well as that can be interpreted as symmetric transit time solution. It can be applied if two nodes in a network have parallel connections with different transit times.


## 6. Continuous Dynamic Multicommodity Flow

We discussed the maximum dynamic flow and contraflow problems with intermediate storage inSection 4 and Section 5, respectively, where transit times are taken in discrete settings. Actually, discrete dynamic flow function ψ assigns the flow from the source node at each time step θ=0,…,T satisfying the capacity constraints. In this section, we formulate the dynamic multicommodity flow with intermediate storage in continuous-time settings. A continuous dynamic flow function ψc with intermediate storage is defined as the flow rate per unit time that leaves from the source at each moment of time by allowing the storage of excess flow at intermediate nodes without violating the capacity constraints.By using natural transformation, Fleischer and Tardos [16] established the relation between discrete and continuous flow models. This natural transformation defines the continuous dynamic flow for time interval θ,θ+1 with ψacθ,θ+1=ψaθ, where ψaθ is the amount of discrete dynamic flow entering arc a∈A at each time step θ=0,…,T. Here, we use this logic to transform the discrete-time multicommodity flow to continuous-time multicommodity flow with intermediate storage as follows: any discrete multicommodity flow over time ψai with integral time horizon T is equivalent to the continuous multicommodity flow over time ψai,cθ,θ+1 by incorporating the flow ψ entering an arc a at time step θ≤T−τa as a constant flow rate on arc a during the unit time interval θ,θ+1 by allowing the storage of excess flow at intermediate nodes. Mathematically,(17)∫θθ+1ψai,cαdα=ψaiθ,∀a∈A,i∈K.We formulate the dynamic multicommodity flow models with intermediate storage in continuous settings as follows:(18)maxdi=∑a∈δoutsi∫θ=0Tψai,cθdθ=∑a∈δinti∫θ=τaTψai,cθ−τadθ+∑v∈I:bv≥0∫θ=0Tψvi,cθdθ,such that(19)∑a∈δinv∫β=τaθψai,cβ−τadβ−∑a∈δoutv∫β=0θψai,cβdβ≥0,∀v∈I,i∈K,θ∈T,(20)0≤ψacθ=∑i∈Kψai,cθ≤ua,∀a∈A,θ∈T,(21)0≤ψvcθ=∑i∈Kψvi,cθ≤bv,∀v∈I,θ∈T,(22)∑a∈δinvua≤bv≤T∑a∈δinvua,∀v∈I.Here, equation (18) represents an objective function, which is to maximize the total amount of flow out from the source in continuous-time settings, which is sent to the sink and the intermediate nodes. The nonconservation of the flow is represented by equation (19). Equations (20)–(22) have their usual meanings as in Section 2.Dynamic flow problems defined inSection 4 and Section 5 can be solved in continuous-time settings by using this natural transformation with their respective algorithms within the same time complexity.


## 7. Conclusion

If the amount of flow out from the source node is more than the minimum cut capacity, then the excess flow cannot reach the sink. To deal with this problem, maximum static, maximum dynamic, and maximum dynamic contraflow problems with the storage of excess flow at intermediate nodes have been studied in two-terminal general network.In this paper, we have investigated the multicommodity flow models with intermediate storage in static as well as dynamic networks. We have introduced the maximum static and maximum dynamic multicommodity flow problems. We have presented a polynomial time algorithm to solve the maximum static multicommodity flow problem and a pseudopolynomial time algorithm for the maximum dynamic multicommodity flow problem by allowing the storage of excess flow at intermediate nodes. Moreover, we have presented an algorithm to solve the maximum dynamic multicommodity contraflow problem with symmetric as well as asymmetric transit times. By using natural transformation in multicommodity network, we solved the maximum dynamic flow and maximum dynamic contraflow problems with intermediate storage in continuous-time settings. To the best of our knowledge, the maximum multicommodity flow problems with intermediate storage and their solution strategies for the static flow, dynamic flow, and contraflow problems are introduced for the first time.The universally maximum multicommodity flow problem (the earliest arrival flow problem) with intermediate storage is harder problem, which is of interest for the further research. This problem isNP-hard even in case of two-terminal series parallel networks. Together with this, we are interested to work on maximum flow and earliest arrival flow problems with orientation-dependent transit times and flow-dependent transit times. We are also interested in implementing these techniques as a case study in Kathmandu road network.



---

*Source: 5063207-2021-07-21.xml*