The p-median problem is an NP-complete combinatorial optimization problem often used in the fields of facility location and clustering. Given a graph with n nodes and an integer p < n, the p-median problem seeks a set of p medians such that the sum of the distances of the n nodes from their nearest median is minimized. This dissertation develops a genetic algorithm that generates solutions to the p-median problem that improves on previously published genetic algorithms by implementing operators that exploit domain specific information. More specifically, this GA explores the following: (1) The advantages of using "good" solutions generated using extant heuristics in the initial generation of chromosomes. (2) The effectiveness of a crossover operation that exchanges centers in the same neighborhood rather than exchanging arbitrarily chosen subsets of centers. (3) The efficacy of using a biased mutation operator that favors replacing existing medians from less fit chromosomes with non-median nodes from the same neighborhood as the median being replaced. Using published problem sets with known solutions, this dissertation examines solutions identified by the new genetic algorithm in order to determine the accuracy, efficiency and performance characteristics of the new algorithm. In addition, it tests the contribution of each of the algorithm's operators by systematically controlling for all the other factors. The results of the analysis showed that integrating operators that exploited domain specific information did have an overall positive impact on the genetic algorithm. In addition, the results showed that using a structured initial population had little impact on the algorithm's ability to find an optimal solution but it did create a better initial solution and allowed the algorithm to produce a relatively good solution early in the search. Also, the analysis showed that a directed approach to crossover operations was effective and produced superior solutions. Finally, the analysis showed that a directed approach toward mutation did not have a large impact on the overall functionality of the algorithm and may be inferior to an arbitrary approach to mutation.

This report presents an optimization of the allocation of maintenance resources for Air Navigation Service (ANS) equipment of which LFV is responsible for the maintenance. The purpose the authors have worked after is to research ways of minimizing travelling time linked to maintenance visits for ANS equipment, this report includes the suggestions where the maintenance facilities should be placed in order to minimize the total travelling time. The report describes the problem background and presents the customer, LFV. It includes a chapter on some of the theories used for facility location and routing, and also presents methods for reducing the total travelling time used for maintenance visits annually. The authors have worked with a given set of airports in Sweden. Information about the general work with maintenance as well as the annual demand of maintenance, including the frequency of visits, for each airport included in this project was received by Pär Oberger, the task expert and contact at LFV for this report. A model for facility location based on the p-median model have been created and used when solving the problem, it was written in AMPL and solved with the CPLEX solver. The model was modified with two additional constraints regulating the minimum annual working time and the maximum distance for one-way travelling. The authors deems that a solution with five facilities is better since the benefit of additional facilities, in term of lower total distance, do not compensate for the assumed cost of establishing them.

Förväntningarna på en väl fungerande trafiksituation med få stopp på vägarna är idag höga i Sverige. Befolkningsmängden i Stockholm ökar ständigt vilket innebär en ökad reseefterfrågan som bidrar till ett högt belastat vägnät. Vägar i storstadsmiljö med hårt belastad trafik är känsliga för minsta störning eftersom det kan innebära en stor påverkan på hela nätverket och på så sätt beröra ett stort antal trafikanter. För att minimera störningar i vägnätet bedriver Trafik Stockholm som en del av deras arbete verksamheten VägAssistans. VägAssistans är ett användbart verktyg för att snabbt lösa störningar i vägnätet och behålla en god trafikmiljö på vägarna. Ur ett samhällsekonomiskt perspektiv är det viktigt att VägAssistansfordonen placeras så att fordonet är snabbt på plats vid en händelse för att minimera störningar i nätverket. För detta krävs korta inställelsetider till områden där hög frekvens av händelser förekommer. Dessutom är det även viktigt att fordonen placera så att samtliga vägar i nätverket kan nås inom en rimlig körtid. Syftet med detta examensarbete är att utveckla ett beslutstödsverktyg för utvärdering av VägAssistansfordonsplaceringar. Syftet innefattar även att för beslutstödsverktyget utveckla en efterfrågemodell för prognostisering av framtida händelser, en körtidsmodell för att generera körtider i nätverket samt att ta fram intressanta effektivitetsmått för utvärdering och jämförelse av olika fordonplaceringar. Beslutstödsverktyget som utvecklas i detta projekt anses vara till stor nytta för Trafik Stockholm vid utvärdering av Vägassistansfordonsplaceringar i Stockholm. Dessa utvärderingar kan användas som stöd för att strategiskt placera VägAssistansfordonen så att händelser servas snabbt för att minimera störningen i nätverket som händelsen ger upphov till. En snabbare servad händelse innebär att antalet berörda trafikanter minimeras vilket leder till en minskad samhällskostnad.

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.

The Swedish Red Cross (SRK) plays an important humanitarian role by selling donated clothes in order to collect more money to help people in need. An extended network of 251 second-hand stores is built nationwide, where donors leave their clothes and buyers can buy them at competitive prices. However, an amount of these clothes remain unsold and ends up being shipped to textile recycling centers. The organization plans to build some Regional Sorting Facilities, where a careful sorting will take place and the clothes will be stored, until they will be redistributed to other stores within thecountry.This project aims to find the optimal number and location of these facilities in a way that the transportation cost from stores to facilities is minimized. SRKs Logistics Department operationalizes this aim to the following objective: place a minimum number of facilities such that at least 50% of the stores or 50% of the produced revenues are reached in less than 90 minutes of driving time. Thus, modern GIS software is used in a Location-Allocation analysis to solve the p-median problem. The core of the methodology in this thesis is the well known Vertex Substitution heuristic algorithm (Teitz &amp; Bart).Empirical evaluations of seven (7) scenarios comprised of optimally placing an increasing number of facilities from one (1) to seven (7) reveal that five (5) facilities is sufficient to meet the operational objective with the minimal number of resources/facilities. The solutions for all scenarios are analyzed in terms of statistics (Key Performance Indicators) and are illustrated on maps.

This study deals with four location problems. The first problem is a brand new location problem on a line and considers the location decisions for depots and quarries in a highway construction project. We develop optimal solution properties of the problem. Using these properties, a dynamic programming algorithm is proposed. The second problem is also a brand new dynamic location problem on a line and locates concrete batching mobile and immobile facilities for a railroad construction project. We develop two mixed integer models to solve the problem. For solving large size problems, we propose a heuristic. Performances of models and the heuristic are tested on randomly generated instances plus a case study data and results are presented. The third problem is a generalization of the second problem to network locations. It is a dynamic version of the well known p-median problem and incorporates mobile facilities. The problem is to locate predetermined number of mobile and immobile facilities over a planning horizon such that sum of facility movement and allocation costs is minimized. Three constructive heuristics and a branch-and-price algorithm are proposed. Performances of these solution procedures are tested on randomly generated instances and results are presented. In the fourth problem we consider a special case of the third problem, allowing only conventional facilities. The algorithm for the third problem is improved so that generating columns and solving a mixed integer model are used repetitively. Performance of the algorithm is tested on randomly generated instances and results are presented.

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.

Several studies have been carryout on finding optimal locations to minimize CO2 emissions from the last mile distribution perspective. In conjunction with that, there has been no study conducted in Sweden that provides a decision support system to compute the transport consequences of the modifications in the retailer’s store network. This thesis did used the following steps: requirement analysis, system design, implementation and testing to build a prototype decision support system that is to help retailers find optimal locations for a new retail store. This thesis provided a subsequent answer as to which data are needed along with the rightful user interface for said decision support system. Subsequently, this thesis does present a decision support system prototype from which some recommendations were provided as to what skills set and tools are needed for the management and maintenance of said decision support system. The primary data used during this thesis is the Dalarna municipalities, six selected retailer’s stores networks and the Dalarna Road network geo-data (Longitude and latitude). This thesis does conclude that it is possible to integrate an optimization model within the Django framework using a geo data to build a decision support system.

No description available.

The p-median problem is often used to locate p service centers by minimizing their distances to a geographically distributed demand (n). The optimal locations are sensitive to geographical context such as road network and demand points especially when they are asymmetrically distributed in the plane. Most studies focus on evaluating performances of the p-median model when p and n vary. To our knowledge this is not a very well-studied problem when the road network is alternated especially when it is applied in a real world context. The aim in this study is to analyze how the optimal location solutions vary, using the p-median model, when the density in the road network is alternated. The investigation is conducted by the means of a case study in a region in Sweden with an asymmetrically distributed population (15,000 weighted demand points), Dalecarlia. To locate 5 to 50 service centers we use the national transport administrations official road network (NVDB). The road network consists of 1.5 million nodes. To find the optimal location we start with 500 candidate nodes in the network and increase the number of candidate nodes in steps up to 67,000. To find the optimal solution we use a simulated annealing algorithm with adaptive tuning of the temperature. The results show that there is a limited improvement in the optimal solutions when nodes in the road network increase and p is low. When p is high the improvements are larger. The results also show that choice of the best network depends on p. The larger p the larger density of the network is needed.