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.     

Approximating connected facility location with buy-at-bulk edge costs via random sampling

In the connected facility location problem with buy-at-bulk edge costs we are given a set of clients with positive demands and a set of potential facilities with opening costs in an undirected graph with edge lengths obeying the triangle inequality. Moreover, we are given a set of access cable types, each with a cost per unit length and a capacity such that the cost per capacity decreases from small to large cables, and a core cable type of infinite capacity. The task is to open some facilities and to connect them by a Steiner tree using core cables, and to build a forest network using access cables such that the edge capacities suffice to simultaneously route all client demands unsplit to the open facilities. The objective is to minimize the total cost of opening facilities, building the core Steiner tree, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for this problem based on a random sampling technique.     

Diversification strategies in local search for a nonbifurcated network loading problem

This paper examines a variant of the network loading problem, a network design problem found in the telecommunications industry. In this problem, facilities of fixed capacity must be installed on the edges of an undirected network to carry the flow from a central vertex to a set of demand vertices. The objective is to minimize the total installation costs. In this work, the nonbifurcated version of the problem is considered, where the demand at any given vertex must be satisfied through a single path. The proposed heuristics alternate between a construction phase and a local search phase. Each new construction phase, except the first one, is part of a diversification strategy aimed at providing a new starting point for the following local search phase. Different diversification strategies are tested and compared on large-scale instances with up to 500 vertices.     

A MIP-based approach to solve the prize-collecting local access network design problem

This paper presents a new combinatorial optimization problem that can be used to model the deployment of broadband telecommunications systems in which optical fiber cables are installed between a central office and a number of end-customers. In this capacitated network design problem the installation of optical fiber cables with sufficient capacity is required to carry the traffic from the central office to the end-customers at minimum cost. In the situation motivating this research the network does not necessarily need to connect all customers (or at least not with the best available technology). Instead, some nodes are potential customers. The aim is to select the customers to be connected to the central server and to choose the cable capacities to establish these connections. The telecom company takes the strategic decision of fixing a percentage of customers that should be served, and aims for minimizing the total cost of the network providing this minimum service. For that reason the underlying problem is called the Prize-Collecting Local Access Network Design problem (PC-LAN).     

Optimal planning of network structures within an exchange area

The cost-optimal planning and capacity extension of a given network structure is described by a mixed-integer program. The decision variables in this model are first discrete digital systems (PCM) set up on existing cable lines and secondly new cable links required in the future. Furthermore, this formulation takes account of the circuit capacity of the system and path diversification required for reliability reasons. This planning model describes a real-world problem that can be formulated not only mathematically as a true reproduction of reality but can also be solved in a closed form within reasonable computer time. Opposite to the operational planning methods, this model allows a global cost-optimal network to be obtained, which is subject to a certain set of constraints.     

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.     

Algorithms for the non-bifurcated network design problem

In this paper we consider the non-bifurcated network design problem where a given set of cities must be connected by installing on a given set of links integer multiples of some base capacity so that a set of commodity demands can be routed. Each commodity flow is constrained to run through a single path along the network. The objective is to minimize the sum of capacity installation and routing costs. We present an exact algorithm and four new heuristics. The first heuristic generates an initial feasible solution, then it improves it until a necessary condition for optimality is satisfied. Two heuristics are partial enumeration methods and the last one iteratively applies a tabu search method to different initial feasible solutions. Computational results over a set of test problems from the literature show the effectiveness of the proposed algorithms.     

结点有约束的交通网络最短路径模型

结点有约束的网络是一类特殊的网络，如具有禁止通行限制信息的交通路网等，由于最短路径的求解是有后效性的，经典的Dijkstra算法等不能直接用来求解该问题，本文提出了一种结点有约束的交通网络最短路径建模方法，该方法所建模型为一般网络模型，可用任一传统高效的算法求其最短路径，从根本上降低了问题的复杂性，为很好地解决交通、通信等领域中的此类问题提供了有益的方法。     

基于不确定理论的原油海运网络连通可靠性研究

原油海运网络是原油进口国的海上生命线,为科学衡量网络中节点受到突发事件影响后的原油海运网络的连通可靠性,本文采用不确定变量来描述突发事件发生后各节点的连通性,引入不确定理论对原油海运网络连通可靠性进行评估,并建立了不确定原油海运网络的最可靠路径选择模型。本文不确定变量的引入不再依赖较多的历史数据去描绘节点失效的概率分布,而且提出的最可靠路径选择模型可以确保突发事件发生后原油的及时运输。本文还提出了α-最可靠路径和最大测度最可靠路径选择问题,给出不确定原油海运网络最可靠路径风险值的不确定分布,为突发事件发生后决策者的路径选择提供依据。本文以中国进口原油海运网络为例作案例分析。     

Hub and spoke network design with single-assignment,capacity decisions and balancing requirements

In this paper, an extension of the capacitated single-allocation hub location problem is considered in which the capacity of the hubs is part of the decision making process and balancing requirements are imposed on the network. The decisions to be made comprise (i) the selection of the hubs, (ii) the allocation of the spoke nodes to the hubs, (iii) the flow distribution through the sub network defined by the hubs and (iv) the capacity level at which each hub should operate. In the latter case, for each potential hub, a set of available capacities is considered among which one can be chosen. The objective is to minimize the total cost, which includes the setup cost for the hubs as well as the flow routing cost. Economies of scale are assumed for the costs. Balancing requirements are imposed to the network. In particular, a value is considered for the maximum difference between the maximum and minimum number of spoke nodes that are allocated to the hubs. Two mixed-integer linear programming formulations are proposed and analyzed for this problem. The results of a set of computational experiments using an off-the-shelf commercial solver are presented. These tests aim at evaluate the possibility of solving the problem to optimality using such a solver with a particular emphasis to the impact of the balancing requirements. The tests also allow an analysis of the gap of the bounds provided by linear relaxation.     

Telecommunication Network Capacity Design for Uncertain Demand

The expansion of telecommunication services has increased the number of users sharing network resources. When a given service is highly demanded, some demands may be unmet due to the limited capacity of the network links. Moreover, for such demands, telecommunication operators should pay penalty costs. To avoid rejecting demands, we can install more capacities in the existing network. In this paper we report experiments on the network capacity design for uncertain demand in telecommunication networks with integer link capacities. We use Poisson demands with bandwidths given by normal or log-normal distribution functions. The expectation function is evaluated using a predetermined set of realizations of the random parameter. We model this problem as a two-stage mixed integer program, which is solved using a stochastic subgradient procedure, the Barahona's volume approach and the Benders decomposition.     

Optimal use of hub facilities: A two-hub model with fixed arc costs

Summary We introduce a model of a communication network design problem involving the utilization of hub facilities. That is, for a problem with two sets of customers and no intraset demand we seek to determine how the hub node associated with each set should be utilized. We assume that the only costs are the fixed costs associated with creating each of the three types of connecting arcs. A key parameter is the “group” size which is the number of communication circuits which can be bundled together in an arc. The optimal design depends strongly on how closely the arcs can be filled to capacity. The general demand problem is shown to be NP-Hard. However, for unit demand, we derive an almost “all or nothing” result which specifies that all flow should be direct node-to-node or, on the other hand, all or almost all flow should go via the hubs. Research supported in part by Grant SAB-94-0115 from the Spanish Interministerial Commission of Science and Technology while this author was on sabbatical leave at the Polytechnic University of Catalonia in Barcelona.     

An extended shortest path problem: A data envelopment analysis approach

A special and important network structured linear programming problem is the shortest path problem. Classical shortest path problems assume that there are unit of shipping cost or profit along an arc. In many real occasions, various attributes (various costs and profits) are usually considered in a shortest path problem. Because of the frequent occurrence of such network structured problems, there is a need to develop an efficient procedure for handling these problems. This paper studies the shortest path problem in the case that multiple attributes are considered along the arcs. The concept of relative efficiency is defined for each path from initial node to final node. Then, an efficient path with the maximum efficiency is determined.     

The fleet size and mix problem for capacitated arc routing

There have been several attempts to solve the capacitated arc routing problem with m vehicles starting their tours from a central node. The objective has been to minimize the total distance travelled. In the problem treated here we also have the fixed costs of the vehicles included in the objective function. A set of vehicle capacities with their respective costs are used. Thus the objective function becomes a combination of fixed and variable costs. The solution procedure consists of four phases. In the first phase, a Chinese or rural postman problem is solved depending on whether all or some of the arcs in the network demand service with the objective of minimizing the total distance travelled. It results in a tour called the giant tour. In the second phase, the giant tour is partitioned into single vehicle subtours feasible with respect to the constraints. A new network is constructed with the node set corresponding to the arcs of the giant tour and with the arc set consisting of the subtours of the giant tour. The arc costs include both the fixed and variable costs of the subtours. The third phase consists of solving the shortest path problem on this new network to result in the least cost set of subtours represented on the new network. In the last phase a postprocessor is applied to the solution to improve it. The procedure is repeated for different giant tours to improve the final solution. The problem is extended to the case where there can be upper bounds on the number of vehicles with given capacities using a branch and bound method. Extension to directed networks is given. Some computational results are reported.     

Network flow interdiction on planar graphs

The network flow interdiction problem asks to reduce the value of a maximum flow in a given network as much as possible by removing arcs and vertices of the network constrained to a fixed budget. Although the network flow interdiction problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work, we introduce pseudo-polynomial algorithms that overcome various restrictions of previous methods. In particular, we propose a planarity-preserving transformation that enables incorporation of vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a new approach is introduced that allows us to determine in pseudo-polynomial time the minimum interdiction budget needed to remove arcs and vertices of a given network such that the demands of the sink node cannot be completely satisfied anymore. The algorithm works on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the sources equals the sum of the demands at the sinks. A simple extension of the proposed method allows us to broaden its applicability to solve network flow interdiction problems on planar networks with a single source and sink having no restrictions on the demand and supply. The proposed method can therefore solve a wider class of flow interdiction problems in pseudo-polynomial time than previous pseudo-polynomial algorithms and is the first pseudo-polynomial algorithm that can solve non-trivial planar flow interdiction problems with multiple sources and sinks. Furthermore, we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers.     

Arc routing problems with time-dependent service costs

This paper studies an arc routing problem with capacity constraints and time-dependent service costs. This problem is motivated by winter gritting applications where the “timing” of each intervention is crucial. The exact problem-solving approach reported here first transforms the arc routing problem into an equivalent node routing problem. Then, a column generation scheme is used to solve the latter. The master problem is a classical set covering problem, while the subproblems are time-dependent shortest path problems with resource constraints. These subproblems are solved using an extension of a previously developed algorithm. Computational results are reported on problems derived from a set of classical instances of the vehicle routing problem with time windows.     

On the enrouting protocol problem under uncertainty

In this paper we present a two-stage stochastic mixed 0–1 dynamic multicommodity model and algorithm for determining the enrouting protocol in the telecommunications network under uncertainty. Given the network connectivity, node processing and buffer and arc flow capacity, the aim is to determine the outgoing arc for the information flow reaching a given node for each destination terminal node (i.e., obtaining the route to be followed by the information flow from each origin terminal node to each destination terminal node). The origin–destination (O–D) flow matrix is given by the number of information packets to be sent from the origin terminal nodes to the destination terminal nodes along a given time horizon, i.e., a call scale. The uncertainty in the O–D flow matrix is treated via a scenario tree approach. The main goal is to minimize a composite function of the expected lost information, a penalization of the deviation from the FIFO strategy on the information flow entering the network, and the expected number of nodes visited by the information packets. A mixture of an enrouting arc generation scheme and a genetic algorithm for obtaining the enrouting protocols over the scenarios is presented. The tool presented in this paper could be used for simulating the enrouting protocols to analyze the saturation of the network, but it has a time constraint for real time operation. Faster algorithms are needed to define the routing tables during the operation stage. Computational experience is reported.     

Algorithms for the quickest path problem and the reliable quickest path problem

The quickest path problem consists of finding a path in a directed network to transmit a given amount of items from an origin node to a destination node with minimal transmission time, when the transmission time depends on both the traversal times of the arcs, or lead time, and the rates of flow along arcs, or capacity. In telecommunications networks, arcs often also have an associated operational probability of the transmission being fault free. The reliability of a path is defined as the product of the operational probabilities of its arcs. The reliability as well as the transmission time are of interest. In this paper, algorithms are proposed to solve the quickest path problem as well as the problem of identifying the quickest path whose reliability is not lower than a given threshold. The algorithms rely on both the properties of a network which turns the computation of a quickest path into the computation of a shortest path and the fact that the reliability of a path can be evaluated through the reliability of the ordered sequence of its arcs. Other constraints on resources consumed, on the number of arcs of the path, etc. can also be managed with the same algorithms.     

The capacitated p-hub median problem with integral constraints: An application to a Chinese air cargo network

Consolidation at hubs in a pure hub-and-spoke network eliminates partial center-to-center direct loads, resulting in savings in transportation costs. In this research, we propose a general capacitated p-hub median model, with economies of scale and integral constraints on the paths. This model requires the selection of a specific p among a set of candidate hubs so that the total cost on the resulting pure capacitated hub-and-spoke network is minimized while simultaneously meeting origin–destination demands, operational capacity and singular path constraints. We explored the problem structure and developed a genetic algorithm using the path for encoding. This algorithm is capable of determining local optimality within less than 0.1% of the Lagrangian relaxation lower bounds on our Chinese air cargo network testing case and has reasonable computational times. The study showed that designating airports with high pickups or deliveries as hubs resulted in a high percentage of origin–destination pairs (ODs) in direct deliveries. Furthermore, the more hubs there are, the higher the direct share and the less likely for double rehandles. Sensitivity analysis on the discount rate showed that the economies of scale on trunk lines of hub-and-spoke networks may have a substantial impact on both the operating costs and the route patterns.     

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.