Facility Location Problems with Continuous Demand

点击翻译按钮获取中文摘要

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).