Master of Science / Department of Industrial and Manufacturing Systems Engineering / Jessica L. Heier Stamm / Gifts-in-kind (GIK) donations negatively affect the humanitarian supply chain at the point of receipt near the disaster site. In any disaster, as much as 50 percent of GIK donations are irrelevant to the relief efforts. This proves to be a significant issue to humanitarian organizations because the quantity and type of future GIK are uncertain, making it difficult to account for GIK donations at the strategic planning level. The result is GIK consuming critical warehouse space and manpower. Additionally, improper treatment of GIK can result in ill-favor of donors and loss of donations (both cash and GIK) and support for the humanitarian organization. This thesis proposes a robust facility location approach that mitigates the impact of GIK by providing storage space for GIK and pre-positions supplies to meet initial demand. The setting of the problem is strategic planning for hurricane relief along the Gulf and Atlantic Coasts of the United States. The approach uses a robust scenario-based method to account for uncertainty in both demand and GIK donations. The model determines the location and number of warehouses in the network, the amount of pre-positioned supplies to meet demand, and the amount of space in each warehouse to alleviate the impact of GIK. The basis of the model is a variant of the covering facility location model that must satisfy all demand and GIK space requirements. A computational study with multiple cost minimizing objective functions illustrates how the model performs with realistic data. The results show that strategic planning in the preparedness phases of the disaster management cycle will significantly mitigate the impact of GIK.

This project investigates how remanufacturing of robotic lawn mowers can be incorporated into an existent forward supply chain. The project is conducted as a single case study on Husqvarna where an interview study and a literature study provide the empirical data and theory, respectively. Alternatives are proposed for potential remanufacturing cases at various locations, where different parties ranging from original equipment manufacturers to independent manufacturers perform the remanufacturing process. SWOT analyses are conducted to identify the most promising alternatives for a further economic analysis. The economic evaluation is based on net present values and a sensitivity analysis which together determines the feasibility of the alternatives. The results of the project answer three research questions. The first concludes that out of seven defined production systems there are only two that are not suitable for remanufacturing in a general case mainly due to the low flexibility of these systems. The results of the second identifies labor, logistics, and operational prerequisite factors that must be considered when implementing remanufacturing for case specific alternatives. The conclusion of the third research question lists the feasibility of the alternatives from which the recommendations for Husqvarna are presented. This project recommends Husqvarna to implement a remanufacturing process for their robotic lawn mowers either by enlisting their current dealers or by themselves at a location nearby the spare parts warehouse in Torsvik. Which alternative is the most profitable depends mainly on the expected quantity of the acquired cores, i.e. Husqvarna as a centralized remanufacturer benefits more from higher quantities while the decentralized dealer alternative would comparably be more profitable if the quantities were lower. As it is perceived that initial collected quantities will be low, and possibly even somewhat higher for the dealers, a decentralized remanufacturing process could be the most profitable alternative to start with. Using a third-party remanufacturer is also feasible but considered risky and therefore not recommended as they could have the same core acquisition problem as Husqvarna while having lower profitability.

The aim of thiswork is to locate a semi-obnoxious facility, i.e. tominimize the distances to a given set of customers in order to save transportation costs on the one hand and to avoid undesirable interactions with other facilities within the region by maximizing the distances to the corresponding facilities on the other hand. Hence, the goal is to satisfy economic and environmental issues simultaneously. Due to the contradicting character of these goals, we obtain a non-convex objective function. We assume that distances can be measured by rectilinear distances and exploit the structure of this norm to obtain a very efficient dual pair of algorithms.

No description available.

<div>The problem of optimally placing sensors can often be formulated as a facility location problem. In the literature of operations research, facility location problems are mathematical optimization problems where one or more facilities must be placed in relation to a given number of demand points or customers. Within the context of sensor placement, for example, this translates to placing wireless communication nodes that connect to a set of users or placing smoke detectors to adequately cover a region for safety assurances. However, while the classical facility location problem has been extensively studied, its direct applicability to and effectiveness for the optimal sensor placement problem can be diminished when real-world uncertainties are considered. In addition, the physics of the underlying systems in optimal sensor placement problems can directly impact the effectiveness of facility location formulations. Extensions to existing location formulations that are tailored for the system of interest are necessary to ensure optimal sensor network design.</div><div><br></div><div>This dissertation focuses on developing and applying problem-specific optimal sensor placement methods under uncertainty in sensor performance. With the classical discrete facility location problems as a basis, our models are formulated as mixed-integer linear and nonlinear programs that, depending on the specific application, can also be in the form of a stochastic program, a robust optimization framework, or require probability distributions for uncertain parameters. We consider optimal placement problems from three different areas, particularly the optimal placement of data concentrators in Smart Grid communications networks, the optimal placement of flame detectors within petrochemical facilities, and the optimal selection of infectious disease detection sites across a nation. For each application, we carefully consider the underlying physics of the system and the uncertainties and then develop extensions of previous sensor placement formulations that effectively handle these qualities. In addition, depending on the degree of nonlinear complexity of the problem, specific relaxations and iterative solution strategies are developed to improve the ability to find tractable solutions. All proposed models are implemented in Pyomo, a Python-based optimization modeling language, and solved with state-of-the-art optimization solvers, including IPOPT, Gurobi, and BARON for nonlinear, mixed-integer, and mixed-integer nonlinear programs, respectively. Numerical results show that our tailored formulations for the problems of interest are effective in handling uncertainties and provide valuable sensor placement design frameworks for their respective industries. Furthermore, our extensions for placement of sensors under probabilistic failure are appropriately general for application in other areas.<br><b></b><i></i><u></u><br></div>

Facility location, as an important topic in computer science and operations research, is concerned with placing facilities for "serving" demand points (each representing a customer) to minimize the (service) cost. In the real world, data is often associated with uncertainty because of measurement inaccuracy, sampling discrepancy, outdated data sources, resource limitation, etc. Hence, problems on uncertain data have attracted much attention. In this dissertation, we mainly study a classical facility location problem: the k- center problem and several of its variations, on uncertain points each of which has multiple locations that follow a probability density function (pdf). We develop efficient algorithms for solving these problems. Since these problems more or less have certain geometric flavor, computational geometry techniques are utilized to help develop the algorithms. In particular, we first study the k-center problem on uncertain points on a line, which is aimed to find k centers on the line to minimize the maximum expected distance from all uncertain points to their expected closest centers. We develop efficient algorithms for both the continuous case where the location of every uncertain point follows a continuous piecewise-uniform pdf and the discrete case where each uncertain point has multiple discrete locations each associated with a probability. The time complexities of our algorithms are nearly linear and match those for the same problem on deterministic points. Then, we consider the one-center problem (i.e., k= 1) on a tree, where each uncertain point has multiple locations in the tree and we want to compute a center in the tree to minimize the maximum expected distance from it to all uncertain points. We solve the problem in linear time by proposing a new algorithmic scheme, called the refined prune-and-search. Next, we consider the one-dimensional one-center problem of uncertain points with continuous pdfs, and the one-center problem in the plane under the rectilinear metric for uncertain points with discrete locations. We solve both problems in linear time, again by using the refined prune-and-search technique. In addition, we study the k-center problem on uncertain points in a tree. We present an efficient algorithm for the problem by proposing a new tree decomposition and developing several data structures. The tree decomposition and these data structures may be interesting in their own right. Finally, we consider the line-constrained k-center problem on deterministic points in the plane where the centers are required to be located on a given line. Several distance metrics including L1, L2, and L1 are considered. We also study the line-constrained k-median and k-means problems in the plane. These problems have been studied before. Based on geometric observations, we design new algorithms that improve the previous work. The algorithms and techniques we developed in this dissertation may and other applications as well, in particular, on solving other related problems on uncertain data.

The exploding HD video streaming traffic calls for deploying content servers deeper inside network operators infrastructures. Telco-CDN are new content distribution services that are managed by Internet Service Providers (ISP). Since the network operator controls both the infrastructure and the content delivery overlay, it is in position to engineer Telco-CDN so that networking resources are optimally utilized. In this thesis, we focus on the optimal resource placement in Telco-CDN. We first investigated the placement of application components in Telco-CDN. Popular services like Facebook or Twitter, with a size in the order of hundreds of Terabytes, cannot be fully replicated on a single data-center. Instead, the idea is to partition the service into smaller components and to locate the components on distinct sites. It is the same and unique method for Telco-CDN operators. We addressed this k-Component Multi-Site Placement Problem from an optimization standpoint. We developed linear programming models, designed approximation and heuristic algorithms to minimize the overall service delivery cost. Thereafter, we extend our works to address the problem of optimal video place- ment for Telco-CDN. We modeled this problem as a k-Product Capacitated Facility Location Problem, which takes into account network conditions and users¿ prefer- ences. We designed a genetic algorithm in order to obtain near-optimal performances of such "push" approach, then we implemented it on the MapReduce framework in order to deal with very large data sets. The evaluation signifies that our optimal placement keeps align with cooperative LRU caching in term of storage efficiency although its impact on network infrastructure is less severe. We then explore the caching decision problem in the context of Information Cen- tric Network (ICN), which could be a revolutionary design of Telco-CDN. In ICN, routers are endowed with caching capabilities. So far, only a basic Least Recently Used (LRU) policy implemented on every router has been proposed. Our first contri- bution is the proposition of a cooperative caching protocol, which has been designed for the treatment of large video streams with on-demand access. We integrated our new protocol into the main router software (CCNx) and developed a platform that automatically deploys our augmented CCNx implementation on real machines. Ex- periments show that our cooperative caching significantly reduces the inter-domain traffic for an ISP with acceptable overhead. Finally, we aim at better understanding the behavior of caching policies other than LRU. We built an analytical model that approximates the performance of a set of policies ranging from LRU to Least Frequently Used (LFU) in any type of network topologies. We also designed a multi-policy in-network caching, where every router implements its own caching policy according to its location in the network. Compared to the single LRU policy, the multi-caching strategy considerably increases the hit- ratio of the in-network caching system in the context of Video-on-Demand application. All in one, this thesis explores different aspects related to the resource placement in Telco-CDN. The aim is to explore optimal and near-optimal performances of various approaches.

A planar single facility location problem, also known as the Fermat&ndash / Weber problem, is to

Hazardous Materials (HazMat) are transported throughout Canada in a great number of road shipments. The transportation of HazMat poses special risks for neighboring population and environment. While HazMat accidents are rare events, they could be catastrophic in nature and could result in substantial damage to nearby communities. Effective emergency response plays an important role in the safe transportation of HazMat. Transportation of HazMat involves different parties, including shippers, regulators, and surrounding communities. While the shipping party is responsible for safe delivery of HazMat shipments, it is the responsibility of local emergency service agencies to respond to accidents occurring within their jurisdictions. In this research, the emergency response to HazMat transport accidents is assumed to be delegated exclusively to specially trained and equipped HazMat teams. This research proposes a new comprehensive systematic approach to determine the best location of HazMat teams on regional bases utilizing HazMat transport risk as a location criterion. The proposed model is the first to consider emergency response roles in HazMat transport risk analysis, and was intended as an optimization tool to be used by practitioners for HazMat emergency response planning. Additionally, the proposed model can be used to assess risk implications in regards to current locations of HazMat teams in a region, and to develop effective strategies for locating HazMat teams, such as closing and/or relocating teams in the region. The model investigates how HazMat team locations can be tailored to recognize the risk of transporting HazMat and would provide a more objective set of input alternatives into the multi-criteria decision making process of regionally locating HazMat teams. The proposed model was applied to the region of southwestern Ontario in effort to illustrate its features and capabilities in the HazMat emergency response planning and decision making process. Accordingly, the model provided very useful insights while reviewing several HazMat team location strategies for the southwestern Ontario region and investigating tradeoff among different factors. This research contributes to a better understanding of emergency response roles by reducing HazMat transport risks, and will greatly benefit both researchers and practitioners in the field of HazMat transport and emergency response.

The subject of this thesis is to study approximation algorithms for some network design problems in face of uncertainty. We consider two widely studied models of handling uncertainties - Robust Optimization and Stochastic Optimization. We study a robust version of the well studied Uncapacitated Facility Location Problem (UFLP). In this version, once the set of facilities to be opened is decided, an adversary may close at most β facilities. The clients must then be assigned to the remaining open facilities. The performance of a solution is measured by the worst possible set of facilities that the adversary may close. We introduce a novel LP for the problem, and provide an LP rounding algorithm when all facilities have same opening costs. We also study the 2-stage Stochastic version of the Steiner Tree Problem. In this version, the set of terminals to be covered is not known in advance. Instead, a probability distribution over the possible sets of terminals is known. One is allowed to build a partial solution in the first stage a low cost, and when the exact scenario to be covered becomes known in the second stage, one is allowed to extend the solution by building a recourse network, albeit at higher cost. The aim is to construct a solution of low cost in expectation. We provide an LP rounding algorithm for this problem that beats the current best known LP rounding based approximation algorithm.