Optimisation of gravity-fed water distribution network design: A critical review

This paper surveys the literature on the optimisation of water distribution network design. The water distribution network design (WDND) optimisation problem entails finding the material and diameter of each pipe in the network so that the total cost of the network is minimised without violating any hydraulic constraints. This is a difficult combinatorial optimisation problem, in which decision variables are discrete and both cost function and constraints are non-linear. Over the past 30 years, a large number of methods, especially in the field of (meta) heuristics, have been developed to solve this problem, most of which obtain good results on the available benchmark networks. In addition to outlining the basic features of each method, a detailed computational comparison is presented. Based on this comparison, some issues with the current state of the art in this domain are discussed, and some future research directions are suggested. Additionally, the need for an adequate set of benchmark instances is motivated, and the minimal requirements for an instance set generator are discussed.     

Implementation of scatter search for multi-objective optimization: a comparative study

Interest in the design of efficient meta-heuristics for the application to combinatorial optimization problems is growing rapidly. The optimal design of water distribution networks is an important optimization problem which consists of finding the best way of conveying water from the sources to the users, thus satisfying their requirements. The efficient design of looped networks is a much more complex problem than the design of branched ones, but their greater reliability can compensate for the increase in cost when closing some loops. Mathematically, this is a non-linear optimization problem, constrained to a combinatorial space, since the diameters are discrete and it has a very large number of local solutions. Many works have dealt with the minimization of the cost of the network but few have considered their cost and reliability simultaneously. The aim of this paper is to evaluate the performance of an implementation of Scatter Search in a multi-objective formulation of this problem. Results obtained in three benchmark networks show that the method here proposed performs accurately well in comparison with other multi-objective approaches also implemented.     

Effective Relaxations and Partitioning Schemes for Solving Water Distribution Network Design Problems to Global Optimality

In this paper, we address the development of a global optimization procedure for the problem of designing a water distribution network, including the case of expanding an already existing system, that satisfies specified flow demands at stated pressure head requirements. The proposed approach significantly improves upon a previous method of Sherali et al. (1998) by way of adopting tighter polyhedral relaxations, and more effective partitioning strategies in concert with a maximal spanning tree-based branching variable selection procedure. Computational experience on three standard test problems from the literature is provided to evaluate the proposed procedure. For all these problems, proven global optimal solutions within a tolerance of 10^–4% and/or within 1$ of optimality are obtained. In particular, the two larger instances of the Hanoi and the New York test networks are solved to global optimality for the very first time in the literature. A new real network design test problem based on the Town of Blacksburg Water Distribution System is also offered to be included in the available library of test cases, and related computational results are presented.     

Worst-case performance of Wong's Steiner tree heuristic

A study of the worst-case performance of Wong's heuristic for the Steiner problem in directed networks (SPDN) is presented in this paper.SPDN is a classic combinatorial optimization problem having the status of a very difficult problem (NP-hard problem) and it is known as an optimization model for a broad class of problems in networks. Several exact and heuristic approaches have been designed for SPDN in the last twenty five years.Some papers analyze theoretical and experimental behavior of heuristics for SPDN, specially for undirected networks, but none of these has studied the worst-case performance of Wong's heuristic. In this paper, we find a lower bound for that performance and show that this bound is consistent with comparable results in the literature on SPDN and its undirected version.     

A pseudo-polynomial algorithm for optimal capacitor placement on electric power distribution networks

Allocation of shunt capacitor banks on radial electric power distribution networks allow reduction of energy losses and aggregated benefits. Four decades ago Durán proposed the use of dynamic programming to find optimal capacitor placement on these networks; however, with the restricting assumption of single-ended networks, which precluded its application to real capacitor allocation problems. Subsequently heuristic methods prevailed in the capacitor allocation literature. Here the Extended Dynamic Programming Approach (EDP) lifts Durán’s restricting assumption; a richer definition of state and the projection of multidimensional informations into equivalent one-dimensional representations are the supporting concepts. In addition to allow consideration of multi-ended networks, EDP deals with other requirements of capacitor allocation studies, including the use of both fixed and switched capacitors and representation of voltage drops along the networks. When switched capacitors are considered the optimization procedure also solves the capacitor control problem, obtaining the best tap adjustments for them. Case studies with real scale distribution networks put into perspective the benefits of the methodology; EDP has the appeal of providing global optimal solutions with pseudo-polynomial computational complexity in the worst-case, and with linear complexity for practical applications.     

Stochastic activity networks with truncated exponential activity times

This paper presents an approach for using right-truncated exponentially distributed random variables to model activity times in stochastic activity networks. The advantages of using the right-truncated exponential distribution are discussed. The moments of a project completion time using the proposed distribution are derived and compared with other estimated moments in literature.     

A cross entropy approach to design of reliable networks

One of the most important parameters determining the performance of communication networks is network reliability. The network reliability strongly depends on not only topological layout of the communication networks but also reliability and availability of the communication facilities. The selection of optimal network topology is an NP-hard problem so that computation time of enumeration-based methods grows exponentially with network size. This paper presents a new solution approach based on cross-entropy method, called NCE, to design of communication networks. The design problem is to find a network topology with minimum cost such that all-terminal reliability is not less than a given level of reliability. To investigate the effectiveness of the proposed NCE, comparisons with other heuristic approaches given in the literature for the design problem are carried out in a three-stage experimental study. Computational results show that NCE is an effective heuristic approach to design of reliable networks.     

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.²     

City-courier routing and scheduling problems

This research seeks to propose innovative routing and scheduling strategies to help city couriers reduce operating costs and enhance service level. The strategies are realized by constructing a new type of routing and scheduling problem. The problem directly takes into account the inherent physical and operating constraints associated with riding in city distribution networks, which makes the problem involve multiple objectives and visiting specified nodes and arcs. Through network transformations, this study first formulates the city-courier routing and scheduling problem as a multi-objective multiple traveling salesman problem with strict time windows (MOMTSPSTW) that is NP-hard and new to the literature, and then proposes a multi-objective Scatter Search framework that seeks to find the set of Pareto-optimal solutions to the problem. Various new and improved sub-procedures are embedded in the solution framework. This is followed by an empirical study that shows and analyzes the results of applying the proposed method to a real-life city-courier routing and scheduling problem.     

Multi-period traffic routing in satellite networks

We introduce a traffic routing problem over an extended planning horizon that appears in geosynchronous satellite networks. Unlike terrestrial (e.g., fiber optic) networks, routing on a satellite network is not transparent to the customers. As a result, a route change is associated with significant monetary penalties that are usually in the form of discounts (up to 40%) offered by the satellite provider to the customer that is affected. The notion of these rerouting penalties requires the network planners to explicitly consider these penalties in their routing decisions over multiple time periods and introduces novel challenges that have not been considered previously in the literature. We develop a branch-and-price-and-cut procedure to solve this problem and describe an algorithm for the associated pricing problem. Our computational work demonstrates that the use of a multi-period optimization procedure as opposed to a myopic period-by-period approach can result in cost reductions up to 13% depending on problem characteristics and network size considered. These cost reductions correspond to potential savings of several hundred million dollars for large satellite providers.     

Gröbner bases for solving ΔQ-equations in water distribution networks

The analysis of water distribution network is of great interest to hydraulic engineers. Although the water distribution network has been extensively studied for the last decades, there are still many unsolved problems awaiting clarification. In this paper, an algorithm is presented that describes a computationally efficient technique for water distribution networks based on Gröbner basis method. Gröbner basis algorithm provides the exact algorithmic solutions for solving the system of equations. However, Gröbner algorithm works only for polynomials and moreover for a large scale network, it takes a long CPU time. Hence, we present two other algorithms that work for non-polynomials and large scale problems. Three examples are presented to show the effectiveness of Gröbner basis method compared with Hardy Cross method, linear theory and Gradient method.     

A cutting plane procedure for the travelling salesman problem on road networks

A cutting plane algorithm for the exact solution of the symmetric travelling salesman problem (TSP) is proposed. The real tours on a usually incomplete road network, which are in general non-Hamiltonian, are characterized directly by an integer linear programming model. The algorithm generates special cutting planes for this model. Computational results for real road networks with up to 292 visiting places are reported, as well as for classical problems of the literature with up to 120 cities. Some of the latter problems have been solved for the first time with a pure cutting plane approach.     

Wireless three-hop networks with stealing II: exact solutions through boundary value problems

We study the stationary distribution of a random walk in the quarter plane arising in the study of three-hop wireless networks with stealing. Our motivation is to find exact tail asymptotics (beyond logarithmic estimates) for the marginal distributions, which requires an exact solution for the bivariate generating function describing the stationary distribution. This exact solution is determined via the theory of boundary value problems. Although this is a classical approach, the present random walk exhibits some salient features. In fact, to determine the exact tail asymptotics, the random walk presents several unprecedented challenges related to conformal mappings and analytic continuation. We address these challenges by formulating a boundary value problem different from the one usually seen in the literature.     

树状网络上的Web代理服务器最优放置问题

一般网络上Web代理服务器(Web proxy)最优放置问题是一个NP困难问题.此文讨论树状网络上的最优放置问题,改进了已有结果,得到了一个时间复杂度为O(nhk)的多项式时间算法,这里n为网络结点数,h为树的高度,而k为要放置的代理服务器个数.     

Optimizing revenue in CDMA networks under demand uncertainty

Mathematical programming models for telecommunications network design are prevalent in the literature, but little research has been reported on stochastic models for cellular networks. We present a stochastic revenue optimization model for CDMA networks inspired by bid pricing models from the airline industry. We describe the optimality conditions for the model and develop a supergradient algorithm to solve it. We provide computational results that show the effects of the distribution and variance of demand. Finally, we discuss areas of future research, including a method to optimize the locations of the towers.     

A novel method for optimal capacitor placement and sizing in distribution systems with nonlinear loads and DG using GA

A genetic algorithm (GA) is proposed for simultaneous power quality improvement, optimal placement and sizing of fixed capacitor banks in radial distribution networks with nonlinear loads and distributed generation (DG) imposing voltage–current harmonics. In distribution systems, nonlinear loads and DGs are often considered as harmonic sources. For optimizing capacitor placement and sizing in the distribution system, objective function includes the cost of power losses, energy losses and capacitor banks. At the same time, constraints include voltage limits, number/size of installed capacitors (at each bus) and the power quality limits of standard IEEE-519. In this study, new fitness function is used to solve the constrained optimization problem with discrete variables. Simulation results for two IEEE distorted networks (18-bus and 33-bus test systems) are presented and solutions of the proposed method are compared with those of previous methods described in the literature. The main contribution of this paper is computing the (near) global solution with a lower probability of getting stuck at a local optimum and weak dependency on initial conditions, while avoiding numerical problems in large systems. Results show that proposed method could be effectively used for optimal capacitor placement and sizing in distorted distribution systems.     

Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems

We consider the problem of optimizing a novel acoustic leakage detection system for urban water distribution networks. The system is composed of a number of detectors and transponders to be placed in a choice of hydrants such as to provide a desired coverage under given budget restrictions. The problem is modeled as a particular Prize-Collecting Steiner Arborescence Problem. We present a branch-and-cut-and-bound approach taking advantage of the special structure at hand which performs well when compared to other approaches. Furthermore, using a suitable stopping criterion, we obtain approximations of provably excellent quality (in most cases actually optimal solutions). The test bed includes the real water distribution network from the Lausanne region, as well as carefully randomly generated realistic instances.     

A branch-and-bound approach for maximum quasi-cliques

Detecting quasi-cliques in graphs is a useful tool for detecting dense clusters in graph-based data mining. Particularly in large-scale data sets that are error-prone, cliques are overly restrictive and impractical. Quasi-clique detection has been accomplished using heuristic approaches in various applications of graph-based data mining in protein interaction networks, gene co-expression networks, and telecommunication networks. Quasi-cliques are not hereditary, in the sense that every subset of a quasi-clique need not be a quasi-clique. This lack of heredity introduces interesting challenges in the development of exact algorithms to detect maximum cardinality quasi-cliques. The only exact approaches for this problem are limited to two mixed integer programming formulations that were recently proposed in the literature. The main contribution of this article is a new combinatorial branch-and-bound algorithm for the maximum quasi-clique problem.     

Synchronization in cross-docking networks: A research classification and framework

Cross-docking is a distribution strategy that enables the consolidation of less-than-truckload shipments into full truckloads without long-term storage. Due to the absence of a storage buffer inside a cross-dock, local and network-wide cross-docking operations need to be carefully synchronized. This paper proposes a framework specifying the interdependencies between different cross-docking problem aspects with the aim to support future research in developing decision models with practical and scientific relevance. The paper also presents a new general classification scheme for cross-docking research based on the inputs and outputs for each problem aspect. After classifying the existing cross-docking research, we conclude that the overwhelming majority of papers fail to consider the synchronization of local and network-wide cross-docking operations. Lastly, to highlight the importance of synchronization in cross-docking networks, two real-life illustrative problems are described that are not yet addressed in the literature.