Facility Location Problems with Continuous Demand

现代区位理论始于1909年阿尔弗雷德·韦伯的开创性著作《工业标准》。从那时起，越来越多的模型和算法出现在文献中。这些模型的一个关键但往往被忽视的方面是对需求的充分表示。绝大多数文献的动机是物流问题，并集中在应用程序中，客户的需求被假定为离散和聚合到一个相对较少的点。然而，在许多城市应用中，潜在客户的数量可能以百万计，并且将每个客户住宅表示为单独的需求点通常是不可行的。此外，需求往往是不确定的，而且可能非常零星地出现。因此，它可能是更准确地表示需求，而不是连续分布，无论是在一个区域或沿着城市的街道，特别是在城市环境中。本项目的目标是开发模型和有效的算法，为广泛的设施选址问题与连续的需求。例如，处理不同类型的解空间（平面或网络），范数（测地线范数，加权或乘法范数），需求表示（连续，分段线性，阶跃函数），目标函数（中位数，中心，覆盖，公平，多标准）以及随机需求或时间动态问题的问题。必须科普连续的需求增加了一个分析，往往是非线性组件已经非常具有挑战性的组合优化问题。为这些问题开发有效的算法，无论是精确的还是非精确的，都需要数学工具的组合（例如，微积分、组合和非线性优化、图论）与来自理论计算机科学的工具（例如，计算几何、复杂性理论、算法设计和分析）。

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