Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

The Steiner connectivity problem

The Steiner connectivity problem has the same significance for line planning in public transport as the Steiner tree problem for telecommunication network design. It consists in finding a minimum cost set of elementary paths to connect a subset of nodes in an undirected graph and is, therefore, a generalization of the Steiner tree problem. We propose an extended directed cut formulation for the problem which is, in comparison to the canonical undirected cut formulation, provably strong, implying, e.g., a class of facet defining Steiner partition inequalities. Since a direct application of this formulation is computationally intractable for large instances, we develop a partial projection method to produce a strong relaxation in the space of canonical variables that approximates the extended formulation. We also investigate the separation of Steiner partition inequalities and give computational evidence that these inequalities essentially close the gap between undirected and extended directed cut formulation. Using these techniques, large Steiner connectivity problems with up to 900 nodes can be solved within reasonable optimality gaps of typically less than five percent.     

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.     

On the analysis of optimization problems in arc-dependent networks

This paper is concerned with the design and analysis of algorithms for optimization problems in arc-dependent networks. A network is said to be arc-dependent if the cost of an arc $a$ depends upon the arc taken to enter $a$. These networks are fundamentally different from traditional networks in which the cost associated with an arc is a fixed constant and part of the input. We first study the arc-dependent shortest path (ADSP) problem, which is also known as the suffix-1 path-dependent shortest path problem in the literature. This problem has a polynomial time solution if the shortest paths are not required to be simple. The ADSP problem finds applications in a number of domains, including highway engineering, turn penalties and prohibitions, and fare rebates. In this paper, we are interested in the ADSP problem when restricted to simple paths. We call this restricted version the simple arc-dependent shortest path (SADSP) problem. We show that the SADSP problem is NP-complete. We present inapproximability results and an exact exponential algorithm for this problem. We also extend our results for the longest path problem in arc-dependent networks. Additionally, we explore the problem of detecting negative cycles in arc-dependent networks and discuss its computational complexity. Our results include variants of the negative cycle detection problem such as longest, shortest, heaviest, and lightest negative simple cycles.²     

A deep-submicron steiner tree

An A-Tree is a rectilinear Steiner tree in which every sink is connected to a driver by a shortest length path, while simultaneously minimizing total wire length. This paper presents a polynomial approximation algorithm for the generalized version of an A-Tree problem with upper-bounded delays along each path from the driver to the sinks and with restrictions on the number of Steiner nodes. We refer to it as “Deep-submicron Steiner tree”, as minimizing the number of Steiner nodes is crucial for signal integrity issues in deep-submicron Very-Large-Scaled-Integrated-circuit (VLSI) designs. The idea behind the algorithm is to control two parameters in order to construct a feasible (with respect to the paths delays and the number of Steiner nodes) tree of small cost.The simulation results show the high efficiency of our approach.     

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.     

IP modeling of the survivable hop constrained connected facility location problem

We consider a generalized version of the rooted connected facility location problem which occurs in planning of telecommunication networks with both survivability and hop-length constraints. Given a set of client nodes, a set of potential facility nodes including one predetermined root facility, a set of optional Steiner nodes, and the set of the potential connections among these nodes, that task is to decide which facilities to open, how to assign the clients to the open facilities, and how to interconnect the open facilities in such a way, that the resulting network contains at least λ edge-disjoint paths, each containing at most H edges, between the root and each open facility and that the total cost for opening facilities and installing connections is minimal. We study two IP models for this problem and present a branch-and-cut algorithm based on Benders decomposition for finding its solution. Finally, we report computational results.     

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.     

Loose Cover of Graphs

This paper introduces a new definition of embedding a local structure to a given network, called loose cover of graphs. We derive several basic properties on the notion of loose cover, which includes transitivity, maximality, and the computational complexity of finding a loose cover by paths and cycles. In particular, we show that the decision problem is in P if the given local structure is a path with three or less vertices, while it is NP-complete for paths consisting of six or more vertices.     

An Algorithm for Solving the Shortest Path Improvement Problem on Rooted Trees Under Unit Hamming Distance

Shortest path problems play important roles in computer science, communication networks, and transportation networks. In a shortest path improvement problem under unit Hamming distance, an edge-weighted graph with a set of source–terminal pairs is given. The objective is to modify the weights of the edges at a minimum cost under unit Hamming distance such that the modified distances of the shortest paths between some given sources and terminals are upper bounded by the given values. As the shortest path improvement problem is NP-hard, it is meaningful to analyze the complexity of the shortest path improvement problem defined on rooted trees with one common source. We first present a preprocessing algorithm to normalize the problem. We then present the proofs of some properties of the optimal solutions to the problem. A dynamic programming algorithm is proposed for the problem, and its time complexity is analyzed. A comparison of the computational experiments of the dynamic programming algorithm and MATLAB functions shows that the algorithm is efficient although its worst-case complexity is exponential time.     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].     

The first <Emphasis Type="Italic">K</Emphasis> minimum cost paths in a time-schedule network

The time-constrained shortest path problem is an important generalisation of the classical shortest path problem and in recent years has attracted much research interest. We consider a time-schedule network, where every node in the network has a list of pre-specified departure times and departure from a node may take place only at one of these departure times. The objective of this paper is to find the first K minimum cost simple paths subject to a total time constraint. An efficient polynomial time algorithm is developed. It is also demonstrated that the algorithm can be modified for finding the first K paths for all possible values of total time.     

灾后运输网络中的最短路修复合作博弈

在最短路修复合作博弈中,当灾后运输网络规模较大时,最优成本分摊问题难以直接求解。基于拉格朗日松弛理论,提出了一种最短路修复合作博弈成本分摊算法。该算法将最短路修复合作博弈分解为两个具有特殊结构的子博弈,进而利用两个子博弈的结构特性,可以{高效地}求解出二者的最优成本分摊,将这两个成本分摊相加,可以获得原博弈的一个近乎最优的稳定成本分摊。结果部分既包含运输网络的随机仿真,也包含玉树地震灾区的现实模拟,无论数据来源于仿真还是现实,该算法都能在短时间内为最短路修复合作博弈提供稳定的成本分摊方案。     

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.     

Minimal curvature-constrained networks

This paper introduces an exact algorithm for the construction of a shortest curvature-constrained network interconnecting a given set of directed points in the plane and a gradient descent method for doing so in 3D space. Such a network will be referred to as a minimum Dubins tree, since its edges are Dubins paths (or slight variants thereof). The problem of constructing a minimum Dubins tree appears in the context of underground mining optimisation, where the objective is to construct a least-cost network of tunnels navigable by trucks with a minimum turning radius. The Dubins tree problem is similar to the Steiner tree problem, except the terminals are directed and there is a curvature constraint. We propose the minimum curvature-constrained Steiner point algorithm for determining the optimal location of the Steiner point in a 3-terminal network. We show that when two terminals are fixed and the third varied in the planar version of the problem, the Steiner point traces out a limaçon.     

Reroute sequence planning in telecommunication networks and compact vector summation

The paper deals with the reroute sequence planning in telecommunication networks. Initially, we are given communication requests between terminal pairs and a path system which is able to satisfy these demands while respecting the physical link capacities. A reconfiguration problem arises when the path set is recalculated by a global optimization method for achieving a better resource utilization. After the recalculation the paths in the routing have to be changed to the optimized ones in the working network. In this case, a sequence of one by one reroutings have to be found with the constraint that the capacities should not be violated and no one of the demands can become unsatisfied during the reroute process. Provided that the (initial and final) free capacities are large enough, such a permutation can be computed. The paper deals with theoretical results giving bounds for these free capacities, with vector-sum and discrepancy methods.     

A simplification of the double-sweep algorithm to solve the k-shortest path problem

In this paper, we define the k-shortest path problem, which will be used to model the problem of routing aircraft through a network of airfields. This problem finds the optimal alternative routes from one or more origins to one or more destinations. We solve this problem using the double-sweep algorithm. We present a simplification to the double-sweep algorithm, and show that this simplification reduces the computational complexity of the algorithm by a factor of k. We prove that the simplified double-sweep algorithm converges. Finally, we demonstrate this algorithm on a small airlift network.     

A multicast problem with shared risk cost

In this paper, we study a minimum cost multicast problem on a network with shared risk link groups (SRLGs). Each SRLG contains a set of arcs with a common risk, and there is a cost associated with it. The objective of the problem is to find a multicast tree from the source to a set of destinations with minimum transmission cost and risk cost. We present a basic model for the multicast problem with shared risk cost (MCSR) based on the well-known multicommodity flow formulation for the Steiner tree problem (Goemans and Myung in Networks 1:19–28, 1993; Polzin and Daneshmand in Discrete Applied Mathematics 112(1–3): 241–261, 2001). We propose a set of strong valid inequalities to tighten the linear relaxation of the basic model. We also present a mathematical model for undirected MCSR. The computational results of real life test instances demonstrate that the new valid inequalities significantly improve the linear relaxation bounds of the basic model, and reduce the total computation time by half in average.     

Gradient-Constrained Minimum Networks. III. Fixed Topology

The gradient-constrained Steiner tree problem asks for a shortest total length network interconnecting a given set of points in 3-space, where the length of each edge of the network is determined by embedding it as a curve with absolute gradient no more than a given positive value m, and the network may contain additional nodes known as Steiner points. We study the problem for a fixed topology, and show that, apart from a few easily classified exceptions, if the positions of the Steiner points are such that the tree is not minimum for the given topology, then there exists a length reducing perturbation that moves exactly 1 or 2 Steiner points. In the conclusion, we discuss the application of this work to a heuristic algorithm for solving the global problem (across all topologies).     

Fast paths in large-scale dynamic road networks

Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger part of the road network. We provide computational results that show the efficacy of our approach.