一类有增益网络的最大流模型

一般带容量限制的网络图中流出源点与流入汇点的流量相等,但在实际应用中,存在一类流量经过弧发生变化的网络,使得流出源点与流入汇点的流量不相等。针对此类问题,建立了增益网络最大流模型,并通过增设虚弧将增益网络转换成循环网络,利用循环网络中汇点流量瞬间平衡的优点简化了模型。最后,结合实例进行分析,编写程序对实例进行了计算,计算结果验证了该模型的有效性。     

Ripples,complements, and substitutes in generalized networks

We extend the qualitative theory of sensitivity analysis for minimum-cost pure network flows of Granot and Veinott [17] to generalized network flow problems, that is, network flow problems where the amount of flow picked up by an arc is multiplied by a (positive) gain while traversing the arc. Three main results are presented. The ripple theorem gives upper bounds on the absolute value of optimal-flow variations as a function of variations in the problem parameter(s). The theory of substitutes and complements provides necessary and sufficient conditions for optimal-flow changes to consistently have the same (or the opposite) sign(s) in two given arcs, whereas the monotonicity theorem links changes in the value of the parameters to changes in optimal arc flows. Bounds on the rates of changes are also discussed. Compared with pure networks, the presence of gains makes qualitative sensitivity analysis here a much harder task. We show the profound effect on computational issues caused by the departure from the pure network structure. © 1996 John Wiley & Sons, Inc.     

求解传感器网络最大生存时间的最大流算法

节能是传感器网络研究的中心问题之一,目的是延长网络的生存时间。因此对于一个给定网络,很自然地关心它的最大生存时间是多少。从网络最大流的角度分析这个问题,给出了求解传感器网络最大生存时间确切值的算法。     

The conjugate gradient technique for certain quadratic network problems

We consider a class of network flow problems with pure quadratic costs and demonstrate that the conjugate gradient technique is highly effective for large-scale versions. It is shown that finding a saddle point for the Lagrangian of an m constraint, n variable network problem requires only the solution of an unconstrained quadratic programming problem with only m variables. It is demonstrated that the number of iterations for the conjugate gradient algorithm is substantially smaller than the number of variables or constraints in the (primal) network problem. Forty quadratic minimum-cost flow problems of various sizes up to 100 nodes are solved. Solution time for the largest problems (4,950 variables and 99 linear constraints) averaged 4 seconds on the CBC Cyber 70 Model 72 computer.     

Shortest path interdiction problem with arc improvement recourse: A multiobjective approach

We consider the shortest path interdiction problem involving two agents, a leader and a follower, playing a Stackelberg game. The leader seeks to maximize the follower's minimum costs by interdicting certain arcs, thus increasing the travel time of those arcs. The follower may improve the network after the interdiction by lowering the costs of some arcs, subject to a cardinality budget restriction on arc improvements. The leader and the follower are both aware of all problem data, with the exception that the leader is unaware of the follower's improvement budget. The effectiveness of an interdiction action is given by the length of a shortest path after arc costs are adjusted by both the interdiction and improvement. We propose a multiobjective optimization model for this problem, with each objective corresponding to a different possible improvement budget value. We provide mathematical optimization techniques to generate a complete set of strategies that are Pareto‐optimal. Additionally, for the special case of series‐parallel graphs, we provide a dynamic‐programming algorithm for generating all Pareto‐optimal solutions.     

Mathematical control theory solution of an interactive accounting flows model

In this paper we have applied the mathematical control theory to the accounting network flows, where the flow rates are constrained by linear inequalities. The optimal control policy is of the “generalized bang-bang” variety which is obtained by solving at each instant in time a linear programming problem whose objective function parameters are determined by the “switching function” which is derived from the Hamiltonian function. The interpretation of the adjoint variables of the control problem and the dual evaluators of the linear programming problem demonstrates an interesting interaction of the cross section phase of the problem, which is characterized by linear programming, and the dynamic phase of the problem, which is characterized by control theory.     

Optimal interdiction of a supply network

Under certain conditions, the re-supply capability of a combatant force may be limited by the characteristics of the transportation network over which supplies must flow. Interdiction by an opposing force may be used to reduce the capacity of that network. The effects of such efforts vary for differing missions and targets. With only a limited total budget available, the interdictor must decide which targets to hit, and with how much effort. An algorithm is presented for determining the optimum interdiction plan for minimizing network flow capacity when the minimum capacity on an arc is positive and the cost of interdiction is a linear function of arc capacity reduction.     

A note on the stochastic shortest-route problem

This paper develops an algorithm for a “shortest route” network problem in which it is desired to find the path which yields the shortest expected distance through the network. It is assumed that if a particular arc is chosen, then there is a finite probability that an adjacent arc will be traversed instead. Backward induction is used and appropriate recursion formulae are developed. A numerical example is provided.     

Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support

We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016     

Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems

Until recently, fast algorithms for the maximum flow problem have typically proceeded by constructing layered networks and establishing blocking flows in these networks. However, in recent years, new distance-directed algorithms have been suggested that do not construct layered networks but instead maintain a distance label with each node. The distance label of a node is a lower bound on the length of the shortest augmenting path from the node to the sink. In this article we develop two distance-directed augmenting path algorithms for the maximum flow problem. Both the algorithms run in O(n²m) time on networks with n nodes and m arcs. We also point out the relationship between the distance labels and layered networks. Using a scaling technique, we improve the complexity of our distance-directed algorithms to O(nm log U), where U denotes the largest arc capacity. We also consider applications of these algorithms to unit capacity maximum flow problems and a class of parametric maximum flow problems.     

Min/max bounds for dynamic network flows

This paper presents an algorithm for determining the upper and lower bounds for arc flows in a maximal dynamic flow solution. The procedure is basically an extended application of the Ford-Fulkerson dynamic flow algorithm which also solves the minimal cost flow problem. A simple example is included. The presence of bounded optimal are flows entertains the notion that one can pick a particular solution which is preferable by secondary criteria.     

The dynamic transportation problem: A survey

The dynamic transportation problem is a transportation problem over time. That is, a problem of selecting at each instant of time t, the optimal flow of commodities from various sources to various sinks in a given network so as to minimize the total cost of transportation subject to some supply and demand constraints. While the earliest formulation of the problem dates back to 1958 as a problem of finding the maximal flow through a dynamic network in a given time, the problem has received wider attention only in the last ten years. During these years, the problem has been tackled by network techniques, linear programming, dynamic programming, combinational methods, nonlinear programming and finally, the optimal control theory. This paper is an up-to-date survey of the various analyses of the problem along with a critical discussion, comparison, and extensions of various formulations and techniques used. The survey concludes with a number of important suggestions for future work.     

A branch-and-bound algorithm for flow-path design of automated guided vehicle systems

An algorithm for determining the optimal, unidirectional flow path for an automated guided vehicle system with a given facility layout is presented. The problem is formulated as an integer program. The objective is to minimize the total distance traveled by vehicles subject to the constraint that the resulting network consists of a single strongly connected component. A specialized branch-and-bound solution procedure is discussed in detail.     

Approximation algorithms for general one‐warehouse multi‐retailer systems

Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross‐docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ε‐optimality can be obtained by solving a related piece‐wise linear concave cost multi‐commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ε) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece‐wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece‐wise concavity feature of the cost functions. This gives rise to a unified and generic LP‐based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

One machine sequencing to minimize mean flow time with minimum number tardy

The problem of sequencing n jobs on one machine is considered, under the multiple objective of minimizing mean flow time with the minimum number of tardy jobs. A simple procedure is first proposed to schedule for minimum flow time with a specified subset of jobs on time. This is used in conjunction with Moore's Algorithm in a simple heuristic producing good and often optimal schedules. A branch-bound algorithm is presented to produce the optimal schedule efficiently with the help of several theorems which eliminate much branching.     

干扰及机动条件下的比例导引智能调控策略

由于红外诱饵干扰样式复杂、目标机动形式多变导致传统比例导引律极易被干扰。为提高采用比例导引方法的导弹性能,提出一种利用径向基函数网络调控比例系数及导弹发射时机的智能导引律。以飞行时间及脱靶量为参考,通过构建加权型指标函数将求解最优比例系数及发射时机问题转化为单目标优化问题;引入量子粒子群算法求解最优决策参量,并以其作为网络输出,干扰样式作为网络输入,离线训练径向基函数网络;为提高训练效率,结合K-means及K最近邻算法初始化径向基函数网络。仿真结果表明,当存在红外诱饵干扰时,智能导引律性能优于扩展比例导引律及自适应滑模导引律。     

Manpower allocation with time windows and job‐teaming constraints

In this work, we study manpower allocation with time windows and job‐teaming constraints. A set of jobs at dispersed locations requires teams of different types of workers where each job must be carried out in a preestablished time window and requires a specific length of time for completion. A job is satisfied if the required composite team can be brought together at the job's location for the required duration within the job's time window. The objective is to minimize a weighted sum of the total number of workers and the total traveling time. We show that construction heuristics used with simulated annealing is a good approach to solving this NP‐hard problem. In experiments, this approach is compared with solutions found using CPLEX and with lower bounds obtained from a network flow model. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.     

The frequency assignment problem: A solution via nonlinear programming

This paper gives a mathematical programming model for the problem of assigning frequencies to nodes in a communications network. The objective is to select a frequency assignment which minimizes both cochannel and adjacent-channel interference. In addition, a design engineer has the option to designate key links in which the avoidance of jamming due to self interference is given a higher priority. The model has a nonconvex quadratic objective function, generalized upper-bounding constraints, and binary decision variables. We developed a special heuristic algorithm and software for this model and tested it on five test problems which were modifications of a real-world problem. Even though most of the test problems had over 600 binary variables, we were able to obtain a near optimum in less than 12 seconds of CPU time on a CDC Cyber-875.     

Modeling and analysis of multiobjective lot splitting for N‐product M‐machine flowshop lines

Lot splitting is a new approach for improving productivity by dividing production lots into sublots. This approach enables accelerating production flow, reducing lead‐time and increasing the utilization of organization resources. Most of the lot splitting models in the literature have addressed a single objective problem, usually the makespan or flowtime objectives. Simultaneous minimization of these two objectives has rarely been addressed in the literature despite of its high relevancy to most industrial environments. This work aims at solving a multiobjective lot splitting problem for multiple products in a flowshop environment. Tight mixed‐integer linear programming (MILP) formulations for minimizing the makespan and flowtime are presented. Then, the MinMax solution, which takes both objectives into consideration, is defined and suggested as an alternative objective. By solving the MILP model, it was found that minimizing one objective results in an average loss of about 15% in the other objective. The MinMax solution, on the other hand, results in an average loss of 4.6% from the furthest objective and 2.5% from the closest objective. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010