Traditionally, transportation road networks have been designed for minimal congestion. Unfortunately, such approaches do not guarantee minimal vehicle emissions. Given the negative impacts of vehicle pollutants as well as tighter national air quality standards, it is critical for regions to be able to identify capacity modifications to road networks such that vehicle emissions are minimal. This ability combined with land use changes and opportunities for non-auto travel are paramount in helping regions improve air quality. However, network design research has yet to directly address this topic. To fill this apparent gap in network design research, an emissions network design problem and solution method are proposed in this thesis. Three air pollutants are considered: hydrocarbons, nitrogen oxides, and carbon monoxide. The proposed model is applied to two road networks: Sioux Falls, ND and Anaheim, CA. The model is a bi-level optimization problem solved using a genetic algorithm and incorporates the influence of demand uncertainty. Findings indicate designing for minimal congestion tends to increase emissions of criteria air pollutants. However, not adding capacity to a road network also increases emissions of pollutants. Therefore, an optimization problem and solution method, such as the model presented here, is useful for identifying capacity additions that reduce vehicle emissions. It is also useful for understanding the tradeoffs between designing a network for minimal congestion versus minimal vehicle emissions. / text

No description available.

Network design problems involving survivability usually include trade-off of the potential for lost revenues and customer goodwill against the extra costs required to increase the network survivability. It also involves selection of nodes and edges from lists of potential sets to accomplish certain desirable properties. In many applications it is imperative to have built-in reliability or survivability of the network. Delays of traffic are undesirable since it affects quality of service (QoS) to clients of the network. In this dissertation we consider the construction of an optimization system for network design with survivability properties that may help in the planning of mesh topologies while maintaining a certain degree of survivability of the network. This is done by providing for at least two diverse paths between certain "special" nodes to provide protection against any single edge or node failure. This part is modelled by using mixed integer programming techniques. A software product called CPLEX then solves these models and various facilities are built into the decision support system to allow the decision maker to experiment with some topological and flow requirement changes. / Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2007

On April 27, 1802, I gave a shout of joy ... It was seven years ago I proposed to myself a problem which I have not been able to solve directly, but for which I had found by chance a solution, and I knew that it was correct, without being able to prove it. The matter often returned to my mind and I had sought twenty times unsuccessfully for this solution. For some days I had carried the idea about with me continually. At last, I do not know how, I found it, together with a large number of curious and new considerations concerning the theory of probability. Andre Marie Ampere. Facility location problems (or plant location problems) are general models that can be used when a set of clients has to be served by facilities. More precisely, we are given a set of potential facility locations and a set of clients. The optimization problem is to select a subset of the locations at which to place facilities and then to assign clients to theses facilities so as to minimize total cost. Most formulations considered in this thesis can be viewed as general models that can be applied to a wide range of context and practical situations. However, as this research has been partly initiated by the interest of the author in telecommunication network design we will introduce these models by considering problems in this particular area. In the context of telecommunication network design an application of discrete location theory is the optimization of access networks with concentrators. Typically, we have a number of terminal points that must be connected to a service point. An obvious solution is to use a dedicated link for each terminal (star network). However, it is clear that this solution can be very expensive when the number of terminals is large and when they are far from the service point. Access networks are often constructed by inserting concentrators between the terminals and the service point. Many terminals are connected to a facility which in turn is connected by a single link to the service point. The objective is to build a network that will provide the service at minimum cost. If no extra constraints are involved the mmimum cost network problem can be expressed as an uncapacitated facility location problem (UFL). If the number of terminals that can be connected to a concentrator is limited we obtain a so-called capacitated facility location problem (CFL). CFL can be extended to consider various types of concentrators with various capacities. This problem is the multi-capacitated facility location problem (MCFL). MCFL is a straightforward model for low speed packet switched data networks typical among which are networks connecting sellingpoint terminals to a database. For other networks, the problem may involve various traffic constraints. In chapter 1 we present those problems and compare solutions obtained by Lagrangian relaxation and simulated annealing algorithms. The architecture mentioned above can be extended with more than one hierarchical level of concentrator. Unfortunately, we pay for this cost saving through a decrease of reliability. Therefore, the number of levels is often limited to one or two. In chapter 2 we study an extension of UFL and CFL to two levels of concentrators. Obviously, the structure of a network changes according to the way requirements vary with time. In order to plan investments and to develop strategies, the evolution of a network has to be determined for several years ahead (typically four or five years). In this case the main questions to answer are: Where and when to establish concentrators and of what size? In chapter 3 we study this problem for the dynamic version of UFL. Now, with the network optimization problem, there naturally arises the problem of allocating the total minimum cost among customers fairly. Namely, we would like to allocate the cost in such a way that no subgroup of users would have incentive to withdraw and build their own network. The standard way to approach such a problem is by the means of cooperative game theory. In chapter 4 we study the core of location games derived from UFL and CFL, and in chapter 5 we propose methods to compute the nucleolus of these games.

We model Pup Matching, the logistics problem of matching or pairing semitrailers known as pups to cabs able to tow one or two pups simultaneously, as an NP-complete version of the Network Loading Problem (NLP). We examine a branch and bound solution approach tailored to the NLP formulation through the use of three families of cutting planes and four heuristic procedures. Theoretically, we specify facet defining conditions for a cut family that we refer to as odd flow inequalities and show that each heuristic yields a 2-approximation. Computationally, the cheapest of the four heuristic values achieved an average error of 1.3% among solved test problems randomly generated from realistic data. The branch and bound method solved to optimality 67% of these problems. Application of the cutting plane families reduced the average relative difference between upper and lower bounds prior to branching from 18.8% to 6.4%. / Singapore-MIT Alliance (SMA)

The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs at a specified arc dependent cost. The problem is to determine the number of facilities to be loaded on the arcs that will satisfy the given demand at minimum cost. This paper studies two core subproblems of the NLP. The first problem, motivated by a Lagrangian relaxation approach for solving the problem, considers a multiple commodity, single arc capacitated network design problem. The second problem is a three node network; this specialized network arises in larger networks if we aggregate nodes. In both cases, we develop families of facets and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems. These results in turn strengthen the formulation of the NLP.

Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the Multi-level Network Design (MLND) problem seeks a fixed cost minimizing design that spans all the nodes and connects the nodes at each level by facilities of the corresponding or higher type. This problem generalizes the well-known Steiner network problem and the hierarchical network design problem, and has applications in telecommunication, transportation, and electric power distribution network design. In a companion paper we introduced the problem, studied alternative model formulations, and analyzed the worst-case performance of heuristics based on Steiner network and spanning tree solutions. This paper develops and tests a dual-based algorithm for the Multi-level Network Design (MLND) problem. The method first performs problem preprocessing to fix certain design variables, and then applies a dual ascent procedure to generate upper and lower bounds on the optimal value. We report extensive computational results on large, random networks (containing up to 500 nodes, and 5000 edges) with varying cost structures. The integer programming formulation of the largest of these problems has 20,000 integer variables and over 5 million constraints. Our tests indicate that the dualbased algorithm is very effective, producing solutions guaranteed to be within 0 to 0.9% of optimality.

Most logistics network design models assume exogenous customer demand that is independent of the service time or level. This paper examines the benefits of segmenting demand according to lead-time sensitivity of customers. To capture lead-time sensitivity in the network design model, we use a facility grouping method to ensure that the different demand classes are satisfied on time. In addition, we perform a series of computational experiments to develop a set of managerial insights for the network design decision making process. / Singapore-MIT Alliance (SMA)

Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2007.

Recent advancements in sensory devices are presenting various opportunities for widespread applications of wireless sensor networks (WSNs). The most distinguishing characteristic of a WSN is the fact that its sensors have nite and non-renewable energy resources. Many research e orts aim at developing energy e cient network topology and routing schemes for prolonging the network lifetime. However, we notice that, in the majority of the literature, topology control and routing problems are handled separately, thus overlooking the interrelationships among them. In this dissertation, we consider an integrated topology control and routing problem in WSNs which are unique type of data gathering networks characterized by limited energy resources at the sensor nodes distributed over the network. We suggest an underlying hierarchical topology and routing structure that aims to achieve the most prolonged network lifetime via e cient use of limited energy resources and addressing operational speci cities of WSNs such as communication-computation trade-o , data aggregation, and multi-hop data transfer for better energy e ciency. We develop and examine three di erent objectives and their associated mathematical models that de- ne alternative policies to be employed in each period of a deployment cycle for the purpose of maximizing the number of periods so that the network lifetime is prolonged. On the methodology side, we develop e ective solution approaches that are based on decomposition techniques, heuristics and parallel heuristic algorithms. Furthermore, we devise visualization tools to support our optimization e orts and demonstrate that visualization can be very helpful in solving larger and realistic problems with dynamic nature. This dissertation research provides novel analytical models and solution methodologies for important practical problems in WSNs. The solution algorithms developed herein will also contribute to the generalized mixed-discrete optimization problem, especially for the problems with similar characteristics.