专栏首页物流IT圈【原创】从地图到线路规划 (八)

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

区位问题(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 个作为建设快递代收点的位置,选择的原则是方便各村的村民,即各村庄离拟建立的快递代收点的加权距离之和最小。

图 2. 留守营镇村庄地图示意

表 1. 留守营镇村落经纬度表

这个实际问题可用 p-中值模型来解决。考虑到现实因素,将该镇相隔较近的村落看作一个村落,少数偏远村落则可适当忽略,最终需要考虑村落共 55 个,利用 MATLAB 软件做村落分布点图,如图 3所示。

图 3. 留守营镇村庄地图示意

由于各村人数相差不大,并且对快递服务需求量相当,所以为简化问题,将各村需求量看作是相同的,即(1)式中的 wi = 1。用 Dev-C++编写贪婪取走算法的程序,运行可知所选出的 8 个地址标号分别为:

1、 4、 7、 8、 10、 11、 12、 15,并且 55 个村落被指派到相应的快递代收点,指派方案见表 3。

文章参考:

https://github.com/ilkayDevran/The_Pmedian_Problem_Python

应用数学进展, 2016, 5(2), 276-281 http://www.hanspub.org/journal/aam http://dx.doi.org/10.12677/aam.2016.52035

http://www.csie.ntnu.edu.tw/~u91029/LocationAllocationProblem.html?from=singlemessage#1

本文分享自微信公众号 - 物流IT圈(exiter18),作者:小美

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【知识贴】什么是合同物流的仓配一体化?

    我们一般遇到名词的解释,第一感觉会去百科词条搜一下。为了更加的有说服力,我通过网络、行业权威杂志仔细找了找关于合同物流的关键词文章,希望能找到比较详细的解释。结...

    物流IT圈
  • 【原创】带你走进物流行业(1)-概览篇

    接着上篇(《真有披着物流外衣的科技公司吗?》),先聊聊物流行业,这个行业很大,很久远,也很复杂。水上的水下的,不仅仅业务上有,IT上也有。

    物流IT圈
  • 我在编程20年中学到的5件事 - DaedTech

    物流IT圈
  • 麦肯锡教我的思考武器

    这篇文章不是关于金工-量投-机学的,为什么跨度这么大写这篇文章,原因是硬实力 (比如专业) 和软实力 (比如管理) 两手都要抓,而当你职位越来越高时,软实力也就...

    用户5753894
  • Spark UDF加载外部资源

    由于Spark UDF的输入参数必须是数据列column,在UDF中进行如Redis查询、白/黑名单过滤前,需要加载外部资源(如配置参数、白名单)初始化它们的实...

    mikeLiu
  • ios Charts MarkerView遇到的一个问题

    两个问题 问题1:最大值的的时候 MarkerView 坐标有问题 ,原因就是最大值的时候,曲线已经在View的顶部了,所以MarkerView 的Y坐标还要...

    赵哥窟
  • 强化学习

    强化学习能够实现很多的任务,这些任务目标往往可以归纳化为最大化长期奖励、最小化长期惩罚。比如在写论文,写完论文过审了,得到最佳论文凭证的奖学金,获得很高的引用,...

    云大学小编
  • 从 Google CRE 谈运维的服务意识

    花名“谦益”,是公众号“Forrest 随想录”的作者,多届 ArchSummit 运维专题明星讲师和优秀出品人,TGO 杭州分会会员。目前专注于云计算和人工智...

    用户1682855
  • Function接口的使用,对系统设计很大帮助

    Java8 添加了一个新的特性Function,顾名思义这一定是一个函数式的操作。我们知道Java8的最大特性就是函数式接口。所有标注了@FunctionalI...

    架构师修炼
  • python对列表中的字典按[key]时间排序

    在翻看之前的一些面试题,发现其中有一个问题就是对列表中的字典按照某个key进行排序,题目是这样的:

    the5fire

扫码关注云+社区

领取腾讯云代金券