Congestion and oversaturated roads pose significant problems and create delays in every major city in the world. Before this problem can be addressed, we must know how much traffic is flowing over the links in the network. We transform a road network into a directed graph with a network flow function, and ask the question, “What subset of vertices (intersections) should be monitored such that knowledge of the flow passing through these vertices is sufficient to calculate the flow everywhere in the graph?” To minimize the cost of placing sensors, we seek the smallest number of monitored vertices. This is known as the Sensor Location Problem (SLP). We explore conditions under which a set of monitored vertices produces a unique solution to the problem and disprove a previous result published on the problem. Finally, we explore a matrix formulation of the problem and present cases when the flow can or cannot be calculated on the graph.

abstract: Due to environmental and geopolitical reasons, many countries are embracing electric vehicles (EVs) as an alternative to gasoline powered automobiles. Other alternative-fuel vehicles (AFVs) powered by compressed gas, hydrogen or biodiesel have also been tested for replacing gasoline powered vehicles. However, since the associated refueling infrastructure of AFVs is sparse and is gradually being built, the distance between recharging points (RPs) becomes a crucial prohibitive attribute in attracting drivers to use such vehicles. Optimally locating RPs will both increase demand and help in developing the refueling infrastructure. The major emphasis in this dissertation is the development of theories and associated algorithms for a new set of location problems defined on continuous network space related to siting multiple RPs for range limited vehicles. This dissertation covers three optimization problems: locating multiple RPs on a line network, locating multiple RPs on a comb tree network, and locating multiple RPs on a general tree network. For each of the three problems, finding the minimum number of RPs needed to refuel all Origin-Destination (O-D) flows is considered as the first objective. For this minimum number, the location objective is to locate this number of RPs to minimize weighted sum of the travelling distance for all O-D flows. Different exact algorithms are proposed to solve each of the three algorithms. In the first part of this dissertation, the simplest case of locating RPs on a line network is addressed. Scenarios include single one-way O-D pair, multiple one-way O-D pairs, round trips, etc. A mixed integer program with linear constraints and quartic objective function is formulated. A finite dominating set (FDS) is identified, and based on the existence of FDS, the problem is formulated as a shortest path problem. In the second part, the problem is extended to comb tree networks. Finally, the problem is extended to general tree networks. The extension to a probabilistic version of the location problem is also addressed. / Dissertation/Thesis / Doctoral Dissertation Industrial Engineering 2020

In today’s extremely competitive marketplace, firms are facing the need to meet or exceed increasing customer expectations while cutting costs to stay competitive in a global market. To develop competitive advantage in this business climate, companies must make informed decisions regarding their supply chain. In recent years, supply chain networks have received increasing attention among companies. The decision makers confront the network design problem in different situations. In order to make decisions, especially in strategic supply chain management, decision makers must have a holistic view of all the components. Supply chain network design, particular facility location problems, is one of the most complex strategic decision problems in supply chain management The aim of this dissertation is to make an inquiry about the facility location problems and related issues in supply chain and logistics management, and the use of modelling approaches to solve these problems. The methodology is to construct a review protocol by forming a review panel, and developing a detailed search strategy with clear inclusion and exclusion criteria. In addition, the measurement for evaluating the quality of studies is presented with a strategy for extracting data and synthesising the methodologies. The search results show the background of the facility location problems, the importance and the basic questions of these problems. The taxonomy of facility location problems with eighteen factors is presented. The basic static and deterministic problems in facility location including the covering, centre, median and fixed charge problems are discussed. Also, the extension of facility location problems comprises of location-allocation, multi-objective, hierarchical, hub, undesirable and competitive problems. In terms of uncertainty, dynamic, stochastic and robust facility location problems are presented. Finally, strengths and weaknesses of different modelling approaches are discussed; importantly, gaps from the review process are indentified. Recommendations of future research are described; and the facility location problem to be addressed by the proposed research is shown. In addition, contributions of the proposed facility location problem are illustrated.

In this thesis some problems in mathematical programming have been studied. Chapter 1 contains a brief review of the problems studied and the motivation for choosing these problems for further investigation. The development of two algorithms for finding all the vertices of a convex polyhedron and their applications are reported in Chapter 2. The linear complementary problem is studied in Chapter 3 and an algorithm to solve this problem is outlined. Chapter 4 contains a description of the plant location problem (uncapacited). This problem has been studied in some depth and an algorithm to solve this problem is presented. By using the Chinese representation of integers a new algorithm has been developed for transforming a nonsingular integer matrix into its Smith Normal Form; this work is discussed in Chapter 5. A hybrid algorithm involving the gradient method and the simplex method has also been developed to solve the linear programming problem. Chapter 6 contains a description of this method. The computer programs written in FORTRAN IV for these algorithms are set out in Appendices Rl to R5. A report on study of the group theory and its application in mathematical programming is presented as supplementary material. The algorithms in Chapter 2 are new. Part one of Chapter 3 is a collection of published material on the solution of the linear complementary problem; however the algorithm in Part two of this Chapter is original. The formulation of the plant location problem (uncapacited) together with some simplifications are claimed to be original. The use of Chinese representation of integers to transform an integer matrix into its Smith Normal Form is a new technique. The algorithm in Chapter 6 illustrates a new approach to solve the linear programming problem by a mixture of gradient and simplex method.

Konstanz, Univ., Diplomarb., 2003.

Master of Agribusiness / Department of Agricultural Economics / Jason S. Bergtold / Location optimization of a new dairy processing plant is crucial given the significant capital investment of $350 million required to build the plant. Couple this with notable differences in milk and transportation costs due to location, an examination of historical Net Present Value (NPV) of Earnings Before Interest, Taxes, Depreciation and Amortization (EBITDA) adjusted by a discount rate of 3% is warranted to help determine the most optimal location for a new dairy processing plant investment. This thesis is an examination of historical EBITDA NPV for three locations: Dumas, TX, Sioux Falls, SD, and Lansing, MI in an effort to predict the optimal location of a future dairy processing plant. These locations were chosen due to each having the necessary milk supply that would both encourage milk production and support increases in dairy processing. Prices dairy processors receive for cheese can fluctuate but are not tied to the location in which the cheese is produced. Transportation costs of the cheese are determined by the distance to the processing plant from Plymouth, WI, which is where most further cheese processing takes place. Therefore, this thesis includes a sensitivity analysis for the Lansing, MI location to determine a breakeven milk cost and cheddar cheese price. The NPV was positive for the Dumas, TX location at $100 million as compared to (-$820) million and (-$247) million at the Sioux Falls, SD and Lansing, MI locations, respectively. The results indicate an emerging EBITDA NPV trend favoring the Lansing, MI location as indicated by this location having the best performance in the last two years (2016-2017) of $104 million compared to a negative performance at both of the other locations. The previous 8 years performance would favor the Dumas, TX location, however more weight was given to the past 2 years performance as an indicator for future economic returns. As a result, this thesis concludes the Lansing, MI location as the most favorable location for a new dairy processing investment.

No description available.

A new branch of machine and deep learning models has evolved in constrained optimization, specifically in mixed integer programming problems (MIP). These models draw inspiration from earlier solver methods, primarily the heuristic, branch and bound. While utilizing the branch and bound framework, machine and deep learning models enhance either the computational efficiency or performance of the model. This thesis examines how imitating different variable selection strategies of classical MIP solvers behave on a state-of-the-art deep learning model. A recently developed deep learning algorithm is used in this thesis, which represents the branch and bound state as a bipartite graph. This graph serves as the input to a graph network model, which determines the variable in the MIP on which branching occurs. This thesis compares how imitating different classical branching strategies behaves on different algorithm outputs and, most importantly, time span. More specifically, this thesis conducts an empirical study on a MIP known as the facility location problem (FLP) and compares the different methods for imitation. This thesis shows that the deep learning algorithm can outperform the classical methods in terms of time span. More specifically, imitating the branching strategies resulting in small branch and bound trees give rise to a more rapid performance in finding the global optimum. Lastly, it is shown that a smaller embedding size in the network model is preferred for these instances when looking at the trade-off between variable selection and time cost. / En ny typ av maskin och djupinlärningsmodeller har utvecklats inom villkors optimering, specifikt för så kallade blandade heltalsproblem (MIP). Dessa modeller hämtar inspiration från tidigare lösningsmetoder, främst en heuristisk som kallas “branch and bound”. Genom att använda “branch and bound” ramverket förbättrar maskin och djupinlärningsmodeller antingen beräkningshastigheten eller prestandan hos modellen. Denna uppsats undersöker hur imitation av olika strategier för val av variabler från klassiska MIP-algoritmer beter sig på en modern djupinlärningsmodell. I denna uppsats används en nyligen utvecklad djupinlärningsalgoritm som representerar “branch and bound” tillståndet som en bipartit graf. Denna graf används som indata till en “graph network” modell som avgör vilken variabel i MIP-problemet som tas hänsyn till. Uppsatsen jämför hur imitation av olika klassiska “branching” strategier påverkar olika algoritmutgångar, framför allt, tidslängd. Mer specifikt utför denna uppsats en empirisk studie på ett MIP-problem som kallas för “facility location problem” (FLP) och jämför imitationen av de olika metoderna. I denna uppsats visas det att denna djupinlärningsalgoritm kan överträffa de klassiska metoderna när det gäller tidslängd. Mer specifikt ger imitation av “branching” strategier som resulterar i små “branch and bound” träd upphov till en snabbare prestation vid sökning av den globala optimala lösningen. Slutligen visas det att en mindre inbäddningsstorlek i nätverksmodellen föredras i dessa fall när man ser på avvägningen mellan val av variabler och tidskostnad.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Jessica L. Heier Stamm / Coordination between humanitarian organizations is critical during the response effort to a disaster, as coordinating aid improves efficiency, reduces duplication of efforts, and ultimately leads to better outcomes for beneficiaries. One particular challenge arises when temporary facilities must be established post-disaster due to the destruction of buildings. For example, the 2015 Nepal earthquakes created a need for the placement of over 4,000 temporary learning facilities after several school buildings were damaged or destroyed. It is important that humanitarians coordinate well to fill these needs efficiently and effectively, while maintaining equity among beneficiaries in the affected areas. This means ensuring that enough facilities are provided in a timely manner, and are distributed fairly to all in need. The goals of this thesis are to study coordination strategies focusing primarily on the placement of temporary educational facilities for children following a disaster. This research also aims to gather useful data by surveying active humanitarians in order to better understand their decisions made in the field. This work uses the results of this survey, along with publicly available data published after the 2015 Nepal earthquakes to create an agent-based simulation model, and uses the Nepal case study to demonstrate the efficacy of the model framework. This research finds that organizations' initial location of operation can greatly impact the number of facilities they are collectively able to establish, the geographic disparity across the region, and the organizations' utilization. Specifically, while focusing efforts on the districts with the most need is most efficient and effective, a more uniform approach yields a more equitable response. This work also finds that there can be a trade-off between overall effectiveness and the number of partnerships established in the field. These findings show a need for further study into the intricacies of coordination between humanitarian workers. This author advocates for the use of information sharing mechanisms among practitioners, as well as further utilization of agent-based modeling as a means of studying the complex nature of disaster response. Specifically there is a need to further study educational needs as a logistical problem, and strategies for solving the post-disaster facility location problem.

Some oil and gas companies are drilling and developing fields in the Arctic Ocean, which has an environment with sea ice called ice floes. These companies must protect their platforms from ice floe collisions. One proposal is to use a system that consists of autonomous underwater vehicles (AUVs) and docking stations. The AUVs measure the under-water topography of the ice floes, while the docking stations launch the AUVs and recharge their batteries. Given resource constraints, we optimize quantities and locations for the docking stations and the AUVs, as well as the AUV scheduling policies, in order to provide the maximum protection level for the platform. We first use an queueing approach to model the problem as a queueing system with abandonments, with the objective to minimize the abandonment probability. Both M/M/k+M and M/G/k+G queueing approximations are applied and we also develop a detailed simulation model based on the queueing approximation. In a complementary approach, we model the system using a multi-stage stochastic facility location problem in order to optimize the docking station locations, the AUV allocations, and the scheduling policies of the AUVs. A two-stage stochastic facility location problem and several efficient online scheduling heuristics are developed to provide lower bounds and upper bounds for the multi-stage model, and also to solve large-scale instances of the optimization model. Even though the model is motivated by an oil industry project, most of the modeling and optimization methods apply more broadly to any radial detection problems with queueing dynamics. / text