A Branch-and-Bound Algorithm for Concave Network Flow Problems

In this paper a Branch-and-Bound (BB) algorithm is developed to obtain an optimal solution to the single source uncapacitated minimum cost Network Flow Problem (NFP) with general concave costs. Concave NFPs are NP-Hard, even for the simplest version therefore, there is a scarcity of exact methods to address them in their full generality. The BB algorithm presented here can be used to solve optimally single source uncapacitated minimum cost NFPs with any kind of concave arc costs. The bounding is based on the computation of lower bounds derived from state space relaxations of a dynamic programming formulation. The relaxations, which are the subject of the paper (Fontes et al., 2005b) and also briefly discussed here, involve the use of non-injective mapping functions, which guarantee a reduction on the cardinality of the state space. Branching is performed by either fixing an arc as part of the final solution or by removing it from the final solution. Computational results are reported and compared to available alternative methods for addressing the same type of problems. It could be concluded that our BB algorithm has better performance and the results have also shown evidence that it has a sub-exponential time growth.     

Network Design for Express Shipment Delivery

Service network design problems arise at airlines (passenger and cargo), trucking companies, railroads, etc., wherever there is a need to determine cost minimizing routes and schedules, given constraints on resource availability and level of service. We focus on a particular service network design application, namely, the express shipment delivery problem, and we develop models and a solution technique designed specifically for large-scale express delivery problems with time windows. Using data from an express delivery company, we demonstrate that our approach can produce savings in total operating costs and provide a valuable tool for making decisions at strategic and tactical levels.     

Lower Bounds from State Space Relaxations for Concave Cost Network Flow Problems

In this paper we obtain Lower Bounds (LBs) to concave cost network flow problems. The LBs are derived from state space relaxations of a dynamic programming formulation, which involve the use of non-injective mapping functions guaranteing a reduction on the cardinality of the state space. The general state space relaxation procedure is extended to address problems involving transitions that go across several stages, as is the case of network flow problems. Applications for these LBs include: estimation of the quality of heuristic solutions; local search methods that use information of the LB solution structure to find initial solutions to restart the search (Fontes et al., 2003, Networks, 41, 221–228); and branch-and-bound (BB) methods having as a bounding procedure a modified version of the LB algorithm developed here, (see Fontes et al., 2005a). These LBs are iteratively improved by penalizing, in a Lagrangian fashion, customers not exactly satisfied or by performing state space modifications. Both the penalties and the state space are updated by using the subgradient method. Additional constraints are developed to improve further the LBs by reducing the searchable space. The computational results provided show that very good bounds can be obtained for concave cost network flow problems, particularly for fixed-charge problems.     

运输问题求解的一种网络算法

本着重探讨了在网络图上求运输问题的初始解的方法，并指出在求解受时间约束的运输问题时得到的初始解，在很大程度就是该问题的最优解，通过实例说明了该算法。     

Stochastic Survivable Network Design Problems

In this paper we introduce survivable network design problems under a two-stage stochastic model with fixed recourse and finitely many scenarios. We propose a new cut-based formulation based on orientation properties which is stronger than the undirected cut-based model. We use a two-stage branch&cut algorithm for solving the decomposed model to provable optimality. In order to accelerate the computations, we suggest a new cut strengthening technique for the decomposed L-shaped optimality cuts that is computationally fast and easy to implement.     

A capacity scaling heuristic for the multicommodity capacitated network design problem

In this paper, we propose a capacity scaling heuristic using a column generation and row generation technique to address the multicommodity capacitated network design problem. The capacity scaling heuristic is an approximate iterative solution method for capacitated network problems based on changing arc capacities, which depend on flow volumes on the arcs. By combining a column and row generation technique and a strong formulation including forcing constraints, this heuristic derives high quality results, and computational effort can be reduced considerably. The capacity scaling heuristic offers one of the best current results among approximate solution algorithms designed to address the multicommodity capacitated network design problem.     

一种新的交通网络设计优化算法

交通网络设计问题是研究如何用定量的方法在已有交通网络上添加或扩容某些路段的问题.文章在回顾交通网络设计问题文献的基础上,提出了基于图论网络优化思想的解决该类问题的一种新思路,给出了启发式算法,并进行了算法复杂性分析,最后通过算例验证了其有效性.     

空铁联运网络的模型构建与算法设计

针对空铁联运网络具体联运路径的设计问题,借鉴枢纽航线网络p-枢纽中位问题的研究思想,将非枢纽城市间可以直航考虑进去,以联运网络总成本最低为目标函数,构建了允许直航的空铁联运网络混合整数规划模型,并设计了基于遍历搜索的最短路算法来求解模型.最后选取样本城市对模型和算法进行算例分析,给出了不同参数组合下的最优目标值和具体联运路径,设计了中国14个城市的空铁联运网络.算例结果表明联运总成本大小和联运路径的数目与枢纽数目m、折扣系数ρ紧密相关:m越大,ρ越小,联运总成本越小,联运路径数目越多;反之亦然.     

一个解决线性互补问题的新型神经网络

本文构造了一个新型的解决线性互补问题的神经网络,不同于那些运用罚函数和拉格朗日函数的神经网络,它的结构简单,易于计算,我们证明了该神经网络的全局收敛性和稳定性,并给出数值实验检验其有效性。     

A Perturbation Result for Dynamical Contact Problems

This paper is intended to be a first step towards the continuous dependence of dynamical contact problems on the initial data as well as the uniqueness of a solution. Moreover, it provides the basis for a proof of the convergence of popular time integration schemes as the Newmark method. We study a frictionless dynamical contact problem between both linearly elastic and viscoelastic bodies which is formulated via the Signorini contact conditions. For viscoelastic materials fulfilling the Kelvin-Voigt constitutive law, we find a characterization of the class of problems which satisfy a perturbation result in a non-trivial mix of norms in function space. This characterization is given in the form of a stability condition on the contact stresses at the contact boundaries. Furthermore, we present perturbation results for two well-established approximations of the classical Signorini condition: The Signorini condition formulated in velocities and the model of normal compliance, both satisfying even a sharper version of our stability condition.     

P-枢纽航线网络设计问题的一种启发式算法

针对无容量限制的多重分派枢纽中位问题(UMApHMP),提出了一种基于禁忌搜索和最短路算法的新的启发式算法。利用CAB基准数据对该算法进行了验证,计算结果表明所提算法具有较强寻优能力和较快的求解效率。     

The Minimum Concave Cost Network Flow Problem with fixed numbers of sources and nonlinear arc costs

We prove that the Minimum Concave Cost Network Flow Problem with fixed numbers of sources and nonlinear arc costs can be solved by an algorithm requiring a number of elementary operations and a number of evaluations of the nonlinear cost functions which are both bounded by polynomials inr, n, m, wherer is the number of nodes,n is the number of arcs andm the number of sinks in the network.On leave from Institute of Mathematics, P.O. Box 631, Bo Ho, Hanoi, Vietnam.     

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.     

An Evolution Program for Non-Linear Transportation Problems

In this paper we describe main features of a Strongly Feasible Evolution Program (SFEP) designed to solve non-linear network flow problems. The program can handle non-linearities both in the constraints and in the objective function. The solutions procedure is based on a recombination operator in which all parents in a small mating pool have equal chance of contributing their genetic material to offspring. When offspring is created with better fitness value than that of the worst parent, the worst parent is discarded from the mating pool while the offspring is placed in it. The main contributions are in the massive parallel initialization procedure which creates only feasible solutions with simple heuristic rules that increase chances of creating solutions with good fitness values for the initial mating pool, and the gene therapy procedure which fixes defective genes ensuring that the offspring resulting from recombination is always feasible. Both procedures utilize the properties of network flows. The algorithm is capable of handling mixed integer problems with non-linearities in both constraints and the objective function. Tests were conducted on a number of previously published transportation problems with 49 and 100 decision variables, which constitute a subset of network flow problems. Convergence to equal or better solutions was achieved with often less than one tenth of the previous computational efforts.     

A Numerical Approach for Solving Some Convex Maximization Problems

We are concerned with concave programming or the convex maximization problem. In this paper, we propose a method and algorithm for solving the problem which are based on the global optimality conditions first obtained by Strekalovsky (Soviet Mathematical Doklady, 8(1987)). The method continues approaches given in (Journal of global optimization, 8(1996); Journal of Nolinear and convex Analyses 4(1)(2003)). Under certain assumptions a convergence property of the proposed method has been established. Some computational results are reported. Also, it has been shown that the problem of finding the largest eigenvalue can be found by the proposed method.     

带凹性生产成本运输问题的新随机规划模型及其求解

提出了一种新的能反映决策者满意度的随机变量序关系,并据此研究了随机不等式的确定性等价类,方法被称为满意度方法.最后将其应用于带凹性生产成本运输问题的求解中,并将方法与常用的机会约束方法进行比较,说明满意度法不仅合理可行,而且当决策者对约束条件的要求越高时,它所得最优值越优于机会约束法所得最优值.     

Constraint Generation for Network Reliability Problems

This paper presents a constraint generation approach to the network reliability problem of adding spare capacity at minimum cost that allows the traffic on a failed link to be rerouted to its destination. Any number of non-simultaneous link failures can be part of the requirements on the spare capacity. The key result is a necessary and sufficient condition for a multicommodity flow to exist, which is derived in the appendix. Computational results on large numbers of random networks are presented.     

带固定轴线成本的轴辐式网络设计问题

带固定轴线成本的轴辐式网络设计问题广泛应用于第三方物流、邮政和航空运输等领域. 现有研究主要考虑了枢纽站的节点成本, 本研究则强调合并运输的固定轴线成本. 固定轴线成本的必要性在于：轴辐式网络中的轴线运输需要借助更大型的运输工具, 因此必须支付固定成本. 建立了该问题的混合整数规划模型, 探讨了最优解特征, 并构造了求解问题的拉格朗日松驰算法, 实验显示算法具有非常好的求解效率与求解质量. 同时, 还讨论了一个重要的扩展问题：增加O-D流的绕道约束, 绕道约束常常应用于快递运输和应急物流等领域. 在局部修改原算法的基础上提供了扩展问题的求解方案.     

An Adaptive Neural Network Model for Nonlinear Programming Problems

In this paper a canonical neural network with adaptively changing synaptic weights and activation function parameters is presented to solve general nonlinear programming problems. The basic part of the model is a sub-network used to find a solution of quadratic programming problems with simple upper and lower bounds. By sequentially activating the sub-network under the control of an external computer or a special analog or digital processor that adjusts the weights and parameters, one then solves general nonlinear programming problems. Convergence proof and numerical results are given.     

A Mixed Integer Formulation for Multiple-Route Transit Network Design

We consider the design of multiple transit lines in a network and present a mixed integer formulation for this multiple-route transit network design problem (MRTNDP). With the introduction of node labels, the formulation can exploit the route structure and hence attains efficiency in obtaining a cost minimizing transit network design. This revised version was published online in July 2006 with corrections to the Cover Date.