The p-Median problem (PMP) is one of the most widely applied location problems in urban and regional planning to support spatial decision-making. As an NP-hard problem, the PMP remains challenging to solve optimally, especially for large-sized problems. This research focuses on developing geocomputational approaches to improve the effectiveness and efficiency of solving the PMP. This research also examines existing PMP methods applied to choropleth mapping and proposes a new approach to address issues associated with uncertainty. Chapter 2 introduces a new algorithm that solves the PMP more effectively. In this chapter, a method called the spatial-knowledge enhanced Teitz and Bart heuristic (STB) is proposed to improve the classic Teitz and Bart (TB) heuristic.. The STB heuristic prioritizes candidate facility sites to be examined in the solution set based on the spatial distribution of demand and candidate facility sites. Tests based on a range of PMPs demonstrate the effectiveness of the STB heuristic. Chapter 3 provides a high performance computing (HPC) based heuristic, Random Sampling and Spatial Voting (RSSV), to solve large PMPs. Instead of solving a large-sized PMP directly, RSSV solves multiple sub-PMPs with each sub-PMP containing a subset of facility and demand sites. Combining all the sub-PMP solutions, a spatial voting strategy is introduced to select candidate facility sites to construct a PMP for obtaining the final problem solution. The RSSV algorithm is well-suited to the parallel structure of the HPC platform. Tests with the BIRCH dataset show that RSSV provides high-quality solutions and reduces computing time significantly. Tests also demonstrate the dynamic scalability of the algorithm; it can start with a small amount of computing resources and scale up or down when the availability of computing resources changes. Chapter 4 provides a new classification scheme to draw choropleth maps when data contain uncertainty. Considering that units in the same class on a choropleth map are assigned the same color or pattern, the new approach assumes the existence of a representative value for each class. A maximum likelihood estimation (MLE) based approach is developed to determine class breaks so that the overall within-class deviation is minimized while considering uncertainty. Different methods, including mixed integer programming, dynamic programming, and an interchange heuristic, are developed to solve the new classification problem. The proposed mapping approach is then applied to map two American Community Survey datasets. The effectiveness of the new approach is demonstrated, and the linkage of the approach with the PMP method and the Jenks Natural Breaks is discussed.

This dissertation presents spatial partitioning algorithms to solve location-allocation problems. Location-allocations problems pertain to both the selection of facilities to serve demand at demand points and the assignment of demand points to the selected or known facilities. In the first part of this dissertation, we focus on the well known and well-researched location-allocation problem, the "p-median problem", which is a distance-based location-allocation problem that involves selection and allocation of p facilities for n demand points. We evaluate the performance of existing p-median heuristic algorithms and investigate the impact of the scale of the problem, and the spatial distribution of demand points on the performance of these algorithms. Based on the results from this comparative study, we present guidelines for location analysts to aid them in selecting the best heuristic and corresponding parameters depending on the problem at hand. Additionally, we found that existing heuristic algorithms are not suitable for solving large-scale p-median problems in a reasonable amount of time. We present a density-based decomposition methodology to solve large-scale p-median problems efficiently. This algorithm identifies dense clusters in the region and uses a MapReduce procedure to select facilities in the clustered regions independently and combine the solutions from the subproblems. Lastly, we present a novel greedy heuristic algorithm to solve the contiguity constrained fixed facility demand distribution problem. The objective of this problem is to create contiguous service areas for the facilities such that the demand at all facilities is uniform or proportional to the available resources, while the distance between demand points and facilities is minimized. The results in this research are shown in the context of creating emergency response plans for bio-emergencies. The algorithms are used to select Point of Dispensing (POD) locations (if not known) and map them to population regions to ensure that all affected individuals are assigned to a POD facility.

No description available.

This research is concerned with the development of algorithmic approaches for solving problems that arise in the design and analysis of telecommunication networks, location-allocation distribution contexts, and intelligent transportation networks. Specifically, the corresponding problems addressed in these areas are a local access and transport area (LATA) network design problem, the discrete equal-capacity p-median problem (PMED), and the estimation of dynamic origin-destination path ows or trip tables in a general network. For the LATA network problem, we develop a model and apply the Reformulation-Linearization Technique (RLT) to construct various enhanced tightened versions of the proposed model. We also design efficient Lagrangian dual schemes for solving the linear programming relaxation of the various enhanced models, and construct an effective heuristic procedure for deriving good quality solutions in this process. Extensive computational results are provided to demonstrate the progressive tightness resulting from the enhanced formulations and their effect on providing good quality feasible solutions. The results indicate that the proposed procedures typically yield solutions having an optimality gap of less than 2% with respect to the derived lower bound, within a reasonable effort that involves the solution of a single linear program. For the discrete equal-capacity p-median problem, we develop various valid inequalities, a separation routine for generating cutting planes via specific members of such inequalities, as well as an enhanced reformulation that constructs a partial convex hull representation that subsumes an entire class of valid inequalities via its linear programming relaxation. We also propose suitable heuristic schemes for solving this problem, based on sequentially rounding the continuous relaxation solutions obtained for the various equivalent formulations of the problem. Extensive computational results are provided to demonstrate the effectiveness of the proposed valid inequalities, enhanced formulations, and heuristic schemes. The results indicate that the proposed schemes for tightening the underlying relaxations play a significant role in enhancing the performance of both exact and heuristic solution methods for solving this class of problems. For the estimation of dynamic path ows in a general network, we propose a parametric optimization approach to estimate time-dependent path ows, or origin-destination trip tables, using available data on link traffic volumes for a general road network. Our model assumes knowledge of certain time-dependent link ow contribution factors that are a dynamic generalization of the path-link incidence matrix for the static case. We propose a column generation approach that uses a sequence of dynamic shortest path subproblems in order to solve this problem. Computational results are presented on several variants of two sample test networks from the literature. These results indicate the viability of the proposed approach for use in an on-line mode in practice. Finally, we present a summary of our developments and results, and offer several related recommendations for future research. / Ph. D.

In this study, the design of a three-level distribution system is considered in which a single supplier ships a number of items to the retailers via a set of distribution centers (DC) and stochastic demand is observed at the retailers. The problem is to specify the number and location of the DCs, and the assignment of the retailers to the DCs in such a way that total facility, transportation, safety stock, and joint ordering and average inventory costs are minimized, and customer service requirements are satisfied. Single source constraints are imposed on the assignment of the retailers to the DCs. The integrated location/inventory model incorporates the inventory management decisions into the strategic location/allocation decisions by considering the benefits of risk pooling and the savings that result in the joint replenishment of a group of items. We develop two heuristic methods to solve the non-linear integer-programming model in an integrated way: (1) Improvement type heuristic, (2) Constructive type heuristic. The heuristic algorithms are tested on a number of problem instances with 81 demand points (retailers) and 4 different types of items. Both of the heuristics are able to generate solutions in very reasonable times. The results are compared to the results of the p-median problem and found that the total cost and the number of DCs can be lowered using our integrated model instead of the p-median problem. Finally, sensitivity analysis is performed with respect to the changes in inventory, transportation, and ordering cost parameters, and variability of the demand.

Made available in DSpace on 2014-12-17T14:52:50Z (GMT). No. of bitstreams: 1 AndreMG_DISSERT.pdf: 2426032 bytes, checksum: 12cecc3ac8e26d885793286de73b6a32 (MD5) Previous issue date: 2010-02-26 / The decrease in crime is one of the core issues that cause concern in society today. This study aims to propose improvements to public safety from the choice of points to the location of police units, ie the points which support the car and the police. For this, three models were developed in order to assist decision making regarding the best placement of these bases. The Model of Police Units Routing has the intention to analyze the current configuration of a given region and develop optimal routes for round preventative. The Model of Allocation and Routing for New Police Units (MARNUP) used the model of facility location called p-median weighted and traveling salesman problem (TSP) combined aiming an ideal setting for regions that do not yet have support points or to assess how far the distribution is present in relation to that found in solution. The Model Redefinition and Routing Unit Police (MRRUP) seek to change the current positioning taking into account the budgetary constraints of the decision maker. To verify the applicability of these models we used data from 602 points to instances of police command that is responsible for the capital city of Natal. The city currently has 31 police units for 36 of these 19 districts and police have some assistance. This reality can lead to higher costs and higher response times for answering emergency calls. The results of the models showed that in an ideal situation it is possible to define a distance of 500 km/round, whereas in this 900 km are covered by approximately round. However, a change from three-point lead reduced to 700 km / round which represents a decrease of 22% in the route. This reduction should help improve response time to emergency care, improving the level of service provided by the increase of solved cases, reducing police shifts and routing preventive patrols / A diminui??o da criminalidade ? uma das quest?es centrais que geram preocupa??o na sociedade atual. O presente estudo objetiva propor melhorias a seguran?a p?blica a partir da escolha de pontos para a localiza??o de unidades policiais, ou seja, dos pontos que servem de apoio ?s viaturas e aos policiais. Para isto, tr?s modelos matem?ticos foram desenvolvidos no intuito de auxiliar a tomada de decis?o com rela??o ao melhor posicionamento destas bases. O Modelo de Roteiriza??o das Unidades Policiais tem como intuito analisar a configura??o atual de determinada regi?o e desenvolver rotas ?timas para a ronda preventiva. O Modelo de Aloca??o e Roteiriza??o de Novas Unidades Policiais (MARNUP) utilizou o modelo de localiza??o de instala??es denominado de p-medianas e o problema do caixeiro viajante (TSP) combinados objetivando uma configura??o ideal para regi?es que ainda n?o possuem pontos de apoio ou para avaliar o qu?o distante est? a distribui??o presente em rela??o ao encontrado na solu??o. O Modelo de Redefini??o e Roteiriza??o de Unidades Policiais (MRRUP) busca a mudan?a do posicionamento atual levando em considera??o as restri??es or?ament?rias do decisor. Para a verifica??o da aplicabilidade destes modelos utilizou-se dados de 602 pontos de ocorr?ncias do Comando de Policiamento da Capital que ? respons?vel pelo munic?pio de Natal. A cidade atualmente possui 31 unidades policiais para 36 bairros e destes 19 possuem algum aux?lio policial. Esta realidade pode gerar custos mais elevados e maiores tempos de resposta para o atendimento de chamadas de emerg?ncias. Os resultados encontrados pelos modelos mostraram que em uma situa??o ideal ? poss?vel delimitar uma dist?ncia percorrida de 500 km, enquanto no presente 900 km s?o percorridos aproximadamente por ronda. Contudo, uma mudan?a de tr?s pontos leva a redu??o para 700 km/ronda o que representa uma diminui??o de 22% no percurso. Esta diminui??o deve ajudar na melhoria do tempo de resposta ao atendimento de emerg?ncias, na melhoria do n?vel de servi?o proporcionada pelo aumento de casos resolvidos, na redu??o dos deslocamentos policiais e no roteamento de rondas preventivas

Die vorliegende Masterarbeit beschäftigt sich mit den MINISUM-Modellen auf einem Graphen. Die Eigenschaften des „generalized“ p-Median-Problem werden neben den Eigenschaften des ordinären p-Median-Problems untersucht. Dabei kommt folgende Diskrepanz zum Vorschein: Obwohl das „generalized“ p-Median-Problem eine unendliche Anzahl an potenziellen Lösungsmöglichkeiten besitzt und der optimale Standort bei einer derartigen Problemstellung sowohl im Knoten als auch auf der Kante des Graphen liegen kann, wird der Median oft ausschließlich in den Knoten des Graphen gesucht. Dadurch entsteht das Risiko, dass beim Lösen des Problems der optimale Standort von Anfang an nicht mitberücksichtigt wird. Die Forschungsaufgabe dieser Arbeit ist, das „generalized“ p-Median-Problem so zu erweitern, dass aus einem Problem mit unendlicher Anzahl an Lösungsmöglichkeiten ein endliches Problem wird, welches optimal mit einer diskreten Methode gelöst werden kann. Im ersten Schritt werden die potenziellen Standorte auf den Kanten (die sogenannten fiktiven Knoten) ermittelt. Sie werden mit den Knoten des Graphen gleichgestellt und bei der Auffindung des kostenminimalen Standortes einkalkuliert. Damit sind alle potenziellen Standorte abgedeckt und das Problem erhält eine endliche Anzahl an Lösungsmöglichkeiten. Eine weitere Herausforderung liegt in der unkonventionellen Formulierung des Kostenparameters, der beim „generalized“ p-Median-Problem zusätzlich berücksichtigt wird. Die Kosten stellen eine logarithmische Kostenfunktion dar, die von der Verteilung der Nachfrage auf die Mediane abhängig ist. Diese Variable wird als Zuteilung bezeichnet und muss zusätzlich vor der Formulierung des Optimierungsproblems bestimmt werden. Die Zuteilung ist für die Ermittlung der Kosten zuständig und fließt in das Modell nur indirekt mit ein. Abschließend wird die Funktionsfähigkeit des neuen Modells überprüft und dem ursprünglichen Modell (dem umformulierten Warehouse Location Problem) gegenübergestellt. Tatsächlich werden bei dem erweiterten Modell durch die Platzierung der Mediane auf die Kante zusätzliche Kosten eingespart. Die vorliegende Arbeit zeigt das Prinzip, wie das „generalized“ p-Median-Problem erweitert werden kann, und liefert den Beweis über die Funktionstüchtigkeit dieser Methode. / The following master’s thesis deals with the MINISUM models on a graph. In this regard the properties of the generalized p-median problem have been investigated alongside the properties of the ordinary p-median problem. In the course of the investigation, the following discrepancy comes to the fore: although the generalized p-median problem has an infinite number of potential solutions, and the optimal location for such a problem may lie in both the vertex and on the edge of the graph, the median is often searched for exclusively in the vertex of the graph. This creates the risk that, upon attempting to find a solution, the optimal location to place the median may not be taken into consideration right from the start. The goal of the following thesis is to extend the generalized p-median problem so that a problem with an infinite number of possible solutions becomes a finite problem which can best be solved with a discrete method. In the first step, all potential locations along the edges (the so-called fictitious vertices) are determined using an empirical-analytical approach. They are equated with the vertices of the graph and taken into account when locating the minimum cost location. This covers all potential locations and through this method the problem receives a finite number of possible solutions. Another challenge lies in the unconventional formulation of the cost parameter, which is additionally taken into account in the generalized p-median problem. The cost represents a logarithmic cost function that depends on the distribution of demand on the median. In the following work, this variable shall be called the allocation and must first be determined in order to formulate the optimization problem framework. The allocation is responsible for determining the costs and is included only indirectly in the model. Finally, the functionality of the new model is checked and compared with the original model, the rewritten warehouse location problem. In fact, the placement of medians on an edge saves additional costs in the extended model. The following elaboration shows the principle of how the generalized p-median problem can be extended, and provides proof of the functionality of this extension.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The evolution of computer hardware as well as new applications of mathematical programming techniques, efficiently implemented in many commercial solvers, has given rise to new algorithms called hybrid metaheuristic, which have been applied to solve combinatorial problems. This work presents several approaches which try to deal with the hybridization of local search based metaheuristics with exact algorithms to solve two problems of combinatorial optimization. More specifically, the first problem, capacitated p-median problem, the proposed approach considers heuristic elimination of variable of the original mathematical model, that produce solutions of very good quality in a short amount of time, and a combination with an iterative procedure in which only a certain subset of points is considered. As regards the second problem, unrelated parallel machine scheduling with sequence and machine dependent setup time problem of minimizing makespan, is proposed a mathematical model to search the neighborhood of a solution and identify movement sequences to minimize the objective function. In both cases, mathematical models are solved using a commercial solver. Extensive computational experiments are carried out to demonstrate the good performance of the proposed approaches. / A recente evolução dos computadores como também dos métodos exatos oriundos da programação matemática, muitos destes eficientemente implementados em otimizadores comerciais, propiciou o surgimento de novos algoritmos, denominados metaheurísticas híbridas, que têm sido aplicados para resolução de problemas combinatoriais. Este trabalho apresenta abordagens que hibridizam metaheurísticas baseadas em busca local com algoritmos exatos de programação matemática para resolver dois problemas de otimização combinatória. Mais especificamente, para o primeiro problema, o problema das p-medianas capacitado, a proposta considera a eliminação heurística de variáveis do modelo matemático, que permite a obtenção de soluções de boa qualidade em um curto tempo computacional, e a combinação com um procedimento iterativo no qual apenas um determinado subconjunto de pontos é considerado. No que se refere ao segundo problema, programação de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência e da máquina com objetivo de minimizar o tempo de processamento total da máquina com maior carga entre todas (makespan), propõe-se um modelo matemático para varrer a vizinhança de uma solução e identificar sequências de movimentos de tarefas que podem ser aplicadas na respectiva solução de modo a minimizar a função objetivo. Nos dois casos os modelos matemáticos são resolvidos utilizando um otimizador comercial. Extensivos testes computacionais são realizados para demonstrar o bom desempenho das abordagens propostas.

No description available.

Recently, there has been a surge in the research and application of "Green energy" in the United States. This has been driven by the following three objectives: (1) to reduce the nation's reliance on foreign oil, (2) to mitigate emission of greenhouse gas, and (3) to create an economic stimulus within the United States. Switchgrass is the biomass of choice for the Southeastern United States. In this dissertation, we address a feedstock logistics problem associated with the delivery of switchgrass for conversion into biofuel. In order to satisfy the continual demand of biomass at a bioenergy plant, production fields within a 48-km radius of its location are assumed to be attracted into production. The bioenergy plant is expected to receive as many as 50-400 loads of biomass per day. As a result, an industrialized transportation system must be introduced as early as possible in order to remove bottlenecks and reduce the total system cost. Additionally, we assume locating multiple bioenergy plants within a given region for the production of biofuel. We develop mixed integer programming formulations for the feedstock logistics problem that we address and for some related problems, and we solve them either through the use of decomposition-based methods or directly through the use of CPLEX 12.1.0. The feedstock logistics problem that we address spans the entire system-from the growing of switchgrass to the transporting of bio-crude oil, a high energy density intermediate product, to a refinery for conversion into a final product. To facilitate understanding, we present the reader with a case study that includes a preliminary cost analysis of a real-life-based instance in order to provide the reader appropriate insights of the logistics system before applying optimization techniques for its solution. First, we consider the benefits of active versus passive ownership of the production fields. This is followed by a discussion on the selection of baler type, and then, a discussion of contracts between various business entities. The advantages of storing biomass at a satellite storage location (SSL) and interactions between the operations performed at the production field with those performed at the storage locations are then established. We also provide a detailed description of the operations performed at a SSL. Three potential equipment options are presented for transporting biomass from the SSLs to a utilization point, defined in this study as a Bio-crude Plant (BcP). The details of the entire logistics chain are presented in order to highlight the need for making decisions in view of the entire chain rather than basing them on its segments. We model the feedstock logistics problem as a combination of a 2-level facility location-allocation problem and a multiple traveling salesmen problem (mATSP). The 2-level facility location-allocation problem pertains to the allocation of production fields to SSLs and SSLs to one of the multiple bioenergy plants. The mATSP arises because of the need for scheduling unloading operations at the SSLs. To this end, we provide a detailed study of 13 formulations of the mATSP and their reformulations as ATSPs. First, we assume that the SSLs are always full, regardless of when they are scheduled to be unloaded. We, then, relax this assumption by providing precedence constraints on the availability of the SSLs. This precedence is defined in two different ways and, is then, effectively modeled utilizing all the formulations for the mATSP and ATSP. Given the location of a BcP for the conversion of biomass to bio-crude oil, we develop a feedstock logistics system that relies on the use of SSLs for temporary storage and loading of round bales. Three equipment systems are considered for handling biomass at the SSLs, and they are either placed permanently or are mobile, and thereby, travel from one SSL to another. We use a mathematical programming-based approach to determine SSLs and equipment routes in order to minimize the total cost incurred. The mathematical program is applied to a real-life production region in South-central Virginia (Gretna, VA), and it clearly reveals the benefits of using SSLs as a part of the logistics system. Finally, we provide a sensitivity analysis on the input parameters that we used. This analysis highlights the key cost factors in the model, and it emphasizes areas where biggest gains can be achieved for further cost reduction. For a more general scenario, where multiple BcPs have to be located, we use a nested Benders' decomposition-based method. First, we prove the validity of using this method. We, then, employ this method for the solution of a potential real-life instance. Moreover, we successfully solve problems that are more than an order of magnitude larger than those solved directly by CPLEX 12.1.0. Finally, we develop a Benders' decomposition-based method for the solution of a problem that gives rise to a binary sub-problem. The difficulty arises because of the sub-problem being an integer program for which the dual solution is not readily available. Our approach consists of first solving the integer sub-problem, and then, generating the convex hull at the optimal integer point. We illustrate this approach for an instance for which such a convex hull is readily available, but otherwise, it is too expensive to generate for the entire problem. This special instance is the solution of the mATSP (using Benders' decomposition) for which each of the sub-problems is an ATSP. The convex hull for the ATSP is given by the Dantzig, Fulkerson, and Johnson constraints. These constraints at a given integer solution point are only polynomial in number. With the inclusion of these constraints, a linear programming solution and its corresponding dual solution can now be obtained at the optimal integer points. We have proven the validity of using this method. However, the success of our algorithm is limited because of a large number of integer problems that must be solved at every iteration. While the algorithm is theoretically promising, the advantages of the decomposition do not seem to outweigh the additional cost resulting from solving a larger number of decomposed problems. / Ph. D.