Search

Network associated with the set of elements and linearly ordered subset of elements, known as paths, satisfying the switching property is an abstract network. Due to the switching property, flows crossing at intersections are diverted to the non-crossing sides. Each element of an abstract network is equipped with two types of integral capacities: one is movement capacity which transships the flow from an element to its adjacent element and another is the storage capacity which holds the flow at the element. Due to insufficient movement capacity of intermediate elements, flow out from the source may not reach at the destination. If the flow out from the source is more than the minimum cut capacity, then the problem associated with the settlement of excess flow at appropriate intermediate elements is termed as network flow with intermediate storage. In this paper, we discuss the static and dynamic flow models with intermediate storage in an abstract network using temporal repetition of flow. We solve abstractmaximum dynamic flow and contraflow problems with intermediate storage.

Contraflow is one of the best and widely accepted techniques in evacuation planning problems, where the reversal of arcs is made to increase the amount and decrease the time of ow transmission. At the time of evacuation, if the flow value leaving the source node exceeds the bottleneck capacity of the network, then the storage of excess flow at comparatively safer intermediate nodes can be a milestone to save the life of evacuees. In this paper, we introduce the maximum dynamic contraflow problem in a general network and earliest arrival contraflow problem in two-terminal series-parallel network with asymmetric transit times on anti-parallel arcs. We present polynomial time solution strategies with orientation dependent transit times by allowing the storage of flow at intermediate nodes.

Multi-commodity flow problem appears when several distinct commodities are shipped from supply nodes to the demand nodes through a network without violating the capacity constraints. The quickest multi-commodity flow problem deals with the minimization of time satisfying given demand. Ingeneral, the quickest multi-commodity flow problems are computationally hard. The outbound lane capacities can be increased through reverting the orientation of lanes towards the demand nodes. We present two approximation algorithms by introducing partial contraow technique in the continuous-time quick estmulti-commodity ow problem: one polynomial-time with the help of length-bounded flow and another FPTAS by using _-condensed time-expanded graph. Both algorithms reverse only necessary arc capacities to get the optimal solutions and save unused arc capacities which may be used for other purposes.

Routing of more than one different commodity from specific origin nodes to the corresponding destination nodes through the arcs of an underlying network respecting the capacity constraints is one of the main problems in operational research. Among them, the quickest multi-commodity flow problem concerns with minimization of time taken to complete this process. The general multi-commodity and quickest multi-commodity flow problems are computationally hard. By flipping the orientation of lanes towards the demand nodes, the outbound lane capacities are increases. We introduce lane reversals in the quickest multi-commodity flow problem and present two approximation algorithms, one polynomial-time with the help of length-bounded flow and another FPTAS by using ∆-condensed time-expanded graph. Both algorithms prevent reversing arc capacities that are not required by the optimal flows that may be of interest for other purposes.

People have unpleasant experience of driving through congested road network of urban areas, where transit time is not constant but flow-dependent. Network flow over time with flow-dependent transit times is more realistic than flow over time with fixed transit time on arcs which is an active area of research from last two decades. In traffic assignment problem, transmission time of the vehicles directly depends on the number of vehicles entering on the road. So, general transit time function is non-decreasing, convex and left-continuous. In this paper we discuss how a general transit time function can be approximated by the step function. It relaxes the inflow-dependent transit times to a bow graph. We calculate maximum bow flow by using temporally repeated flow for the given time horizon. Our aim is to show how flow value in step function converges to the flow value of general transit time function by increasing number of points in the domain of the step function.

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.

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.

Network flow over time is an important area for the researcher relating to the traffic assignment problem. Transmission times of the vehicles directly depend on the number of vehicles entering the road. Flow over time with fixed transit times can be solved by using classical (static) flow algorithms in a corresponding time expanded network which is not exactly applicable for flow over time with inflow dependent transit times. In this paper we discuss the time expanded graph for inflow-dependent transit times and non-existence of earliest arrival flow on it. Flow over time with inflow-dependent transit times are turned to inflow-preserving flow by pushing the flow from slower arc to the fast flow carrying arc. We gave an example to show that time horizon of quickest flow in bow graph GB was strictly smaller than time horizon of any inflow-preserving flow over time in GB satisfying the same demand. The relaxation in the modified bow graph turns the problem into the linear programming problem.