Facility Location Problems with Continuous Demand
Lead Research Organisation:
University of Edinburgh
Department Name: Sch of Mathematics
Abstract
Modern location theory started in 1909 with Alfred Weber's seminal work Über den Standort der Industrien. Since then, an ever increasing number of models and algorithms has appeared in the literature. A crucial, but often neglected aspect of these models is an adequate representation of demand. The vast majority of the literature is motivated by problems in logistics and focusses on applications where customer demand is assumed to be discrete and aggregated to a relatively small number of points. However, in many urban applications the number of potential customers can be in the millions and representing every customer residence as a separate demand point is usually infeasible. Moreover, demand is often uncertain and may occur very sporadically. Thus, it might be much more accurate to represent demand instead as continuously distributed, either across a region or along the streets of a city; especially in urban environments.
The goal of this project is to develop models and efficient algorithms for a wide range of facility location problems with continuous demand. For example problems that deal with different types of solutions spaces (planar or network), norms (geodesic norms, weighted or multiplicative norms), demand representations (continuous, piecewise linear, step functions), objective functions (median, center, covering, equity, multi-criteria) as well as problems with stochastic demands or time dynamic problems. Having to cope with continuous demand adds an analytic and often non-linear component to an already very challenging combinatorial optimization problem. Developing efficient algorithms for such problems, whether they are exact or heuristics, requires a combination of tools from mathematics (e.g., calculus, combinatorial and non-linear optimization, graph theory) with tools from theoretical computer science (e.g., computational geometry, complexity theory, design and analysis of algorithms).
The goal of this project is to develop models and efficient algorithms for a wide range of facility location problems with continuous demand. For example problems that deal with different types of solutions spaces (planar or network), norms (geodesic norms, weighted or multiplicative norms), demand representations (continuous, piecewise linear, step functions), objective functions (median, center, covering, equity, multi-criteria) as well as problems with stochastic demands or time dynamic problems. Having to cope with continuous demand adds an analytic and often non-linear component to an already very challenging combinatorial optimization problem. Developing efficient algorithms for such problems, whether they are exact or heuristics, requires a combination of tools from mathematics (e.g., calculus, combinatorial and non-linear optimization, graph theory) with tools from theoretical computer science (e.g., computational geometry, complexity theory, design and analysis of algorithms).
Organisations
People |
ORCID iD |
| Joerg Kalcsics (Primary Supervisor) | |
| Thomas Byrne (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509644/1 | 01/10/2016 | 30/09/2021 | |||
| 1783553 | Studentship | EP/N509644/1 | 01/09/2016 | 31/03/2020 | Thomas Byrne |
| Description | I have been looking at facility location problems. These are generally problems deciding on the optimal placement of a facility to which customers travel in order to obtain a service (such as a hospital, school, shop, etc.) within an area in which we know the customer demand and the locations of existing facilities (be those facilities of ours and competitors) in order to satisfy some objective (such as find the placement of an additional facility which: minimises the average distance travelled to one of your facilities by a customer; or maximises the total number of customers your facilities capture). We assume that customers travel to their nearest facility (where we use their 'Manhattan distance' (sides of a block) rather than 'Euclidean distance' (straight line) which is more suited for urban scenarios) and have customer density rather than discrete points of demand (more sensible for large applications). Within my PhD I have found created or adapted existing algorithms to solve problems of this type exactly under different conditions. The first algorithm solved such problems relaxing the constraint that customer density had to be uniform (i.e. the same demand everywhere). Afterwards I explored the much larger problem of introducing a barrier within which there is no demand and customers cannot pass through it. I created a rather complex and exhausting algorithm to solve this problem for barriers with certain (sensible) properties and am now in the middle of creating a neater and more general algorithm to do the same. In a collaboration with an academic at the Braunschweig University of Technology, I also investigated the game theory version of facility location, whereby two players take turns to place points on a rectangular board and at the end of the game the board is split up into the areas to which a point of a certain player is the closest and the player with the largest area wins. I found conditions on the board which determines whether the player who goes first wins or loses and detailed the optimal strategies for both players. |
| Exploitation Route | This is a very exciting area of research that has only recently begun to be explored despite having such a clear impact. Problems of this type in this setting are known to be challenging and very demanding which makes them perfect for some of the great minds in operational research to come together to try to solve which rewarding outcomes I am sure. While my work is purely theoretical, it has such obvious real world applications. The problem of finding the perfect location for a facility (which can be anything from a shop to an air-drop, a WiFi router to a component on a circuit board) is one which many people and enterprises face and the fact that my algorithms find the best location for any sort of facility in a variety of environments causes it to naturally be of value. Once the work is complete somebody may do well to implement these algorithms into a program to provide these industries with the answers to their questions. |
| Sectors | Aerospace, Defence and Marine,Agriculture, Food and Drink,Construction,Digital/Communication/Information Technologies (including Software),Education,Electronics,Energy,Environment,Healthcare,Leisure Activities, including Sports, Recreation and Tourism,Government, Democracy and Justice,Manufacturing, including Industrial Biotechology,Culture, Heritage, Museums and Collections,Retail,Security and Diplomacy,Transport,Other |