Dissertations / Theses on the topic 'Locational problems'
To see the other types of publications on this topic, follow the link: Locational problems.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Locational problems.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Chakraborti, Nisith Ranjan. "Solution of certain locational problems arising in L1 Norms." Thesis, University of North Bengal, 1994. http://hdl.handle.net/123456789/598.
Full text
2
Hussein, E. A. "Dual-based methods for some covering problems in locational analysis." Thesis, University of Liverpool, 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.356269.
Full text
3
Ross, Kim A. "The locational history of Scotland's district lunatic asylums, 1857-1913." Thesis, University of Glasgow, 2014. http://theses.gla.ac.uk/5320/.
Full textAbstract:
This thesis looks into the later ‘Asylum Age’ in Scotland, concentrating on the legislation and construction of Scotland’s district lunatic asylums from the passing of the Lunacy (Scotland) Act, 1857 to the Mental Deficiency and Lunacy (Scotland) Act, 1913. Concentrating on the specific geographies of the asylums, what Foucault refers to as “the space reserved by society for insanity” (Foucault, 1965:251), the thesis weaves a new route between previous radical/critical and progressive/simplistic interpretations of the ‘Asylum Age’, by integrating a Foucauldian interpretation with non-representational theories around the engineering of affective atmospheres. This more nuanced approach, which concentrates on the ‘affective power’ of the institutions across different geographical scales (site and situation, grounds and buildings), recognises the ways in which Scotland’s district asylums, constructed predominantly for pauper patients, were moulded and reshaped as the discourses around the treatment of insanity were developed. The moral, medical and hygienic dimensions to the discourses ultimately outlined the institutional geography, by having a profound influence on asylum location and layout. The ideal district ‘blueprint’ for asylum siting and design, as put forward by the Scottish Lunacy Commissioners, is uncovered and reconstructed by ‘picking out’ the macro and micro-geographies discussed in the annual reports of the General Board. The research then moves to uncover the system ‘on the ground’ as it was constructed in bricks-and-mortar by the various district boards. As asylum location and architecture was a relatively novel concern, questions of siting and design became more pertinent, and indeed central, in institutional planning during the decades after the mid-century lunacy reforms. Thus, despite periods of waning enthusiasm for the institution as a mechanism for ‘curing’ insanity, fitting the building to its purposes continually involved a variety of structural innovations, stylistic refinements and new ways of organising the external and internal spaces of the asylums.
4
Davies, Amanda Catherine. "A case of community safety : displacing complex ‘social’ problems in Fortitude Valley." Thesis, Queensland University of Technology, 2011. https://eprints.qut.edu.au/50961/1/Amanda_Davies_Thesis.pdf.
Full textAbstract:
Public dialogue regarding the high concentration of drug use and crime in inner city locations is frequently legitimised through visibility of drug-using populations and a perception of high crime rates. The public space known as the Brunswick Street Mall (Valley mall), located in the inner city Brisbane suburb of Fortitude Valley, has long provided the focal point for discussions regarding the problem of illicit drug use and antisocial behaviour in Brisbane. During the late 1990s a range of stakeholders in Fortitude Valley became mobilised to tackle crime and illicit drugs. In particular they wanted to dismantle popular perceptions of the area as representing the dark and unsafe side of Brisbane. The aim of this campaign was to instil a sense of safety in the area and dislodge Fortitude Valley from its reputation as a =symbolic location of danger‘.
This thesis is a case study about an urban site that became contested by the diverse aims of a range of stakeholders who were invested in an urban renewal program and community safety project. This case study makes visible a number of actors that were lured from their existing roles in an indeterminable number of heterogeneous networks in order to create a community safety network. The following analysis of the community safety network emphasises some specific actors: history, ideas, technologies, materialities and displacements.
The case study relies on the work of Foucault, Latour, Callon and Law to draw out the rationalities, background contingencies and the attempts to impose order and translate a number of entities into the community safety project in Fortitude Valley.
The results of this research show that the community safety project is a case of ontological politics. Specifically the data indicates that both the (reality) problem of safety and the (knowledge) solution to safety were created simultaneously. This thesis explores the idea that while violence continues to occur in the Valley, evidence that community safety got done is located through mapping its displacement and eventual disappearance. As such, this thesis argues that community safety is a =collateral reality‘.
5
Thangavelu, Balajee. "Single-Facility location problem among two-dimensional existing facility locations." Ohio University / OhioLINK, 2003. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1175283985.
Full text
6
Dias, Fábio Carlos Sousa. "Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica." reponame:Repositório Institucional da UFC, 2008. http://www.repositorio.ufc.br/handle/riufc/17871.
Full textAbstract:
DIAS, Fábio Carlos Sousa. Algoritmos para o problema de localização simples baseados nas formulações clássica e canônica. 2008. 81 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2008.Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-22T17:13:52Z No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5)
Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-22T17:16:23Z (GMT) No. of bitstreams: 1 2008_dis_fcsdias.pdf: 533140 bytes, checksum: 547c9cf8d771e2646884c423f5a39936 (MD5)
Made available in DSpace on 2016-06-22T17:16:23Z (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.
7
Dias, FÃbio Carlos Sousa. "Algoritmos para o problema de localizaÃÃo simples baseados nas formulaÃÃes clÃssica e canÃnica." Universidade Federal do CearÃ, 2008. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=2827.
Full textAbstract:
Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgicoNeste 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.
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.
8
Wei, Hu. "SOLVING CONTINUOUS SPACE LOCATION PROBLEMS." The Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1205514715.
Full text
9
San, Felice Mário César 1985. "Online facility location and Steiner problems = Problemas online de localização de instalações e de Steiner." [s.n.], 2015. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275552.
Full textAbstract:
Orientador: Orlando LeeTese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-27T12:18:11Z (GMT). No. of bitstreams: 1 SanFelice_MarioCesar_D.pdf: 1457706 bytes, checksum: 4813f4ed44c52462656d56537d73d5dc (MD5) Previous issue date: 2015
Resumo: Nesta tese estudamos problemas online das famílias de localização de instalações e de Steiner, através da abordagem de análise competitiva. O objetivo nestes problemas é construir uma rede de custo mínimo para atender a uma determinada demanda. Nós apresentamos resultados conhecidos para o problema Online da Localização de Instalações (OFL), o problema Online da Árvore de Steiner (OST) e o problema Online Single-Source Rent-or-Buy (OSRoB). O OFL consiste em atender a um conjunto de clientes, através da abertura de algumas instalações e da conexão de cada cliente com uma instalação aberta. O OST tem por objetivo conectar um conjunto de terminais utilizando uma árvore, que pode conter vértices não terminais, chamados vértices de Steiner. O OSRoB é uma versão rent-or-buy do OST, onde todos os terminais devem ser conectados a um nó especial chamado raíz. Os algoritmos e técnicas que apresentamos para estes problemas são importantes no desenvolvimento dos nossos algoritmos para os problemas que consideramos. Apresentamos novos resultados para o problema Online da Localização de Instalações com Coleta de Prêmios (OPFL), o problema Online da Árvore Estrela de Steiner (OSTS), e o problema Online da Localização de Instalações Conectadas (OCFL). O OPFL é uma generalização do OFL, em que alguns clientes podem ficar desconectados mediante o pagamento de penalidades. O OSTS é uma variante do OST, em que os vértices possuem custos não negativos. O OCFL é uma combinação do OFL e do OST, em que um conjunto de clientes precisa ser atendido através da abertura de algumas instalações, da conexão de cada cliente com uma instalação aberta, e da construção de uma árvore, mais custosa, que conecta as instalações abertas
Abstract: In this thesis we study online problems from the facility location and Steiner families, through the point of view of competitive analysis. The goal in these problems is to build a minimum cost network to attend a certain demand. We present known results for the Online Facility Location problem (OFL), the Online Steiner Tree problem (OST) and the Online Single-Source Rent-or-Buy problem (OSRoB). The OFL consists of serving a set of clients by opening some facilities and by connecting each client to a facility. The OST aims to connect a set of terminals in order to create a tree network, that may contain nonterminals, called Steiner nodes. The OSRoB is a rent-or-buy version of the OST, in which all terminals must be connected to a special node called root. The algorithms and techniques that we present for these problems play an important role in the design of our algorithms for the problems we consider. We present new results for the Online Prize-Collecting Facility Location problem (OPFL), the Online Steiner Tree Star problem (OSTS), and the Online Connected Facility Location problem (OCFL). The OPFL is a generalization of the OFL, in which some clients may be left unconnected by paying a penalty. The OSTS is a variant of the OST, in which the nodes have non-negative costs. The OCFL is a combination of the OFL and the OST, in which a set of clients needs to be served by opening some facilities, by connecting each client to a facility, and by creating a more expensive tree network that connects the open facilities
Doutorado
Ciência da Computação
Doutor em Ciência da Computação
10
Mazi, Abdullah Mazi E. "Combining heuristic and exact approach for the vertex p-centre problem and other related location problems." Thesis, University of Kent, 2010. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.544027.
Full text
11
Barutcuoglu, Aras. "Multiobjective Hub Location Problem." Master's thesis, METU, 2009. http://etd.lib.metu.edu.tr/upload/3/12610817/index.pdf.
Full textAbstract:
In this study, we propose a two-phase solution approach for approximating the efficient frontier of a bicriteria hub location problem. We develop an evolutionary algorithm to locate the hubs on the network as the first phase. In the second phase, we develop a bounding procedure based on dominance relations and using the determined bounds, we solve the allocation subproblem for each located hub set. The two-phase approach is tested on the Australian Post data set and it is observed that our approach approximates the entire efficient frontier well. In addition, we suggest an interactive procedure to find the solutions that are in the decision maker&rsquos preferred region of the solution space. In this procedure, we progressively incorporate the preferences of the decision maker and direct the search towards the preferred regions. Based on some computational experiments, it is observed that the interactive procedure converges to the preferred regions.
12
Yes̨ilkökc̨en, Gülcan N. "Supply connected location-allocation problem /." *McMaster only, 1997.
Find full text
13
Koc, Cagri. "Heterogeneous location- and pollution-routing problems." Thesis, University of Southampton, 2015. https://eprints.soton.ac.uk/384001/.
Full textAbstract:
This thesis introduces and studies new classes of heterogeneous vehicle routing problems with or without location and pollution considerations. It develops powerful evolutionary and adaptive large neighborhood search based metaheuristics capable of solving a wide variety of such problems with suitable enhancements, and provides several important managerial insights. It is structured into five main chapters. After the introduction presented in Chapter 1, Chapter 2 classifies and reviews the relevant literature on heterogeneous vehicle routing problems, and presents a comparative analysis of the available metaheuristic algorithms for these problems. Chapter 3 describes a hybrid evolutionary algorithm for four variants of heterogeneous fleet vehicle routing problems with time windows. The algorithm successfully combines several metaheuristics and introduces a number of new advanced efficient procedures. Extensive computational experiments on benchmark instances show that the algorithm is highly competitive with state-of-the art methods for the three variants. New benchmark results on the fourth problem are also presented. In Chapter 4, the thesis introduces the eet size and mix location-routing problem with time windows (FSMLRPTW) which extends the classical location-routing problem by considering a heterogeneous fleet and time windows. The main objective of the FSMLRPTW is to minimize the sum of depot cost, vehicle fixed cost and routing cost. The thesis presents integer programming formulations for the FSMLRPTW, along with a family of valid inequalities and an algorithm based on adaptation of the hybrid evolutionary metaheuristic. The strengths of the formulations are evaluated with respect to their ability to yield optimal solutions. Extensive computational experiments on new benchmark instances show that the algorithm is highly effective. Chapter 5 introduces the fleet size and mix pollution-routing problem (FSMPRP) which extends the previously studied pollution-routing problem (PRP) by considering a heterogeneous vehicle fleet. The main objective is to minimize the sum of vehicle fixed costs and routing cost, where the latter can be defined with respect to the cost of fuel and CO2 emissions, and driver cost. An adaptation of the hybrid evolutionary algorithm is successfully applied to a large pool of realistic PRP and FSMPRP benchmark instances, where new best solutions are obtained for the former. Several analyses are conducted to shed light on the trade-offs between various performance indicators. The benefit of using a heterogeneous fleet over a homogeneous one is demonstrated. In Chapter 6, the thesis investigates the combined impact of depot location, fleet composition and routing decisions on vehicle emissions in urban freight distribution characterized by several speed limits, where goods need to be delivered from a depot to customers located in different speed zones. To solve the problem, an adaptive large neighborhood search algorithm is successfully applied to a large pool of new benchmark instances. Extensive analyses are conducted to quantify the effect of various problem parameters, such as depot cost and location, customer distribution and fleet composition on key performance indicators, including fuel consumption, emissions and operational costs. The results illustrate the benefits of locating depots located in suburban areas rather than in the city centre and of using a heterogeneous fleet over a homogeneous one. The conclusions, presented in Chapter 7, summarize the results of the thesis, provide limitations of this work, as well as future research directions.
14
Velten, Sebastian. "Discrete location problems with flexible objectives." Hamburg Kovač, 2008. http://d-nb.info/992492661/04.
Full text
15
Boga, Sreekanth Roppel Thaddeus A. "Vision-enhanced localization for cooperative robotics." Auburn, Ala., 2009. http://hdl.handle.net/10415/1970.
Full text
16
Pedrosa, Lehilton Lelis Chaves 1985. "Approximation algorithms for facility location problems and other supply chain problems." [s.n.], 2014. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275516.
Full textAbstract:
Orientadores: Flávio Keidi Miyazawa, Maxim SviridenkoTese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-25T09:17:37Z (GMT). No. of bitstreams: 1 Pedrosa_LehiltonLelisChaves_D.pdf: 3649302 bytes, checksum: 9f37cca5fca5af1697c2099c8e0f2798 (MD5) Previous issue date: 2014
Resumo: O resumo poderá ser visualizado no texto completo da tese digital
Abstract: The abstract is available with the full electronic document
Doutorado
Ciência da Computação
Doutor em Ciência da Computação
17
Ingco, Divinagracia I. (Divinagracia Ilagan). "Network design problems for improving facility locations." Thesis, Massachusetts Institute of Technology, 1989. http://hdl.handle.net/1721.1/14494.
Full textAbstract:
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1989.Includes bibliographical references (leaf 116).
by Divinagracia I. Ingco.
M.S.
18
Pita, Ana Rita Granjo de Azevedo Vieira. "The Lean Startup approach in the implementation of a children location device." Master's thesis, Instituto Superior de Economia e Gestão, 2019. http://hdl.handle.net/10400.5/19295.
Full textAbstract:
Mestrado em Gestão/MBANesta dissertação de mestrado, a metodologia Lean Startup é usada para desenvolver uma solução comercial de um dispositivo vestível capaz de rastrear crianças.
In this master thesis, The Lean Startup methodology is used to develop a business solution of a wearable device that is able to track children.
info:eu-repo/semantics/publishedVersion
19
Dominguez-Marin, Patrizia. "The discrete ordered median problem: models and solution methods /." Dordrecht [u.a.] : Kluwer Acad. Publ, 2003. http://www.loc.gov/catdir/enhancements/fy0822/2003061145-d.html.
Full text
20
Yesilkokcen, Gulcan N. "Supply connected location-allocation problem." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape10/PQDD_0007/NQ42775.pdf.
Full text
21
Nadirler, Deniz. "Undesirable And Semi-desirable Facility Location Problems." Master's thesis, METU, 2004. http://etd.lib.metu.edu.tr/upload/12605244/index.pdf.
Full textAbstract:
In this thesis, single undesirable and semi-desirable facility location problems are analyzed in a continuous planar region considering the interaction between the facility and the existing demand points. In both problems, the distance between the facility and the demand points is measured with the rectilinear metric. The aim in the first part where the location of a pure undesirable facility is considered, is to maximize the distance of the facility from the closest demand point. In the second part, where the location of a semi-desirable facility is considered, a conflicting objective measuring the service cost of the facility is added to the problem of the first part. For the solution of the first problem, a mixed integer programming model is used. In order to increase the solution efficiency of the model, new branch and bound strategies and bounding schemes are suggested. In addition, a geometrical method is presented which is based on upper and lower bounds. For the biobjective problem, a three-phase interactive geometrical branch and bound algorithm is suggested to find the most preferred efficient solution.
22
Sugihara, Kenya. "Studies on maximum-cover source location problems." 京都大学 (Kyoto University), 2008. http://hdl.handle.net/2433/136023.
Full text
23
Haimovich, Mordecai, and Thomas L. Magnanti. "Location Games and Bounds for Median Problems." Massachusetts Institute of Technology, Operations Research Center, 1985. http://hdl.handle.net/1721.1/5368.
Full textAbstract:
We consider a two-person zero-sum game in which the maximizer selects a point in a given bounded planar region, the minimizer selects K points in that region,.and the payoff is the distance from the maximizer's location to the minimizer's location closest to it. In a variant of this game, the maximizer has the privilege of restricting the game to any subset of the given region. We evaluate/approximate the values (and the saddle point strategies) of these games for K = 1 as well as for K + , thus obtaining tight upper bounds (and worst possible demand distributions) for K-median problems.
24
Zhang, Jingru. "Geometric Facility Location Problems on Uncertain Data." DigitalCommons@USU, 2017. https://digitalcommons.usu.edu/etd/6337.
Full textAbstract:
Facility location, as an important topic in computer science and operations research, is concerned with placing facilities for "serving" demand points (each representing a customer) to minimize the (service) cost. In the real world, data is often associated with uncertainty because of measurement inaccuracy, sampling discrepancy, outdated data sources, resource limitation, etc. Hence, problems on uncertain data have attracted much attention.
In this dissertation, we mainly study a classical facility location problem: the k- center problem and several of its variations, on uncertain points each of which has multiple locations that follow a probability density function (pdf). We develop efficient algorithms for solving these problems. Since these problems more or less have certain geometric flavor, computational geometry techniques are utilized to help develop the algorithms. In particular, we first study the k-center problem on uncertain points on a line, which is aimed to find k centers on the line to minimize the maximum expected distance from all uncertain points to their expected closest centers. We develop efficient algorithms for both the continuous case where the location of every uncertain point follows a continuous piecewise-uniform pdf and the discrete case where each uncertain point has multiple discrete locations each associated with a probability. The time complexities of our algorithms are nearly linear and match those for the same problem on deterministic points. Then, we consider the one-center problem (i.e., k= 1) on a tree, where each uncertain point has multiple locations in the tree and we want to compute a center in the tree to minimize the maximum expected distance from it to all uncertain points. We solve the problem in linear time by proposing a new algorithmic scheme, called the refined prune-and-search. Next, we consider the one-dimensional one-center problem of uncertain points with continuous pdfs, and the one-center problem in the plane under the rectilinear metric for uncertain points with discrete locations. We solve both problems in linear time, again by using the refined prune-and-search technique. In addition, we study the k-center problem on uncertain points in a tree. We present an efficient algorithm for the problem by proposing a new tree decomposition and developing several data structures. The tree decomposition and these data structures may be interesting in their own right. Finally, we consider the line-constrained k-center problem on deterministic points in the plane where the centers are required to be located on a given line. Several distance metrics including L1, L2, and L1 are considered. We also study the line-constrained k-median and k-means problems in the plane. These problems have been studied before. Based on geometric observations, we design new algorithms that improve the previous work. The algorithms and techniques we developed in this dissertation may and other applications as well, in particular, on solving other related problems on uncertain data.
25
Tresoldi, E. "LOCATION AND ROUTING PROBLEMS: A UNIFIED APPROACH." Doctoral thesis, Università degli Studi di Milano, 2012. http://hdl.handle.net/2434/172439.
Full textAbstract:
This thesis is about location and routing problems. We propose a unified algorithmic
approach, based on the branch-and-cut-and-price paradigm, for the exact solution of general
location and routing problems involving both costs and profits. In particular three different
types of N P -hard problems are taken into account: the first is an extension, arising in the
context of waste collection management, of the well studied Vehicle Routing Problem. The
second is based on the Multi-Depot Vehicle Routing Problem with profits and has applications in the exploration of planetary surfaces. The last problem is about the distribution of
drugs in emergency situations. For every problem a detailed description and a mathematical
formulation are given.
The largest part of the thesis is dedicated to the careful explanation of how our method
can be efficiently implemented in every of the problems taken into account. In particular we
propose new algorithmic ideas and several modifications and extensions to many procedures
already presented in the literature. However, all components of our algorithms are fully
presented and analyzed pointing out every methodological and practical issue.
Extensive computational experiments and comparisons are carried out to evaluate the
performance of our approach and the tractability of the problems addressed.
26
Das, Pali. "Solutions of some single facility location problems." Thesis, University of North Bengal, 1997. http://hdl.handle.net/123456789/600.
Full text
27
Poetranto, Groß Dwi Retnani. "Network flow and location (FlowLoc) : the source location problem /." München : Verl. Dr. Hut, 2009. http://bvbr.bib-bvb.de:8991/F?func=service&doc_library=BVB01&doc_number=017179775&line_number=0001&func_code=DB_RECORDS&service_type=MEDIA.
Full text
28
Poetranto, Gross Dwi Retnani. "Network flow and location (FlowLoc) the source location problem." München Verl. Dr. Hut, 2008. http://d-nb.info/992662664/04.
Full text
29
Sun, Shu-ho. "A two-dimensional continuum approach to facility location problems /." Hong Kong : University of Hong Kong, 1999. http://sunzi.lib.hku.hk/hkuto/record.jsp?B21795381.
Full text
30
Ji, Yiming Biaz Saad. "Location estimation in wireless networks." Auburn, Ala., 2006. http://repo.lib.auburn.edu/2006%20Spring/doctoral/JI_YIMING_28.pdf.
Full text
31
Al-Loughani, Intesar Mansour. "Algorithmic Approaches for Solving the Euclidean Distance Location and Location-Allocation Problems." Diss., Virginia Tech, 1997. http://hdl.handle.net/10919/30694.
Full textAbstract:
This dissertation is concerned with the development of algorithmic approaches for solving
the minisum location and location-allocation problems in which the Euclidean metric is
used to measure distances. To overcome the nondifferentiability difficulty associated with
the Euclidean norm function, specialized solution procedures are developed for both the
location and the location-allocation problems. For the multifacility location problem
(EMFLP), two equivalent convex differentiable reformulations are proposed. The first of
these is formulated directly in the primal space, and relationships between its Karush-Kuhn-
Tucker (KKT) conditions and the necessary and sufficient optimality conditions for
EMFLP are established in order to explore the use of standard convex differentiable
nonlinear programming algorithms that are guaranteed to converge to KKT solutions. The
second equivalent differentiable formulation is derived via a Lagrangian dual approach
based on the optimum of a linear function over a unit ball (circle). For this dual approach,
which recovers Francis and Cabot's (1972) dual problem, we also characterize the
recovery of primal location decisions, hence settling an issue that has remained open since
1972. In another approach for solving EMFLP, conjugate or deflected subgradient based
algorithms along with suitable line-search strategies are proposed. The subgradient
deflection method considered is the Average Direction Strategy (ADS) imbedded within
the Variable Target Value Method (VTVM). The generation of two types of subgradients
that are employed in conjunction with ADS are investigated. The first type is a simple
valid subgradient that assigns zero components corresponding to the nondifferentiable
terms in the objective function. The second type expends more effort to derive a low-norm
member of the subdifferential in order to enhance the prospect of obtaining a descent
direction. Furthermore, a Newton-based line-search is also designed and implemented in
order to enhance the convergence behavior of the developed algorithm. Various
combinations of the above strategies are composed and evaluated on a set of test
problems. Computational results for all the proposed algorithmic approaches are
presented, using a set of test problems that include some standard problems from the
literature. These results exhibit the relative advantages of employing the new proposed
procedures.
Finally, we study the capacitated Euclidean distance location-allocation problem. There
exists no global optimization algorithm that has been developed and tested for this class of
problems, aside from a total enumeration approach. We develop a branch-and-bound
algorithm that implicitly/partially enumerates the vertices of the feasible region of the
transportation constraints in order to determine a global optimum for this nonconvex
problem. For deriving lower bounds on node subproblems, a specialized variant of the
Reformulation-Linearization Technique (RLT) is suitably designed which transforms the
representation of this nonconvex problem from the original defining space into a higher
dimensional space associated with a lower bounding (largely linear) convex program. The
maximum of the RLT relaxation based lower bound that is obtained via a deflected
subgradient strategy applied to a Lagrangian dual formulation of this problem, and another
readily computed lower bound in the projected location space is considered at each node
of the branch-and-bound tree for fathoming purposes. In addition, certain cut-set
inequalities in the allocation space, and objective function based cuts in the location space
are generated to further tighten the lower bounding relaxation. Computational experience
is provided on a set of randomly generated test problems to investigate both the RLT-based
and the projected location- space lower bounding schemes. The results indicate that
the proposed global optimization approach for this class of problem offers a promising
viable solution procedure. In fact, for two instances available available in the in the
literature, we report significantly improved solutions. The dissertation concludes with
recommendations for further research for this challenging class of problems. Data for the
collection of test problems is provided in the Appendix to facilitate further testing in this
area.Ph. D.
32
Shareef, Ali. "Localization and Energy Modeling in Wireless Sensor Networks." Fogler Library, University of Maine, 2008. http://www.library.umaine.edu/theses/pdf/ShareefA2008.pdf.
Full text
33
Quintero, Araújo Carlos Leonardo. "Applications of simheuristics and horizontal cooperation concepts in rich vehicle routing problems." Doctoral thesis, Universitat Oberta de Catalunya, 2017. http://hdl.handle.net/10803/460831.
Full textAbstract:
En una economia globalitzada, les companyies s’enfronten a nombrosos reptes associats a les complexes tasques de logística i distribució. Gràcies al desenvolupament de les tecnologies de la informació i la comunicació, els clients es troben en qualsevol part del món, però també els competidors. Per tant, les companyies necessiten ser més competitives, cosa que implica eficiència econòmica i sostenibilitat. Una estratègia que les firmes poden seguir per a ser més competitives és la cooperació horitzontal, que genera economies d’escala, increment en la utilització de recursos i reducció de costos. Molts d’aquests reptes en logística i transport, així com algunes estratègies de cooperació horitzontal, es poden abordar mitjançant diferents variants del conegut problema d’encaminament de vehicles (VRP). Malgrat que el VRP ha estat àmpliament estudiat, la majoria dels treballs publicats corresponen a versions massa simplificades de la realitat. Per a omplir aquest buit entre la teoria i les aplicacions de la vida real, fa poc que ha sorgit el concepte de problemes «enriquits» d’encaminament de vehicles (RVRP). Per tant, es necessiten nous mètodes de solució per a resoldre eficientment nous RVRP, així com per a quantificar els beneficis generats per la implementació d’estratègies de cooperació horitzontal en aplicacions reals, de manera que es puguin fer servir com a suport per a la presa de decisions. Per a abordar aquesta varietat de problemes es proposen diferents metaheurístiques basades en aleatorització esbiaixada. Aquests mètodes es combinen amb simulació (fet que es coneix com simheurístiques) per a resoldre situacions en les quals apareix la incertesa. Els mètodes proposats han estat avaluats utilitzant instàncies de prova tant teòriques com de la vida real.En una economía globalizada, las compañías se enfrentan a numerosos retos asociados a las complejas tareas de logística y distribución. Gracias al desarrollo de las tecnologías de la información y la comunicación, los clientes se encuentran en cualquier lugar del mundo, pero también los competidores. Por lo tanto, las compañías necesitan ser más competitivas, lo que implica eficiencia económica y sostenibilidad. Una estrategia que las firmas pueden seguir para ser más competitivas es la cooperación horizontal, generando así economías de escala, incremento en la utilización de recursos y reducción de costes. Muchos de estos retos en logística y transporte, así como algunas estrategias de cooperación horizontal, pueden abordarse mediante diferentes variantes del conocido problema de enrutamiento de vehículos (VRP). Pese a que el VRP ha sido ampliamente estudiado, la mayoría de los trabajos publicados corresponden a versiones simplificadas de la realidad. Para llenar este vacío entre la teoría y las aplicaciones de la vida real, recientemente ha surgido el concepto de problemas «enriquecidos» de enrutamiento de vehículos (RVRP). Por lo tanto, se necesitan nuevos métodos de solución para resolver de forma eficiente nuevos RVRP, así como para cuantificar los beneficios generados por la implementación de estrategias de cooperación horizontal en aplicaciones reales, de modo que puedan usarse como apoyo para la toma de decisiones. Para abordar tal variedad de problemas se proponen diferentes metaheurísticas basadas en aleatorización sesgada. Estos métodos se combinan con simulación (lo que se conoce como simheurísticas) para resolver situaciones en las que aparece la incertidumbre. Los métodos propuestos han sido evaluados utilizando instancias de prueba tanto teóricas como de la vida real.
In a globalized economy, companies have to face different challenges related to the complexity of logistics and distribution strategies. Due to the development of information and communication technologies (ICT), customers and competitors may be located anywhere in the world. Thus, companies need to be more competitive, which entails efficiency from both an economic and a sustainability point of view. One strategy that companies can follow to become more competitive is to cooperate with other firms, a strategy known as horizontal cooperation (HC), allowing the use of economies of scale, increased resource utilization levels, and reduced costs. Many of these logistics and transport challenges, as well as certain HC strategies, may be addressed using variants of the vehicle routing problem (VRP). Even though VRP has been widely studied, the majority of research published corresponds to oversimplified versions of the reality. To fill the existing gap between the academic literature and real-life applications, the concept of rich VRPs (RVRPs) has emerged in the past few years in order to provide a closer representation of real-life situations. Accordingly, new approaches are required to solve new RVRPs efficiently and to quantify the benefits generated through the use of HC strategies in real applications. Thus, they can be used to support decision-making processes regarding different degrees of implementation of HC. Several metaheuristic methods based on biased randomization techniques are proposed. Additionally, these methods are hybridized with simulation (ie simheuristics) to tackle the presence of uncertainty. The proposed approaches are tested using a large set of theoretical and real-life benchmarks.
34
Kaiser, Markus [Verfasser]. "Spatial Uncertainties in Continuous Location Problems / Markus Kaiser." Aachen : Shaker, 2016. http://d-nb.info/1084536854/34.
Full text
35
Yonezawa, Kouki. "Studies on online financial and server-location problems." 京都大学 (Kyoto University), 2004. http://hdl.handle.net/2433/145308.
Full textAbstract:
Kyoto University (京都大学)0048
新制・課程博士
博士(情報学)
甲第11080号
情博第125号
新制||情||29(附属図書館)
22612
UT51-2004-J752
京都大学大学院情報学研究科通信情報システム専攻
(主査)教授 岩間 一雄, 教授 富田 眞治, 教授 湯淺 太一
学位規則第4条第1項該当
36
Heller, Stephanie [Verfasser]. "Matroid Flows: Interdiction and Location Problems / Stephanie Heller." München : Verlag Dr. Hut, 2013. http://d-nb.info/1031844724/34.
Full text
37
Gwalani, Harsha. "Spatial Partitioning Algorithms for Solving Location-Allocation Problems." Thesis, University of North Texas, 2019. https://digital.library.unt.edu/ark:/67531/metadc1609062/.
Full textAbstract:
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.
38
Bafna, Nitin Nemichand. "LABELING SCHEMES FOR SOME LOCATION PROBLEMS ON TREES." Kent State University / OhioLINK, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=kent1178309019.
Full text
39
Balcik, Burcu. "Multi Item Integrated Location/inventory Problem." Master's thesis, METU, 2003. http://etd.lib.metu.edu.tr/upload/4/1093640/index.pdf.
Full textAbstract:
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.
40
鄭國榮 and Kwok-wing Philip Cheng. "Some results on the location problem." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1998. http://hub.hku.hk/bib/B31215051.
Full text
41
Cheng, Kwok-wing Philip. "Some results on the location problem /." Hong Kong : University of Hong Kong, 1998. http://sunzi.lib.hku.hk/hkuto/record.jsp?B19589074.
Full text
42
Wang, Yu Carleton University Dissertation Mathematics and Statistics. "The P-median problem and the uncapacitated facility location problem." Ottawa, 1996.
Find full text
43
Gianessi, Paolo. "Optimisation Stratégique et tactique en logistique urbaine." Thesis, Paris 13, 2014. http://www.theses.fr/2014PA132036/document.
Full textAbstract:
L'efficacité du transport des marchandises en ville est un sujet complexe préoccupant les autorités locales depuis de nombreuses années. Les enjeux sont immenses, une meilleure organisation du trafic devant permettre d'augmenter la sécurité, réduire les nuisances, minimiser les coûts. La Logistique Urbaine vise à concevoir des systèmes de distribution des marchandises en ville permettant d'acheminer les flux dans les meilleures conditions à la fois pour la communauté et les transporteurs. Cette thèse se deroule dans le cadre du projet ANR MODUM qui propose un système basé sur un anneau de Centres de Distribution Urbains (CDU) situés autour d'une ville. La première partie étudie ce système d'un point de vue stratégique et tactique. Le Multicommodity-Ring Location Routing Problem aborde les décisions concernants l'installation et la connexion en anneau des CDU en simplifiant les détails plus tactiques. Trois méthodes ont été developpées et testées sur un jeu d'instances exhaustif se révélant très efficaces. The Multicommodity-Ring Vehicle Routing Problem est le problème dérivé que l'on obtient quand l'anneau est fixé. Une approche de type Branch&Price est proposée pour ce problème. La deuxième partie porte sur le Vehicle Routing Problem with Intermediate Replenishment Facilities, un problème plus tactique qui se produit dans un système logistique lorsque les véhicules peuvent se recharger auprès des points de remplissage et effectuer plusieurs tournées lors d'une même journée. Plusieurs algorithmes exacts ont été developpés et testés. Les résultats obtenus sur des jeux d'instances tirés de la littérature sont prometteursUrban freight transport is a matter of increasing concern in the economic, commercial, social and environmental operations of our cities, due to the constantly increasing growth and urbanization of the civilization. An improved managem ent of the traffic related to the freight transport can have a positive impact in many respects : security, congestion of the road network, noise and air pollution, costs. City Logistics studies the dynamic management of urban freight transport in order to deliver distribution systems solutions that may be suitable for both the community and freight carriers. This thesis originates from the ANR Project MODUM, which proposes a freight distribution system based on a ring of Urban Distribution Centers (UDCs) located in the outskirts of a city. In the first part, this system is studied from both a strategic and a tactical point of view. The Multicommodity-Ring Location Routing Problem (MRLRP) considers long-term decisions, i.e. the installation of the UDCs and the ring connection, without disregarding more tactical aspects. The MRLRP has been tackled by three solution methods, which proved effective on a large set of test instances. In the second part of the thesis, the Vehicle Routing Problem with Intermediate Replenishment Facilities (VRPIRF) is studied. The VRPIRF is a more tactical problem that arises in City Logistics each time both the multi-trip and the multi-depot features, i.e. the possibility for a vehicle to be reloaded at one of a set of facilities, are present. Several exact algorithms, namely two of type Branch&Cut and two of type Branch& Price, have been developed for this problem. computational experiments on benchmark instances taken from the literature have been conducted to assess their performance, leading to very promising results
44
辛樹豪 and Shu-ho Sun. "A two-dimensional continuum approach to facility location problems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1999. http://hub.hku.hk/bib/B31223394.
Full text
45
Naidoo, Krishantha. "A study into Healthcare Service Location Problems, Location and Allocation in the Inanda area." Master's thesis, Faculty of Engineering and the Built Environment, 2021. http://hdl.handle.net/11427/32922.
Full textAbstract:
Inanda is a predominantly rural area located on the northern coast of the province of KwaZulu Natal, South Africa. It is bordered by the areas of Phoenix, Verulam and Tongaat. In the context of healthcare accessibility in the Inanda area, the research aimed at investigating the problem in service location planning. This was done by investigating level of accessibility to existing healthcare facilities available to the residents of Inanda. Following the classification of accessibility problems, recommendations were made on where the facility locations can be improved or expanded to provide better accessibility in terms of location-allocation. Literature that has been reviewed focused on geographic location, GIS and accessibility measures, spatial accessibility, models used to test accessibility, service location planning and accessibility measures and metrics so as to provide a background and precedent for the service location planning carried out in the research. The research aimed to confirm that accessibility to the healthcare facilities is indeed a problem and to propose alternative strategies to overcome the accessibility problems identified. The access to healthcare service locations is dependent on a number of factors. Some of these factors include travel time and distance, available capacity at facilities, existing road network, and provision or lack thereof of an efficient public transport system. This accessibility to the health service locations was assessed by using available GIS information on healthcare facilities and using accessibility analysis to identify problems in terms of the services location as well as additional location-allocation of current and additional facilities. The analysis was based on the assumption that all service locations have unlimited capacity. Flowmap was used as the tool to analyse the GIS data and conduct various accessibility models. The different models were Expansion Model Analysis, Relocation Model Analysis, Catchment Area and Clinic Allocation Analysis, Catchment Profile, Market share of Supply Locations, Regular Proximity Count, Average Distance in Competition, Proximity Count in Competition, Lowest Mean Trip Cost Alternate, Second Best Catchment Distance and Pareto Cover Set. The results of the research showed that while the locations of the existing healthcare facilities are not ideal, most are accessible to the majority of the Inanda residents. The information on actual capacity available at each of the locations was not available at the time of the research being carried out and would be worthwhile to research in the future.
46
Albareda, Sambola Maria. "Models and Algorithms for Location-Routing and Related Problems." Doctoral thesis, Universitat Politècnica de Catalunya, 2003. http://hdl.handle.net/10803/6510.
Full textAbstract:
The most common decisions to be taken in the design of logistic systems are related to the location of facilities and the management of vehicle fleets.In this thesis, we study three of the optimization problems arising around this kind of decisions; namely the LRP, the SGAP and the SLRP. The first problem analyzed in this work is a capacitated LRP with one single uncapacitated vehicle at each open plant. To model this problem we resort to an auxiliary network that allows us to represent feasible solutions as families of paths satisfying a series of side constraints.
The solutions of a reinforced LP relaxation of this model are used as the basis of a rounding heuristic designed to build feasible solutions of the problem. Those solutions are then improved with a TS heuristic.
Two lower bounds, distinct from that obtained with the LP relaxation of the model, are proposed for this problem. The first one is obtained by bound ing separately the two different parts of the cost of any feasible solution, namely the fixed costs for opening plants and the route costs. The second lower bound is the result of applying CG to the Lagrangian dual obtained by dualizing the assignment constraints. The pricing problem obtained from our formulation is an ESPPRC. The complexity of this problem, and the fact that optimality of the obtained solutions is not always necessary, have motivated us to develope a simple heuristic for it.
The computational experiences show a very good behavior of the TS procedure both, for the computational effort required and the quality of the solutions. The first lower bound proposed gives satisfactory results in reasonable amounts of time. In the case of the CG approach, results are very encouraging. In some of the tested instances the program terminated because of the CPU time limit specification, before succeeding to find a valid lower bound.
In those instances, the algorithm was always stalled in the exact resolution of an ESPPRC. The difficulties encountered to solve this problem represent a limitation of this approach and suggest the future study of alternative solution methods. In spite of this limitation, in a high proportion of the instances the algorithm succeeded, and the final gap between the upper and the lower bound was always 0. The success in these instances is partially due to the use of our heuristic to generate new columns whenever this is possible.
The second problem studied in this thesis is a SGAP. In this assignment problem the jobs are interpreted as customers that can request a service with a given probability, and each agent can serve a limited number of customers. This uncertainty about the presence of each customer is represented by modelling the demands of the customers as Bernoulli distributed independent random variables. The problem consists of finding an a priori assignment of customers to agents. Once the actual requests for service are known, an adaptive action is taken to tackle violations of the capacity constraints. On the one hand, part of the customers assigned to overloaded agents can be reassigned. On the other hand, some of the service requests can be disregarded. Different penalties for reassignment and for unattended service requests are pre-specified. The problem is formulated as a recourse model, where the recourse function gives the expected penalties for reassignments and unattended service requests.
Since this recourse function is defined as the expected value of an integer programming recourse model, it does not have the regularity properties characteristic of those defined by linear recourse models. To overcome the difficulties caused by this, we construct a convex approximation of the recourse function that is tight in all feasible points. Moreover, as illustrated in the computational experiences, the use of this approximation reduces the computational effort required to evaluate the recourse function is some orders of magnitude. The convex approximation of the recourse function allows us to adapt the well-known L-shaped method to our problem. Integrality of the first stage variables is tackled in three different ways, giving raise to three versions of the algorithm. The difference among them resides in the hierarchy between the branching and the addition of violated cuts. On the one hand, we present a version where cuts are only added when integer solutions are found. On the other hand, a version is proposed where branching is only performed when no more violated cuts can be identified. The remaining version is designed as a tradeoff of these two; at each node of the search tree, new optimality cuts are added, if needed, and branching is performed if the solution at hand is fractional. Computational experiences point out this last version as the best of the three, since the efforts devoted to obtain a rich approximation of the recourse function and to achieve integrality are more balanced.
We have also derived both, lower and upper bounds for this specific SGAP. Upper bounds are obtained from three simple heuristics. All them are based on solving deterministic approximations of the SGAP and provide good quality solutions in small amounts of CPU time. A lower bound is derived from a family of linear stochastic subproblems. Althoug in some of the tested instances the gap between the bounds exceeded the 30%, in the general case we obtained small gaps.
One of the heuristics was used in the exact algorithm to provide it with a good upper bound. The lower bound is also used in the three versions of the algorithm, as the basis of some of the optimality cuts and also to identify optimal solutions. The quality of these bounds is one of the factors that explain the success of the exact algorithm.
The last problem studied in this thesis is a SLRP. The stochasticity considered here is of the same type as that considered for the SGAP. Again, customers may request a service with a given probability and this is modeled by introducing Bernoulli random variables to represent the demands. A two stage model is proposed for this problem. In a first stage, a set of plants to open has to be chosen together with a family of disjoint routes (one rooted at each open plant) that visit all the customers. In the second stage, once all the demands become available, the actual routes have to be designed. For plants whose number of service requests does not exceed the capacity, the actual route is derived from that designed a priori by skipping customers with no demand. When the requests for service allocated to a plant exceed its capacity, a subset of them is randomly chosen to be served, and they are visited in the order defined by the a priori route.
Penalties are paid for the unattended service requests. The expected total cost of the actual routes and the expected penalties for unserviced customers are contained in the recourse function.
We present a two phase heuristic to solve this problem. In the first phase, a series of subproblems are sequentially solved to build an initial solution. In the second phase, this solution is successively improved using LS. This improving phase requires a high number of evaluations of the recourse function. Although we have developed an analytical expression for this recourse function, the computational effort required for its evaluation is considerable due to its combinatorial nature. For this reason, we approximate it with a simpler auxiliary function that has allowed us to obtain solutions in small computational times.
We also propose a lower bound obtained from bounding different parts of the objective function independently. Unfortunately, we only could find reasonable bounds for the sum of fixed costs for opening the plants plus the expected penalty paid for unserviced customers. Further research is intended to improve the bounding of the expected total cost of the routes.
The evaluation of the quality of the solutions obtained with our heuristic is not easy due to the lack of a tight global lower bound. However, the partial bound on the costs relative to the plants allows to conclude that the heuristic makes in general a good choice of the set of plants. As for the allocation of customers to plants and the design of the routes we can only evaluate the evolution along the search. In the computational experiences reported it can be seen that this evolution is satisfactory.
47
Baldacci, Roberto. "Algorithms for location and routing problems in distribution systems." Thesis, Imperial College London, 1999. http://hdl.handle.net/10044/1/11811.
Full text
48
Brauer, Sascha [Verfasser]. "Classification and approximation of geometric location problems / Sascha Brauer." Paderborn : Universitätsbibliothek, 2019. http://d-nb.info/1196688095/34.
Full text
49
Ballesteros, Jaime. "Mixed Spatial and Nonspatial Problems in Location Based Services." FIU Digital Commons, 2013. http://digitalcommons.fiu.edu/etd/930.
Full textAbstract:
With hundreds of millions of users reporting locations and embracing mobile technologies, Location Based Services (LBSs) are raising new challenges. In this dissertation, we address three emerging problems in location services, where geolocation data plays a central role. First, to handle the unprecedented growth of generated geolocation data, existing location services rely on geospatial database systems. However, their inability to leverage combined geographical and textual information in analytical queries (e.g. spatial similarity joins) remains an open problem. To address this, we introduce SpsJoin, a framework for computing spatial set-similarity joins. SpsJoin handles combined similarity queries that involve textual and spatial constraints simultaneously. LBSs use this system to tackle different types of problems, such as deduplication, geolocation enhancement and record linkage. We define the spatial set-similarity join problem in a general case and propose an algorithm for its efficient computation. Our solution utilizes parallel computing with MapReduce to handle scalability issues in large geospatial databases.
Second, applications that use geolocation data are seldom concerned with ensuring the privacy of participating users. To motivate participation and address privacy concerns, we propose iSafe, a privacy preserving algorithm for computing safety snapshots of co-located mobile devices as well as geosocial network users. iSafe combines geolocation data extracted from crime datasets and geosocial networks such as Yelp. In order to enhance iSafe's ability to compute safety recommendations, even when crime information is incomplete or sparse, we need to identify relationships between Yelp venues and crime indices at their locations. To achieve this, we use SpsJoin on two datasets (Yelp venues and geolocated businesses) to find venues that have not been reviewed and to further compute the crime indices of their locations. Our results show a statistically significant dependence between location crime indices and Yelp features.
Third, review centered LBSs (e.g., Yelp) are increasingly becoming targets of malicious campaigns that aim to bias the public image of represented businesses. Although Yelp actively attempts to detect and filter fraudulent reviews, our experiments showed that Yelp is still vulnerable. Fraudulent LBS information also impacts the ability of iSafe to provide correct safety values. We take steps toward addressing this problem by proposing SpiDeR, an algorithm that takes advantage of the richness of information available in Yelp to detect abnormal review patterns. We propose a fake venue detection solution that applies SpsJoin on Yelp and U.S. housing datasets. We validate the proposed solutions using ground truth data extracted by our experiments and reviews filtered by Yelp.
50
Lê, Huy Minh [Verfasser]. "Robust Single Machine Scheduling-Location Problems / Huy Minh Lê." München : Verlag Dr. Hut, 2021. http://d-nb.info/1238423116/34.
Full text