选址问题

是指在规划区域里选择一个或多个设施的位置，使得目标最优。

四个要素

设施、规划区域、位置（距离）、目标

设施

按照设施的 空间维度 划分，可以将选址问题分为：
1.立体选址问题：设施的高度不能被忽略，如集装箱装箱问题。
2.平面选址问题：设施的长、宽不能被忽略，如货运站的仓位布局问题。
3.线选址问题：设施的宽度不能被忽略，如在仓库两边的传送带布局问题。
4.点选址问题：设施可以被简化为一个点，绝大多数时候我们遇到的都是这类问题。

按照设施的 规划数量 划分，可以将选址问题分为：
1.单设施选址
2.多设施选址

规划区域

按照规划区域的结构划分，可以将选址问题分为：
1.连续选址问题：设施可以在给定范围的任意位置选址，设施的候选位置为无穷多。
2.离散选址问题：设施的候选位置是有限且较少的，实际中最常遇到这类问题。
3.网格选址问题：规划区域被划分为许多的小单元，每个设施占据其中有限个单元。

位置（距离）

按照设施与需求点位置的关系，可以将所要获取的距离分为：
1.间接距离：
有向赋权图：Dijkstra算法和Floyed算法
两种算法的代码链接
2.直接距离：
（1）两点间距离公式
（2）Lp距离计算方式如下：d = (Σ(x1i-x2i)p)1/p

p=1时：L1范式，又称曼哈顿距离，在二维平面上 d=|x1-x2|+|y1-y2|。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色表示高楼大厦，灰色表示街道，则下图中红线、蓝线、黄线的行驶距离都是一样的，都是曼哈顿距离。
在这里插入图片描述
p=2：L2范式，又称欧氏距离，定义于欧几里得空间中，是最常见的距离度量方式，在二维平面上 d=((x1-x2)2+(y1-y2)2)1/2，即两点间的直线距离，上图中的绿线。

p=∞：切比雪夫距离（Chebyshev distance），在二维平面上 d=max(|x1-x2|, |y1-y2|)。玩过国际象棋的都知道，国王走一步能够移动到相邻的8个方格中的任意一个位置，那么国王从格子(x1,y1)走到格子(x2,y2)最少的步数就是切比雪夫距离。可以试试看，下图已经标注国王到达任意位置所需要的步数。
在这里插入图片描述

目标：

1.单目标选址问题
2.多目标选址问题：实际的问题往往都是多目标规划问题，比如既想距离尽可能短，又想要费用尽可能少

三大问题：

1.P中值问题 P-Median Problem

研究：在备选设施集合里，如何选择p个设施，使所有需求点得到服务，并且需求点到其最近设施的加权距离总和最小。

这是一个MinSum问题，可由以下整数规划模型表示：

在这里插入图片描述
应用场景：在物流领域应用得非常广泛，加权距离代表了运输成本，目标是总成本最少。

2.P中心问题 P-Center Problem

研究：在备选设施集合里，如何选择p个设施，使所有需求点得到服务，并且每个需求点到其最近设施的最大距离最小。

这是一个MinMax问题，可由以下整数规划模型表示（符号说明与上面类似）：
在这里插入图片描述
应用场景：应急设施的选址，比如警局、消防局、医院，要求尽可能快地到达任意位置。

3.覆盖问题 Covering Problem

覆盖问题分为最大覆盖问题和集覆盖问题两类。

（1）集覆盖问题

研究：在备选设施集合里，已知每个设施的服务范围，如何选择设施，使所有需求点得到服务，并且设施数p最小或成本最小。
在这里插入图片描述

（2）最大覆盖问题

研究：在备选设施集合里，已知每个设施的服务范围，如何选择p个设施，使得服务的需求点数最多或需求量最大。
应用场景：追求覆盖面的场景，比如移动基站的选址、物流中心的选址。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/193327.html原文链接：https://javaforall.net

数学建模中的选址问题_数学建模停车场规划问题

文章目录

选址问题