Search

This paper deals with multi-depot bus scheduling (MDBS) problem. Depot workload balancing constraints are introduced. In this case, the problem can be stated as a two-objective multi-commodity flow...

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 maximum concurrent flow problem (MCFP) is a multicommodity flow problem in which every pair of vertices can send and receive flow concurrently. The objective of MCFP is to find a maximum throughput and the flow corresponding to the throughput under a set of capacity constraints. We present an improved version of the Flow Deviation Method for the maximum concurrent flow problem, which was first presented by Daniel Bienstock and Olga Raskina in 2000. The algorithm is based on linear programming formulation involving Frank-Wolfe procedure and minimum-cost flow problem. The correctness of the algorithm is strictly proved and the performance is evaluated under several networks of different sizes.

This paper presents a fast and efficient method for load flow analysis of radial distribution networks. Here, an adaptive algorithm is proposed to analyze the load flow problem of distribution systems. An adaptive algorithm is the combination of backward/forward (BW/FW) sweep and cuckoo search (CS) algorithms. In the proposed method, the optimum load flow analysis of the radial distribution system is attained, while optimizing the voltage and current computation of the BW/FW sweep algorithm. Now, by the CS, the output voltage of the BW/FW sweep algorithm is compared with the standard voltage and optimized. From the optimized voltage and current, load flow parameters like power loss and real and reactive power flow are assessed. The proposed method is implemented using the MATLAB platform and tested into the IEEE 33 bus radial distribution system. The effectiveness of the proposed technique is determined by comparing with the BW/FW algorithm and genetic algorithm-based BW/FW algorithm.

Flows over time problems consider finding optimal dynamic flows over a network where capacities and transit times on arcs are given. In this paper we study a multicommodity flow over time problem in which no storage of flow at nodes is allowed and solutions are restricted to loopless flow-paths. We propose an exact algorithm based on a column generation approach for a path-based linear programming model and present the results of a preliminary computational study.

Under consideration is the electric power flow optimization problem for an electric power system which typically arises in calculation of electrical power auctions in the “day-ahead” and balancing markets. It was established that the problem of finding a feasible flow in the balancing market is NP-hard in the strong sense even in case of one generator. The problem of finding an optimal flow in the day-ahead market is proved to be NP-hard even with one generator and without controlled cuts.

Multi-commodity flow problems (MCFs) can be found in many areas, such as transportation, communication, and logistics. Therefore, such problems have been studied by a multitude of researchers, and a variety of methods have been proposed for solving it. However, most researchers only discuss the properties of different models and algorithms without taking into account the impacts of actual implementation. In fact, the true performance of a method may differ greatly across various implementations. In this paper, several popular optimization solvers for implementations of column generation and Lagrangian relaxation are discussed. In order to test scalability and optimality, three groups of networks with different structures are used as case studies. Results show that column generation outperforms Lagrangian relaxation in most instances, but the latter is better suited to networks with a large number of commodities.

International audience; In this paper, we consider multicommodity flow problems, with unsplit-table flows and piecewise linear routing costs. We first focus on the case where the piecewise linear routing costs are convex. We show that this problem is N P-hard for the general case, but polynomially solvable when there is only one commodity. We then propose a strengthened mixed-integer programming formulation for the problem. We show that the linear relaxation of this formulation always gives the optimal solution of the problem for the single commodity case. We present a wide array of computational experiments, showing this formulation also produces very tight linear programming bounds for the multi-commodity case. Finally, we also adapt our formulation for the non-convex case. Our experimental results imply that the linear programming bounds for this case, are only slightly than the ones of state-of-the-art models for the splittable flow version of the problem.

We consider the piecewise linear multicommodity network flow problem with the addition of a constraint specifying that the total flow on each arc must be an integer. This problem has applications in transportation and logistics, where total flows might represent vehicles or containers filled with different products. We introduce formulations that exploit this integrality constraint by adapting to our problem a technique known as discretization that has been used to derive mixed-integer programming models for several combinatorial optimization problems. We enhance the discretized models either by adding valid inequalities derived from cut-set inequalities or by using flow disaggregation techniques. Since the size of the formulations derived from discretization and flow disaggregation rapidly increases with problem dimensions, we develop an efficient and effective Lagrangian relaxation method to compute lower and upper bounds. We perform computational results on a large set of randomly generated instances that allow us to compare the relative efficiency of the different modeling alternatives (flow disaggregation plus addition of cut-set inequalities with or without discretization), when used within the Lagrangian relaxation approach.

Flow variations over time generalize standard network flows by introducing an element of time. In contrast to the classical case of static flows, a flow over time in such a network specifies a flow rate entering an arc for each point in time. In this setting, the capacity of an arc limits the rate of flow into the arc at each point in time. Traditionally, flows over time are computed in time-expanded networks that contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic toolbox developed for static network flows, its drawback is the enormous size of the time-expanded network. In this paper, we extend the results about the minimum flow problem to network flows (with n nodes and m arcs) in which the time-varying lower bounds can involve both the source and the sink nodes (as in Fathabadi et al.) and also one additional node other than the source and the sink nodes. It is shown that this problem for the set \(\{0,1,\ldots ,T\}\) of time points can be solved by at most n minimum flow computations, by suitably extending the dynamic minimum flow algorithm and reoptimization techniques. The running time of the presented algorithm is \(O(n^2m)\).

A new version of fractional minimal cost flow problem with fuzzy arc costs is focused in this study. The fuzzy arc costs are applied as in most of the real-world applications, the parameters have high degree of uncertainty. The goal of this problem is to determine the minimum fuzzy fractional cost of sending and passing a specified flow value into and from a network. A decomposition-based solution methodology is introduced to tackle this problem. The methodology applies Zadeh’s extension principle to decompose the problem to two upper bound and lower bound problems. These problems are capable of being solved for different $$\alpha$$ -cut values to construct the fuzzy fractional minimal cost flow value as the objective function value. The efficiency of the proposed solution methodology is studied over some well-known examples of fractional minimal cost flow problem. The obtained results show the superiority of the proposed approach comparing to the methods of the literature.

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.

Designing and optimizing different flows in networks is a relevant problem in many contexts. While a number of methods have been proposed in the physics and optimal transport literature for the one-commodity case, we lack similar results for the multi-commodity scenario. In this paper we present a model based on optimal transport theory for finding optimal multi-commodity flow configurations on networks. This model introduces a dynamics that regulates the edge conductivities to achieve, at infinite times, a minimum of a Lyapunov functional given by the sum of a convex transport cost and a concave infrastructure cost. We show that the long time asymptotics of this dynamics are the solutions of a standard constrained optimization problem that generalizes the one-commodity framework. Our results provide new insights into the nature and properties of optimal network topologies. In particular, they show that loops can arise as a consequence of distinguishing different flow types, complementing previous results where loops, in the one-commodity case, were obtained as a consequence of imposing dynamical rules to the sources and sinks or when enforcing robustness to damage. Finally, we provide an efficient implementation of our model which convergences faster than standard optimization methods based on gradient descent., Comment: 13 pages, 7 figures

In this paper, we present a new multi-commodity network flow-based formulation for the multi-period cell formation problem. The objective of the model is to minimize the total costs of acquisition, disposal, and relocation of machines, manufacturing, and inter-cell/intra-cell material handling. The main contribution of this paper comes from the fact that we structure the underlying problem as a multi-period multi-commodity network flow problem with general integer variables for machine acquisition, disposal, and relocation connecting one period to the next. This formulation is more efficient than the formulations we have encountered in the literature. Another contribution of this paper is that the flow variables representing the flow of parts through the system is path based; as a result, this approach makes it very easy to model alternate process routings. This paper illustrates the formulation by the use of two examples taken from the literature and presents computational results for other representative problems.

A Multi-Agent network flow problem is addressed in this paper where a set of transportation-agents can control the capacities of a set of routes. Each agent incurs a cost proportional to the chosen capacity. A third-party agent, a customer, is interesting in maximizing the product flow transshipped from a source to a sink node through the network. He offers a reward proportional to the flow value, which is shared equally among the transportation-agents. We address the problem of finding a stable strategy (i.e., a Nash Equilibrium) which maximizes the network flow. We show that this problem, already proved to be NP-hard, can be modeled and solved using mixed integer linear programming (MILP).

In this paper, we give an algorithm to optimize the number of elementary k-flows obtained by decomposing a given k-route flow. It is known that a k-route flow can be decomposed into a linear combination of elementary k-flows, and there are many algorithms proposed for that decomposition. However, the number of elementary k-flows from those algorithms can be as large as O ( | E | ) when | E | is the number of edges in our network. As we have to reroute our flow for each elementary k-flow, it is more desirable to have a smaller number of the elementary flows in the combination. Let v be a maximum k-route flow value of our network, and h be a real number such that 0 h 1 . Denote τ h be the maximum value such that the flow value of the network is h ⋅ v , when edges with flow value less than τ h are removed. We propose an algorithm to decompose a ( v − k ⋅ τ h ⋅ O P T ) / v -fraction of a k-route flow to at most 1 1 − h ⋅ O P T elementary k-flows, when OPT is an optimal number of elementary k-flows required.

We address the Multi Layer Hierarchical Ring Network Design Problem. The aim of this problem is to connect nodes that are assigned to different layers using a hierarchy of rings of bounded length. We present a multi-commodity flow based mixed integer linear programming formulation and experimentally evaluate it on various graphs. Instances up to 76 nodes and 281 edges could be solved to optimality.

Processing networks (cf. Koene in Minimal cost flow in processing networks: a primal approach, 1982) and manufacturing networks (cf. Fang and Qi in Optim Methods Softw 18:143---165, 2003) are well-studied extensions of traditional network flow problems that allow to model the decomposition or distillation of products in a manufacturing process. In these models, so called flow ratios $$\alpha _e \in [0,1]$$źeź[0,1] are assigned to all outgoing edges of special processing nodes. For each such special node, these flow ratios, which are required to sum up to one, determine the fraction of the total outgoing flow that flows through the respective edges. In this paper, we generalize processing networks to the case that these flow ratios only impose an upper bound on the respective fractions and, in particular, may sum up to more than one at each node. We show that a flow decomposition similar to the one for traditional network flows is possible and can be computed in strongly polynomial time. Moreover, we show that there exists a fully polynomial-time approximation scheme (FPTAS) for the maximum flow problem in these generalized processing networks if the underlying graph is acyclic and we provide two exact algorithms with strongly polynomial running-time for the problem on series---parallel graphs. Finally, we study the case of integral flows and show that the problem becomes $${\mathcal {NP}}$$NP-hard to solve and approximate in this case.

The general problem of estimating origin-destination matrices in congested traffic networks is formulated as a mathematical program with equilibrium constraints. In this paper a path flow entropy model based on an equilibrium assignment approach is presented. It is assumed the flows on links are disaggregated due to some external reasons. Using the L-shaped algorithm the problem is transformed into a problem with less constraints. Then applying the lagrangian dual function the original problem is reduced to a nonlinear convex problem with only one linear constraint.

This paper deals with the user equilibrium problem (flow assignment with equal journey time by alternative routes) and system optimum (flow assignment with minimal average journey time) in a network consisting of parallel routes with a single origin-destination pair. The travel time is simulated by arbitrary smooth nondecreasing functions. We prove that the equilibrium and optimal assignment problems for such a network can be reduced to the fixed point problem expressed explicitly. A simple iterative method of finding equilibriumand optimal flow assignment is developed. The method is proved to converge geometrically; under some fairly natural conditions the method is proved to converge quadratically.

The computational challenge offered by many traditional network flow models is modest, and large-scale instances can be solved fast. When the composition of the flow is part of the model, the required computation time may increase substantially. This is in particular true for the pooling problem, where the relative content of certain flow components is restricted. Flow entering the network at the source nodes has a given composition, whereas the composition in other nodes is determined by the composition of entering flows. At the network terminals, the flow composition is subject to restrictions referred to as quality constraints. The pooling problem is known to be strongly NP-hard, even if the network has only one pool, but is solvable in polynomial time if also the number of terminals or the number of quality parameters (flow components) is bounded. The problem is also NP-hard if there are only two sources and terminals and only one quality parameter. Two related questions have been left open in the literature so far. For the single-pool version, it has not been known whether the problem is solvable in polynomial time if the number of sources is bounded. For the version with a single quality parameter and two sources and terminals, the question whether a pseudo-polynomial algorithm exists has been open. This paper gives positive answers to both questions.

We develop a qualitative analysis theory for the convex-cost dynamic multicommodity production planning problem, which can be used, without performing any computational work, to provide invaluable insight to managers when faced with the task of deciding how to respond to changes in problem environment. We first formulate the problem as a multicommodity flow problem with parameters associated with each arc–commodity pair. We then reduce the problem to an equivalent single-commodity flow problem and develop a complete characterization of conformality among production, sales, and inventory activities in various instances of the problem. By combining the conformality characterizations with the monotonicity theory of Granot and Veinott [Granot F, Veinott AF Jr (1985) Substitutes, complements and ripples in network flow. Math. Oper. Res. 10:471–497] for single-commodity problems, we study the effects of changes in problem environment on optimal production, sales, and inventory schedules in the multicommodity problem. Numerous applications are presented and analyzed.

The Minimum Cost-Time Network Flow (MCTNF) problem deals with shipping the available supply through the directed network to satisfy demand at minimal total cost and minimal total time. Shipping cost is dependent on the value of flow on the arcs; however shipping time is a fixed time of using an arc to send flow. In this paper, a new Bi-Objective Minimum Cost-Time Flow (BOMCTF) problem is formulated. The first and second objective functions consider the total shipping cost and the total shipping fixed time, respectively. We utilize the weighted sum scalarization technique to convert the proposed model to a well-known fixed charge minimum cost flow problem with single objective function. This problem is a parametric mixed integer programming which can be solved by the existence methods. A numerical example is taken to illustrate the proposed approach.

This study uses a minimum cost flow method to solve a dispatch problem in order to minimize the consumption of coal in the dispatching of a thermal power system. Low-carbon generation dispatching is also considered here since the scheduling results are consistent with energy-saving generation dispatch. Additionally, this study employs minimum coal consumption as an objective function in considering the output constraints, load balance constraints, line loss, ramp rate limits, spinning reverse needs, prohibited operating zone requirements, security constraints, and other common constraints. The minimum cost flow problem, considering the loss of network flow, is known as a generalized network flow problem, which can be expressed as a quadratic programming problem in mathematics. Accordingly, the objective function was solved by LINGO11, which was used to calculate a network in a single time; a continuous period dispatch plan was obtained by accumulating each period network flow together. This analysis proves it feasible to solve a minimal cost flow problem with LINGO11. Theoretical analysis and numerical results prove the correctness and effectiveness of the proposed method.

We study the approximability of the All-or-Nothing multicommodity flow problem in directed graphs with symmetric demand pairs (SymANF). The input consists of a directed graph $$G = (V, E)$$G=(V,E) and a collection of (unordered) pairs of nodes $$\mathcal {M}= \left\{ s_1t_1, s_2t_2, \ldots , s_kt_k\right\} $$M=s1t1,s2t2,?,sktk. A subset $$\mathcal {M}'$$M? of the pairs is routable if there is a feasible multicommodity flow in $$G$$G such that, for each pair $$s_it_i \in \mathcal {M}'$$siti?M?, the amount of flow from $$s_i$$si to $$t_i$$ti is at least one and the amount of flow from $$t_i$$ti to $$s_i$$si is at least one. The goal is to find a maximum cardinality subset of the given pairs that can be routed. Our main result is a poly-logarithmic approximation with constant congestion for SymANF. We obtain this result by extending the well-linked decomposition framework of Chekuri et al. (2005) to the directed graph setting with symmetric demand pairs. We point out the importance of studying routing problems in this setting and the relevance of our result to future work.

It was about 40 years ago that the ARPANET had surpassed 40 nodes and was rapidly growing at the rate of one node per month. The first government and commercial P/S networks were emerging. Designing an efficient topology and flow assignment strategy that could meet the requirements at lowest costs was essential in order to outperform the competition represented by circuit-switched or private-line networks. The challenge was to solve a combined flow and capacity assignment problem. Researchers at UCLA, under Len Kleinrock’s leadership and DARPA support, developed a method based on multicommodity flow and non-linear programming principles called the Flow Deviation (FD) algorithm. The key underlying technique was to “deviate flows” on incrementally improving paths until the optimum was reached. In the early days, the FD algorithm was used to design and “upgrade” the growing ARPANET topology. After the ARPANET topology became stable, the FD algorithm took on a life of its own as an intuitive, efficient method to solve a variety of network flow problems in different domains, from ARPANET packets to WDM wavelengths, urban traffic cars and SDN tunnels, as reflected in the over 500 citations. This paper reviews the key concepts and features of the FD algorithm as published in 1973, traces the various problems and scenarios to which it has been applied (most recently, vehicular traffic management) and discusses the possible use of FD in today’s SDN tunnel allocation.

The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases such as the uncapacitated lot-sizing problem and many of its variants. We study the MCCNFP over a grid network with a general nonnegative separable concave cost function. We show that this problem is polynomially solvable when all sources are in the first echelon and all sinks are in two echelons, and when there is a single source but many sinks in multiple echelons. The polynomiality argument relies on a combination of a particular dynamic programming formulation and an investigation of the extreme points of the underlying flow polyhedron. We derive an analytical formula for the inflow into any node in an extreme point solution, which generalizes a result of Zangwill (Manag Sci 14(7):429---450, 1968) for the multi-echelon lot-sizing problem.

In the planning and operation of distribution network, flow calculation and optimal flow is the hot issue for many experts and scholars to study. In network reconfiguration, service restoration and capacitor configuration, it needs hundreds even thousands times of power flow calculation. So it is very important to propose a suitable optimization algorithm. Based on the three-phase model we proposed hybrid particle swarm algorithm to calculate the three-phase power flow. The method uses the superposition principle. The distribution network is divided into two network models, one is the pure radial network without cyclic structure, and another is the pure cyclic network without radiation structure. We do iterative calculation respectively using hybrid particle algorithm, getting the calculation results. The hybrid algorithm is a new reference for the future optimization of power flow calculation in this paper.

The present paper discusses enhanced flow in a capacitated indefinite quadratic transportation problem. Sometimes, situations arise where either reserve stocks have to be kept at the supply points say, for emergencies, or there may be extra demand in the markets. In such situations, the total flow needs to be controlled or enhanced. In this paper, a special class of transportation problems is studied, where the total transportation flow is enhanced to a known specified level. A related indefinite quadratic transportation problem is formulated, and it is shown that to each basic feasible solution called corner feasible solution to related transportation problem, there is a corresponding feasible solution to this enhanced flow problem. The optimal solution to enhanced flow problem may be obtained from the optimal solution to the related transportation problem. An algorithm is presented to solve a capacitated indefinite quadratic transportation problem with enhanced flow. Numerical illustrations are also included in support of the theory. Computational software GAMS is also used.

The article discuses a number of fundamental results related to determining the maximum output flow in a network after edge failures. On the basis of four theorems, we propose very efficient augmentation algorithms for restoring the maximum possible output flow in a repairable flow network, after an edge failure. In many cases, the running time of the proposed algorithm is independent of the size of the network or varies linearly with the size of the network. The high computational speed of the proposed algorithms makes them suitable for optimising the performance of repairable flow networks in real time and for decongesting overloaded branches in networks. We show that the correct algorithm for maximising the flow in a static flow network, with edges fully saturated with flow, is a special case of the proposed reoptimisation algorithm, after transforming the network into a network with balanced nodes. An efficient two-stage augmentation algorithm has also been proposed for maximising the output flow in a network with empty edges. The algorithm is faster than the classical flow augmentation algorithms. The article also presents a study on the link between performance, topology and size of repairable flow networks by using a specially developed software tool. The topology of repairable flow networks has a significant impact on their performance. Two networks built with identical type and number of components can have very different performance levels because of slight differences in their topology.

In this paper, a new design optimization method-cross entropy methods for passenger flow routing in passenger hubs is employed, in order to develop rational and efficient passenger flow routing program, which will help improving the passenger flow organization. According to the description and characteristics of the problem, we transform the problem into a combinatorial optimization problem, so that it is convenient to explore the best solution. The numerical example declares that the method given above can obtain the optimal solution under the condition of fixed demand. Results show that the cross entropy method is effective, and can be well applied in passenger flow routing design problem. Systematic studying the passenger terminal passenger flow routing design optimization techniques and methods and developing rational and efficient passenger flow routing program will help improving the organization of passenger flow. According to the description of the problem and the characteristics of itself, the paper transforms the problem into a combinatorial optimization problem, so that it is convenient to explore the best solution. The paper also employs the cross entropy method to solve the problems. Numerical example declares that the method given above can obtain the optimal solution under the condition of fixed demand. Results show that the cross entropy method is effective, and this method can be well applied in passenger flow routing design problem.

This paper describes an exact algorithm to solve a nonlinear mixed-integer programming model due to capacity expansion and flow assignment in multicommodity networks. The model combines continuous multicommodity flow variables associated with nonlinear congestion costs and discrete decision variables associated with the arc expansion costs. After establishing precise correspondences between a mixed-integer model and a continuous but nonconvex model, an implicit enumeration approach is derived based on the convexification of the continuous objective function. Numerical experiments on medium size instances considering one level of expansion are presented. The results reported on the performance of the proposed algorithm show that the approach is efficient, as commercial solvers were not able to tackle the instances considered.

We consider the dynamic version of the maximum flow network interdiction problem; that is, we assume a positive number is assigned to each arc which indicates the traversal time of the flow through that arc. We also assume that an intruder uses a single resource with limited budget to interrupt the flow of a single commodity through the network within a given time limit of T. A new formulation based on the concept of Temporally Repeated Flow (TRF) is presented. The problem is then solved using Benders' decomposition. Another solution method, based on the most vital arcs in a network is also discussed. Finally, some computational results are reported.

In the generalized max flow problem, the aim is to find a maximum flow in a generalized network, i.e., a network with multipliers on the arcs that specify which portion of the flow entering an arc at its tail node reaches its head node. We consider this problem for the class of series-parallel graphs. First, we study the continuous case of the problem and prove that it can be solved using a greedy approach. Based on this result, we present a combinatorial algorithm that runs in O(m*m) time and a dynamic programming algorithm with running time O(m*log(m)) that only computes the maximum flow value but not the flow itself. For the integral version of the problem, which is known to be NP-complete, we present a pseudo-polynomial algorithm.

The proportional network flow problem is a generalization of the equal flow problem on a generalized network in which the flow on arcs in given sets must all be proportional. This problem appears in several natural contexts, including processing networks and manufacturing networks. This paper describes a transformation on the underlying network that reduces the problem to the equal flow problem; this transformation is used to show that algorithms that solve the equal flow problem can be directly applied to the proportional network flow problem as well, with no increase in asymptotic running time. Additionally, computational results are presented for the proportional network flow problem demonstrating equivalent performance to the same algorithm for the equal flow problem.

The paper focuses on constructing and investigation of cost-effective difference schemes for the numerical solution of the two-dimensional three-phase non-isothermal flow problem without capillary and gravitational forces. In this paper, the finite difference method is used to solve the problem numerically. The method of energy inequalities is applied to examine the stability of the finite difference scheme with respect to the initial data and the right-hand sides of the equations. Three cost-effective difference schemes are constructed on the base of the studied scheme. The efficiency of the proposed algorithms is analyzed on the basis of comparing the average time spent on the numerical implementation of one time layer.

The present work studies a maximum multicom-modity flow problem with local constrains, which not only enrich the content of the multicommodity flow problem, but also can be used to operate optimization decisions of some practical problems, such as the logistics distribution problems stemming out of transportations. The major contributions are as follows: (A) Develop a multicommodity flow problem and study the existence of its solutions. (B) Design an approximation algorithm to solve the defined problem. (C) Propose and prove the approximation measures as well as the time complexity of the designed algorithm.

Many transportation, communications, and logistics problems can be formulated as large multi-commodity flow problems, which are often solved using the traditional column generation method. During the application of the column generation, one needs to find initial solutions, so-called feasible columns in a first step. In order to determine these feasible columns and also solve dependent price problems within an acceptable time, this paper proposes several novel methods: Two methods by solving the global problem and two methods by finding the shortest and widest paths are proposed to compute the initial columns. Furthermore, we propose two methods by finding the shortest paths with commodities and sources (SPC and SPS) for solving price problems. Several well-known network instances are used as case studies in our evaluation to test the efficiency of each method. It is shown that the widest-path method is the best for finding initial columns. For solving the price problems, the preference of the two path-finding methods depend on the network structure.

Network reconfiguration problem has been studied in the literature for more than 20 years. In this study, we extend the problem with one of the today's challenges: integration of renewables at the distribution system level. First, the effect of network reconfiguration on the maximum service capability is examined in a case study. Next, an Optimal Power Flow problem in the form of Semi-Definite Programming is solved and we observe that, in contrast to general expectation, minimization of power loss and minimization of operation cost actually conflict with each other in network reconfiguration problem when renewables are integrated into the radial system. Multi-objective optimization approach is adopted to show all pareto optimal solutions of the problem. Necessity of uni-directional flow in distribution system is studied and a new policy for radial network is proposed to reduce wasted energy.

There are many multi-commodity maximisation problems present in the literature. The problem addressed in this article deals with the number of sources producing a mixture of multiple commodities with different proportions. There are also separators which separate the commodity flows. However, component failures often occur after the separation of commodities, resulting in a limited flow capacity to carry these commodities. As a result, production from certain number of sources has to be reduced to adjust for the capacity reduction caused by component failures. The objective is to maximise the flow with respect to one particular commodity, while satisfying the capacity constraints and the flow conservation law. This problem can be solved as a linear programming problem. In this article, a new algorithm is proposed for a three-commodity problem, which performs much faster than the simplex method. The three-commodity problem has a close relation to oil and gas production, where three different commodities, n...

We investigate the integral multicommodity flow problem in symmetric directed graphs. In order to complete this study on symmetry, we also investigate the symmetric multicommodity flow problem, where requests are symmetric (a symmetric request is actually a pair of requests with the same required capacity and reversed endpoints).It is known that by using a specificity of symmetric digraphs, it is possible to find 2-commodity flows in polynomial time when one of the requests is of value 1. We show that this specificity does not extend to greater flow values, and prove that the 2-commodity flow problem is NP-complete.When requests are symmetric, we propose a polynomial-time algorithm that finds symmetric 2-commodity flows by using 5 simple flow computations, and prove that the symmetric 3-commodity flow problem is NP-complete.

Minimum Cost Maximum Flow Problem (MCMFP) is to find the maximum flow with minimal total cost, i.e., the minimum cost maximum flow, in transportation network. In this paper, MCMFP is formulated using a bi-level programming model. As a solution method of the model, an algorithm named MCMF-A is proposed. The basic idea of the MCMF-A algorithm can be described as follows: first find a maximum flow without opposite flow in transportation network, next construct its residual network with regard to the maximum flow, then find a negative-cost cycle in the residual network by calling well-known Floyd Algorithm; if Floyd Algorithm finds that there is no negative-cost cycle in the residual network, then the maximum flow is minimum cost maximum flow, else adjust the maximum flow via the negative-cost cycle to get a new maximum flow with no opposite flow and less total transportation cost. The theory, on which the MCMF-A algorithm is based, is presented. The MCMF-A algorithm can find the optimal solution to MCMFP, and has good performance in the sense of being implemented on computer, computational time and required memory for computation. Numerical experiments demonstrate that the MCMF-A algorithm is an efficient and robust method to solve MCMFP, which can serve as an effective tool to solve other related optimization problems.

The pooling problem is an extension of the minimum cost network flow problem where the composition of the flow depends on the sources from which it originates. At each source, the composition is known. In all other nodes, the proportion of any component is given as a weighted average of its proportions in entering flow streams. The weights in this average are simply the arc flow. At the terminals of the network, there are bounds on the relative content of the various components. Such problems have strong relevance in e.g. planning models for oil refining, and in gas transportation models with quality constraints at the reception side. Although the pooling problem has bilinear constraints, much progress in solving a class of instances to global optimality has recently been made. Most of the approaches are however restricted to networks where all directed paths have length at most three, which means that there is no connection between pools. In this work, we generalize one of the most successful formulations of the pooling problem, and propose a multi-commodity flow formulation that makes no assumptions on the network topology. We prove that our formulation has stronger linear relaxation than previously suggested formulations, and demonstrate experimentally that it enables faster computation of the global optimum.

The minimal-cost network flow problem with fixed lower and upper bounds on arc flows has been well studied. This paper investigates an important extension, in which some or all arcs have variable lower bounds. In particular, an arc with a variable lower bound is allowed to be either closed (i.e., then having zero flow) or open (i.e., then having flow between the given positive lower bound and an upper bound). This distinctive feature makes the new problem NP-hard, although its formulation becomes more broadly applicable, since there are many cases where a flow distribution channel may be closed if the flow on the arc is not enough to justify its operation. This paper formulates the new model, referred to as MCNF-VLB, as a mixed integer linear programming, and shows its NP-hard complexity. Furthermore, a numerical example is used to illustrate the formulation and its applicability. This paper also shows a comprehensive computational testing on using CPLEX to solve the MCNF-VLB instances of up to medium-to-large size.

This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.

This study is part of a series of research projects on a distribution system we developed to deal with cases in a state-owned company. It concerns the design of the Public Service Obligation State-owned Company (PSO-SOC) distribution system. The intrinsic features of PSO-SOC are distributing strategic commodities and having subsidies within the cost function. Hence their distribution flow has to be secured under consideration of moving the commodities within road networks that have traffic flow dependency. This paper focuses on the solution of the proposed model which represents traffic flow dependency within a freight distribution network. The mathematical formulation takes the form of a Minimum Cost Multicommodity Flow (MCMF) problem. Traffic flow dependency is incorporated into the model by introducing a coefficient of speed, which is derived from the traffic assignment of ordinary traffic associated with the transportation of the type of freight under consideration The solution of the proposed model is formulated by Network Representation (NR), in which all of the components of the mathematical model are represented in the form of dummy links and nodes added to the original (physical) network. It is to be noted then, that the traffic flow on each road or link is represented by a link performance function (LPF), depicting traffic flow dependent travel time and consequent cost. The MCMF problem of NR is further solved by a Primal–Dual Algorithm. Finally, an illustrative example is exercised to show how the proposed step-wise solution works.

A problem and a new algorithm are given for the linear fractional minimal cost flow problem on network. Using a new check number and combining the characteristic of network to extend the traditional theories of minimum cost flow problem, discussed the relation between it and its dual problem. Optimality conditions are derived and a Network Simplex Algorithm is proposed that leads to optimal solution assuming certain properties. Finally, an numerical example test is also developed.

We consider a multicommodity flow problem on a complete graph whose edges have random, independent, and identically distributed capacities. We show that, as the number of nodes tends to infinity, the maximum utility, given by the average of a concave function of each commodity flow, has an almost-sure limit. Furthermore, the asymptotically optimal flow uses only direct and two-hop paths, and can be obtained in a distributed manner.

An in-house simulation program was developed that can be utilized to predict flow characteristics such as pressure and velocities in any flow network system comprising multiple flow components, i.e., pipe, pump, heat exchanger, valves, etc. Although the code is intended for applications to network flow systems in a vehicle, it is written in a generalized manner to handle any possible network configuration of flow components. Therefore, it can easily function in various industrial applications. The network system where the flow is assumed to be one-dimensional is mathematically formulated by applying two conservation rules, mass and energy, to each flow component. These rules produce a set of non-linear equations. These non-linear equations are solved iteratively by adopting the Newton-Raphson scheme. This program has been tested in many different cases to demonstrate its validity and applicability. In this paper, two examples are introduced to show how the program can be used to find solutions in real engineering problems. Throughout the study, it was found that the code can most efficiently be used to verify a proposed design concept in an early design stage of the vehicle development cycle. The thermal analysis portion of the program will be dealt with in Part II of the paper.