An optimal capacity assignment for the robust design problem in capacitated flow networks

This paper proposes an exact algorithm to solve the robust design problem in a capacitated flow network in which each edge has several possible capacities. A capacitated flow network is popular in our daily life. For example, the computer network, the power transmission network, or even the supply chain network are capacitated flow networks. In practice, such network may suffer failure, partial failure or maintenance. Therefore, each edge in the network should be assigned sufficient capacity to keep the network functioning normally. The robust design problem (RDP) in a capacitated flow network is to search for the minimum capacity assignment of each edge such that the network still survived even under the edge’s failure. However, how to optimally assign the capacity to each edge is not an easy task. Although this kind of problem was known of NP-hard, this paper proposes an efficient exact algorithm to search for the optimal solutions for such a network and illustrates the efficiency of the proposed algorithm by numerical examples.     

An integrated approach for collection network design,capacity planning and vehicle routing in reverse logistics

This study considers network design, capacity planning and vehicle routing for collection systems in reverse logistics. The network design and capacity planning problems are to determine the static locations and capacities of collection points as well as the dynamic allocations of demand points to the opened collection points over a planning horizon, and the vehicle routing problem is to determine the number and routes of vehicles in such a way that each collection point must be visited exactly once by one vehicle starting and terminating at the depot while satisfying the return demands at collection points and the vehicle capacity. The objective is to minimize the sum of fixed costs to open collection points and to acquire vehicles as well as variable costs to transport returns at demand points to the opened collection points and travel the opened collection points by vehicles. Unlike the location-routing problems, the integrated problem considered in this study has several features: multi-period dynamic model, capacity planning for collection points, maximum allowable collection distances, etc. To solve the integrated problem, two types of tabu search algorithms, hierarchical and integrated ones, are suggested, and their test results are reported. In particular, the efficiency of the integrated approach is shown by comparing the two algorithm types.     

Survivable capacitated network design problem: new formulation and Lagrangean relaxation

This work is focused on the analysis of the survivable capacitated network design problem. This problem can be stated as follows: Given a supply network with point-to-point traffic demands, specific survivability requirements, a set of available capacity ranges and their corresponding discrete costs for each arc, find minimum cost capacity expansions such that these demands can be met even if a network component fails. Solving this problem consists of selecting the links and their capacity, as well as the routings for each demand in every failure situation. This type of problem can be shown to be NP-hard. A new linear mixed-integer mathematical programming formulation is presented. An effective solution procedure based on Lagrangean relaxation is developed. Comparison heuristics and improvement heuristics are also described. Computational results using these procedures on different sizes of randomly generated networks are reported.     

A model for the capacitated,hop-constrained,per-packet wireless mesh network design problem

Three critical factors in wireless mesh network design are the number of hops between supply and demand points, the bandwidth capacity of the transport media, and the technique used to route packets within the network. Most previous research on network design has focused on the issue of hop constraints and/or bandwidth capacity in wired networks while assuming a per-flow routing scheme. However, networks that employ per-packet routing schemes in wireless networks involve different design issues that are unique to this type of problem. We present a methodology for designing wireless mesh networks that consider bandwidth capacity, hop constraints, and profitability for networks employing a per-packet routing system.     

A dual ascent approach to the fixed-charge capacitated network design problem

In this paper we consider the problem of constructing a network over which a number of commodities are to be transported. Fixed costs are associated to the construction of network arcs and variable costs are associated to routing of commodities. In addition, one capacity constraint is related to each arc. The problem is to determine a network design that minimizes the total cost; i.e., it balances the construction and operating costs. A dual ascent procedure for finding improved lower bounds and near-optimal solutions for the fixed-charge capacitated network design problem is proposed. The method is shown to generate tighter lower bounds than the linear programming relaxation of the problem.     

Topological Design of Survivable Mesh-Based Transport Networks

The advent of Sonet and DWDM mesh-restorable networks which contain explicit reservations of spare capacity for restoration presents a new problem in topological network design. On the one hand, the routing of working flows wants a sparse tree-like graph for minimization of the classic fixed charge plus routing (FCR) costs. On the other hand, restorability requires a closed (bi-connected) and preferably high-degree topology for efficient sharing of spare capacity allocations (SCA) for restoration over non-simultaneous failure scenarios. These diametrically opposed considerations underlie the determination of an optimum physical facilities graph for a broadband network provider. Standalone instances of each constituent problem are NP-hard. The full problem of simultaneously optimizing mesh-restorable topology, routing, and sparing is therefore very difficult computationally. Following a comprehensive survey of prior work on topological design problems, we provide a {1–0} MIP formulation for the complete mesh-restorable design problem and also propose a novel three-stage heuristic. The heuristic is based on the hypothesis that the union set of edges obtained from separate FCR and SCA sub-problems constitutes an effective topology space within which to solve a restricted instance of the full problem. Where fully optimal reference solutions are obtainable the heuristic shows less than 8% gaps but runs in minutes as opposed to days. In other test cases the reference problem cannot be solved to optimality and we can only report that heuristic results obtained in minutes are not improved upon by CPLEX running the full problem for 6 to 18 hours. The computational behavior we observe gives insight for further work based on an appreciation of the problem as embodying unexpectedly difficult feasibility apects, as well as optimality aspects.     

Urban rapid transit network capacity expansion

This paper examines a multi-period capacity expansion problem for rapid transit network design. The capacity expansion is realized through the location of train alignments and stations in an urban traffic context by selecting the time periods. The model maximizes the public transportation demand using a limited budget and designing lines for each period. The location problem incorporates the user decisions about mode and route. The network capacity expansion is a long-term planning problem because the network is built over several periods, in which the data (demand, resource price, etc.) are changing like the real problem changes. This complex problem cannot be solved by branch and bound, and for this reason, a heuristic approach has been defined in order to solve it. Both methods have been experimented in test networks.     

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.     

Parking Capacity and Pricing in Park'n Ride Trips: A Continuous Equilibrium Network Design Problem

In this paper we consider the problem of designing parking facilities for park'n ride trips. We present a new continuous equilibrium network design problem to decide the capacity and fare of these parking lots at a tactical level. We assume that the parking facilities have already been located and other topological decisions have already been taken.The modeling approach proposed is mathematical programming with equilibrium constraints. In the outer optimization problem, a central Authority evaluates the performance of the transport network for each network design decision. In the inner problem a multimodal traffic assignment with combined modes, formulated as a variational inequality problem, generates the share demand for modes of transportation, and for parking facilities as a function of the design variables of the parking lots. The objective is to make optimal parking investment and pricing decisions in order to minimize the total travel cost in a subnetwork of the multimodal transportation system.We present a new development in model formulation based on the use of generalized parking link cost as a design variable.The bilevel model is solved by a simulated annealing algorithm applied to the continuous and non-negative design decision variables. Numerical tests are reported in order to illustrate the use of the model, and the ability of the approach to solve applications of moderate size.     

Optimal double-resource assignment for the robust design problem in multistate computer networks

This paper proposes a novel approach to get the exact optimal double-resource assignment for the robust design problem in multistate computer networks. A multistate computer network consists of links and vertices where both kinds of resources may have several states due to failure, partial failure or maintenance. Therefore, each link (vertex) in the network should be assigned sufficient capacity to keep the network functioning normally. The robust design problem (RDP) in a multistate computer network (MCN) is to search for the minimum capacity assignment of each link and vertex such that the network still survived even under both kinds of failures. However, how to optimally assign the capacity to each resource is not an easy task. This paper proposes an efficient approach to do such assignment and illustrates the efficiency of the proposed approach by some numerical examples.     

A non-smooth model for signalized road network design problems

A signalized road network is considered where the set of link capacity expansions and signal setting variables are simultaneously determined. This paper addresses a new optimization scheme for a signalized road network design problem (SRNDP). A SRNDP can be formulated as a mathematical program with equilibrium constraints (MPEC) where user equilibrium is expressed as a variational inequality problem. Due to non-differentiability of the perturbed solutions in equilibrium constraints, a non-smooth model is established. A bundle subgradient projection (BSP) method is presented with global convergence. Numerical calculations are conducted on a real data city road network and large-scale grid networks where promising results are obtained.     

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.     

Internet protocol network design with uncertain demand

We present a case study concerning the design and dimensioning of the internet protocol network of TDC, the largest Danish network operator. Due to historical reasons the number of points of presence (POPs) in the network has reached a level, believed to be too high. To point out potential POPs for dismantling, we consider a network planning problem concerning dimensioning of the POPs and capacity expansion of the transmission links of the network. This problem is formulated as a two-stage stochastic program using a finite number of scenarios to describe the uncertain outcome of future demand. The problem is then solved by an L-shaped algorithm, and we report results of our computational experiments.     

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.     

A ring-mesh topology design problem for optical transport networks

This paper deals with a ring-mesh network design problem arising from the deployment of an optical transport network. The problem seeks to find an optimal clustering of traffic demands in the network such that the total cost of optical add-drop multiplexer (OADM) and optical cross-connect (OXC) is minimized, while satisfying the OADM ring capacity constraint, the node cardinality constraint, and the OXC capacity constraint. We formulate the problem as an integer programming model and propose several alternative modeling techniques designed to improve the mathematical representation of the problem. We then develop various classes of valid inequalities to tighten the mathematical formulation of the problem and describe an algorithmic approach that coordinates tailored routines with a commercial solver CPLEX. We also propose an effective tabu search procedure for finding a good feasible solution as well as for providing a good incumbent solution for the column generation based heuristic procedure that enhances the solvability of the problem. Computational results exhibit the viability of the proposed method.     

Polyhedral results for the edge capacity polytope

Network loading problems occur in the design of telecommunication networks, in many different settings. For instance, bifurcated or non-bifurcated routing (also called splittable and unsplittable) can be considered. In most settings, the same polyhedral structures return. A better understanding of these structures therefore can have a major impact on the tractability of polyhedral-guided solution methods. In this paper, we investigate the polytopes of the problem restricted to one arc/edge of the network (the undirected/directed edge capacity problem) for the non-bifurcated routing case.?As an example, one of the basic variants of network loading is described, including an integer linear programming formulation. As the edge capacity problems are relaxations of this network loading problem, their polytopes are intimately related. We give conditions under which the inequalities of the edge capacity polytopes define facets of the network loading polytope. We describe classes of strong valid inequalities for the edge capacity polytopes, and we derive conditions under which these constraints define facets. For the diverse classes the complexity of lifting projected variables is stated.?The derived inequalities are tested on (i) the edge capacity problem itself and (ii) the described variant of the network loading problem. The results show that the inequalities substantially reduce the number of nodes needed in a branch-and-cut approach. Moreover, they show the importance of the edge subproblem for solving network loading problems. Received: September 2000 / Accepted: October 2001?Published online March 27, 2002     

Designing a two-echelon distribution network under demand uncertainty

This paper proposes a comprehensive methodology for the stochastic multi-period two-echelon distribution network design problem (2E-DDP) where product flows to ship-to-points are directed from an upper layer of primary warehouses to distribution platforms (DPs) before being transported to the ship-to-points. A temporal hierarchy characterizes the design level dealing with DP location and capacity decisions, as well as the operational level involving transportation decisions as origin-destination flows. These design decisions must be calibrated to minimize the expected distribution cost associated with the two-echelon transportation schema on this network under stochastic demand. We consider a multi-period planning horizon where demand varies dynamically from one planning period to the next. Thus, the design of the two-echelon distribution network under uncertain customer demand gives rise to a complex multi-stage decisional problem. Given the strategic structure of the problem, we introduce alternative modeling approaches based on two-stage stochastic programming with recourse. We solve the resulting models using a Benders decomposition approach. The size of the scenario set is tuned using the sample average approximation (SAA) approach. Then, a scenario-based evaluation procedure is introduced to post-evaluate the design solutions obtained. We conduct extensive computational experiments based on several types of instances to validate the proposed models and assess the efficiency of the solution approaches. The evaluation of the quality of the stochastic solution underlines the impact of uncertainty in the two-echelon distribution network design problem (2E-DDP).     

The final answer to the complexity of a basic problem in resilient network design

To provide resilience to failures of the multi-commodity flow network, either in the failure-free state flows can be routed along multiple paths and over-dimensioned, or whenever a failure occurs flows can be restored along unaffected paths. The complexity of the network design depends on the selected method of providing resilience and on a number of design options—whether single or multiple commodities and single- or multi-element failures are considered, if the reaction to failures is dependent or independent on the failure, which mechanism of capacity release and reuse is applied, etc. For almost all combinations of those choices either the corresponding design problem has already been shown to be NP-hard or a compact linear programming formulation of the problem has been provided. The only case that has resisted an answer is when flows are restored in a state-dependent manner using the stub release mechanism. In this paper it is proved that the corresponding network design problem is NP-hard even for a single commodity and for single-element failures. The proof is based on the reduction of the Hamiltonian path problem.     

A modified active set algorithm for transportation discrete network design bi-level problem

Transportation discrete network design problem (DNDP) is about how to modify an existing network of roads and highways in order to improve its total system travel time, and the candidate road building or expansion plan can only be added as a whole. DNDP can be formulated into a bi-level problem with binary variables. An active set algorithm has been proposed to solve the bi-level discrete network design problem, while it made an assumption that the capacity increase and construction cost of each road are based on the number of lanes. This paper considers a more general case when the capacity increase and construction cost are specified for each candidate plan. This paper also uses numerical methods instead of solvers to solve each step, so it provides a more direct understanding and control of the algorithm and running procedure. By analyzing the differences and getting corresponding solving methods, a modified active set algorithm is proposed in the paper. In the implementation of the algorithm and the validation, we use binary numeral system and ternary numeral system to avoid too many layers of loop and save storage space. Numerical experiments show the correctness and efficiency of the proposed modified active set algorithm.