Tabu Search for a Network Loading Problem with Multiple Facilities

This paper examines a network design problem that arises in the telecommunications industry. In this problem, communication between a gateway vertex and a number of demand vertices is achieved through a network of fiber optic cables. Since each cable has an associated capacity (bandwidth), enough capacity must be installed on the links of the network to satisfy the demand, using possibly different types of cables. Starting with a network with no capacity or some capacity already installed, a tabu search heuristic is designed to find a solution that minimizes the cost of installing any additional capacity on the network. This tabu search applies a k-shortest path algorithm to find alternative paths from the gateway to the demand vertices. Numerical results are presented on different types of networks with up to 200 vertices and 100 demand vertices.     

An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems

In this paper an algorithm is presented for determining the K best paths that may contain cycles in a directed network.The basic idea behind the algorithm is quite simple. Once the best path has been determined it is excluded from the network in such a way that no new path is formed and no more paths are excluded. This step leads to an enlarged network where all the paths, but the best one, can be determined. The method is repeated until the desired paths have been computed.The proposed algorithm can be used not only for the classical K shortest paths problem but also for ranking paths under a nonlinear objective function, provided that an algorithm to determine the best path exists.Computational results are presented and comparisons with other approaches for the classical problem are made.     

Enhanced formulations and branch-and-cut for the two level network design problem with transition facilities

We consider a new combinatorial optimization problem that combines network design and facility location aspects. Given a graph with two types of customers and two technologies that can be installed on the edges, the objective is to find a minimum cost subtree connecting all customers while the primary customers are served by a primary subtree that is embedded into the secondary subtree. In addition, besides fixed link installation costs, facility opening costs, associated to each node where primary and secondary subtree connect, have to be paid. The problem is called the Two Level Network Design Problem with Transition Facilities (TLNDF).     

A tree search algorithm for the multi-commodity location problem

The multi-commodity location problem is an extension of the simple plant location problem. The problem is to decide on locations of facilities to meet customer demands for several commodities in such a way that total fixed plus variable costs are minimized. Only one commodity may be supplied from any location.In this paper a primal and a dual heuristic for producing good bounds are presented. A method of improving these bounds by using a new Lagrangean relaxation for the problem is also presented. Computational results with problems taken from the literature are provided.     

An upper bound on the expected completion time of PERT networks

In this paper the problem of determining an upper bound on the expected project completion time, described by the PERT network, is considered. It is assumed that activity durations are independent random variables with given means. The exact forms of probability distributions do not have to be known; however, their cumulative distribution functions are expected to belong to the so-called NBUE class. Very simple algorithms for deriving this bound are presented. The computations can even be performed manually for more involved networks. Our approach producing a pessimistic evaluation of the expected value of the project duration, extends considerably the information obtained through the use of the classical PERT that always underestimates this value. The results are illustrated by a simple example, and errors of approximations are discussed.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

Wide area telecommunication network design: application to the Alberta SuperNet

This article proposes a solution methodology for the design of a wide area telecommunication network. This study is motivated by the Alberta SuperNet project, which provides broadband Internet access to 422 communities across Alberta. There are two components to this problem: the network design itself, consisting of selecting which links will be part of the solution and which nodes should house shelters; and the loading problem which consists of determining which signal transport technology should be installed on the selected edges of the network. Mathematical models are described for these two subproblems. A tabu search algorithm heuristic is developed and tested on randomly generated instances and on Alberta SuperNet data.     

Scheduling preventive maintenance for modular designed components: A dynamic approach

One of the benefits of modular design is ease-of-service. While modular design helps simplify field maintenance, extensive depot maintenance and spare modules are required to support the field maintenance. This study develops a dynamic approach for scheduling preventive maintenance at a depot with the limited availability of spare modules and other constraints. A backward allocation algorithm is proposed and applied to scheduling the preventive maintenance of an engine module installed in T-59 advanced jet trainers in the Republic of Korea Air Force. The algorithm developed by this study can be used to solve similar problems for various systems such as aerospace vehicles, heavy machinery, and medical equipment. The contribution of this study includes the uniqueness of the algorithm, the flexibility to deal with variables changing over time, and the ability to incorporate additional variables to handle complex situations.     

Computational experience with a difficult mixedinteger multicommodity flow problem

The following problem arises in the study of lightwave networks. Given a demand matrix containing amounts to be routed between corresponding nodes, we wish to design a network with certain topological features, and in this network, route all the demands, so that the maximum load (total flow) on any edge is minimized. As we show, even small instances of this combined design/routing problem are extremely intractable. We describe computational experience with a cutting plane algorithm for this problem.This research was partially supported by a Presidential Young Investigator Award and the Center for Telecommunications Research, Columbia University.Corresponding author.     

Integrated supply chain planning under uncertainty using an improved stochastic approach

This paper proposes an integrated model and a modified solution method for solving supply chain network design problems under uncertainty. The stochastic supply chain network design model is provided as a two-stage stochastic program where the two stages in the decision-making process correspond to the strategic and tactical decisions. The uncertainties are mostly found in the tactical stage because most tactical parameters are not fully known when the strategic decisions have to be made. The main uncertain parameters are the operational costs, the customer demand and capacity of the facilities. In the improved solution method, the sample average approximation technique is integrated with the accelerated Benders’ decomposition approach to improvement of the mixed integer linear programming solution phase. The surrogate constraints method will be utilized to acceleration of the decomposition algorithm. A computational study on randomly generated data sets is presented to highlight the efficiency of the proposed solution method. The computational results show that the modified sample average approximation method effectively expedites the computational procedure in comparison with the original approach.     

An MPEC formulation and its cutting constraint algorithm for continuous network design problem with multi-user classes

Continuous network design problem (CNDP) is to determine the set of link capacity expansions and the corresponding equilibrium flows for which the measures of performance index for the network is optimal. Conventionally, CNDP assumed users to be homogeneous, that is, all travelers on the same link of the network are identical insofar as congestion effect and they have the same value of time (VOT). In fact, it does not accord with the real situation that all have the same VOT. So, multiple user classes with different VOT should be considered. This paper examines the CNDP with different VOT for multiple user classes, which is generally expressed as a mathematical programming with equilibrium constraint (MPEC). Then, the cut constraint algorithm (CCA) is presented to solve the problem. The numerical experiments on the examples from the literature are illustrated to demonstrate that our model and algorithm are feasible.     

基于网络等级特征与VMS的交叉巢式Logit模型

基于等级特征与可变信息板(VMS)研究了交叉巢式Logit(CNL)模型及网络交通流分配。综合幂函数与指数函数表示方法给出新的信息效用衰减因子,结合道路等级特征表示VMS对车流的影响系数及CNL模型的分配系数;给出等级结构道路网络的随机用户均衡条件下的交叉巢式Logit路径选择模型及其等价数学规划,并设计网络流分配算法。通过实例网络的计算与分析,得到一些有意义的结论:等级结构越显著的路网总出行时间费用越低且其分散参数(θ)弹性绝对值越大;对具有较强随机性的实际路网,若增加一定的确定性则节省更多网络总出行时间;道路网络中设置了VMS时总出行时间受分散参数的影响更小。     

TRUST REGION METHOD IN NEURAL NETWORK

1.IntroductionHopfieldandTank[5]presentedamodeltosolvetravellingsalesmanproblem,thusinitiatingtheapplicationofneuralnetwork(NN)inthefieldofoptimization.SincethenmanyNNmodelshavebeenproposedtosolvelinearprogramming(LP)problems(13,8,11,14,15])andquadraticprogramming(oP)problems([1,8,20]),asLPandoPhavefundamentalimportanceinthetheoryandpracticeofoptimization.Therewerealsoafewmodelsforgeneralnonlinearprogramming(NP)problem([2,6,9,18]).InthispaperwewillpresentaHopfield-typeneuralnetworkmodelw…     

Logistics network design for product recovery in fuzzy environment

The design of product recovery network is one of the important and challenging problems in the field of reverse logistics. Some models have been formatted by researchers under deterministic environment. However, uncertainty is inherent during the process of the practical product recovery. In order to deal with uncertainty, this paper employs a fuzzy programming tool to design the product recovery network. Based on different criteria, three types of optimization models are proposed and some properties of them are investigated. To solve the proposed models, we design a hybrid intelligent algorithm which integrates fuzzy simulation and genetic algorithm. Finally, several numerical examples are presented to illustrate the effectiveness of the proposed models and algorithm.     

一个新的解线性规划的神经网络

本文提出一个新的解线性规划的Hopfields-型网络。该网络基于线性规划的对偶理论,并使用了Sigmoid函数,但不需要预先给定的罚参数和乘法模拟器,我们证明该网络不仅全局收敛到线性规划的精确解,而且能同时解原规划和对偶规划。由于在该网络中没有使用乘法模拟器而利用了Sigmoid函数,因此该模型是很容易用硬件实现的。     

Design of survivable IP-over-optical networks

In the past years, telecommunications networks have seen an important evolution with the advances in optical technologies and the explosive growth of the Internet. Several optical systems allow a very large transport capacity, and data traffic has dramatically increased. Telecommunications networks are now moving towards a model of high-speed routers interconnected by intelligent optical core networks. Moreover, there is a general consensus that the control plan of the optical networks should utilize IP-based protocols for dynamic provisioning and restoration of lightpaths. The interaction of the IP routers with the optical core networks permits to achieve end-to-end connections, and the lightpaths of the optical networks define the topology of the IP network. This new infrastructure has to be sufficiently survivable, so that network services can be restored in the event of a catastrophic failure. In this paper we consider a multilayer survivable network design problem that may be of practical interest for IP-over-optical neworks. We give an integer programming formulation for this problem and discuss the associated polytope. We describe some valid inequalities and study when these are facet defining. We discuss separation algorithms for these inequalities and introduce some reduction operations. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

Facility location models for planning a transatlantic communications network

This paper presents two facility location models for the problem of determining how to optimally serve the requirements for communication circuits between the United States and various European and Middle Eastern countries. Given a projection of future requirements, the problem is to plan for the economic growth of a communications network to satisfy these requirements. Both satellite and submarine cable facilities may be used. The objective is to find an optimal placement of cables (type, location, and timing) and the routing of individual circuits between demand points (over both satellites and cables) such that the total discounted cost over a T-period horizon is minimized. This problem is cast as a multiperiod, capacitated facility location problem. Two mathematical models differing in their provisions for network reliability are presented. Solution approaches are outlined and compared by means of computational experience. Use of the models both in planning the growth of the network and in the economic evaluation of different cable technologies is also discussed.     

区域废弃物网络系统的选址-运输优化模型

区域废弃物网络系统优化设计包括设施的选址和废弃物运输路线的确定。考虑了多类型设施、多种废弃物流和模糊数形式的废弃物产生量,建立了模糊机会约束规划模型来求得整个系统的优化配置。通过将模型中的机会约束清晰化,将模糊机会约束规划模型转化成等价的确定模型来求解。实例表明了模型的有效性。