Indiana University-Purdue University Indianapolis (IUPUI) / While optimization techniques have been studied since 300 B.C. when Euclid first considered the minimal distance between a point and a line, it wasn’t until 1966 that location optimization was first applied to a problem in healthcare. Location optimization techniques are capable of increasing efficiency and equity in the placement of many types of services, including those within the healthcare industry, thus enhancing quality of life. Medical imaging is a healthcare service which helps to determine medical diagnoses in acute and preventive care settings. It provides physicians with information guiding treatment and returning a patient back to optimal health. In this study, a retrospective analysis of the locations of current medical imaging centers in central Indiana is performed, and alternate placement as determined using optimization techniques is considered and compared. This study focuses on reducing the drive time experienced by the population within the study area to their nearest imaging facility. Location optimization models such as the P-Median model, the Maximum Covering model, and Clustering and Partitioning are often used in the field of operations research to solve location problems, but are lesser known within the discipline of Geographic Information Science. This study was intended to demonstrate the capabilities of these powerful algorithms and to increase understanding of how they may be applied to problems within healthcare. While the P-Median model is effective at reducing the overall drive time for a given network set, individuals within the network may experience lengthy drive times. The results further indicate that while the Maximum Covering model is more equitable than the P-Median model, it produces large sets of assigned individuals overwhelming the capacity of one imaging center. Finally, the Clustering and Partitioning method is effective at limiting the number of individuals assigned to a given imaging center, but it does not provide information regarding average drive time for those individuals. In the end, it is determined that a capacitated Maximal Covering model would be the preferred method for solving this particular location problem.

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 2015-05-08T14:53:37Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3740949 bytes, checksum: 4b4bb1e725e28d0a9a489835e70b4e60 (MD5) Previous issue date: 2014-02-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Find emergency public services falls into one of the classic optimization problems where points are available for candidates who are chosen, among them, those that optimize the efficiency criteria established, to find a limited number of facilities. The set of candidate sites have great influence on the final solution generated by a model location . In the research, three strategies were used to elect local candidates to position the cars of police : decision of the Security Manager , p-median model and method of clustering k-means. With the support of Geographical Information Systems (GIS ) it was possible to georeference the occurrences of crimes , to visualize the distribution of selected local candidates and identify the presence of hotspots of crime. Aiming to solve the problem of allocating vehicles adopted two approaches : exact and heuristic . Therefore, two hybrid meta - heuristics were implemented - GRASP combined with VND and GRASP with exact model. They obtained same or very approximate solutions of the optimal solution . It was developed a system of spatial decision support based on the solution of the formulation of the problem of locating facilities with restricted coverage and backup coverage. It is a Web tool built with by WebGIS technology / Localizar serviços públicos emergenciais se enquadra em um dos problemas clássicos de otimização onde pontos candidatos são disponibilizados para que sejam escolhidos, dentre eles, aqueles que otimizem o critério de eficiência estabelecido, visando localizar um número limitado de facilidades. O conjunto de locais candidatos tem grande influência sobre a solução final gerada por um modelo de localização. Na pesquisa, foram definidas três estratégias para eleger os locais candidatos ao posicionamento de viaturas policiais: decisão do gestor de segurança, modelo de Pmedianas e método de clusterização k-means. Com apoio de Sistemas de Informação Geográfica (SIG) foi possível georreferenciar as ocorrências de crimes, visualizar a distribuição dos locais candidatos selecionados e identificar a presença de hotspots de crimes. Visando resolver o problema de alocação de viaturas adotou-se duas abordagens: exata e heurística. Para tanto, duas meta-heurísticas híbridas foram implementadas - GRASP combinado com VND e GRASP com modelo exato, as quais obtiveram soluções iguais ou muito aproximadas da solução ótima. Foi desenvolvido um sistema de apoio a decisão espacial baseado na solução da formulação do problema de localização de facilidades com restrições de cobertura e cobertura backup. Trata-se de uma ferramenta WEB construída com base os padrões usados pela tecnologia WebGIS

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

Les problèmes que nous considérons dans cette thèse sont de nature combinatoire. Notre principal intérêt est le problème de restructuration de données semi-structurées. Par exemple des données stockées sous la forme d’un fichier XML sont des données semi-structurées. Ce problème peut être ramené à une instance du problème du p-médian. Le principal obstacle ici est la taille des instances qui peut devenir très grande. Certaines instances peuvent avoir jusqu’à 10000 ou 20000 sommets, ce qui implique plusieurs centaines de millions de variables. Pour ces instances, résoudre ne serait-ce que la relaxation linéaire du problème est très difficile. Lors d’expériences préliminaires nous nous sommes rendu compte que CPLEX peut résoudre des instances avec 1000 sommets dans des temps raisonnables. Mais pour des instances de 5000 sommets, il peut prendre jusqu’à 14 jours pour résoudre uniquement la relaxation linéaire. Pour ces raisons nous ne pouvons utiliser de méthodes qui considère la résolution de la relaxation linéaire comme une opération de base, comme par exemple les méthodes de coupes et de branchements. Au lieu d’utiliser CPLEX nous utilisons une implémentation parallèle (utilisant 32 processeurs) de l’algorithme du Volume. L’instance pour laquelle CPLEX demande 14 heures est résolue en 24 minutes par l’implémentation séquentielle et en 10 minutes par l’implémentation parallèle de l’algorithme du Volume. La solution de la relaxation linéaire est utilisée pour construire une solution réalisable, grâce à l’application d’une heuristique de construction gloutonne puis d’une recherche locale. Nous obtenons des résultats comparables aux résultats obtenus par les meilleures heuristiques connues à ce jour, qui utilisent beaucoup plus de mémoire et réalisent beaucoup plus d’opérations. La mémoire est importante dans notre cas, puisque nous travaillons sur des données de très grandes tailles. Nous étudions le dominant du polytope associé au problème du p-médian. Nous discutons de sa relaxation linéaire ainsi que de sa caractérisation polyédrale. Enfin, nous considérons une version plus réaliste du problème de restructuration de données semi-structurées. Grosso modo, nous ajoutons au problème du p-médian original des nouveaux sommets s’ils aident à réduire le coût global des affectations. / The problems we consider in this thesis are of combinatorial nature. Our main interest is the problem of approximating typing of a semistructured data. For example XML is a semistructured data. This problem may be reduced to an instance of the p-median problem. The main obstacle here is the size of the instances that may be very huge, about 10000 and 20000 nodes which imply several hundreds of million variables. For these instances, even solving the linear relaxation is a hard task. In some preliminary results we noticed that Cplex may solve instances of size 1000 in an acceptable time. But for some instances having 5000 nodes, it may needs 14 days for solving only the linear relaxation. Therefore, we cannot use methods that consider the linear relaxation as an elementary operation, as for example branch-and-cut methods. Instead of using Cplex we use the Volume algorithm in a parallel implementation (32 processors).For the instance where the Cplex needs 14 hours, the Volume algorithm in sequential implementation needs 24 minutes and in parallel implementation it needs 10 minutes. The solution of the linear relaxation is used to produce a feasible solution by first applying a greedy and then a local search heuristic. We notice that the results we obtain are relatively the same as those given by the best method known up today, which produces more effort and consumes more memory. Memory is important in our case since the data we consider are huge. We study the dominant of the polytope associated with the p-median problem. We discuss linear relaxation and a polyhedral characterization. Finally, we consider a more realistic version of the p-median problem when applied to the problem of approximating typing of a semistructured data. Roughly speaking, we add new nodes to the underlying graph if this help to reduce the overall cost.

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.

GPS technology has been embedded into portable, low-cost electronic devices nowadays to track the movements of mobile objects. This implication has greatly impacted the transportation field by creating a novel and rich source of traffic data on the road network. Although the promise offered by GPS devices to overcome problems like underreporting, respondent fatigue, inaccuracies and other human errors in data collection is significant; the technology is still relatively new that it raises many issues for potential users. These issues tend to revolve around the following areas: reliability, data processing and the related application. This thesis aims to study the GPS tracking form the methodological, technical and practical aspects. It first evaluates the reliability of GPS based traffic data based on data from an experiment containing three different traffic modes (car, bike and bus) traveling along the road network. It then outline the general procedure for processing GPS tracking data and discuss related issues that are uncovered by using real-world GPS tracking data of 316 cars. Thirdly, it investigates the influence of road network density in finding optimal location for enhancing travel efficiency and decreasing travel cost. The results show that the geographical positioning is reliable. Velocity is slightly underestimated, whereas altitude measurements are unreliable.Post processing techniques with auxiliary information is found necessary and important when solving the inaccuracy of GPS data. The densities of the road network influence the finding of optimal locations. The influence will stabilize at a certain level and do not deteriorate when the node density is higher.

Indiana University-Purdue University Indianapolis (IUPUI) / The aging infrastructure of a wastewater collection system can leak, capture ground water, and capture precipitation runoff. These are some of the most common problems in many of today’s US collection systems and are often collectively referred to as Rain Derived Inflow and Infiltration (RDII or I/I). The goal of this study is to investigate such optimized methods and their potential to improve flow monitor placement, especially for RDII studies, and to improve upon Stevens (2005) methodology. This project adopts a methodology from the “facility location problem”, a branch of operations research and graph theory. Solutions to a facility location problem will be adapted and utilized within a transportation GIS application to determine optimal placement.

No description available.