Maximum flow problem on dynamic generative network flows with time-varying bounds

This paper considers a new class of network flows, called dynamic generative network flows in which, the flow commodity is dynamically generated at a source node and dynamically consumed at a sink node and the arc-flow bounds are time dependent. Then the maximum dynamic flow problem in such networks for a pre-specified time horizon T is defined and mathematically formulated in both arc flow and path flow presentations. By exploiting the special structure of the problem, an efficient algorithm is developed to solve the general form of the dynamic problem as a minimum cost static flow problem.     

A parametric algorithm for convex cost network flow and related problems

The convex cost network flow problem is to determine the minimum cost flow in a network when cost of flow over each arc is given by a piecewise linear convex function. In this paper, we develop a parametric algorithm for the convex cost network flow problem. We define the concept of optimum basis structure for the convex cost network flow problem. The optimum basis structure is then used to parametrize v, the flow to be transsshipped from source to sink. The resulting algorithm successively augments the flow on the shortest paths from source to sink which are implicitly enumerated by the algorithm. The algorithm is shown to be polynomially bounded. Computational results are presented to demonstrate the efficiency of the algorithm in solving large size problems. We also show how this algorithm can be used to (i) obtain the project cost curve of a CPM network with convex time-cost tradeoff functions; (ii) determine maximum flow in a network with concave gain functions; (iii) determine optimum capacity expansion of a network having convex arc capacity expansion costs.     

New formulation and relaxation to solve a concave-cost network flow problem

In this paper we study a minimum cost, multicommodity network flow problem in which the total cost is piecewise linear, concave of the total flow along the arcs. Specifically, the problem can be defined as follows. Given a directed network, a set of pairs of communicating nodes and a set of available capacity ranges and their corresponding variable and fixed cost components for each arc, the problem is to select for each arc a range and identify a path for each commodity between its source and destination nodes so as to minimize the total costs. We also extend the problem to the case of piecewise nonlinear, concave cost function. New mathematical programming formulations of the problems are presented. Efficient solution procedures based on Lagrangean relaxations of the problems are developed. Extensive computational results across a variety of networks are reported. These results indicate that the solution procedures are effective for a wide range of traffic loads and different cost structures. They also show that this work represents an improvement over previous work made by other authors. This improvement is the result of the introduction of the new formulations of the problems and their relaxations.     

Determining the Optimal Flows in Zero-Time Dynamic Networks

Here we are dealing with minimum cost flow problem on dynamic network flows with zero transit times and a new arc capacity, horizon capacity, which denotes an upper bound on the total flow traversing through on an arc during a pre-specified time horizon T. We develop a simple approach based on mathematical modelling attributes to solve the min-cost dynamic network flow problem where arc capacities and costs are time varying, and horizon capacities are considered. The basis of the method is simple and relies on the appropriate defining of polyhedrons, and in contrast to the other usual algorithms that use the notion of time expanded network, this method runs directly on the original network.     

Lexicographic optimisation in generalised network flow problems

In this paper the lexicographic optimisation of the multiobjective generalised network flow problem is considered. Optimality conditions are proved on the basis of the equivalence of this problem and a weighted generalised network flow problem. These conditions are used to develop a network-based algorithm which properly modifies primal-dual algorithms for minimum cost generalised network flow problems. Computational results indicate that this algorithm is faster than general-purpose algorithms for linear lexicographic optimisation. Besides, this model is used for approaching a water resource system design problem.     

The hub covering flow problem

The hub covering flow problem (HCFP) seeks to find the minimal cost hub-and-spoke network by optimally locating hub nodes and assigning non-hub nodes to the hub nodes subject to a coverage constraint. The cost of establishing such a hub network is based on a fixed cost of opening hubs and the cost of transporting demand flow through the network. We also present an extension called the multi-aircraft HCFP. The results from computational experiments are presented and discussed.     

Minimum concave-cost network flow problems: Applications,complexity, and algorithms

We discuss a wide range of results for minimum concave-cost network flow problems, including related applications, complexity issues, and solution techniques. Applications from production and inventory planning, and transportation and communication network design are discussed. New complexity results are proved which show that this problem is NP-hard for cases with cost functions other than fixed charge. An overview of solution techniques for this problem is presented, with some new results given regarding the implementation of a particular branch-and-bound approach.     

Modeling centrality measures in social network analysis using bi-criteria network flow optimization problems

Centrality measures play an important role in the field of network analysis. In the particular case of social networks, the flow represents the way in which information passes through the network nodes. Freeman et al. (1991) were the first authors to relate centrality measures to network flow optimization problems in terms of betweenness, closeness, and the influence of one node over another one. Such measures are single dimensional and, in general, they amalgamate several heterogeneous dimensions into a single one, which is not suitable for dealing with most real-world problems. In this paper we extend the betweenness centrality measure (or concept) to take into account explicitly several dimensions (criteria). A new closeness centrality measure is defined to deal not only with the maximum flow between every ordered pair of nodes, but also with the cost associated with communications. We shall show how the classical measures can be enhanced when the problem is modeled as a bi-criteria network flow optimization problem.     

Optimizing cost flows by edge cost and capacity upgrade

We examine a network upgrade problem for cost flows. A budget can be distributed among the arcs of the network. An investment on each single arc can be used either to decrease the arc flow cost, or to increase the arc capacity, or both. The goal is to maximize the flow through the network while not exceeding bounds on the budget and on the total flow cost.

The problems are NP-hard even on series-parallel graphs. We provide an approximation algorithm on series-parallel graphs which, for arbitrary δ,>0, produces a solution which exceeds the bounds on the budget and the flow cost by factors of at most 1+δ and 1+, respectively, while the amount of flow is at least that of an optimum solution. The running time of the algorithm is polynomial in the input size and 1/(δ). In addition we give an approximation algorithm on general graphs applicable to problem instances with small arc capacities.     

The hub location and network design problem with fixed and variable arc costs: formulation and dual-based solution heuristic

Many air, less-than-truck load and intermodal transportation and telecommunication networks incorporate hubs in an effort to reduce total cost. These hubs function as make bulk/break bulk or consolidation/deconsolidation centres. In this paper, a new hub location and network design formulation is presented that considers the fixed costs of establishing the hubs and the arcs in the network, and the variable costs associated with the demands on the arcs. The problem is formulated as a mixed integer programming problem embedding a multi-commodity flow model. The formulation can be transformed into some previously modelled hub network design problems. We develop a dual-based heuristic that exploits the multi-commodity flow problem structure embedded in the formulation. The test results indicate that the heuristic is an effective way to solve this computationally complex problem.     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

Network design and flow problems with cross-arc costs

Network design and flow problems appear in a wide variety of transportation applications. We consider a new variation to this important class of problems, in which the cost associated with an arc depends not only on the amount of flow moving across that arc, but on the amount of flow on other arcs in the network as well. We formulate an integer program to address this problem, discuss a real-world application in which cross-arc costs are found, and conduct computational experiments on a broad class of problems to analyze how the model performs as network characteristics vary.     

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

An introduction to dynamic generative networks: Minimum cost flow

What we are dealing with is a class of networks called dynamic generative network flows in which the flow commodity is dynamically generated at source nodes and dynamically consumed at sink nodes. As a basic assumption, the source nodes produce the flow according to time generative functions and the sink nodes absorb the flow according to time consumption functions. This paper tries to introduce these networks and formulate minimum cost dynamic flow problem for a pre-specified time horizon T. Finally, some simple, efficient approaches are developed to solve the dynamic problem, in the general form when the capacities and costs are time varying and some other special cases, as a minimum cost static flow problem.     

The biobjective undirected two-commodity minimum cost flow problem

We address the two-commodity minimum cost flow problem considering two objectives. We show that the biobjective undirected two-commodity minimum cost flow problem can be split into two standard biobjective minimum cost flow problems using the change of variables approach. This technique allows us to develop a method that finds all the efficient extreme points in the objective space for the two-commodity problem solving two biobjective minimum cost flow problems. In other words, we generalize the Hu's theorem for the biobjective undirected two-commodity minimum cost flow problem. In addition, we develop a parametric network simplex method to solve the biobjective problem.     

Multi-depot vehicle scheduling problems with time windows and waiting costs

The multi-depot vehicle scheduling problem with time windows (MDVSPTW) consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task is restricted to begin within a prescribed time interval and vehicles are supplied by different depots. The problem is formulated as an integer nonlinear multi-commodity network flow model with time variables and is solved using a column generation approach embedded in a branch-and-bound framework. This paper breaks new ground by considering costs on exact waiting times between two consecutive tasks instead of minimal waiting times. This new and more realistic cost structure gives rise to a nonlinear objective function in the model. Optimal and heuristic versions of the algorithm have been extensively tested on randomly generated urban bus scheduling problem (UBSP) and freight transport scheduling problem (FTSP). The results show that such a general solution methodology outperforms specialized algorithms when minimal waiting costs are used, and can efficiently treat the case with exact waiting costs.     

A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks

Genetic algorithms and other evolutionary algorithms have been successfully applied to solve constrained minimum spanning tree problems in a variety of communication network design problems. In this paper, we enlarge the application of these types of algorithms by presenting a multi-population hybrid genetic algorithm to another communication design problem. This new problem is modeled through a hop-constrained minimum spanning tree also exhibiting the characteristic of flows. All nodes, except for the root node, have a nonnegative flow requirement. In addition to the fixed charge costs, nonlinear flow dependent costs are also considered. This problem is an extension of the well know NP-hard hop-constrained Minimum Spanning Tree problem and we have termed it hop-constrained minimum cost flow spanning tree problem. The efficiency and effectiveness of the proposed method can be seen from the computational results reported.     

A cost allocation problem arising in hub–spoke network systems

This paper studies a cost allocation problem arising from hub–spoke network systems. When a large-scale network is to be constructed jointly by several agents, both the optimal network design and the fair allocation of its cost are essential issues. We formulate this problem as a cooperative game and analyze the core allocation, which is a widely used solution concept. The core of this game is not necessarily non-empty as shown by an example. A reasonable scheme is to allocate the cost proportional to the flow that an agent generates. We show that, if the demand across the system has a block structure and the fixed cost is high, this cost allocation scheme belongs to the core. Numerical experiments are given with real telecommunication traffic data in order to illustrate the usefulness of our analytical findings.     

A specialized network simplex algorithm for the constrained maximum flow problem

The constrained maximum flow problem is to send the maximum flow from a source to a sink in a directed capacitated network where each arc has a cost and the total cost of the flow cannot exceed a budget. This problem is similar to some variants of classical problems such as the constrained shortest path problem, constrained transportation problem, or constrained assignment problem, all of which have important applications in practice. The constrained maximum flow problem itself has important applications, such as in logistics, telecommunications and computer networks. In this research, we present an efficient specialized network simplex algorithm that significantly outperforms the two widely used LP solvers: CPLEX and lp_solve. We report CPU times of an average of 27 times faster than CPLEX (with its dual simplex algorithm), the closest competitor of our algorithm.     

Generalized minimal cost flow problem in fuzzy nature: An application in bus network planning problem

The aim of minimal cost flow problem (MCFP) in fuzzy nature, which is denoted with FMCFP, is to find the least cost of the shipment of a commodity through a capacitated network in order to satisfy imprecise concepts in supply or demand of network nodes and capacity or cost of network links. Fuzzy supply–demand may arise in real problems, where incomplete statistical data or simulation results are used. Also, variation in the cost or capacity of links is commonly happening. In the present paper, after defining a total order on LR type fuzzy numbers, three models are studied; MCFP with fuzzy costs, MCFP with fuzzy supply–demand and a combination of two cases. For the first model, scaling negative cycle cancelling algorithm, which is a polynomial time algorithm, is proposed. For the second model, “nominal flow” is introduced which provides an efficient scheme for finding fuzzy flow. For the third model, we present an exact and some heuristic methods. Numerical examples are illustrated to demonstrate the efficiency of the proposed schemes. Finally, an application of this viewpoint in bus network planning problem is provided.