# Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals

Authors: Urmila Pyakurel; Shiva Prakash Gupta; Durga Prasad Khanal; Tanka Nath Dhamala
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

The multicommodity flow problem arises when several different commodities are transshipped from specific supply nodes to the corresponding demand nodes through the arcs of an underlying capacity network. The maximum flow over time problem concerns to maximize the sum of commodity flows in a given time horizon. It becomes the earliest arrival flow problem if it maximizes the flow at each time step. The earliest arrival transshipment problem is the one that satisfies specified supplies and demands. These flow over time problems are computationally hard. By reverting the orientation of lanes towards the demand nodes, the outbound lane capacities can be increased. We introduce a partial lane reversal approach in the class of multicommodity flow problems. Moreover, a polynomial-time algorithm for the maximum static flow problem and pseudopolynomial algorithms for the earliest arrival transshipment and maximum dynamic flow problems are presented. Also, an approximation solution to the latter problem is obtained in polynomial-time.


---

## Body

## 1. Introduction

The multicommodity flow problems concern with the routing of various commodities through a network to the specific source-sink pairs. For instance, message routing in telecommunications, railway and vehicle routine in transportation, and production planning and logistics support in general and in an emergency can be modeled as a multicommodity flow problem. For details and implementations, we refer to [1–4].The transportation network is considered as a network associated with the transshipment of distinct commodities where the supply points (origins), the demand points (destinations), and the junction of road segments constitute the nodes. The connections between the two nodes signify the arcs. On each arc, the capacity that limits the flow amount (i.e., transported commodities) and the travel time are allocated.The multicommodity flow problem can be classified into static and dynamic flow problems. The former one has been categorized as maximum, maximum concurrent, and minimum cost flow problems. The latter one has been categorized as maximum, maximum concurrent, quickest, and the earliest arrival multicommodity flow problems [5, 6].If we do not distinguish the flow in the multicommodity flow problem, then it becomes a single-commodity flow problem. The dynamic flow (also known as flow over time) problem is introduced by Ford and Fulkerson [7]. In connection to this problem, Gale [8] proposed a more general problem known as the earliest arrival flow problem. The earliest arrival flow problem having multiple sources and sinks with given supplies and demands is the earliest arrival transshipment problem. Generally, a solution to this problem does not exist in the case of multiple sinks. However, it does always exists for multiple sources and a single-sink [9].The multicommodity flow problem is more complex than their single-commodity part. Hall et al. [10] have shown that multicommodity flow over time is NP-hard even for series-parallel graphs or have only two commodities. Kappmeier [11] provided solutions of maximum multicommodity flow over time and multisource single-sink multicommodity earliest arrival transshipment problems using a time-expanded network within pseudopolynomial-time complexity.Lane reversal implies flipping of arc orientations to amplify the flow and reduce the travel time by increasing its capacity. Flow models and strongly polynomial-time algorithms for two-terminal maximum and quickest flow problems were developed by Rebennack et al. [12]. The lane reversals are made at time zero and kept fixed afterward. The budget constraint problem with lane reversals is investigated in [13]. The optimal solutions of the earliest arrival flow in the two-terminal general network for both discrete and continuous-time settings can be found in [14–16]. Nath et al. [17] investigated the quickest contra-flowloc problem. By reversing the directions of arcs whenever necessary, a polynomial-time algorithm is presented by Pyakurel and Dhamala [18] for multisource single-sink earliest arrival transshipment. The major concern of partial lane reversals is to make use of the capacities of unused arcs in a network for other purposes. Pyakurel et al. [19] introduced the partial lane reversal strategy in which only essential arc capacities are used to extend the flow value. Dhamala et al. [20] investigated the quickest multicommodity flow problem with partial lane reversals. The saved capacities of unused arcs can be used for the logistic supports and facility location in emergency periods.In this paper, we introduce the maximum static multicommodity flow (MSMCF), the maximum dynamic multicommodity flow (MDMCF), and the earliest arrival multicommodity transshipment (EAMCT) problems with partial lane reversals. We present efficient algorithms to solve these problems by reducing them into single-commodity flow problems and decomposing the flow along the paths.The paper is organized as follows. In Section2, we provide some basic notations and models used in the article. The MSMCF problem with partial lane reversals is introduced and an algorithm to solve the problem is presented in Section 3. The MDMCF problem with partial lane reversals is introduced in Section 4. In this section, we present algorithms to find a solution to this problem. The EAMCT problem and an algorithm to solve this problem is presented in Section 5. The paper is concluded in Section 6.


## 2. Preliminaries

The multicommodity flow problem consists of the shipping of distinct commodities from their respective origin nodes to corresponding destination nodes through a given network. Basic notations and mathematical formulations are given below.


### 2.1. Flow Models and Notations

Let a dynamic network topology be given byN=V,A,K,u,τ,di,S+,S−,T with finite sets of nodes V, arcs A, and commodities K=1,2,…,k, where V=n and A=m. Each commodity i∈K with demand di is routed through a unique source-sink pair si,ti. The sets S+andS−⊂V denote source and sink sets of all commodities, respectively. On each arc e=v,w, the capacity function u:A⟶Z≥0 restricts the flow of commodities and a nonnegative transit time function τ:A⟶Z≥0 measures the time to transship the flow from the entry point v to the exit point w of arc e=v,w. The time period T is given in advance which is denoted by T=0,1,…,T−1 in discrete and T=0,T in continuous-time settings. A static network is a network besides the temporal dimension denoted by N=V,A,K,u,di,S+,S−. Many nice properties developed primarily based on static network topology are building blocks for most of the real-world dynamic flow problems.


#### 2.1.1. Static Multicommodity Flow

A multicommodity flowψ for the given static network N is the sum of all nonnegative static flows ψi defined by the functions ψi:A⟶ℛ+ for each commodity i satisfying(1)excessψiv=−di,ifv=si,0,ifv∉si,ti,di,ifv=ti,∀i∈K,(2)0≤∑i∈Kψei≤ue,∀e∈A,where(3)excessψiv=∑e∈Ainvψei−∑e∈Aoutvψei,represents the excess flow of commodity i at node v. The sets Aoutv=v,w|w∈V and Ainv=w,v|w∈V denote the outgoing arcs from node v and the incoming arcs to node v, respectively, such that AoutS−=∅ and AinS+=∅, except in the lane reversals. The second condition of the constraints in (1) are flow conservation constraints for each commodity at intermediate nodes. The constraints in (2) are bundle constraints that limit the flow of each commodity on the arc. The network flow is called circulation if it satisfies flow conservation at all the nodes, i.e., excessψiv=0,∀v∈V. The maximum static multicommodity flow problem with k-commodities consist of ψ1,ψ2,…,ψk single-commodity flows maximizing ∑i=1kψi satisfying constraints (1) and (2).A polynomial-time solution of the MSMCF problem has been obtained by linear programming techniques (e.g., ellipsoid method or interior-point method). In this problem, each commodityi=1,2,3,…,k has a unique source-sink pair si−ti, and we wish to send the maximum flow from the source nodes si to the sink nodes ti satisfying given bundle capacity ue on each arc e=v,w. That is, we wish to maximize the sum of the flows over all the commodities.


#### 2.1.2. Dynamic Multicommodity Flow

For a given dynamic networkN with constant transit time on arcs, a multicommodity flow over times ξ is a sum of flows defined by ξi:A×T⟶ℛ+ satisfying constraints (4)–(6):(4)excessξiv,T−1=−di,ifv=si,0,ifv∉si,ti,di,ifv=ti,∀i∈K,(5)excessξiv,θ≥0,∀v∉si,ti,i∈K,θ∈T,(6)0≤ξeθ=∑i∈Kξeiθ≤ue,∀e∈A,θ∈T,where(7)excessξiv,θ=∑δ=τeθ∑e∈Ainvξeiδ−τe−∑δ=0θ∑e∈Aoutvξeiδ,is the excess flow of commodity i on node v at time θ. Here, the second condition of the constraints in (4) are flow conservation constraints at time horizon T, whereas nonconservation of flow at intermediate time points θ∈T=0,1,…,T−1 is represented by the constraints in (5). Similarly, the constraints in (6) are bundle constraints that limit the flow on each arc at each point of time. The aim is to maximize the amount of flow to satisfy the demand di of each commodity i from si to ti which is stated in the first and last conditions of (4). The earliest arrival multicommodity flow problem is to find a dynamic multicommodity flow of maximum value valmaxξθ for all time units θ∈0,1,…,T−1 defined by objective function:(8)valξθ=∑δ=τeθ∑e∈Atiinξeiδ−τe.Instead of each timeθ, if the maximization is considered for a given time θ=T−1, it is defined as an MDMCF problem.The equality in (5) represents strong flow conservation constraints that do not allow to store the flow at intermediate nodes for each time θ (i.e., without intermediate storage). The strict inequality constraint in (5) represents the weak flow conservation constraint at intermediate nodes for all times with intermediate storage.


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

The network topologyN=V,A,K,u,τ,di,S+,S−,T is considered. Fleischer and Skutella [21] 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 multiples of Δ>0 such that T/Δ is bounded by a polynomial in input size. The nodes and arcs in the Δ-condensed time-expanded network are defined as(9)VTΔ=vθ:v∈V,θ=0,1,2,…,T/Δ−1∪si′,ti′:i∈K∪s∗,t∗,AMΔ=vθ,wθ+τe:e=v,w∈A,θ=0,1,…,T−τe/Δ−1,AHΔ=vθ,vθ+1:e=v,w∈A,θ=0,1,…,T/Δ−2,A+Δ=∪s∗,si′:i∈K∪si′,sθ:i∈K,si′∈S+′,θ∈0,1,2,…,T/Δ−1,A−Δ=∪ti′,t∗:i∈K∪tθ,ti′:i∈K,ti′∈S−′,θ∈0,1,2,…,T/Δ−1,where S+′ and S−′ are the super terminals for each commodity as well as for the Δ-condensed time-expanded network, i.e., si′,ti′:i∈K∪s∗,t∗. The copies of VTΔ correspond to flow through V in time T=αΔ for discrete-time and T=αΔ,α+1Δ for continuous-time, where α=0,1,2,…,T/Δ−1. In this setting, for every arc corresponding to a discrete-time with a multiple of Δ, capacities are rescaled by Δue. If arc transit times are not multiples of Δ, then transit times are rounded up to a multiple of Δ by τe′=τe/ΔΔ and 0≤τe′−τe<Δ for all arcs e∈A. If we take Δ=1, then the Δ-condensed time-expanded network reduces to the classical time-expanded network.


### 2.3. Lane Reversal Technique

For a given networkN, the corresponding auxiliary network is denoted by Na=V,Aa,K,ua,τa,di,S+,S−,T with undirected edges in Aa=v,w:v,worw,v∈A, where er=w,v is the reversed arc of e=v,w. The capacity of the auxiliary arc is the sum of capacities of arcs e and er such that uea=ue+uer, where ue=0 if e∉A. The transit time of the auxiliary arc is(10)τea=τe,ife∈A,τer,otherwise.Other network parameters are the same. The transformation of the multicommodity network with lane reversals is represented in Figures1(a) and 1(b). The first, second, and third commodities are shipped through the paths s1−t1, s2−t2, and s3−t3, respectively.Figure 1
Auxiliary network (b) of the given network (a). (a) Capacity, transit time; (b) capacity, transit time.
(a)(b)Example 1.
Let us consider a multicommodity network, wheres1,s2,ands3 are the source nodes and t1,t2,andt3 are the sink nodes as shown in Figure 1(a). The arcs between nodes v and w denoted by v,w and w,v represent the two way of 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 having the same transit time, an auxiliary network is formed with capacities ua and transit time τa as shown in Figure 1(b).


## 2.1. Flow Models and Notations

Let a dynamic network topology be given byN=V,A,K,u,τ,di,S+,S−,T with finite sets of nodes V, arcs A, and commodities K=1,2,…,k, where V=n and A=m. Each commodity i∈K with demand di is routed through a unique source-sink pair si,ti. The sets S+andS−⊂V denote source and sink sets of all commodities, respectively. On each arc e=v,w, the capacity function u:A⟶Z≥0 restricts the flow of commodities and a nonnegative transit time function τ:A⟶Z≥0 measures the time to transship the flow from the entry point v to the exit point w of arc e=v,w. The time period T is given in advance which is denoted by T=0,1,…,T−1 in discrete and T=0,T in continuous-time settings. A static network is a network besides the temporal dimension denoted by N=V,A,K,u,di,S+,S−. Many nice properties developed primarily based on static network topology are building blocks for most of the real-world dynamic flow problems.


### 2.1.1. Static Multicommodity Flow

A multicommodity flowψ for the given static network N is the sum of all nonnegative static flows ψi defined by the functions ψi:A⟶ℛ+ for each commodity i satisfying(1)excessψiv=−di,ifv=si,0,ifv∉si,ti,di,ifv=ti,∀i∈K,(2)0≤∑i∈Kψei≤ue,∀e∈A,where(3)excessψiv=∑e∈Ainvψei−∑e∈Aoutvψei,represents the excess flow of commodity i at node v. The sets Aoutv=v,w|w∈V and Ainv=w,v|w∈V denote the outgoing arcs from node v and the incoming arcs to node v, respectively, such that AoutS−=∅ and AinS+=∅, except in the lane reversals. The second condition of the constraints in (1) are flow conservation constraints for each commodity at intermediate nodes. The constraints in (2) are bundle constraints that limit the flow of each commodity on the arc. The network flow is called circulation if it satisfies flow conservation at all the nodes, i.e., excessψiv=0,∀v∈V. The maximum static multicommodity flow problem with k-commodities consist of ψ1,ψ2,…,ψk single-commodity flows maximizing ∑i=1kψi satisfying constraints (1) and (2).A polynomial-time solution of the MSMCF problem has been obtained by linear programming techniques (e.g., ellipsoid method or interior-point method). In this problem, each commodityi=1,2,3,…,k has a unique source-sink pair si−ti, and we wish to send the maximum flow from the source nodes si to the sink nodes ti satisfying given bundle capacity ue on each arc e=v,w. That is, we wish to maximize the sum of the flows over all the commodities.


### 2.1.2. Dynamic Multicommodity Flow

For a given dynamic networkN with constant transit time on arcs, a multicommodity flow over times ξ is a sum of flows defined by ξi:A×T⟶ℛ+ satisfying constraints (4)–(6):(4)excessξiv,T−1=−di,ifv=si,0,ifv∉si,ti,di,ifv=ti,∀i∈K,(5)excessξiv,θ≥0,∀v∉si,ti,i∈K,θ∈T,(6)0≤ξeθ=∑i∈Kξeiθ≤ue,∀e∈A,θ∈T,where(7)excessξiv,θ=∑δ=τeθ∑e∈Ainvξeiδ−τe−∑δ=0θ∑e∈Aoutvξeiδ,is the excess flow of commodity i on node v at time θ. Here, the second condition of the constraints in (4) are flow conservation constraints at time horizon T, whereas nonconservation of flow at intermediate time points θ∈T=0,1,…,T−1 is represented by the constraints in (5). Similarly, the constraints in (6) are bundle constraints that limit the flow on each arc at each point of time. The aim is to maximize the amount of flow to satisfy the demand di of each commodity i from si to ti which is stated in the first and last conditions of (4). The earliest arrival multicommodity flow problem is to find a dynamic multicommodity flow of maximum value valmaxξθ for all time units θ∈0,1,…,T−1 defined by objective function:(8)valξθ=∑δ=τeθ∑e∈Atiinξeiδ−τe.Instead of each timeθ, if the maximization is considered for a given time θ=T−1, it is defined as an MDMCF problem.The equality in (5) represents strong flow conservation constraints that do not allow to store the flow at intermediate nodes for each time θ (i.e., without intermediate storage). The strict inequality constraint in (5) represents the weak flow conservation constraint at intermediate nodes for all times with intermediate storage.


## 2.1.1. Static Multicommodity Flow

A multicommodity flowψ for the given static network N is the sum of all nonnegative static flows ψi defined by the functions ψi:A⟶ℛ+ for each commodity i satisfying(1)excessψiv=−di,ifv=si,0,ifv∉si,ti,di,ifv=ti,∀i∈K,(2)0≤∑i∈Kψei≤ue,∀e∈A,where(3)excessψiv=∑e∈Ainvψei−∑e∈Aoutvψei,represents the excess flow of commodity i at node v. The sets Aoutv=v,w|w∈V and Ainv=w,v|w∈V denote the outgoing arcs from node v and the incoming arcs to node v, respectively, such that AoutS−=∅ and AinS+=∅, except in the lane reversals. The second condition of the constraints in (1) are flow conservation constraints for each commodity at intermediate nodes. The constraints in (2) are bundle constraints that limit the flow of each commodity on the arc. The network flow is called circulation if it satisfies flow conservation at all the nodes, i.e., excessψiv=0,∀v∈V. The maximum static multicommodity flow problem with k-commodities consist of ψ1,ψ2,…,ψk single-commodity flows maximizing ∑i=1kψi satisfying constraints (1) and (2).A polynomial-time solution of the MSMCF problem has been obtained by linear programming techniques (e.g., ellipsoid method or interior-point method). In this problem, each commodityi=1,2,3,…,k has a unique source-sink pair si−ti, and we wish to send the maximum flow from the source nodes si to the sink nodes ti satisfying given bundle capacity ue on each arc e=v,w. That is, we wish to maximize the sum of the flows over all the commodities.


## 2.1.2. Dynamic Multicommodity Flow

For a given dynamic networkN with constant transit time on arcs, a multicommodity flow over times ξ is a sum of flows defined by ξi:A×T⟶ℛ+ satisfying constraints (4)–(6):(4)excessξiv,T−1=−di,ifv=si,0,ifv∉si,ti,di,ifv=ti,∀i∈K,(5)excessξiv,θ≥0,∀v∉si,ti,i∈K,θ∈T,(6)0≤ξeθ=∑i∈Kξeiθ≤ue,∀e∈A,θ∈T,where(7)excessξiv,θ=∑δ=τeθ∑e∈Ainvξeiδ−τe−∑δ=0θ∑e∈Aoutvξeiδ,is the excess flow of commodity i on node v at time θ. Here, the second condition of the constraints in (4) are flow conservation constraints at time horizon T, whereas nonconservation of flow at intermediate time points θ∈T=0,1,…,T−1 is represented by the constraints in (5). Similarly, the constraints in (6) are bundle constraints that limit the flow on each arc at each point of time. The aim is to maximize the amount of flow to satisfy the demand di of each commodity i from si to ti which is stated in the first and last conditions of (4). The earliest arrival multicommodity flow problem is to find a dynamic multicommodity flow of maximum value valmaxξθ for all time units θ∈0,1,…,T−1 defined by objective function:(8)valξθ=∑δ=τeθ∑e∈Atiinξeiδ−τe.Instead of each timeθ, if the maximization is considered for a given time θ=T−1, it is defined as an MDMCF problem.The equality in (5) represents strong flow conservation constraints that do not allow to store the flow at intermediate nodes for each time θ (i.e., without intermediate storage). The strict inequality constraint in (5) represents the weak flow conservation constraint at intermediate nodes for all times with intermediate storage.


## 2.2.Δ-Condensed Time-Expanded Graph

The network topologyN=V,A,K,u,τ,di,S+,S−,T is considered. Fleischer and Skutella [21] 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 multiples of Δ>0 such that T/Δ is bounded by a polynomial in input size. The nodes and arcs in the Δ-condensed time-expanded network are defined as(9)VTΔ=vθ:v∈V,θ=0,1,2,…,T/Δ−1∪si′,ti′:i∈K∪s∗,t∗,AMΔ=vθ,wθ+τe:e=v,w∈A,θ=0,1,…,T−τe/Δ−1,AHΔ=vθ,vθ+1:e=v,w∈A,θ=0,1,…,T/Δ−2,A+Δ=∪s∗,si′:i∈K∪si′,sθ:i∈K,si′∈S+′,θ∈0,1,2,…,T/Δ−1,A−Δ=∪ti′,t∗:i∈K∪tθ,ti′:i∈K,ti′∈S−′,θ∈0,1,2,…,T/Δ−1,where S+′ and S−′ are the super terminals for each commodity as well as for the Δ-condensed time-expanded network, i.e., si′,ti′:i∈K∪s∗,t∗. The copies of VTΔ correspond to flow through V in time T=αΔ for discrete-time and T=αΔ,α+1Δ for continuous-time, where α=0,1,2,…,T/Δ−1. In this setting, for every arc corresponding to a discrete-time with a multiple of Δ, capacities are rescaled by Δue. If arc transit times are not multiples of Δ, then transit times are rounded up to a multiple of Δ by τe′=τe/ΔΔ and 0≤τe′−τe<Δ for all arcs e∈A. If we take Δ=1, then the Δ-condensed time-expanded network reduces to the classical time-expanded network.


## 2.3. Lane Reversal Technique

For a given networkN, the corresponding auxiliary network is denoted by Na=V,Aa,K,ua,τa,di,S+,S−,T with undirected edges in Aa=v,w:v,worw,v∈A, where er=w,v is the reversed arc of e=v,w. The capacity of the auxiliary arc is the sum of capacities of arcs e and er such that uea=ue+uer, where ue=0 if e∉A. The transit time of the auxiliary arc is(10)τea=τe,ife∈A,τer,otherwise.Other network parameters are the same. The transformation of the multicommodity network with lane reversals is represented in Figures1(a) and 1(b). The first, second, and third commodities are shipped through the paths s1−t1, s2−t2, and s3−t3, respectively.Figure 1
Auxiliary network (b) of the given network (a). (a) Capacity, transit time; (b) capacity, transit time.
(a)(b)Example 1.
Let us consider a multicommodity network, wheres1,s2,ands3 are the source nodes and t1,t2,andt3 are the sink nodes as shown in Figure 1(a). The arcs between nodes v and w denoted by v,w and w,v represent the two way of 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 having the same transit time, an auxiliary network is formed with capacities ua and transit time τa as shown in Figure 1(b).


## 3. Static Mutlicommodity Flow with Lane Reversals

In this section, we introduce the partial lane reversals on the static multicommodity flow problem that makes best utilization of arc capacities to optimize the solution. The procedure for lane reversals is as follows:(1)
Arcer=w,v is reversed iff either ψe−ue>0, where e=v,w, or there is ψe≥0 along the arc e=v,w∉A. If uea−ψe>0, then the arc er is reversed partially, and capacity of remaining arcs er is saved.(2)
Ifψe−ue>0 and uea−ψe=0, then the arc er is reversed completely.(3)
Ifψe−ue<0 neither e nor er is reversed.Problem 1.
A networkN=V,A,K,u,S+,S− is considered. The MSMCF problem with partial lane reversals sends the maximum flow from the sources si to the corresponding sinks ti in the unique pair si,ti for each commodity i=1,2,…,k by saving the unused arc capacity.


### 3.1. Polynomial-Time Solution of MSMCF Problem

General linear programming approach (e.g., ellipsoid method or interior-point method) solves the static multicommodity flow problem in polynomial-time. To solve the MSMCF problem with partial lane reversals (problem1), we present Algorithm 1.Algorithm 1:MSMCF algorithm with partial lane reversals.
Input: given static multicommodity flow network N=V,A,u,K,S+,S−Output: the MSMCF with partial lane reversals(1) The given network is transformed by adding two-way capacities asNa=V,Aa,uea,K,S+,S−.(2) Compute the MSMCF on the transformed networkNa.(3) Decompose the flow along thesi−ti paths and cycles and remove flows in cycles ∀i∈K.(4) Reverseer∈A up to the capacity ψe−ue iff ψe>ue, ue replaced by 0 whenever e∉A, where ψe=∑i=1kψei and ue=∑i=1kuei.(5) For eache∈A, if er is reversed, scer=uea−ψe and sce=0. If neither e nor er is reversed, sce=ue−ψe>0, where sce is the saved capacity of e.(6) Transform the solution to the original network.Theorem 1.
The MSMCF with partial lane reversal problem can be solved using Algorithm1 optimally.Proof.
First, we show that Algorithm1 is feasible. We can compute maximum multicommodity flow either by using the ellipsoid or interior-point methods. Therefore, Step 2 of the algorithm is feasible. Steps 1, 3, 4, 5, and 6 are feasible being transformation, decomposition, reversing arc, and saving arc capacities as in [19]. Hence, feasibility is shown.
Now, we prove the optimality of the algorithm. On the transformed networkNa, the MSMCF is computed iteratively using an efficient algorithm. As flow is send in a unique pair si,ti for each commodity i=1,2,…,k, the problem can be reduced to the static flow for a single commodity. In the static single-commodity flow, the maximum static flow on the transformed network is equivalent to the maximum static flow with partial lane reversals on the original network as in [19], and capacity of unused arcs is saved. Thus, the MSMCF in the transformed network is equal to the MSMCF with partial lane reversals for the original network.Corollary 1.
The MSMCF with partial lane reversals can be computed in polynomial-time complexity.Proof.
The complexity of the algorithm is dominated by Steps 2 and 3. All other steps can be computed in linear time. The maximum multicommodity flow problem is a linear programming problem, so the general linear programming technique (ellipsoid method or interior-point methods) solves the static multicommodity problem on the auxiliary network in polynomial-time in Step 2. This solution is equivalent to the maximum static multicommodity flow problem on the given network. The flow can be decomposed inOmn time in Step 3. Hence, the MSMCF with partial lane reversals can be computed in polynomial-time.Example 2.
If we consider network as in Example1 without temporal dimension, then it becomes a static multicommodity network. We can send the flow on an auxiliary network as shown in Figure 1(b). The maximum static multicommodity flow before lane reversals can be calculated in Figure 1(a) and after lane reversals in Figure 2(a). The saved capacity of unused arcs is shown in Figure 2(b).
The comparison of MSMCF before and after lane reversals is presented in Table1.Figure 2
Network with (a) flow, capacity and (b) flow with saved capacity on the arcs.
(a)(b)Table 1
Maximum multicommodity flow before and after lane reversals.
PathFlow before LRFlow after LR% of flow increaseds1−x−y−t123s2−x−y−t223s3−x−y−t304Total410150LR = lane reversals.Theorem 2.
If a minimum cut in the multicommodity network has the symmetric capacity, then the flow value can be at most doubled with lane reversal reconfiguration.Proof.
We know that the cut setC⊆A is the collection of disconnected and saturated arcs with the property that it disconnects sources and sinks. Let Val (C) be a value of cut which is the sum of the capacities of its individual arcs, i.e., ValC=∑e∈Cue. We know that the arcs e∈C have two-way orientations with asymmetric (or symmetric) capacities. If each arc e∈C has the symmetric capacity, the lane reversal reconfiguration of the multicommodity network expands the capacity of cut two times. Let Ca⊆Aa be the cut set in the auxiliary network, then its value becomes(11)ValCa=∑a∈Cauea=2∑e∈Aue.
The minimum multicommodity cut is(12)ValminCa=min∑a∈Cauea.
Moreover, we have that every optimal maximum static multicommodityψ is less or equal to the minimum multicommodity cut in the auxiliary network. Consequently, the flow value can be increased up to double with lane reversals.
The reconfiguration of the multicommodity network with lane reversals is as follows:(13)Valmaxψ=max∑Pa∈PaψPa≤ValminCa=2Valmaxψ,where Pa is the collection of all paths.
By Theorem1, every optimal maximum static multicommodity flow in auxiliary network Na is a feasible maximum static multicommodity flow with lane reversals in original network N. This completes the proof.


### 3.2. Approximation Solution of MSMCF Problem

Linear programming techniques provide polynomial-time solutions for multicommodity flow problems. However, in many applications, these problems are large in input size and can take a long time to solve using these techniques. Due to this, it is beneficial to develop approximation algorithms that provide solutions close to the optimal solution. As a consequence, an intense attempt was made to obtain an efficient approximate algorithm for the multicommodity flow problem.Let a minimization (or a maximization) problem beX and let the optimal solution of the objective function be denoted by OptI for an instance I∈X. Suppose ɛ>0. An algorithm A is called a 1+ɛor1−ɛ approximation algorithm for problem X, if it produces a feasible solution with objective value AI for each instance I of X such that(14)AI−OptI≤ɛOptI,⇒−ɛOptI≤AI−OptI≤ɛOptI,⇒1−ɛOptI≤AI≤1+ɛOptI.For a problemX, a polynomial-time approximation scheme (PTAS) is an approximation scheme with the running time polynomial in the input size of the problem.For a problemX, a fully polynomial-time approximation scheme (FPTAS) is an approximation scheme with running time polynomial in the input size of the problem as well as polynomial in 1/ϵ.Fleischer [22] presented the first FPTAS for the maximum multicommodity flow problem that is independent of the number of commodities. It is faster than the best previous approximation schemes, whose running time is Oɛ−2m2. To calculate the approximate solution, Fleischer uses path flow linear programming formulation of a maximum multicommodity flow problem. The dual of this linear program corresponds to the problem of assigning length to the edges of the network such that the length of the shortest path from si to ti is at least one for each commodity.Let us assume thatle and lP denote the length of edges and length of the shortest path from si to ti for each i, respectively. Algorithm starts with le=δ,∀e,ψ=0, and selects a path P∈ℙ with lP<1. The flow ψP=ψP+u is assigned along the path P where u=mine∈Pue, and the length le=le1+ɛu/ue,∀e∈P, of each edge is updated. The process is repeated until there exists a path with lP<1 otherwise return ψ,l.Based on this, we present Algorithm2 to calculate approximate solution of MSMCF with partial lane reversals.Algorithm 2: An FPTAS for the MSMCF problem with partial lane reversals.
Input: given static multicommodity flow network N=V,A,u,K,S+,S−Output: the approximate MSMCF solution with partial lane reversals(1) The given network is transformed by adding two-way capacities asNa=V,Aa,uea,K,S+,S−.(2) Compute the approximate MSMCF on the transformed networkNa by using the algorithm by Fleischer [22].(3) Decompose the flow along thesi−ti paths and cycles and remove flows in cycles ∀i∈K.(4) Reverseer∈A up to the capacity ψe−ue iff ψe>ue, ue replaced by 0 whenever e∉A, where ψe=∑i=1kψei and ue=∑i=1kuei.(5) For eache∈A, if er is reversed, scer=uea−ψe and sce=0. If neither e nor er is reversed, sce=ue−ψe>0, where sce is the saved capacity of e.(6) Transform the solution to the original network.Example1 with capacity on arcs only (cf. Figure 2(a)) is considered, and maximum multicommodity flow with lane reversals is calculated.Let us assume thatle=0.25,ɛ=0.4,andψ=0. We choose the path P1:s1−x−y−t1.SincelP1=ls1,x+lx,y+ly,t1=0.25+0.25+0.25=0.75<1 and u=mine∈P1ue=min5,12,3=3, we update the flow ψP1=0+3=3 and calculate the length of edges, i.e., ls1,x=ls1,x1+ɛu/us1,x=0.251+0.4×3/5=0.31.Similarly,lx,y=0.275andly,t1=0.35. Therefore, lP1=0.31+0.275+0.35=0.935<1. But, there is no path between s1 and t1 since edge y,t1 is saturated.We choose the next pathP3:s3−x−y−t3. Since lP3=ls3,x+lx,y+ly,t3=0.25+0.25+0.25=0.75<1 and u=mine∈P3ue=min5,9,4=4, we update the flow value.Now,ls3,x=0.33,lx,y=0.283,ly,t3=0.35,andlp3=0.33+0.283+0.35=0.963<1. But, there is no path between s3 and t3 since edge y,t3 is saturated. Again, we update the flow value and length of the edges.In the same way, the next path isP2:s2−x−y−t2,lp2<1 and u=mine∈P2ue=3,ψP2=0+3=3. There is no path from s2 to t2. Since there is no anymore si−ti path, the algorithm terminates, and maximum flow is 3 + 4 +3 = 10.Corollary 2.
An approximate solution of MSMCF with partial lane reversals can be computed in fully polynomial-time complexity.Proof.
The complexity of the algorithm is dominated by Steps 2 and 3. All other steps can be computed in linear time. The solution to an approximate maximum multicommodity flow problem can be computed by Fleischer [22] on the auxiliary network in Oɛ−2m2 time in Step 2. This solution is equivalent to the maximum static multicommodity flow problem on the given network. The flow can be decomposed in Omn time in Step 3. Hence, the MSMCF with partial lane reversals can be computed in fully polynomial-time.


## 3.1. Polynomial-Time Solution of MSMCF Problem

General linear programming approach (e.g., ellipsoid method or interior-point method) solves the static multicommodity flow problem in polynomial-time. To solve the MSMCF problem with partial lane reversals (problem1), we present Algorithm 1.Algorithm 1:MSMCF algorithm with partial lane reversals.
Input: given static multicommodity flow network N=V,A,u,K,S+,S−Output: the MSMCF with partial lane reversals(1) The given network is transformed by adding two-way capacities asNa=V,Aa,uea,K,S+,S−.(2) Compute the MSMCF on the transformed networkNa.(3) Decompose the flow along thesi−ti paths and cycles and remove flows in cycles ∀i∈K.(4) Reverseer∈A up to the capacity ψe−ue iff ψe>ue, ue replaced by 0 whenever e∉A, where ψe=∑i=1kψei and ue=∑i=1kuei.(5) For eache∈A, if er is reversed, scer=uea−ψe and sce=0. If neither e nor er is reversed, sce=ue−ψe>0, where sce is the saved capacity of e.(6) Transform the solution to the original network.Theorem 1.
The MSMCF with partial lane reversal problem can be solved using Algorithm1 optimally.Proof.
First, we show that Algorithm1 is feasible. We can compute maximum multicommodity flow either by using the ellipsoid or interior-point methods. Therefore, Step 2 of the algorithm is feasible. Steps 1, 3, 4, 5, and 6 are feasible being transformation, decomposition, reversing arc, and saving arc capacities as in [19]. Hence, feasibility is shown.
Now, we prove the optimality of the algorithm. On the transformed networkNa, the MSMCF is computed iteratively using an efficient algorithm. As flow is send in a unique pair si,ti for each commodity i=1,2,…,k, the problem can be reduced to the static flow for a single commodity. In the static single-commodity flow, the maximum static flow on the transformed network is equivalent to the maximum static flow with partial lane reversals on the original network as in [19], and capacity of unused arcs is saved. Thus, the MSMCF in the transformed network is equal to the MSMCF with partial lane reversals for the original network.Corollary 1.
The MSMCF with partial lane reversals can be computed in polynomial-time complexity.Proof.
The complexity of the algorithm is dominated by Steps 2 and 3. All other steps can be computed in linear time. The maximum multicommodity flow problem is a linear programming problem, so the general linear programming technique (ellipsoid method or interior-point methods) solves the static multicommodity problem on the auxiliary network in polynomial-time in Step 2. This solution is equivalent to the maximum static multicommodity flow problem on the given network. The flow can be decomposed inOmn time in Step 3. Hence, the MSMCF with partial lane reversals can be computed in polynomial-time.Example 2.
If we consider network as in Example1 without temporal dimension, then it becomes a static multicommodity network. We can send the flow on an auxiliary network as shown in Figure 1(b). The maximum static multicommodity flow before lane reversals can be calculated in Figure 1(a) and after lane reversals in Figure 2(a). The saved capacity of unused arcs is shown in Figure 2(b).
The comparison of MSMCF before and after lane reversals is presented in Table1.Figure 2
Network with (a) flow, capacity and (b) flow with saved capacity on the arcs.
(a)(b)Table 1
Maximum multicommodity flow before and after lane reversals.
PathFlow before LRFlow after LR% of flow increaseds1−x−y−t123s2−x−y−t223s3−x−y−t304Total410150LR = lane reversals.Theorem 2.
If a minimum cut in the multicommodity network has the symmetric capacity, then the flow value can be at most doubled with lane reversal reconfiguration.Proof.
We know that the cut setC⊆A is the collection of disconnected and saturated arcs with the property that it disconnects sources and sinks. Let Val (C) be a value of cut which is the sum of the capacities of its individual arcs, i.e., ValC=∑e∈Cue. We know that the arcs e∈C have two-way orientations with asymmetric (or symmetric) capacities. If each arc e∈C has the symmetric capacity, the lane reversal reconfiguration of the multicommodity network expands the capacity of cut two times. Let Ca⊆Aa be the cut set in the auxiliary network, then its value becomes(11)ValCa=∑a∈Cauea=2∑e∈Aue.
The minimum multicommodity cut is(12)ValminCa=min∑a∈Cauea.
Moreover, we have that every optimal maximum static multicommodityψ is less or equal to the minimum multicommodity cut in the auxiliary network. Consequently, the flow value can be increased up to double with lane reversals.
The reconfiguration of the multicommodity network with lane reversals is as follows:(13)Valmaxψ=max∑Pa∈PaψPa≤ValminCa=2Valmaxψ,where Pa is the collection of all paths.
By Theorem1, every optimal maximum static multicommodity flow in auxiliary network Na is a feasible maximum static multicommodity flow with lane reversals in original network N. This completes the proof.


## 3.2. Approximation Solution of MSMCF Problem

Linear programming techniques provide polynomial-time solutions for multicommodity flow problems. However, in many applications, these problems are large in input size and can take a long time to solve using these techniques. Due to this, it is beneficial to develop approximation algorithms that provide solutions close to the optimal solution. As a consequence, an intense attempt was made to obtain an efficient approximate algorithm for the multicommodity flow problem.Let a minimization (or a maximization) problem beX and let the optimal solution of the objective function be denoted by OptI for an instance I∈X. Suppose ɛ>0. An algorithm A is called a 1+ɛor1−ɛ approximation algorithm for problem X, if it produces a feasible solution with objective value AI for each instance I of X such that(14)AI−OptI≤ɛOptI,⇒−ɛOptI≤AI−OptI≤ɛOptI,⇒1−ɛOptI≤AI≤1+ɛOptI.For a problemX, a polynomial-time approximation scheme (PTAS) is an approximation scheme with the running time polynomial in the input size of the problem.For a problemX, a fully polynomial-time approximation scheme (FPTAS) is an approximation scheme with running time polynomial in the input size of the problem as well as polynomial in 1/ϵ.Fleischer [22] presented the first FPTAS for the maximum multicommodity flow problem that is independent of the number of commodities. It is faster than the best previous approximation schemes, whose running time is Oɛ−2m2. To calculate the approximate solution, Fleischer uses path flow linear programming formulation of a maximum multicommodity flow problem. The dual of this linear program corresponds to the problem of assigning length to the edges of the network such that the length of the shortest path from si to ti is at least one for each commodity.Let us assume thatle and lP denote the length of edges and length of the shortest path from si to ti for each i, respectively. Algorithm starts with le=δ,∀e,ψ=0, and selects a path P∈ℙ with lP<1. The flow ψP=ψP+u is assigned along the path P where u=mine∈Pue, and the length le=le1+ɛu/ue,∀e∈P, of each edge is updated. The process is repeated until there exists a path with lP<1 otherwise return ψ,l.Based on this, we present Algorithm2 to calculate approximate solution of MSMCF with partial lane reversals.Algorithm 2: An FPTAS for the MSMCF problem with partial lane reversals.
Input: given static multicommodity flow network N=V,A,u,K,S+,S−Output: the approximate MSMCF solution with partial lane reversals(1) The given network is transformed by adding two-way capacities asNa=V,Aa,uea,K,S+,S−.(2) Compute the approximate MSMCF on the transformed networkNa by using the algorithm by Fleischer [22].(3) Decompose the flow along thesi−ti paths and cycles and remove flows in cycles ∀i∈K.(4) Reverseer∈A up to the capacity ψe−ue iff ψe>ue, ue replaced by 0 whenever e∉A, where ψe=∑i=1kψei and ue=∑i=1kuei.(5) For eache∈A, if er is reversed, scer=uea−ψe and sce=0. If neither e nor er is reversed, sce=ue−ψe>0, where sce is the saved capacity of e.(6) Transform the solution to the original network.Example1 with capacity on arcs only (cf. Figure 2(a)) is considered, and maximum multicommodity flow with lane reversals is calculated.Let us assume thatle=0.25,ɛ=0.4,andψ=0. We choose the path P1:s1−x−y−t1.SincelP1=ls1,x+lx,y+ly,t1=0.25+0.25+0.25=0.75<1 and u=mine∈P1ue=min5,12,3=3, we update the flow ψP1=0+3=3 and calculate the length of edges, i.e., ls1,x=ls1,x1+ɛu/us1,x=0.251+0.4×3/5=0.31.Similarly,lx,y=0.275andly,t1=0.35. Therefore, lP1=0.31+0.275+0.35=0.935<1. But, there is no path between s1 and t1 since edge y,t1 is saturated.We choose the next pathP3:s3−x−y−t3. Since lP3=ls3,x+lx,y+ly,t3=0.25+0.25+0.25=0.75<1 and u=mine∈P3ue=min5,9,4=4, we update the flow value.Now,ls3,x=0.33,lx,y=0.283,ly,t3=0.35,andlp3=0.33+0.283+0.35=0.963<1. But, there is no path between s3 and t3 since edge y,t3 is saturated. Again, we update the flow value and length of the edges.In the same way, the next path isP2:s2−x−y−t2,lp2<1 and u=mine∈P2ue=3,ψP2=0+3=3. There is no path from s2 to t2. Since there is no anymore si−ti path, the algorithm terminates, and maximum flow is 3 + 4 +3 = 10.Corollary 2.
An approximate solution of MSMCF with partial lane reversals can be computed in fully polynomial-time complexity.Proof.
The complexity of the algorithm is dominated by Steps 2 and 3. All other steps can be computed in linear time. The solution to an approximate maximum multicommodity flow problem can be computed by Fleischer [22] on the auxiliary network in Oɛ−2m2 time in Step 2. This solution is equivalent to the maximum static multicommodity flow problem on the given network. The flow can be decomposed in Omn time in Step 3. Hence, the MSMCF with partial lane reversals can be computed in fully polynomial-time.


## 4. Dynamic Multicommodity Flow with Partial Lane Reversals

In this section, we introduce the MDMCF with partial lane reversals by reverting the necessary arc capacities. Hall et al. [10] proved that multicommodity flow over time is NP-hard. They provided the solution of the flow over time problem in a network having uniform path length (a network where the length of all paths is the same).The lane reversal strategy cannot be applied in case of uniform path length in general. It may violate the criterion of uniform path length after lane reversals as shown in example3. Two algorithms to solve the MDMCF problem with lane reversals are presented in this section.Example 3.
Let us consider a multicommodity network wheres1,s2,ands3 are the source nodes and t1,t2,andt3 are the sink nodes as shown in Figure 3(a). The first and second numbers on the arcs represent capacity and transit time associated with the arcs. The auxiliary network for reconfiguration is as shown in Figure 3(b). The network is of uniform path length before lane reversals and after the lane reversals, and a new path s3−x−y−t3 is created that violates uniform path length. In general, it proves that the lane reversal strategy fails to satisfy the condition of uniform path length. The lane reversal technique can be applied in case of uniform path length by reversing only those arcs that do not violate uniform path length.Figure 3
(a) Network with uniform path length before lane reversals (capacity, transit time). (b) Lane reversal network of (a) violating uniform path length (capacity, transit time).
(a)(b)


### 4.1. Pseudopolynomial Solution of MDMCF

To deal with the maximum flow over time problem, Ford and Fulkerson [7] introduced the concept of time expansion. This well-known approach can be carried out in the case of the multicommodity flow over time problem. Kappmeier [11] has shown the equivalency between static multicommodity flow on a time-expanded network and dynamic multicommodity flow on the original network as given below.Lemma 1.
LetN=V,A,K,u,τ,S+,S−,T be a flow over time network. For any time horizon T, a feasible static S+′−S−′ multicommodity flow ψ in the time-expanded network NT, there exists a feasible multicommodity flow over time ξ with the sources S+ and sinks S− in network N that sends the same amount of flow with time horizon T, i.e., ψT=ξ and vice-versa.Due to the reduction of the dynamic multicommodity flow problem on networkN to the static multicommodity flow problem on a time-expanded network NT, it can be solved in pseudopolynomial-time complexity.Problem 2.
Consider a networkN=V,A,K,u,τ,S+,S−,T. The MDMCF problem with partial lane reversals sends the maximum flow from the sources si to the corresponding sinks ti 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 solve the maximum multicommodity flow over time problem with partial lane reversals (problem2), we design Algorithm 3.Algorithm 3: Algorithm for MDMCF with partial lane reversals.
Input: given dynamic multicommodity flow network N=V,A,u,τ,K,S+,S−,TOutput: the MDMCF with partial lane reversals(1) A given dynamic network is transformed into time-expanded network byNT=VT,AT=AM∪AH∪A+∪A−,K,u,τ,S+′,S−′,T(2) An auxiliary network is constructed by adding two-way capacities asNTa=VT,ATa,ua,τaK,S+′,S−′,T.(3) Compute the MSMCF on the auxiliary networkNTa.(4) Decompose the flow along thesi−ti paths and cycles and remove flows in cycles ∀i∈K.(5) Reverseerθ∈AT up to the capacity ψaθ−ue iff ψaθ>ue, ue replaced by 0 whenever eθ∉AT where ψe=∑i=1kψei and ue=∑i=1kuei.(6) For eacheθ∈AT, if erθ is reversed, scerθ=uea−ψeθ and sceθ=0. If neither e nor er is reversed, sceθ=ue−ψeθ>0, where sceθ is the saved capacity of e.(7) Transform the solution to the original network.Theorem 3.
Algorithm3 provides pseudopolynomial-time solution of the MDMCF problem with partial lane reversals.Proof.
The theorem will be proved in three steps. In the first step, we show the feasibility. Step 2 of the algorithm is well-defined because it transforms the given dynamic network flow problem into the static network flow problem on the time-expanded auxiliary network. The feasibility of other steps in the algorithm can be shown as similar to Theorem1. In the second step, we prove the optimality. Feasibility implies that any feasible solution of MDMCF on NTa is feasible to the MDMCF with lane reversal solution on network N. Dynamic multicommodity flow problem on network N reduces to a static multicommodity flow problem on NTa. By reducing the multicommodity to a single-commodity and decomposing the flow into the si−ti path, dynamic multicommodity flow solution can be obtained optimally on 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. At last, we show that the algorithm solves it in pseudopolynomial-time. We know that Step 3 is solved in Omn times, and Step 2 can be computed polynomially in the input size of the network, i.e., it depends on T. All other steps can be computed in linear time. Thus, Algorithm 3 solves the MDMCF problem with partial lane reversals on given network N optimally in pseudopolynomial-time complexity.Example 4.
We compute MDMCF on the auxiliary network obtained by adding two-way capacities of Figure1(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 ψ on the time-expanded network which corresponds to multicommodity flow over time ξ on the auxiliary network. The maximum multicommodity flow over time computation after lane reversals is as shown in Figure 4.Figure 4
Time-expanded network of Figure1(b).


### 4.2. Approximate Solution of MDMCF

A time-expanded network is a well-known technique to solve flow over time problems, but it has the drawback of a large blow-up 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 4.Algorithm 4: An FPTAS algorithm for MDMCF with partial lane reversals.
Input: given dynamic multicommodity flow network N=V,A,u,τ,K,S+,S−,TOutput: the MDMCF with partial lane reversals(1) The auxiliary networkNa is transformed to Δ-condensed auxiliary network NTΔa=VTΔ,ATΔa,K,u′a,τ′a,di′,S+′,S−′,T with ue′a=Δue+uer, τe′a=τe/ΔΔ,ife∈A,τer/ΔΔ,otherwise.(2) Compute the approximate MSMCF by using algorithm by Fleischer [22] on the auxiliary network NTΔa.(3) Decompose the flow along thesi−ti paths and cycles and remove flows in cycles ∀i∈K.(4) Reverseerθ∈ATΔ up to the capacity ψe′θ−Δue iff ψe′θ>Δue, ue replaced by 0 whenever eθ∉ATΔ where ψe′=∑i=1kψe′i and ue′=∑i=1kue′i.(5) For eacheθ∈ATΔ, if erθ is reversed, scerθ=uea−ψeθ and sceθ=0. If neither e nor er is reversed, sceθ=ue−ψeθ>0, where sceθ is the saved capacity of e.(6) Transform the solution to the original network.Theorem 4.
Algorithm4 provides approximate solution of the MDMCF problem with partial lane reversals.Proof.
First, we prove the feasibility. Step 1 of the algorithm is well-defined as it transforms the given dynamic network flow into the static network flow on theΔ-condensed auxiliary network. The feasibility of other steps of the algorithm is similar to Theorem 1.
Next, we prove the optimality. Feasibility implies that any approximate optimal solution of MDMCF with lane reversals on networkN is also a feasible approximate solution to the MDMCF on NΔa. Dynamic multicommodity flow problem on network N reduces to a static multicommodity flow problem on NΔa. By reducing the multicommodity to a single commodity and decomposing it into the si−ti path, an approximate dynamic multicommodity flow solution can be obtained optimally on auxiliary network NΔa. An approximate optimal solution on NΔa is a feasible solution on N. The unused capacities of the arcs by partial lane reversals are saved in Step 5. Thus, an approximate MDMCF solution with lane reversals on each arc of the given network N can be computed optimally.Corollary 3.
An FPTAS to the MDMCF problem with partial lane reversal can be computed in fully polynomial-time complexity.Proof.
The complexity of Algorithm4 is dominated by Steps 2 and 3. Step 3 is solved in Omn time. An approximate solution of a static multicommodity flow problem on the Δ-condensed auxiliary network is obtained by Fleischer [22] in Oɛ−2m2 time complexity in Step 2. The Δ-condensed auxiliary network contains n2/ɛ2 nodes and mn/ɛ2 arcs having polynomial-time complexity. Remaining steps can be solved in linear Om time. So, the problem can be computed in fully polynomial-time.
By scaling the capacities and transit times on arcs given in Figure1(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 5 by taking Δ=2.
The comparison of MDMCF before and after lane reversals is shown in Table2 and Figure 6.Figure 5
Δ-condensed time-expanded network of Figure 1(b) after scaling capacity and transit time.Table 2
Maximum multicommodity flow over time with lane reversals.
Time-expandedΔ-condensedPathFlow before LRFlow after LRFlow before LRFlow after LRs1−x−y−t16946s2−x−y−t24646s3−x−y−t30808Total1023820% increased130150LR = lane reversals.Figure 6
Comparison of flow before and after lane reversals.


## 4.1. Pseudopolynomial Solution of MDMCF

To deal with the maximum flow over time problem, Ford and Fulkerson [7] introduced the concept of time expansion. This well-known approach can be carried out in the case of the multicommodity flow over time problem. Kappmeier [11] has shown the equivalency between static multicommodity flow on a time-expanded network and dynamic multicommodity flow on the original network as given below.Lemma 1.
LetN=V,A,K,u,τ,S+,S−,T be a flow over time network. For any time horizon T, a feasible static S+′−S−′ multicommodity flow ψ in the time-expanded network NT, there exists a feasible multicommodity flow over time ξ with the sources S+ and sinks S− in network N that sends the same amount of flow with time horizon T, i.e., ψT=ξ and vice-versa.Due to the reduction of the dynamic multicommodity flow problem on networkN to the static multicommodity flow problem on a time-expanded network NT, it can be solved in pseudopolynomial-time complexity.Problem 2.
Consider a networkN=V,A,K,u,τ,S+,S−,T. The MDMCF problem with partial lane reversals sends the maximum flow from the sources si to the corresponding sinks ti 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 solve the maximum multicommodity flow over time problem with partial lane reversals (problem2), we design Algorithm 3.Algorithm 3: Algorithm for MDMCF with partial lane reversals.
Input: given dynamic multicommodity flow network N=V,A,u,τ,K,S+,S−,TOutput: the MDMCF with partial lane reversals(1) A given dynamic network is transformed into time-expanded network byNT=VT,AT=AM∪AH∪A+∪A−,K,u,τ,S+′,S−′,T(2) An auxiliary network is constructed by adding two-way capacities asNTa=VT,ATa,ua,τaK,S+′,S−′,T.(3) Compute the MSMCF on the auxiliary networkNTa.(4) Decompose the flow along thesi−ti paths and cycles and remove flows in cycles ∀i∈K.(5) Reverseerθ∈AT up to the capacity ψaθ−ue iff ψaθ>ue, ue replaced by 0 whenever eθ∉AT where ψe=∑i=1kψei and ue=∑i=1kuei.(6) For eacheθ∈AT, if erθ is reversed, scerθ=uea−ψeθ and sceθ=0. If neither e nor er is reversed, sceθ=ue−ψeθ>0, where sceθ is the saved capacity of e.(7) Transform the solution to the original network.Theorem 3.
Algorithm3 provides pseudopolynomial-time solution of the MDMCF problem with partial lane reversals.Proof.
The theorem will be proved in three steps. In the first step, we show the feasibility. Step 2 of the algorithm is well-defined because it transforms the given dynamic network flow problem into the static network flow problem on the time-expanded auxiliary network. The feasibility of other steps in the algorithm can be shown as similar to Theorem1. In the second step, we prove the optimality. Feasibility implies that any feasible solution of MDMCF on NTa is feasible to the MDMCF with lane reversal solution on network N. Dynamic multicommodity flow problem on network N reduces to a static multicommodity flow problem on NTa. By reducing the multicommodity to a single-commodity and decomposing the flow into the si−ti path, dynamic multicommodity flow solution can be obtained optimally on 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. At last, we show that the algorithm solves it in pseudopolynomial-time. We know that Step 3 is solved in Omn times, and Step 2 can be computed polynomially in the input size of the network, i.e., it depends on T. All other steps can be computed in linear time. Thus, Algorithm 3 solves the MDMCF problem with partial lane reversals on given network N optimally in pseudopolynomial-time complexity.Example 4.
We compute MDMCF on the auxiliary network obtained by adding two-way capacities of Figure1(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 ψ on the time-expanded network which corresponds to multicommodity flow over time ξ on the auxiliary network. The maximum multicommodity flow over time computation after lane reversals is as shown in Figure 4.Figure 4
Time-expanded network of Figure1(b).


## 4.2. Approximate Solution of MDMCF

A time-expanded network is a well-known technique to solve flow over time problems, but it has the drawback of a large blow-up 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 4.Algorithm 4: An FPTAS algorithm for MDMCF with partial lane reversals.
Input: given dynamic multicommodity flow network N=V,A,u,τ,K,S+,S−,TOutput: the MDMCF with partial lane reversals(1) The auxiliary networkNa is transformed to Δ-condensed auxiliary network NTΔa=VTΔ,ATΔa,K,u′a,τ′a,di′,S+′,S−′,T with ue′a=Δue+uer, τe′a=τe/ΔΔ,ife∈A,τer/ΔΔ,otherwise.(2) Compute the approximate MSMCF by using algorithm by Fleischer [22] on the auxiliary network NTΔa.(3) Decompose the flow along thesi−ti paths and cycles and remove flows in cycles ∀i∈K.(4) Reverseerθ∈ATΔ up to the capacity ψe′θ−Δue iff ψe′θ>Δue, ue replaced by 0 whenever eθ∉ATΔ where ψe′=∑i=1kψe′i and ue′=∑i=1kue′i.(5) For eacheθ∈ATΔ, if erθ is reversed, scerθ=uea−ψeθ and sceθ=0. If neither e nor er is reversed, sceθ=ue−ψeθ>0, where sceθ is the saved capacity of e.(6) Transform the solution to the original network.Theorem 4.
Algorithm4 provides approximate solution of the MDMCF problem with partial lane reversals.Proof.
First, we prove the feasibility. Step 1 of the algorithm is well-defined as it transforms the given dynamic network flow into the static network flow on theΔ-condensed auxiliary network. The feasibility of other steps of the algorithm is similar to Theorem 1.
Next, we prove the optimality. Feasibility implies that any approximate optimal solution of MDMCF with lane reversals on networkN is also a feasible approximate solution to the MDMCF on NΔa. Dynamic multicommodity flow problem on network N reduces to a static multicommodity flow problem on NΔa. By reducing the multicommodity to a single commodity and decomposing it into the si−ti path, an approximate dynamic multicommodity flow solution can be obtained optimally on auxiliary network NΔa. An approximate optimal solution on NΔa is a feasible solution on N. The unused capacities of the arcs by partial lane reversals are saved in Step 5. Thus, an approximate MDMCF solution with lane reversals on each arc of the given network N can be computed optimally.Corollary 3.
An FPTAS to the MDMCF problem with partial lane reversal can be computed in fully polynomial-time complexity.Proof.
The complexity of Algorithm4 is dominated by Steps 2 and 3. Step 3 is solved in Omn time. An approximate solution of a static multicommodity flow problem on the Δ-condensed auxiliary network is obtained by Fleischer [22] in Oɛ−2m2 time complexity in Step 2. The Δ-condensed auxiliary network contains n2/ɛ2 nodes and mn/ɛ2 arcs having polynomial-time complexity. Remaining steps can be solved in linear Om time. So, the problem can be computed in fully polynomial-time.
By scaling the capacities and transit times on arcs given in Figure1(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 5 by taking Δ=2.
The comparison of MDMCF before and after lane reversals is shown in Table2 and Figure 6.Figure 5
Δ-condensed time-expanded network of Figure 1(b) after scaling capacity and transit time.Table 2
Maximum multicommodity flow over time with lane reversals.
Time-expandedΔ-condensedPathFlow before LRFlow after LRFlow before LRFlow after LRs1−x−y−t16946s2−x−y−t24646s3−x−y−t30808Total1023820% increased130150LR = lane reversals.Figure 6
Comparison of flow before and after lane reversals.


## 5. EAMCT with Partial Lane Reversals

The dynamic network topologyN=V,A,K,u,τ,di,S+,S−,T with set of commodities K=1,2,…,k is considered. The earliest arrival multicommodity flow problem is a feasible multicommodity flow over time ξ with time horizon T of a maximum value of ξθ for each θ. This problem becomes EAMCT if it is a feasible multicommodity transshipment over time ξ with time horizon T such that ξ fulfills all supplies and demands di and value of ξθ is maximal at every point in time θ∈0,1,…,T−1.Kappmeier [11] proved that the EAMCT exists in the case of multiple sources and a single-sink. They observed that it is possible to reduce the problem of the multicommodity to the single-commodity in the single source-sink case. If all commodities commence in the same origin and have the same destination, then it can simply consider all commodities as one, compute the earliest arrival transshipment, and split the flow up into the commodities.Problem 3.
A networkN=V,A,K,u,τ,di,S+,t,T with multisource and a single sink is considered. The EAMCT problem with partial lane reversals sends the maximum flow from the sources si to the corresponding sink t in the unique source-sink pair si,t, for each commodity i=1,2,…,k and each time θ satisfying supplies and demands by saving the unused arc capacity.Lemma 2.
EAMCT with multiple sources and a single sink exists, and it can be computed with a running time that is polynomial ink and size of the earliest arrival transshipment in the same network wherein all commodities are considered as one.Proof.
Considering the flow over time networkN=V,A,K,u,τ,di,S+,t,T having multiple sources (k-sources) and a single-sink t with k-commodities. Defining new supplies and demands d′ by(15)dv′=∑i∈Kdvi,if sourcevin∪i∈KS+i,∑i∈Kdti,ifv=tis the sink,0,otherwise.
To compute an earliest arrival transshipment for the instance defined by the networkN, we first build the time-expanded network with supplies and demands and calculate minimum cost flow by considering transit time as the cost using the successive shortest path algorithm. This yields multicommodity flow over time corresponding to the static multicommodity flow.
We split the path for each commodityi∈K into commodity-dependent paths and select a source s∈∪i∈KS+i with supply dsi>0. An s−t path P with a flow value ξP>0 is chosen, and ξP′i=minξp,dsi is set as the flow value. Then, we update the residual demand dsi=dsi−ξP′i and flow value ξP=ξP−ξP′i and continue the process until there is no any source in S+i with positive supply according to Kappmeier [11].
The above construction creates a feasible solution of the EAMCT problem. We have∑P∈PstξP=∑i∈Kdvi by the definition of new demand for each source. ξP′i=minξp,dsi assures that no path capacity is violated as no more supply is sent exceeding the capacity. The flow value is reduced until arc capacities are zero, for any path P, and the constructed flow obeys the capacity constraint due to ∑i∈KξP′i=ξP. Hence, feasible flow satisfying all demands is ξPi for all i. The flow obtained is the earliest arrival flow for a single-commodity setting. Thus, a path decomposition of the earliest arrival transshipment is computed in network N. Selection of path flow for each commodity in polynomial-time in the size of the decomposition. Thus, running time is polynomial in k and size of the input.
Earliest arrival multicommodity flow problem with partial lane reversals on networkN=V,A,K,u,τ,di,S+,t,T is to find S+−t multicommodity flow over time that is maximum for all time steps θ∈0,1,…T−1 satisfying supply and demand of each commodity by reverting the arc partially. We present Algorithm 5 to calculate EAMCT with partial lane reversals.Algorithm 5: EAMCT algorithm with partial lane reversals.
Input: given a multicommodity flow network N=V,A,K,u,τ,di,S+,t,TOutput: the EAMCT with partial lane reversals(1) The given network is transformed to auxiliary network by adding two-way capacities inNa=V,Aa,K,ua,τa,di,∪i∈KS+i,t,T as uea=ue+uer, τea=τe,ife∈A,τer,otherwise.(2) Compute the EAMCT on the transformed networkNa by using algorithm by Kappmeier [11].(3) Decompose the flow along thesi−t paths and cycles and remove flows in cycles ∀i∈K.(4) Reverseerθ∈AT up to the capacity ψaθ−ue iff ψaθ>ue, ue replaced by 0 whenever eθ∉AT where ψe=∑i=1kψei and ue=∑i=1kuei.(5) For eacheθ∈AT, if erθ is reversed, scerθ=uea−ψeθ and sce=0. If neither e nor er is reversed, sceθ=ue−ψeθ>0, where sce is the saved capacity of e.(6) Transform the solution to the original network.Theorem 5.
Algorithm5 always computes an earliest arrival multicommodity flow with lane reversals on the multisource and single-sink network.Proof.
The theorem will be proved in two steps. In the first step, we show the feasibility of the algorithm, and in the second step, we show the optimality. Steps 1 and 4 of the algorithm are feasible according to Rebennack et al. [12]. The feasibility of Step 2 is verified by using the EAMCT algorithm (Kappmeier [11]). Step 3 of the algorithm is feasible being decomposition of flow along paths and cycles and assures that there is no cycle. The feasibility of Step 5 of the algorithm is due to Pyakurel et al. [19]. Thus, Algorithm 5 is feasible. To prove the optimality, we compute the EAMCT solution on the auxiliary network using the algorithm by Kappmeier [11]. From the feasibility of the algorithm, we conclude that every feasible EAMCT solution on the auxiliary network Na is equivalent to the EAMCT solution with lane reversals in the original network N. Thus, the solution obtained on the auxiliary network Na is the EAMCT with lane reversals on the original network N. Moreover, we can save the capacities of all unused arcs of the network by Step 5 of the algorithm.Example 5.
Considering a multisource and a single-sink network with demands for each commodity beingd1=20,d2=6,andd3=15, respectively. We compute maximum multicommodity flow over time on the auxiliary network as shown in Figure 7(a) with the flow, capacities, and transit times on the arcs within time horizon T=6 by searching the successive shortest path for each commodity on each time step θ. The repetition of path flows of each commodity is shown in a time-expanded graph. We get static flow ψ on the time-expanded graph which corresponds multicommodity flow over time ξ on the auxiliary network. Computation of the EAMCT after lane reversals is shown in Figure 7(b).
Table3 represents the value of EAMCT on each path with partial lane reversals.Figure 7
(a) Network having flow, capacity, and transit time on the arc after lane reversals. (b) Time-expanded network of (a).
(a)(b)Table 3
EAMCT with partial lane reversals.
PathψPRepetition forθMulticommodity flow over times1−x−t53, 4, 5, 6ξ1=20s3−x−t54, 5, 6ξ3=15s2−x−t35, 6ξ2=6Total41


## 6. Conclusions

One of the major problems in operational research is transshipping several kinds of commodities (goods) in underlying network topology, respecting capacity constraints on the arcs. Maximizing the sum of flow of all commodities in the specified period, it turns to maximum multicommodity flow over time. Multicommodity flow over time is computationally hard. A time-expanded network is a technique to solve flow over time problems, but it has pseudopolynomial-time complexity. By shrinking the size of the network, aΔ-condensed time-expanded network is introduced without changing flow values too much, and it provided an efficient approximation scheme. By flipping the orientation of lanes, the capacity of the lanes will be increased that amplifies the flow value and reduces the time horizon. Partial lane reversal strategy reverses only necessary arc capacities and saves the capacity of unused arcs that can be used in case of emergency.In this paper, we introduce a partial lane reversal strategy in static multicommodity flow, multicommodity flow over time, and earliest arrival multicommodity transshipment problems and provide algorithms to solve these problems. The first problem is solved in polynomial-time, the second problem is solved in pseudopolynomial-time as well as polynomial-time approximately, and the third problem is solved in pseudopolynomial-time complexity.



---

*Source: 2676378-2020-10-31.xml*