【原创】从地图到线路规划 (八)

物流IT圈

发布于 2019-07-16 11:39:51

6500

发布于 2019-07-16 11:39:51

区位问题（Location Allocation Problem）是GIS 的经典问题之一, 主要应用于城市规划、空间配置、物流中心选址等领域。区位问题类型众多，可从静态或动态的需求、静态或动态的设施区位、离散或连续的地理空间和设施有无容量约束等等等等维度进行类型划分。最常见的离散区位问题可一般化为p中值(p中位，p-median)、p中心(p-center)和覆盖集(set covering)问题。这些问题可形式化为整型线性规划(MIP)数学模型.

然而，有设施容量约束的区位选址问题已被证明是NP难问题，解释一下NP难，

举例，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从中国香港出发，经过广州，北京，上海，…，等 n 个城市，最后返回中国香港。任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 X 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 X？

推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 X 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！这将是个天文数字。

继续整型线性规划数学模型，该模型求解方法是区位问题研究的关键环节之一。区位模型的求解方法包括三大类:精确算法、启发式算法和元启发式算法。通常认为精确算法能求解小规模的或者结构特殊的问题，获得最优或近似最优解；启发式算法适合中大规模的问题，算法效率高，能获得较高质量的可行解；而元启发式算法尝试突破启发式算法容易陷入局部最优的缺陷，获得更高质量的可行解。先讲P中值算法

讲深了没人看，这里只做科普，还是直接找一个案例：

案例分析

秦皇岛市留守营镇有 66 个村庄，图 2 为该镇地图(来源：百度地图)，为方便村民收发快递，现拟在该镇建立若干个快递代收点。查阅资料可获取该镇各村庄地理位置信息(见表 1)，经过实地考察，根据地理、交通和周围环境等因素，初步选出 15 个符合当地实际情况的快递代收点备选地址并记录其位置(见表 2)。现拟从中选出 8 个作为建设快递代收点的位置，选择的原则是方便各村的村民，即各村庄离拟建立的快递代收点的加权距离之和最小。