In this thesis, we study the dynamic facility location problem with mobile customers considering the permanent facilities. Our general aim is to locate facilities considering the movements of customers in time. The problem is studied for three objectives: P-median, P-center and MINMAX P-median. We show that dynamic facility location problem is a large instance of a static facility location problem for P-median and P-center objectives. In the problem, we represent the movements of each customer in time with a time series. Using clustering approaches, we develop a heuristic approach for the problem with P-median objective. K-means algorithm is used as a clustering algorithm and dynamic time warping is used in order to define similarities between the customer time series. Solution method is tested on several experimental settings. We obtain results, which differ at most 2% from the optimal, in small computation times. Generally, in the literature, MINMAX P-median is solved with a heuristic depending on scenarios planning (see Serra and Marianov, 1998). The heuristic finds an initial solution according to scenarios, later the initial solution is tried to be improved. We provide a bounding procedure on the solution of the problem. The bounds can be used by decision maker to judge the solution quality before proceed. The bounding procedure is also analyzed in different experimental settings.

No description available.

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.

The objective of this dissertation is to study commonly occurring location and clustering problems on graphs. The dissertation is presented as a collection of results in topics including finding maximum cliques in large graphs, graph clustering in large scale graphs, determining location of facilities for pre-positioning emergency relief supplies, and selecting nodes to form a virtual backbone in a wireless sensor network. To begin with, a new clique relaxation called a k-community is defined as a connected subgraph such that endpoints of every edge have at least k common neighbors within the subgraph. It is used to develop scale reduction techniques to obtain the maximum clique on very large scale real life networks. Analytically, the technique is been shown to be very effective on power-law random graphs. Experimental results on real life graph instances (Collaboration networks, P2P networks, Social networks, etc.) show our procedure to be much more effective than a regular k-core peeling approach. Next, a general purpose network clustering algorithm based on the clique relaxation concept of k-community is presented. A salient feature of this approach is that it does not use any prior information about the structure of the network. By defining a cluster as a k-community, the proposed algorithm aims to provide a clustering of a network into k-communities with varying values of k. Even though the algorithm is not designed to optimize any particular performance measure, the computational results suggest that it performs well on a number of criteria that are used in literature to evaluate the quality of a clustering. The third topic deals with choosing the locations of disaster response facilities for the storage of emergency supplies, which is critical to the quality of service provided in a large scale emergency like an earthquake. In the existing literature, large scale emergency facility location models have either assumed that disaster response facilities will always be functioning and available when required, or that the functioning of a facility is independent of a particular disaster scenario. In this paper new location models are presented that explicitly take into consideration the stochastic nature of the impact a disaster can have on the disaster response facilities and the population centers in surrounding areas. A comparison of the results obtained using our models with those from models available in literature using a case study suggests that the locations suggested by the model in this paper significantly reduce the expected cost of transportation of supplies when we consider the damage a disaster causes to the disaster response facilities and areas near it. Lastly, a distributed approximate algorithm for forming the communication backbone in wireless sensor networks is presented. Some of the most popular routing protocols for wireless sensor networks require a virtual backbone for efficient communication be- tween the sensors. Connected Dominating Sets (CDS) have been studied as a method of choosing nodes to be in the backbone. The traditional approach is to assume that the transmission range of each node is given and then minimize the number of nodes in the CDS representing the backbone. A recently introduced alternative strategy is based on the concept of k-bottleneck connected dominating set (k-BCDS), which, given a positive integer k, minimizes the transmission range of the nodes that ensures a CDS of size k exists in the network. This paper provides a 6-approximate distributed algorithm for the k-BCDS problem. The results of empirical evaluation of the proposed algorithm are also included.

Truck transportation is considered as a favourable mode by shippers to carry freight at most ranges of distance as it has more flexibility in fleet size, capacity, scheduling, routing, and access. Although truck is considered as the popular mode for freight transportation, road-rail intermodal freight transportation becomes an attractive alternative to road only mode since the latter has no longer assured a reliable service due to traffic congestion problem. It also raises public concern in environmental and road safety impacts. Intermodal freight transportation is defined as a system that carries freight from origin to destination using two or more transportation modes where transfers between modes occur at an intermodal freight terminal. Success of the terminal depends on four major factors, namely: location, efficiency, financial sustainability, and rail level of service. Among these, the location is one of the most crucial success factors and needs to be considered carefully as it has direct and indirect impacts on a number of stakeholders including terminal users, terminal operators, transport network infrastructure providers, and community. Limitations of previous terminal location evaluation models in representing individual preference and behaviour as well as accommodating negotiation and communication between the players bring in an opportunity to develop a new model which is more flexible and capable of providing a solution that is not necessary to be optimal, but acceptable for every player without requiring explicit trade-offs. This thesis is aimed at demonstrating the feasibility of applying an agent-based approach to the evaluation of intermodal freight terminal location and investigating terminal effectiveness against stakeholder equity and some important aspects arising from the different stakeholders’ viewpoints. Agent technologies were introduced to model the stakeholders as individual agents. The agent concept was adopted to develop a decentralised location evaluation system that is able to balance the terminal effectiveness with the stakeholder equity. The proposed agent-based location evaluation model was modelled as a hierarchical control system that comprises three decision levels: local level, stakeholder level and policy level. Policy level is the highest decision level, which is represented by a policy maker. Apart from the policy level, the rest can be viewed as operational decision levels. Local level is the lowest control level. At this level, each stakeholder was classified into stakeholder groups based on their characteristics and interest. The terminal scenarios were then evaluated based on benefit maximisation criteria. Stakeholder control is the higher control level than the local level. It represents the control level where negotiations and decisions between groups of people (stakeholders) with different point of views are made. At this level, negotiation process was used to determine terminal location based on preference and equity of stakeholders. The determined terminal site was then used in the evaluation against constraints to ensure that all agents are satisfied. The terminal location decision for South East Queensland (SEQ) was applied as a case study of this thesis. The SEQ strategic freight transport model was developed, calibrated, and validated to assist in providing inputs for the evaluation of terminal location. The results indicated that for the developed agent-based location evaluation model, Yatala was selected as the most appropriate terminal location that results in the highest effectiveness and equity (as measured by level of satisfaction and Gini coefficient, respectively). Other location evaluation models were also used in comparison with the developed agent-based location evaluation model. Those include P-Median, P-Centre, and maximum covering models. It was found that the agent-based location evaluation model outperformed the other location evaluation models. Finally, a sensitivity analysis was conducted in order to evaluate the consistency of model outputs against the uncertainties in the input parameters. In most cases, the terminal location decisions obtained from the developed agent-based location evaluation model was not sensitive to the changes in those parameters. However, the results suggested that when a unit cost of truck travel delay increased, the impact on the final terminal location decisions was observed. This thesis demonstrated the feasibility of applying a decentralised approach to terminal location decision problem using a multi-agent concept and evaluating it against other well-known location problems. A new framework and methodology for the planning of intermodal terminal location evaluation was also formulated. Finally, the problems of terminal location evaluation and optimisation of intermodal freight terminal operation were integrated into a single evaluation model.

This thesis covers three main issues in content delivery with a focus on placement algorithms of replica servers and replica contents. In a content delivery system, the location of replicas is very important as perceived by a quotation: Closer is better. However, considering the costs incurred by replication, it is a challenge to deploy replicas in a cost-effective manner. The objective of our work is to optimally select the location of replicas which includes sites for replica server deployment, servers for replica contents hosting, and en-route caches for object caching. Our solutions for corresponding applications are presented in three parts of the work, which makes significant contributions for designing scalable, reliable, and efficient systems for Internet content delivery. In the first part, we define the Fault-Tolerant Facility Allocation (FTFA) problem for the placement of replica servers, which relaxes the well known Fault-Tolerant Facility Location (FTFL) problem by allowing an integer (instead of binary) number of facilities per site. We show that the problem is NP-hard even for the metric version, where connection costs satisfy the triangle inequality. We propose two efficient algorithms for the metric FTFA problem with approximation factors 1.81 and 1.61 respectively, where the second algorithm is also shown to be (1.11,1.78)- and (1,2)-approximation through the proposed inverse dual fitting technique. The first bi-factor approximation result is further used to achieve a 1.52-approximation algorithm and the second one a 4-approximation algorithm for the metric Fault-Tolerant k-Facility Allocation problem, where an upper bound of facility number (i. e. k) applies. In the second part, we formulate the problem of QoS-aware content replication for parallel access in terms of combined download speed maximization, where each client has a given degree of parallel connections determined by its QoS requirement. The problem is further converted into the metric FTFL problem and we propose an approximation algorithm which is implemented in a distributed and asynchronous manner of communication. We show theoretically that the cost of our solution is no more than 2F* + RC*, where F* and C* are two components of any optimal solution while R is the maximum number of parallel connections. Numerical experiments show that the cost of our solutions is comparable (within 4% error) to the optimal solutions. In the third part, we establish mathematical formulation for the en-route web caching problem in a multi-server network that takes into account all requests (to any server) passing through the intermediate nodes on a request/response path. The problem is to cache the requested object optimally on the path so that the total system gain is maximized. We consider the unconstrained case and two QoS-constrained cases respectively, using efficient dynamic programming based methods. Simulation experiments show that our methods either yield a steady performance improvement (in the unconstrained case) or provide required QoS guarantees. / http://proxy.library.adelaide.edu.au/login?url= http://library.adelaide.edu.au/cgi-bin/Pwebrecon.cgi?BBID=1461921 / Thesis (Ph.D.) - University of Adelaide, School of Computer Science, 2009

Prompt and efficient intervention is vital in reducing casualty figures during epidemic outbreaks, disasters, sudden civil strife or terrorism attacks. This can only be achieved if there is a fit-for-purpose and location-specific emergency response plan in place, incorporating geographical, time and vehicular capacity constraints. In this research, a comprehensive emergency response model for situations of uncertainties (in locations' demand and available resources), typically obtainable in low-resource countries, is designed. It involves the development of algorithms for optimizing pre-and post-disaster activities. The studies result in the development of four models: (1) an adaptation of a machine learning clustering algorithm, for pre-positioning depots and emergency operation centers, which optimizes the placement of these depots, such that the largest geographical location is covered, and the maximum number of individuals reached, with minimal facility cost; (2) an optimization algorithm for routing relief distribution, using heterogenous fleets of vehicle, with considerations for uncertainties in humanitarian supplies; (3) a genetic algorithm-based route improvement model; and (4) a model for integrating possible new locations into the routing network, in real-time, using emergency severity ranking, with a high priority on the most-vulnerable population. The clustering approach to solving dept location-allocation problem produces a better time complexity, and the benchmarking of the routing algorithm with existing approaches, results in competitive outcomes.

Σε μια εποχή που οι αλλαγές του οικονομικού περιβάλλοντος συμβαίνουν όλο και πιο συχνά, κάθε επιχειρηματικός οργανισμός πρέπει να αποκτήσει ικανότητα να παίρνει γρήγορα τις σωστές αποφάσεις και να τις υλοποιεί. Η λήψη αποφάσεων αποτελεί σημαντικότατο στοιχείο της καθημερινής μας ζωής και καθορίζει τη μετέπειτα πορεία μας καθώς τα αποτελέσματά της φαίνονται σε διάφορους τομείς. Το πλήθος των αποφάσεων που καλούμαστε να λάβουμε είναι τέτοιο που αρκετές φορές αποφασίζουμε ασυνείδητα και μηχανικά. Ωστόσο, το ίδιο δεν μπορεί να συμβεί και στο επιχειρηματικό περιβάλλον όπου οι αποφάσεις έχουν συνήθως στρατηγική σημασία και επηρεάζουν τόσο τη σωστή λειτουργία όσο τη καλή πορεία και τη βιωσιμότητα των επιχειρήσεων. Ο σκοπός της συγκεκριμένης διπλωματικής εργασίας είναι η ανάδειξη του ρόλου της εφοδιαστικής αλυσίδας στη λήψη αποφάσεων. Μέσα από τη δημιουργία κατάλληλων μοντέλων γραμμικού προγραμματισμού, τα οποία αντιπροσωπεύουν τη λειτουργία της εφοδιαστικής αλυσίδας, είναι εφικτή η πρόβλεψη πιθανών μελλοντικών σεναρίων. Συνεπώς, η διοίκηση μιας εταιρείας θα μπορεί να είναι σε θέση να λαμβάνει γρήγορα και αντικειμενικά τις απαραίτητες αποφάσεις στρατηγικής σημασίας για την αντιμετώπιση οποιασδήποτε κατάστασης. Η παρούσα διπλωματική εργασία στηρίχτηκε στην εργασία των M.T. Melo, S. Nickela,b, F. Saldanha da Gama «Dynamic multi-commodity capacitated facility location: a mathematical modeling framework for strategic supply chain planning». Το συγκεκριμένο paper βραβεύτηκε ως ένα από τα καλύτερα το 2012 στο «Euro Award for the Best Ejor Paper 2012». Η δομή της εργασίας είναι η εξής: Στο 1ο κεφάλαιο γίνεται μια εισαγωγή σε βασικές έννοιες όπως αυτή της χωροθέτησης εγκαταστάσεων και της εφοδιαστικής αλυσίδας. Επίσης παρουσιάζεται και η μεθοδολογική προσέγγιση για την παρουσίαση των προβλημάτων. Στο 2ο κεφάλαιο παρουσιάζονται τα μοντέλα χωροθέτησης. Αυτά κατηγοριοποιούνται στα Βασικά Μοντέλα Χωροθέτησης όπου παρατίθενται αναλυτικά οχτώ από αυτά, στα Δυναμικά Μοντέλα Χωροθέτησης και στα Στοχαστικά Μοντέλα Χωροθέτησης. Το 3ο κεφάλαιο ασχολείται με την εφαρμογή. Συγκεκριμένα, παρουσιάζεται η περιγραφή και η διατύπωση του προβλήματος όπου παρατίθενται εκτενώς τα σύνολα, οι παράμετροι, οι μεταβλητές απόφασης και οι περιορισμοί που απαιτούνται για την επίλυση του μοντέλου μας. Το 4ο κεφάλαιο ασχολείται με την ανάλυση των αποτελεσμάτων που προκύπτουν ύστερα από την επίλυση του μοντέλου στο περιβάλλον του AIMMS. Συγκεκριμένα παρατίθενται αναλυτικά τα σενάρια που έχουμε θεωρήσει ως πραγματικά καθώς και οι βέλτιστες λύσεις για κάθε ένα ξεχωριστά από αυτά. Εν κατακλείδι, στο 5ο κεφάλαιο παρουσιάζονται τα συμπεράσματα της συγκεκριμένης εργασίας και η μελλοντική έρευνα. / We are living in a time where the economic environment changes are happening more and more frequently. For that reason, every business organization must acquire capacity to make and implement the right decisions quickly. Decision making is an important part of our daily lives and determines our future since the results are shown in different areas. The number of decisions we take are so many that we decide unconsciously and mechanically. However, the same cannot happen in the business environment where the decisions are usually of strategic importance, while they affect both the proper functioning and the good performance and sustainability of the business. The purpose of this thesis is to highlight the role of supply chain decision making. Through the creation of suitable linear programming models, which represent the operation of the supply chain, it is possible to predict potential future scenarios. Therefore, the management of a company will be able to quickly and objectively make the necessary strategic decisions to deal with any situation. This thesis was based on the work of MT Melo, S. Nickel, F. Saldanha da Gama «Dynamic multi-commodity capacitated facility location: a mathematical modeling framework for strategic supply chain planning». This paper was awarded as one of the best in 2012 in «Euro Award for the Best Ejor Paper 2012». The structure of the paper is as follows: The first chapter contains an introduction to basic concepts such as the facilities location and supply chain. Also, it is presented the methodological approach to the problems. In the second chapter, they are presented the facility location models. These are categorized into Basic Location Models, into Dynamic Location Models and into Stochastic Location Models. The third chapter deals with the application. Specifically, it is presented the description and the formulation of the problem, in detail, along with the sets, the parameters, the decision variables and the constraints that are required in order to solve our model. The fourth chapter deals with the analysis of the results obtained after solving the model in the environment of AIMMS. Specifically, they are presented in detail the scenarios that we consider as real along with the best solutions for each one of them. In conclusion, in the fifth chapter they are presented the conclusions of this study and the future research.

abstract: Concerns about Peak Oil, political instability in the Middle East, health hazards, and greenhouse gas emissions of fossil fuels have stimulated interests in alternative fuels such as biofuels, natural gas, electricity, and hydrogen. Alternative fuels are expected to play an important role in a transition to a sustainable transportation system. One of the major barriers to the success of alternative-fuel vehicles (AFV) is the lack of infrastructure for producing, distributing, and delivering alternative fuels. Efficient methods that locate alternative-fuel refueling stations are essential in accelerating the advent of a new energy economy. The objectives of this research are to develop a location model and a Spatial Decision Support System (SDSS) that aims to support the decision of developing initial alternative-fuel stations. The main focus of this research is the development of a location model for siting alt-fuel refueling stations considering not only the limited driving range of AFVs but also the necessary deviations that drivers are likely to make from their shortest paths in order to refuel their AFVs when the refueling station network is sparse. To add reality and applicability of the model, the research is extended to include the development of efficient heuristic algorithms, the development of a method to incorporate AFV demand estimates into OD flow volumes, and the development of a prototype SDSS. The model and methods are tested on real-world road network data from state of Florida. The Deviation-Flow Refueling Location Model (DFRLM) locates facilities to maximize the total flows refueled on deviation paths. The flow volume is assumed to be decreasing as the deviation increases. Test results indicate that the specification of the maximum allowable deviation and specific deviation penalty functional form do have a measurable effect on the optimal locations of facilities and objective function values as well. The heuristics (greedy-adding and greedy-adding with substitution) developed here have been identified efficient in solving the DFRLM while AFV demand has a minor effect on the optimal facility locations. The prototype SDSS identifies strategic station locations by providing flexibility in combining various AFV demand scenarios. This research contributes to the literature by enhancing flow-based location models for locating alternative-fuel stations in four dimensions: (1) drivers' deviations from their shortest paths, (2) efficient solution approaches for the deviation problem, (3) incorporation of geographically uneven alt-fuel vehicle demand estimates into path-based origin-destination flow data, and (4) integration into an SDSS to help decision makers by providing solutions and insights into developing alt-fuel stations. / Dissertation/Thesis / Ph.D. Geography 2010

DIAS, Fábio Carlos Sousa. Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica. 2008. 89 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2008. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T15:12:03Z No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-15T15:32:35Z (GMT) No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) / Made available in DSpace on 2016-07-15T15:32:35Z (GMT). No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5) Previous issue date: 2008 / In this work, we study the Simple Plant Location Problem (SPLP). Using its classical mathematical programming formulation and another recently proposed formulation, we develop several algorithms to …nd lower and upper bounds for the problem as well as branch-and-bound algorithms. With the classical formulation, such bounds are obtained via the data correction method and dominance criteria between …xed and transportation costs. We propose a projection of this formulation that has shown to be computationally atractive. Using the new formulation, we propose and prove the correctness of several iterative procedures that attempt to …nd an optimal solution to the problem by solving a sequence of parametric sub-problems, each one obtained by removing some variables and constraints of the original formulation. At each iteration of this process, we can obtain lower and upper bounds. We also apply Lagrangean relaxation to this new formulation in order to get other bounds. We consider several possibilities of relaxing the constraints. In addition, we develop branch-and-bound algorithms based on both formulations and the obtained bounds. We evaluate the computational e¢ ciency of all proposed algorithms with hard test instances from the literature. Computational results are reported and comparisons with other algorithms from the literature are carried out. / Neste trabalho, estudamos o problema de localização simples (SPLP - Simple Plant Location Problem). Usando a formulação matemática clássica e uma outra formulação proposta recentemente, desenvolvemos vários algoritmos para encontrar limites inferiores e superiores, bem como algoritmos tipo branch-and-bound. Com a formulação clássica, tais limites são obtidos utilizando o método de correção de dados e critérios de dominância entre os custos …xos e de transporte. Propomos uma projeção dessa formulação, que se mostrou computacionalmente atrativa. Usando a nova formulação propomos e mostramos a corretude de vários procedimentos iterativos que procuram encontrar uma solução para o problema, resolvendo uma seqüência de subproblemas paramétricos obtidos com a remoção de variáveis e restrições da formulação original. Em cada iteração desse processo, podemos gerar limites inferiores e superiores. Aplicamos ainda relaxação lagrangeana a essa nova formulação para obter outros limites. Analisamos várias possibilidades de relaxação das restrições. Desenvolmento também algoritmos branch-and-bound baseados em ambas as formulações e nos limites obtidos. Avaliamos a e…ciência computacional de todos os algoritmos com instâncias de teste difíceis, disponíveis na literatura. Resultados computacionais e comparações com outros algoritmos da literatura são reportados.