On April 27, 1802, I gave a shout of joy ... It was seven years ago I proposed to myself a problem which I have not been able to solve directly, but for which I had found by chance a solution, and I knew that it was correct, without being able to prove it. The matter often returned to my mind and I had sought twenty times unsuccessfully for this solution. For some days I had carried the idea about with me continually. At last, I do not know how, I found it, together with a large number of curious and new considerations concerning the theory of probability. Andre Marie Ampere. Facility location problems (or plant location problems) are general models that can be used when a set of clients has to be served by facilities. More precisely, we are given a set of potential facility locations and a set of clients. The optimization problem is to select a subset of the locations at which to place facilities and then to assign clients to theses facilities so as to minimize total cost. Most formulations considered in this thesis can be viewed as general models that can be applied to a wide range of context and practical situations. However, as this research has been partly initiated by the interest of the author in telecommunication network design we will introduce these models by considering problems in this particular area. In the context of telecommunication network design an application of discrete location theory is the optimization of access networks with concentrators. Typically, we have a number of terminal points that must be connected to a service point. An obvious solution is to use a dedicated link for each terminal (star network). However, it is clear that this solution can be very expensive when the number of terminals is large and when they are far from the service point. Access networks are often constructed by inserting concentrators between the terminals and the service point. Many terminals are connected to a facility which in turn is connected by a single link to the service point. The objective is to build a network that will provide the service at minimum cost. If no extra constraints are involved the mmimum cost network problem can be expressed as an uncapacitated facility location problem (UFL). If the number of terminals that can be connected to a concentrator is limited we obtain a so-called capacitated facility location problem (CFL). CFL can be extended to consider various types of concentrators with various capacities. This problem is the multi-capacitated facility location problem (MCFL). MCFL is a straightforward model for low speed packet switched data networks typical among which are networks connecting sellingpoint terminals to a database. For other networks, the problem may involve various traffic constraints. In chapter 1 we present those problems and compare solutions obtained by Lagrangian relaxation and simulated annealing algorithms. The architecture mentioned above can be extended with more than one hierarchical level of concentrator. Unfortunately, we pay for this cost saving through a decrease of reliability. Therefore, the number of levels is often limited to one or two. In chapter 2 we study an extension of UFL and CFL to two levels of concentrators. Obviously, the structure of a network changes according to the way requirements vary with time. In order to plan investments and to develop strategies, the evolution of a network has to be determined for several years ahead (typically four or five years). In this case the main questions to answer are: Where and when to establish concentrators and of what size? In chapter 3 we study this problem for the dynamic version of UFL. Now, with the network optimization problem, there naturally arises the problem of allocating the total minimum cost among customers fairly. Namely, we would like to allocate the cost in such a way that no subgroup of users would have incentive to withdraw and build their own network. The standard way to approach such a problem is by the means of cooperative game theory. In chapter 4 we study the core of location games derived from UFL and CFL, and in chapter 5 we propose methods to compute the nucleolus of these games.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:267523 |
| Date | January 1998 |
| Creators | Chardaire, P. |
| Publisher | University of East Anglia |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.0135 seconds